P2485 [SDOI2011]计算器

快速幂、扩展欧几里得、BSGS。

1）询问 $1$ 显然快速幂。
2）询问 $2$ 要求满足 $xy \equiv z(mod\ p)$ 。简单来说，

$\begin{aligned} xy&=qp+z \\ xy-qp&=z \\ xy+(-q)*p&=z \\ \end{aligned}$

根据裴蜀定理可知：如果不定方程 $ax+by=d$ 有解，一定满足 $\gcd(a,b)\mid d$。
而上面这个式子是不是长的挺像不定方程的呢？因此直接扩欧即可。
至于如何寻找最小解，可以参照青蛙的约会这道题的题解（皎月半洒花的博客写的很清楚）
因为我们只关心 $x$ 的值，并不关心 $y$ 的值，因此也不用在意 $y$ 的解是否为负数（同青蛙的约会）

3）询问 $3$，裸的 $BSGS$。模板，没有什么好解释的。
这道题还有一个特别坑的地方在于，$y$ 为 $p$的倍数时，有且仅当 $z$ 也为 $p$ 的倍数时，答案为 $1$ ，否则无解。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t,k;
ll y,z,p;
ll xf,yf,ans;
map<ll,ll>a;

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline ll qpow(ll a,ll b,ll md){
    ll base=1;
    while(b){
        if(b&1)     base*=a,base%=md;
        b>>=1;
        a*=a,a%=md;
    }
    return base;
}

inline ll exgcd(ll a,ll b,ll &xf,ll &yf){
    if(!b){
        xf=1,yf=0;
        return a;
    }
    ans=exgcd(b,a%b,xf,yf);
    ll tmp=xf;
    xf=yf,yf=tmp-a/b*yf;
    return ans;
}

inline void bsgs(){
    ll m=ceil(sqrt(p));
    if(y%p==0&&(z%p!=0)) { printf("Orz, I cannot find x!\n");return; }
    if(y%p==0&&z%p==0)  {printf("1\n");return;}
    ll now=z%p,f=qpow(y,m,p);
    a.clear(),a[now]=0;
    for(register int i=1;i<=m;++i)
        now=now*y%p,a[now]=i;
    now=1;ll flag=1;
    for(register int i=1;i<=m;++i){
        now=now*f%p;
        if(a[now]){
            ll ans=(i*m-a[now])%p;
            printf("%lld\n",(ans+p)%p);
            flag=0;return;
        }
    }
    printf("Orz, I cannot find x!\n");
}

int main(){
    t=read();k=read();
    for(register int ac=1;ac<=t;++ac){
        y=read();z=read();p=read();
        if(k==1)    printf("%lld\n",qpow(y,z,p));
        if(k==2)    exgcd(y,p,xf,yf),(z%ans!=0)?printf("Orz, I cannot find x!\n"):printf("%lld\n",((xf*(z/ans))%(p/ans)+p/ans)%p/ans);
        if(k==3)    bsgs();
    }
    return 0;
}