第一问快速幂

第二问快速幂：$x\cdot y=z$ -> $x=\frac{z}{y}$ -> $x=z*y^{p-2}$

第三问B(aby)S(tep)G(aint)S(tep)

令$k=\left\lceil\sqrt{p}\right\rceil$，则$[0,p)$范围内的数都能表示成$Ax-B$的形式，其中$A,B$的范围均在$k$以内。

$$y^{Ax-B}=z$$

$$y^{Ax}=z\cdot y^B$$

右边最多有k项，直接hash存一下

for(int B=0;B<k;B++) 把key为$z\cdot y^i$,value为i的元素插到hash表里，

for(int A=1;A<=k;A++) 

    if($y^{Ax}$在hash表里面)

        ---->>说明找到了！输出$Ak-hash[y^{Ax}]$

如果都没找到说明无解。这样子的BSGS不用求逆。

/**************************************************************
    Problem: 2242
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:356 ms
    Memory:4904 kb
****************************************************************/
 
#include<cstdio>
const int N=(1<<18)-1;
int y,z,p,flag,t,k,ans,s,j;
int la[N+10],et;
struct E{int x,k,nxt;}e[N+10];
#define add(x,k) e[++et]=(E){x,k,la[x&N]},la[x&N]=et;
int count(int x){
    for(int i=la[x&N];i;i=e[i].nxt)
    if(e[i].x==x)return e[i].k;
    return 0;
}
int power(int t,int k,int p){
    int f=1;
    for(;k;k>>=1,t=1LL*t*t%p)if(k&1)f=1LL*f*t%p;
    return f;
}main(){
    scanf("%d%d",&t,&k);
    if(k==1)for(;t--;scanf("%d%d%d",&y,&z,&p),printf("%d\n",power(y,z,p)));
    else if(k==2)for(;t--;){
        scanf("%d%d%d",&y,&z,&p),y%=p,z%=p;
        if(y==0)puts("Orz, I cannot find x!");
        else printf("%lld\n",1LL*z*power(y,p-2,p)%p);
    }
    else for(;t--;){
        scanf("%d%d%d",&y,&z,&p),y%=p,z%=p;
        if(y==0){if(z==0)puts("1");else puts("Orz, I cannot find x!");continue;}
        for(k=s=1;k*k<=p;k++);flag=0;j=z;
        for(int i=0;i<k;i++,s=1LL*s*y%p,j=1LL*j*y%p)add(j,i);
        for(int i=1,j=s,tmp;i<=k&&!flag;i++,j=1LL*j*s%p)if(tmp=count(j))ans=i*k-tmp,flag=1;
        if(flag==0)puts("Orz, I cannot find x!");
        else printf("%d\n",ans);
        for(int i=0,j=z;i<k;i++,j=1LL*j*y%p)la[j&N]=0;
    }
}