题解 P2485 【[SDOI2011]计算器】

· · 题解

其实这道题真心不难，主要也就是BSGS

题目里面有限制条件： p 为质数

你以为它很有用么？a 可以是 p 的倍数啊，这样两数就不互质了

你以为它没用么？a 是 p 的倍数特判掉就好了啊都不带运算的

第一问其实就是 快速幂

第二问其实就是 求逆元（费马小定理）

第三问其实就是 BSGS

//by Judge
#include<map>
#include<cmath>
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int M=1e5+7;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){ int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} ll n,k,y,z,mod; map<ll,int> mp;
inline ll qpow(ll x,ll p){ ll s=1;
    for(;p;p>>=1,x=x*x%mod)
        if(p&1) s=s*x%mod; return s;
}
inline ll BSGS(ll a,ll b){
    if(!(a%mod)&&b) return 0;  // a 是 mod 的倍数，除非 b 等于 0 否则无解
    mp.clear();
    ll h=b%mod,s=sqrt(mod)+1;
    ll t=qpow(a,mod-2);
    for(int i=0;i<=s;++i){
        if(!mp.count(h)) mp[h]=i;
        h=h*t%mod;
    } h=1,t=qpow(a,s);
    for(int i=0;i<=s;++i){
        if(mp.count(h)) return printf("%lld\n",mp[h]+s*i),1;
        h=h*t%mod;
    } return 0;
}
int main(){ n=read(),k=read();
    if(k==1){ for(;n;--n)
            y=read(),z=read(),mod=read(),
            printf("%lld\n",qpow(y,z));
    } else if(k==2){ for(;n;--n){
            y=read(),z=read(),mod=read();
            if(!(y%mod)&&z) puts("Orz, I cannot find x!");  // y 是 mod 的倍数，除非 z=0 否则无解
            else y=qpow(y,mod-2),z=y*z%mod,printf("%lld\n",z);
        }
    } else{ for(;n;--n){
            y=read(),z=read(),mod=read();
            if(!BSGS(y,z)) puts("Orz, I cannot find x!");
        }
    } return 0;
}