BZOJ 2242 计算器

发表于 2017-11-23

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

给定y,z,p,计算\(y^z\mod p\) 的值；
给定y,z,p，计算满足\(xy \equiv z(\mod p)\)的最小非负整数；
给定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;
}