BSGS学习笔记

大步小步算法(\(BabyStepGiantStep\ Algorithm\))

是用来求解形如\(a^x = b (mod\ p)\)之类的问题的。

设\(x=kt-c,t=\lceil \sqrt p\rceil,k,c<p\)

则\(a^{k*t}=b*a^c (mod\ p)\)

我们先枚举\(b*a^c\ (c\in [0,m)\)，存到哈希表里。

然后枚举\(k\)就可以了

因为我们的\(t\)是向上取整的，所以大步比小步大。

所以第一个找到的就是最小解了。

inline int BSGS(int a,int b,int p)
{
//  __gnu_pbds::gp_hash_table<int,int>mp;
    unordered_map<int,int>mp;
    int m=ceil(sqrt(p));//ceil!!
    for(int i=0;i<=m;b=1ll*a*b%p,++i)mp[b]=i;
    a=fpow(a,m);
    for(int i=0,j=1;i<m;j=1ll*j*a%p)
        if(mp.find(j)!=mp.end()&&i*m>=mp[j])
            return i*m-mp[j];
    return -1;
}

BSGS学习笔记

原文：https://www.cnblogs.com/LLCSBlog/p/11755583.html