P2485 [SDOI2011]计算器

对于第一个任务，上快速幂。

对于第二个任务，因为是质数，就不需要扩展欧几里得求逆元了，直接快速幂求逆元。

对于第三给任务，上。

原式：

，则，

枚举，然后用存起来：。接着从小到大枚举，如果，那么最小的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e4+7;
ll qpow(ll a,ll b,int mod) {
    ll res=1;
    while(b) {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void bsgs(int y,int z,int p) {
    if(!y) {
        if(!z) return cout<<"1\n",void();
        else return cout<<"Orz, I cannot find x!\n",void();
    }
    if(z==1||p==1) return cout<<0<<'\n',void();
    unordered_map<ll,int>mp;
    int m=ceil(sqrt(p));
    ll tmp=1,s=1;
    for(int j=0; j<m; ++j)
        mp[tmp*z%p]=j,tmp=tmp*y%p;
    for(int i=1; i<=m; ++i) {
        s=s*tmp%p;
        if(mp.count(s))
            return cout<<i*m-mp[s]<<'\n',void();
    }
    cout<<"Orz, I cannot find x!\n";
}
signed main() {
    cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
    int x,y,z,p,k,m,T;
    cin>>T>>k;
    if(k==1) {
        while(T--) {
            cin>>y>>z>>p;
            cout<<qpow(y,z,p)<<'\n';
        }
    } else if(k==2) {
        while(T--) {
            cin>>y>>z>>p;
            y%=p,z%=p;
            if(!y&&z) {
                cout<<"Orz, I cannot find x!\n";
                continue;
            }
            y%=p,z%=p;
            x=qpow(y,p-2,p)*z%p;
            cout<<x<<'\n';
        }
    } else {
        while(T--) {
            cin>>y>>z>>p;
            bsgs(y%p,z%p,p);
        }
    }
    return 0;
}