浅谈 BSGS 算法

MortisM · 2022-09-27 21:32:26 · 个人记录

先放个模板题的链接：P3846 [TJOI2007] 可爱的质数/【模板】BSGS

BSGS，即 Baby Step Giant Step，又称为大步小步算法，用来解决数论里的一些同余方程问题：已知 a,b,p，求一个最小的 x 满足：

先解释一下这个最小的 x。小学时我们就知道一个数的多少次方在模意义下是有循环节的（虽然不能证明，但是相信大多数人都有这种体会），初中学过欧拉函数 \varphi 以后，我们发现这个循环节的长度就是 \varphi(p)。所以只要有这样的 x，就每个循环节里都会有一个，一共就会有无穷多个。

但是，我们发现欧拉函数无法满足我们的要求，它的时间复杂度是 O(\varphi(p)) 的。当 p 为质数，切理应如此的时候，复杂度就退化为 O(p) 的了，这迫使我们思考是否有更好的算法。

实际上就是这个思考产生个 BSGS 算法。在介绍 BSGS 算法之前，先重申一下 BSGS 算法能解决的问题条件：p 为质数。

下面进入正题，将 x 写成 im-k 的形式，其中 m=\lceil\sqrt p\rceil，一会儿你就会知道这样做的好处。明确一下， 0\leq k\leq m。我们将其带回原来的式子，得到：

把左右都乘一个 a^k 得：

这样，我们就枚举所有 k，算出右边的值，再枚举 i 算出左边的值，这个过程用 map 或者 hash 搞一下即可，时间复杂度 O(\sqrt p+\frac{p}{\sqrt p})。

代码如下：

map<int,int> vis;
int qpow(int a,int b,int p){
    if(!b)return 1%p;
    int t=qpow(a,b>>1,p);
    t=1LL*t*t%p;
    if(b&1)t=1LL*t*a%p;
    return t;
}
void solve(){
    int a,b,p;
    scanf("%d%d%d",&p,&a,&b);
    int m=(int)ceil(sqrt(p)),cur=b;
    for(int i=0;i<=m;i++){
        vis[cur]=i;
        cur=1LL*cur*a%p;
    }
    int mul=qpow(a,m,p);
    cur=mul;
    for(int i=1;i<=m;i++){
        if(vis.count(cur)){
            printf("%d\n",1LL*i*m-vis[cur]);
            return;
        }
        cur=1LL*cur*mul%p;
    }
    printf("no solution\n");
}