题解 P2485 【[SDOI2011]计算器】

wyx__ · 2019-09-21 15:20:04 · 题解

本题算是一道同余方程的综合题。

k=1时，快速幂即可。

k=2时，用扩欧解同余方程即可。可以参考这题

k=3时，用BSGS算法。可以参考这题

大体就是设k=\lceil \sqrt{p} \rceil，然后将式子化为y^{i* p-j} \equiv z(mod p)（i，j未知且\leqp）

然后化为y^{i* p} \equiv z^j(mod p)，枚举j用hash表存z^j，再枚举i查找符合的j。

最后放代码（有点丑）:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void exgcd(ll a,ll b,ll &x,ll &y) {
    if(b==0) {
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-a/b*y;
}//扩欧
ll inv(ll n,ll p) {
    ll x,y;
    exgcd(n,p,x,y);
    return (x+p)%p;
}
ll power(ll a,ll b,ll c) {
    ll ans=1;
    while(b) {
        if(b%2==1)
            ans=ans*a%c;
        a=a*a%c;
        b/=2;
    }
    return ans%c;
}//快速幂
ll bsgs(ll b,ll n,ll p) {
    map<int,int> h;
    ll t=sqrt(p)+1;
    for(int i=0; i<=t; i++)
        h[n*power(b,i,p)%p]=i;
    ll m=power(b,t,p);
    for(int i=1; i<=t; i++)
        if(h[power(m,i,p)]) {
            int ans=i*t-h[power(m,i,p)];
            return (ans%p+p)%p;
        }
    return -1;
}//BSGS
int main() {
    int t,k;
    cin>>t>>k;
    if(k==1){
        for(int i=1;i<=t;i++){
            ll x,y,z;
            cin>>x>>y>>z;
            cout<<power(x,y,z)<<endl;
        }
    }
    if(k==2){
        for(int i=1;i<=t;i++){
            ll x,y,z;
            cin>>x>>y>>z;
            x%=z,y%=z;
            if(x==0&&y!=0)cout<<"Orz, I cannot find x!"<<endl;
            else cout<<(y*inv(x,z)%z+z)%z<<endl;
        }
    }
    if(k==3) {
        for(int i=1; i<=t; i++) {
            ll x,y,z;
            cin>>y>>z>>x;
            if(y%x==0)
                cout<<"Orz, I cannot find x!"<<endl;
            else {
                ll k=bsgs(y,z,x);
                if(k==-1)
                    cout<<"Orz, I cannot find x!"<<endl;
                else
                    cout<<k<<endl;
            }
        }
    }
}