@[Jackson_Miller](/user/754673) 帮你调过了
by songszh @ 2024-01-26 11:07:18
@[Jackson_Miller](/user/754673) 一个问题是特判 `if(y%p==0&&b%p!=0){` 应该是 `if(a%p==0&&b%p!=0){`，第二个是 BSGS 里面你的哈希表没清空。
by songszh @ 2024-01-26 11:08:32
@[Jackson_Miller](/user/754673) 话说这题不是用 exBSGS 更好写一些吗
AC:
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,p,y,z;
unordered_map<int,int>hsh;
int ksm(int a,int b,int p){
int sum=1;
while(b){
if(b&1) sum=sum*a%p;
a=a*a%p;
b>>=1;
}
return sum;
}
int BSGS(int a,int b,int p){
hsh.clear();
int m=sqrt(p)+1;
b%=p;
for(int i=0;i<m;i++){
int fp=ksm(a,i,p);
hsh[b*fp%p]=i;
}
a=ksm(a,m,p);
for(int i=1;i<=m;i++){
int fp=ksm(a,i,p);
if(hsh.count(fp)>0){
if(i*m-hsh[fp]){
return i*m-hsh[fp];
}
}
}
return -1;
}
long long exgcd(long long a,long long b,long long &x1,long long &y2){
if(b==0){
x1=1,y2=0;
return a;
}
long long d=exgcd(b,a%b,x1,y2);
long long z=x1;x1=y2;y2=z-y2*(a/b);
return d;
}
signed main(){
int t,op;
cin>>t>>op;
while(t--){
int p,a,b;
cin>>a>>b>>p;
if(op==1){
cout<<ksm(a,b,p)<<endl;
}
if(op==2){
long long x=0,yy=0,gcd=0;
gcd=exgcd(a,p,x,yy);
if(b%gcd==0){
long long tmp=p/gcd;
x=(((x*b)/gcd)%tmp+tmp)%tmp;
printf("%lld\n",x);
}
else{
printf("Orz, I cannot find x!\n");
}
}
if(op==3){
if(a%p==0&&b%p!=0){
cout<<"Orz, I cannot find x!"<<endl;
} else if(BSGS(a,b,p)==-1){
cout<<"Orz, I cannot find x!"<<endl;
}
else{
cout<<BSGS(a,b,p)<<endl;
}
}
}
return 0;
}
```
by songszh @ 2024-01-26 11:09:09
@[songszh](/user/638084) 爱你
by Jackson_Miller @ 2024-01-26 13:38:53
@[Jackson_Miller](/user/754673) 6。
by songszh @ 2024-01-26 14:26:58