「算法笔记」BSGS

BSGS 用于解决高次同余方程的最小整数解，主要思想是分块。

引入

求出下面方程的最小非负整数解 $x$：

$a^x\equiv b\pmod p\quad (\gcd(a,p)=1)$

此处的未知数 $x$ 在指数上，我们就要用到 $\text{BSGS}$（$\text{Baby Step Giant Step}$）算法。

思想

$\text{BSGS}$ 的本质是分块的思想，我们设 $m=\left\lceil\sqrt p\right\rceil$（注意是上取整），又设 $x=i\times m-j$，其中 $0\le i\le m,0\le j<m$；我们可以将原方程转化为：

$a^{i\times m-j}\equiv b\pmod p$

在 $x=i\times m-j$ 中，$i$ 即为大步，$j$ 即为小步；我们将 $j$ 移到方程的右边得到：

$a^{i\times m}\equiv b\times a^j\pmod p$

观察到 $j$ 只有 $O(m)$ 种取值，所以我们对于每个 $j$，把 $b\times a^j\bmod p$ 的值记录下来，存放在哈希表中（有没有一种分块打表的感觉？）。然后枚举左半边的 $i$，将对应的值在哈希表中查找对应的 $j$，如果能找到对应的 $j$ 那么说明已经找到答案了。

对于插入哈希表中的 $j$ 的值，显然在同一个值时，$j$ 的值越大越好，那么直接覆盖即可，无需关注细节问题！

注意：代码中必须要判断无解情况！（本来就无解，或者没有找到合法解）

时间复杂度：$O(\sqrt p)$

代码

int BSGS(int a,int b,int P) {
    if(b%gcd(a,P)) return -1;
    a%=P,b%=P,mp.clear();
    int m=ceil(sqrt(P));
    for(int i=0;i<m;++i,b=1LL*b*a%P) mp[b]=i;
    for(int i=0,j=a=pow(a,m,P);i<=m;++i,j=1LL*j*a%P) {
        if(mp.count(j)&&i*m>=mp[j]) return i*m-mp[j];
    }
    return -1;
}

引入

思想

代码

习题