题解 | #[SDOI2011]计算器#

思路

询问1：快速幂就可以了。
询问2： $xy\equiv z \mod p$ 可以转化为求解同余方程 $xy+pd=z$ ，使用扩展欧几里得就可以求解，在gcd(y,p)|z的时候有解。
询问3：重点要讲的BSGS算法(我习惯叫北上广深)。我们要求满足同余式 $y^x \equiv z\mod p$ 的最小非负数x，暴力枚举x在[0,p)的范围内，在p非常大的情况下是会爆的。可以令x=mi-j，那么式子转化为了 $y^{mi}\equiv z*y^j\mod p，其中m=\sqrt p$ 。为什么要这样转换？
因为我们固定了m的情况下，i和j的取值都在 $[0,\sqrt p]$ ，就可以把所有的x都表示出来，首先跑一遍j，用map存储所有 $z*y^j$ ，然后再从小到大跑i，找到同余的情况直接跳出即可。复杂度开了个根号。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll fpow(ll a,ll b,ll mod){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1; 
    }
    return res;
}

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    ll gcd=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return gcd;
}

void bsgs(ll y,ll z,ll p){
    z%=p; //可能板子不太好，所以加了很多特判 
    if(y%p==0){ //那么同余0 
        if(z){  //如果右边余不为0 
            cout<<"Orz, I cannot find x!"<<endl;
            return;    
        }else{
            if(p==1){ //如果模数为1 
                cout<<0<<endl;
                return;
            }else{
                cout<<1<<endl; 
                return;
            } 
        }
    }
    ll m=ceil(sqrt(p)); //开根号取整 
    map<ll,ll>mp;
    ll now=z,f=fpow(y,m,p);  
    mp[now]=0;
    for(int j=1;j<=m;j++){ //对于同余式右边 
        now=now*y%p; 
        mp[now]=j; //哈希记录zy^j 
    }
    now=1;
    for(int i=1;i<=m;i++){
        now=now*f%p; //对同余式左边,(y^m)^i 
        if(mp[now]){ //找到了那个最小的x=m*i-j 
            cout<<((i*m-mp[now])%p+p)%p<<endl;
            return;
        }
    }
    cout<<"Orz, I cannot find x!"<<endl;
}


int t,k,y,z,p;

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t>>k;
    if(k==1){
        for(int i=1;i<=t;i++){
            cin>>y>>z>>p;    //第一种直接用快速幂求就行了 
            cout<<fpow(y,z,p)%p<<endl; 
        }
    }else if(k==2){
        for(int i=1;i<=t;i++){
            cin>>y>>z>>p; //第二种用拓展欧几里得 
            ll x,d;
            ll gcd=exgcd(y,p,x,d);
            if(z%gcd) cout<<"Orz, I cannot find x!"<<endl;
            else{
                ll tmp=p/gcd;
                while(x<0) x+=tmp;
                cout<<((x*z/gcd)%tmp+tmp)%tmp<<endl;
            }
        }
    }else if(k==3){
        for(int i=1;i<=t;i++){
            cin>>y>>z>>p;
            bsgs(y,z,p); //第三种用北上广深算法求 
        }
    }
    return 0;
}