BSGS(Baby Step Giant Step)算法

一、BSGS算法

求解高次同余方程
$$A^x \equiv B \ (\bmod \ C)$$
其中 $(A,C)=1$

1.求解

令 $x=im+j$
此时方程转化为
$$A^j \equiv B \cdot A^{-im} \ (\bmod \ C)$$
首先对 $i \in [1,m-1]$ ，计算出 $A^i \% C$ 并将其存入hash表便于查询，此为Baby Step
再枚举等号右侧所有可能值，在hash表中查找，若有，则可得解 $x=im+j$ ，此为Giant Step
显然当 $m=\lceil \sqrt{C} \rceil$ 时最优，时间复杂度为 $O(\sqrt{C})$

inline int Pow(int a,int b,int p){
    int res=1;
    for(;b;b>>=1){
        if(b&1)
            (res*=a)%=p;
        (a*=a)%=p;
    }
    return res;
}
inline int BSGS(int a,int b,int p){
    a%=p;
    if(a==0 && b!=0)
        return -1;
    M.clear();
    int m=sqrt(p)+1;
    int t=1,q=Pow(a,p-1-m,p);
    for(int i=0;i<m;i++){
        if(!M.count(t))
            M[t]=i;
        (t*=a)%=p;
    }
    t=b%p;
    for(int i=0;i<m;i++){
        if(M.count(t)){
            int res=i*m+M[t];
            ((res%=p)+=p)%=p;
            return res;
        }
        (t*=q)%=p;
    }
    return -1;
}