Description

你被要求设计一个计算器完成以下三项任务：

1、给定y,z,p,计算Y^Z Mod P 的值；

2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；

3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。

Solution

打个 \(BSGS\) 板子

令 \(x=a*m-b\)

原式变为 \(y^{a*m}=z*y^b\,\,(mod P)\)

枚举 \(b=[0,m-1]\) 求出所有的取值,并存下来

再枚举 \(a\) ,查找右边是否有出现过,由欧拉定理: \(a\) 不会超过 \(\frac{P}{m}\)

\(y\%P==0\) 时且 \(P>1\) 时无解,特判一下

\(m=sqrt(P)\) 时,复杂度最优

#include
    
     #define int long longusing namespace std;int mod;inline int qm(int x,int k){    int sum=1;    while(k){        if(k&1)sum=1ll*sum*x%mod;        x=1ll*x*x%mod;k>>=1;    }    return sum;}inline int exgcd(int a,int b,int &x,int &y){    if(!b){x=1;y=0;return a;}    int r=exgcd(b,a%b,y,x);y-=a/b*x;    return r;}inline void solo(int a,int b,int c){    int x,y,r;    r=exgcd(a,b,x,y);    if(c%r){puts("Orz, I cannot find x!");return ;}    x*=c/r;b/=r;    x=(x%b+b)%b;    cout<
     
      <
      
       a;inline void bsgs(int y,int z){    y%=mod;z%=mod;    if(z==1){puts("0");return ;}    if(y%mod==0){        if(mod>1)puts("Orz, I cannot find x!");        else puts("0");        return ;    }    a.clear();    int t=sqrt(mod),e=qm(y,t);    for(int i=0;i
       
        >T>>K;  while(T--){      cin>>y>>z>>mod;      if(K==1)cout<
        
         <