bsgs算法

ACM › 学习笔记 › 数学
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 
}