再一次检验了我似乎不会EXGCD

我觉得实际上没有那么毒吧

由于不一定互质且不是倍数一定不成立（裴蜀定理）

先特判

然后如果互质不是乘z吗

所以就除去GCD再乘

Ps.我还瓜皮的以为除了GCD再解一次

然后接着是一个BSGS不卡map

#include
    
     using namespace std;typedef int INT;#define LL long long#define int long longinline void read(int &x){    x=0;    char ch=getchar();    int f=1;    while(ch<'0'||ch>'9'){        if(ch=='-')f=-1;        ch=getchar();    }    while(ch>='0'&&ch<='9'){        x=x*10+ch-'0';        ch=getchar();    }    x*=f;}int mod;inline int quick_pow(LL x,int k){    LL ret=1;    while(k){        if(k%2==1){            ret=ret*x%mod;        }        k/=2;        x=x*x%mod;    }    return ret;}inline LL EXGCD(LL &x,LL &y,int a,int b){    if(!b){        x=1;        y=0;        return a;    }    else{        int GCD=EXGCD(x,y,b,a%b);        int tmp=x;        x=y;        y=tmp-y*(a/b);        return GCD;    }}map
     
       mmp;inline int BSGS(int y,int z){    int m=ceil(sqrt(mod));    mmp.clear();    mmp[z%mod]=0;    int now=1;    for(int i=1;i<=m;i++){        now=now*y%mod;        mmp[now*z%mod]=i;    }    int t=quick_pow(y,m);    int ans=1;    for(int i=1;i<=m;i++){        ans=ans*t%mod;        if(mmp.count(ans)){            int key=i*m-mmp[ans];            return (key%mod+mod)%mod;        }    }return -1;}INT main(){//	freopen("test.in","r",stdin);    int Cas;    int opt;    read(Cas);    read(opt);    while(Cas--){        int y,z;        read(y);        read(z);        read(mod);        if(opt==1){            cout<
      
       <<'\n';        }        if(opt==2){            LL dx,dy;            int GCD=EXGCD(dx,dy,y,mod);            if((z%GCD)!=0){                cout<<"Orz, I cannot find x!"<<'\n';            }            else{                cout<<((dx*z/GCD)%mod+mod)%mod<<'\n';            }        }        if(opt==3){            int ans=BSGS(y,z);            if(ans==-1||y%mod==0){                cout<<"Orz, I cannot find x!"<<'\n';            }            else{                cout<
       
        <<'\n';            }        }    }	}