你被要求设计一个计算器完成以下三项任务:

  1. 给定y,z,p,计算$y^z\mod p$ 的值;
  2. 给定y,z,p,计算满足$xy \equiv z(\mod p)$的最小非负整数;
  3. 给定y,z,p,计算满足$y^x \equiv z (\mod p)$的最小非负整数。

其中p为质数,$y,z,p\le 10^9$

题解

任务一裸快速幂不解释。

任务二显然$x=\frac{z}{y}=z\times y^{-1}$,根据费马小定理$y^{-1}\equiv y^{p-2}(\mod p)$,所以$x\equiv z\times y^{p-2}$,非常显然。

任务三为BSGS。

求$y^x\equiv z(\mod p)$的最小非负整数解。

显然根据费马小定理,$y^{x+(p-1)}\equiv y^x$

所以$0\le x<p-1$

设$x=im-j$,其中$1\le j \le m,1\le i \le \lceil \frac{p}{m}\rceil$,这样即可满足$0\le im-j \le \lceil \frac{p}{m}\rceil m-1$,显然$\lceil \frac{p}{m}\rceil m-1 \ge p-1$,所以显然可以。

则$y^{im-j}\equiv z$,所以$y^{im}\equiv zy^{j}$,所以
$(y^m)^i \equiv zy^j$

所以我们先把$zy^{1},zy^{2}\dots zy^{m}$存进哈希表/map
然后在用$(y^m)^1,(y^m)^2\dots (y^m)^{\lceil \frac{p}{m}\rceil}$依次查询。
如果$(y^m)^i$查到了,并且查到的对应的是$zy^j$,那么答案就是$x=im-j$,找到答案以后就退出。
时间复杂度$O(m+\frac{p}{m})$,当$m=\sqrt{p}$时取得最小值$O(\sqrt{p})$

/*
Author: CNYALI_LK
LANG: C++
PROG: 2242.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll fpm(ll a,ll b,ll p){
    ll c=1;
    a%=p;
    while(b){
        if(b&1)c=c*a%p;
        a=a*a%p;
        b>>=1;
    }
    return c;
}
namespace cheat1{
    ll f(ll a,ll b,ll p){
        return fpm(a,b,p);  
    }
    void js(ll t){
        ll y,z,p;
        while(t){
            --t;
            scanf("%lld%lld%lld",&y,&z,&p);
            printf("%lld\n",f(y,z,p));
        }
    }

}
namespace cheat2{
    ll f(ll a,ll b,ll p){
        a%=p;b%=p;
        if(!b)return 0;
        if(!a)return -1;
        return b*fpm(a,p-2,p)%p;    
    }
    void js(ll t){
        ll y,z,p;
        while(t){
            --t;
            scanf("%lld%lld%lld",&y,&z,&p);
            ll s=f(y,z,p);
            if(s+1)printf("%lld\n",s);
            else printf("Orz, I cannot find x!\n");
        }
    }

}

namespace cheat3{
    ll f(ll a,ll b,ll p){
        a%=p;b%=p;
        if(!a&&!b)return 0;
        if(!a)return -1;

        tr1::unordered_map<ll,ll> mp;
        ll m=(ll)ceil(sqrt((long double)p));
        ll x=b;
        for(ll i=1;i<=m;++i){
            x=x*a%p;
            mp.insert(make_pair(x,i));
        }
        b=1;
        for(ll i=0;i<m;++i)b=b*a%p;
        x=1;
        for(ll i=1;i<=m;++i){
            x=x*b%p;
            if(mp[x])return i*m-mp[x];
        }
        return -1;  
    }
    void js(ll t){
        ll y,z,p,s;
        while(t){
            --t;
            scanf("%lld%lld%lld",&y,&z,&p);
            s=f(y,z,p);
            if(s+1)printf("%lld\n",s);
            else printf("Orz, I cannot find x!\n");
        }
    }

}

int main(){
#ifdef cnyali_lk
    freopen("2242.in","r",stdin);
    freopen("2242.out","w",stdout);
#endif
    ll t,k;
    scanf("%lld%lld",&t,&k);
    if(k==1)cheat1::js(t);
    else if(k==2)cheat2::js(t);
    else cheat3::js(t);
    return 0;
}

标签: none

添加新评论