https://www.luogu.org/problemnew/show/P4861
把好像把一开始b==1的特判去掉就可以AC了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int gcd(int a,int b){
if(!b)
return a;
else{
while(int i=a%b){
a=b;
b=i;
}
return b;
}
}
inline int qpow(ll a,int n,int m) {
//这个快速幂保证p不是1，少模一次是一次
ll s=1;
while(n) {
if(n&1)
s=s*a%m;
a=a*a%m;
n>>=1;
}
return s;
}
unordered_map<int,int> M;
//要求a,n互质 a^x=b mod n .k,t是留给exbsgs调用的
int bsgs(int a,int b,int n,int k=1,int t=0) {
/*if(b==1)
return 0;*/
M.clear();
int m=ceil(sqrt(n));
ll s=b;//BS
for(int i=0; i<m; i++,s=s*a%n)
M[s]=i;
s=k;//GS
k=qpow(a,m,n);
for(ll i=1; i<=m; i++) {
s=s*k%n;
if(M.count(s))
return i*m-M[s]+t; //貌似这样就保证找到的是最小解了，不知道为什么
}
return -1;
}
//a^x=b mod n
int exbsgs(int a,int b,int n) {
/*if(b==1) {
return 0;
}*/
int d=gcd(a,n),k=1,t=0;
while(d^1) {
if(b%d) {
return -1;
}
++t;
b/=d;
n/=d;
k=(ll)k*(a/d)%n;
if(b==k) {
return t;
}
d=gcd(a,n);
}
return bsgs(a,b,n,k,t);
}
int main() {
#ifdef Yinku
freopen("Yinku.in","r",stdin);
#endif // Yinku
int a,b,n;
int m,k;
b=1;
scanf("%d%d",&m,&k);
a=k;
n=m;
a%=n;
b%=n;
int ans=exbsgs(a,b,n);
if(ans==-1)
puts("Let's go Blue Jays!");
else
printf("%d\n",ans);
return 0;
}