如下代码可过双倍经验题 P4195 【模板】扩展BSGS,但此题 TLE了
#include <bits/stdc++.h>
#define int long long
using namespace std;
void exgcd(int a,int b,int &x,int &y) {
if(!b) {
x=1,y=0;
return;
}
exgcd(b,a%b,x,y);
int z=x;
x=y;
y=z-(a/b)*y;
}
int inv(int a,int b) {
int x,y;
exgcd(a,b,x,y);
return (x%b+b)%b;
}
int power(int a,int b,int p) {
if(b==0) return p==1?0:1;
int tmp=power(a,b/2,p);
if(b%2==0) return tmp*tmp%p;
return tmp*tmp%p*a%p;
}
int BSGS(int a,int b,int p) {
map<int,int> hash;hash.clear();
b %= p;
int t=(int)sqrt(p)+1;
for(int j=0; j<t; j++) {
int val=1ll*b*power(a,j,p)%p;
hash[val]=j;
}
a=power(a,t,p);
if(a==0) return b==0?1:-1;
for(int i=0; i<=t; i++) {
int val=power(a,i,p);
int j=hash.find(val)==hash.end()?-1:hash[val];
if(j>=0 && i*t-j>=0) return i*t-j;
}
return -1;
}
int ExBSGS(int a,int b,int p) {
if(b==1 || p==1) return 0;
int g=__gcd(a,p),k=0,xr=1;
while(g>1) {
if(b%g!=0) return -1;
k++;
b /= g; p /= g;
xr=xr*(a/g)%p;
if(xr==b) return k;
g=__gcd(a,p);
}
int ans=BSGS(a,b*inv(xr,p)%p,p);
if(ans==-1) return -1;
return ans+k;
}
signed main() {
int a,b,p;
scanf("%lld%lld%lld",&a,&p,&b);
while(a || b || p) {
a %= p;
b %= p;
int ans=ExBSGS(a,b,p);
if(ans==-1) printf("No Solution\n");
else printf("%lld\n",ans);
scanf("%lld%lld%lld",&a,&p,&b);
}
return 0;
}