bsgs算法

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
1
2
3
4
5
6
7
8
9
10
11
// a^x === b   x=lg(a,b)
int bsgs_lg(int a,int b,int mod){
map<int,int>mp;
int sqr=sqrt(mod-1)+1;
for(int i=0;i<sqr;i++) mp[qpow(a,i,mod)]=i; // baby step
for(int i=0;i<mod-1;i+=sqr){ // giant step
int tp=1ll*b*qpow(a,mod-1-i,mod)%mod; // a^(-i)
if(mp.find(tp)!=mp.end()) return i+mp[tp];
}
return -1;// error
}