BSGS算法 笔记

发表于 | 阅读次数：
本文字数： 575 字 | 阅读时长 ≈ 2 分钟

算法概述

BSGS，全名叫Big Step Giant Step算法，在中国被称为“拔山盖世算法”，或者叫“北上广深”算法。

它用来求解最小的 $x$ 满足 $A^x \equiv B \pmod{p}$，你可以认为是数论意义下的开 $\log$。

我们这里只讨论 $p$ 为质数的情况。

算法步骤

$BSGS$ 的精髓在于，我只求一部分答案，就能很快的求另一部分答案。

首先 $A^{x-1} \equiv 1 \pmod{p}$。那么我们的 $x$ 只要在 $[0,p-1]$ 内枚举即珂。

首先特判 $B=1$，则 $x=0$。

假设现在有一个 $m$ ，我们知道了 $x=[1,m]$ 时 $A^x$ 的值（存在map<>里面），如果满足条件的 $x\le m$，就直接得结果了。

否则，我们假设满足条件的 $x=m+i$（$1\le i\le m$）。那么 $A^m\times A^i \equiv B \pmod{p}$。 则 $A_i=B\times A^{-m} \pmod{p}$。由于 $1\le i\le m$ 这一段中 $A^x$ 的值我们记录过了，我们只要在map里面找是否存在 $B\times A^{-m}$ 即珂。

然后这样我们就求出了 $m+1,m+2…2m$ 间有没有解，只用了一次 map 的查询。

同理，我们假设满足条件的 $x=km+i$，$1\le i\le m$，就能进而求出 $[1,p]$ 中的所有解了。

这个算法的复杂度是 $O(min\{m\log m,\dfrac{p}{m}\log m\})$。

显然， $m=\sqrt{p}$ 的时候，这个式子最小，等于 $O(\sqrt{p} \log \sqrt{p})$。

模板题

洛谷 4028
（洛谷上没有BSGS的板子，只有exBSGS，那个我不会）

代码（仅BSBS部分）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#define F(i,l,r) for(int i=l;i<=r;++i)
int qpow(int a,int b,int m)
{
        int r=1;
        while(b)
        {
                if (b&1) r=r*a%m;
                a=a*a%m,b>>=1;
        }
        return r;
}
map<int,int> x;
map<int,bool> vis;
int BSGS(int a,int b,int p) //a^x=b (mod p)
{
        x.clear(); vis.clear();
        a%=p; b%=p;
        if (a==0) {return -1;}

        int m=(sqrt(p+0.5));
        int ia_m=qpow(a,p-2,p); ia_m=qpow(ia_m,m,p); //ia_m=a^-m
        int cur=1;
        F(i,0,m-1) {x[cur]=(!vis[cur])?i:min(x[cur],i);vis[cur]=1;cur=cur*a%p;}
        if (vis[b]) return x[b];
        cur=1;
        F(i,1,p/m)
        {
                int tmp=b*qpow(ia_m,i,p)%p; //tmp=b*a^(-mi)
                if (vis[tmp]) return i*m+x[tmp];
        }
        return -1;
}
w