BSGS(Baby Step Giant Step)

BSGS

应用：求解关于 $t$ 的同余方程 $a^t \equiv b\pmod p,(a,p)=1$ 的最小正整数解

核心思想：分块

做法：

因为 $(a,p)=1$，根据欧拉定理 $a^{\varphi(p)} \equiv 1 \pmod p$

所以 $a^t \equiv a^{t\text{ }\bmod\text{ }\varphi(p)} \pmod p$

所以 $t \in [0,\varphi(p)-1]$

由于 $p>\varphi(b)$，所以 $t \in [0,p]$

令 $k=\lfloor \sqrt p \rfloor +1$，则可以将 $0 \sim p$ 分成 $\sqrt p $ 段，每一段的长度为 $k$，则可以令 $t=kx-y,x\in[1,k],y \in [0,k-1]$ ，这样 $t$ 取不到 $0$，特判即可。
$$
a^t=a^{kx-y} \equiv b \pmod p\
a^{kx} \equiv b\cdot a^y \pmod p
$$
枚举 $x$，则需要判断是否存在一个 $y$ 满足上式，可以将右侧的值存进哈希表，每次查找即可。若查到一组 $(x,y)$ 满足上式，则可以求出一个 $t$。

洛谷 P3846 [TJOI2007] 可爱的质数/【模板】BSGS/AcWing 3124. BSGS

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
33
34
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int bsgs(int a,int b,int p){
    if(1%p==b%p)return 0;//特判t=0
    int k=sqrt(p)+1;
    unordered_map<int,int>hash;//哈希表
    for(int i=0,j=b%p;i<k;i++){//j=a^y
        hash[j]=i;
        j=1ll*j*a%p;
    }
    
    //求a^k
    int ak=1;
    for(int i=1;i<=k;i++)ak=1ll*ak*a%p;
    
    for(int i=1,j=ak;i<=k;i++){//j=a^x
        if(hash.count(j)) return 1ll*i*k-hash[j];
        j=1ll*j*ak%p;
    }
    return -1;
}

int main(){
    int a,p,b;
    while(cin >> a >> p >> b,a||p||b){
        int res=bsgs(a,b,p);
        if(res==-1)cout << "No Solution\n";
        else cout << res << endl;
    }
    return 0;
}

扩展BSGS

应用：求解关于 $t$ 的同余方程 $a^t \equiv b\pmod p$ 的最小正整数解，$a,p$不一定互质

做法：

若 $a^0 \equiv b \pmod p$，则 $t=0$

否则，$a^t \equiv b \pmod p $。

设 $(a,p)=d$，若 $d=1$，则按照 BSGS 处理，否则：
$$
a^t \equiv b \pmod p \Longleftrightarrow a^t+kp=b
$$
若 $d \not \mid b$ 则无解（$a,p$ 均为 $d$ 的倍数，所以 $b$ 必须是 $d$ 的倍数），否则：
$$
a^t+kp=b \Longleftrightarrow \frac a d\cdot a^{t-1} + k \cdot \frac p d = \frac b d \Longleftrightarrow \frac a d \cdot a^{t-1} \equiv \frac b d \pmod {\frac p d} \
\xLeftrightarrow{(\frac a d,\frac p d)=1} a^{t-1} \equiv \frac b d \cdot (\frac a d)^{-1}\pmod {\frac p d}
$$
此时，记 $t’=t-1,b’= \frac b d \cdot (\frac a d)^{-1},p’=\frac p d$，则原式转化为 $a^{t’} \equiv b’ \pmod {p’}$，回到第一步，求出一个 $t’$，则 $t’+1$ 就是答案。

洛谷 P4195 【模板】扩展 BSGS/exBSGS/AcWing 3125. 扩展BSGS

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF=0x3f3f3f3f;

int bsgs(int a,int b,int p){
    if(1%p==b%p)return 0;
    int k=sqrt(p)+1;
    unordered_map<int,int>hash;
    for(int i=0,j=b%p;i<k;i++){
        hash[j]=i;
        j=1ll*j*a%p;
    }
    
    int ak=1;
    for(int i=1;i<=k;i++)ak=1ll*ak*a%p;
    
    for(int i=1,j=ak;i<=k;i++){
        if(hash.count(j)) return 1ll*i*k-hash[j];
        j=1ll*j*ak%p;
    }
    return -INF;
}

int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}


int exbsgs(int a,int b,int p){
    b=(b%p+p)%p;//把b变成正的
    if(1%p==b%p)return 0;
    int d=gcd(a,p);// 欧几里得算法
    if(d>1){//若a,p不互质
        if(b%d)return -INF;//返回负无穷，防止上一步+1后变成正数
        int x,y;
        exgcd(a/d,p/d,x,y);//求a/d的逆元存在x中
        return exbsgs(a,1ll*b/d*x%(p/d),p/d)+1;
    }
    return bsgs(a,b,p);//a,p互质，使用bsgs
}

int main(){
    int a,p,b;
    while(scanf("%d%d%d",&a,&p,&b),a||p||b){
        int res=exbsgs(a,b,p);
        if(res<0)printf("No Solution\n");
        else printf("%d\n",res);
    }
    return 0;
}

例题：洛谷 P3306 [SDOI2013] 随机数生成器/AcWing 2526. 随机数生成器

小 $ W $ 喜欢读书，尤其喜欢读《约翰克里斯朵夫》。

最近小 $ W $ 准备读一本新书，这本书一共有 $ p $ 页，页码范围为 $ 0..p-1 $。

小 $ W $ 很忙，所以每天只能读一页书。

为了使事情有趣一些，他打算使用 NOI2012 上学习的线性同余法生成一个序列，来决定每天具体读哪一页。

我们用 $ X_i $ 来表示通过这种方法生成出来的第 $ i $ 个数，也即小 $ W $ 第 $ i $ 天会读哪一页。

这个方法需要设置 $ 3 $ 个参数 $ a,b,X_1 $，满足 $ 0 \le a,b,X_1 \le p-1 $，且 $ a,b,X_1 $ 都是整数。

按照下面的公式生成出来一系列的整数。

$$
X_{i+1}=(aX_i+b) \bmod p
$$

其中 $ \bmod p $ 表示前面的数除以 $ p $ 的余数。

可以发现，这个序列中下一个数总是由上一个数生成的，而且每一项都在 $ 0..p-1 $ 这个范围内，是一个合法的页码。

同时需要注意，这种方法有可能导致某两天读的页码完全一样。

小 $ W $ 非常急切的想去读这本书的第 $ t $ 页。

所以他想知道，对于一组给定的 $ a,b,X_1 $，如果使用线性同余法来生成每一天读的页码，最早读到第 $ t $ 页是在哪一天，或者指出他永远不会读到第 $ t $ 页。

输入格式

输入含有多组数据，第一行一个正整数 $ T $，表示这个测试点内的数据组数。

接下来 $ T $ 行，每行有五个整数 $ p，a，b，X_1，t $，表示一组数据。保证 $ X_1 $ 和 $ t $ 都是合法的页码。

注意：$ P $ 一定为质数。

输出格式

共 $ T $ 行，每行一个整数表示他最早读到第 $ t $ 页是哪一天。

如果他永远不会读到第 $ t $ 页，输出 $ -1 $。

数据范围

$ 0 \le a \le p-1 $,
$ 0 \le b \le p-1 $,
$ 2 \le p \le 10^9 $

输入样例：

1
2
3
4
3
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1

输出样例：

1
2
3
1
3
-1

分析：

$x_n=(ax_{n-1}+b)\bmod p$

若 $a=0$，则如果 $x_1=t$，则答案为 $1$，如果 $x_1 \ne t,b=t$，则答案为 $2$ ，否则无解。

若 $a=1$，若 $b=0$ ，则如果 $x_1=t$，则答案为 $1$，否则无解，否则 $x_n=x_{n-1}+b=x_1+(n-1)b\equiv t \pmod p$，也就是解同余方程 $x_1+(n-1)b\equiv t \pmod p$，相当于解不定方程 $(n-1)b + mp = t -x_1 $，使用扩展欧几里得算法。

首先要求出通项公式，由于每一项都是模 $p$ 意义下的，因此可以省略 $\bmod p$，即求 $x_n=ax_{n-1}+b$ 的通项公式。

设 $x_n=ax_{n-1}+b$ 等价于 $x_n+c=a(x_{n-1}+c)$，解得 $c=\frac b {a-1}$

原式等价于 $x_n+\frac b {a-1}=a(x_{n-1}+\frac b {a-1})=a^{n-1}(x_1+\frac b {a-1})$

所以 $a^{n-1} \equiv \frac {x_n+\frac b {a-1}} {x_1+\frac b {a-1}} \pmod p$

由于要求最小的 $n$ 使得 $x_n=t$ ，因此将式子中的 $x_n$ 换为 $t$ 即可。

$a\ge 2,b\ge 1,1\le a-1\le p-2$，所以原式分数上下各部分都与 $p$ 互质，因此使用有理数取模将右侧转化为一个整数 $b’$
$$
a^{n-1} \equiv \frac {x_n+\frac b {a-1}} {x_1+\frac b {a-1}} \equiv [x_n+b(a-1)^{-1}] [x_1+b(a-1)^{-1}]=b’ \pmod p
$$

所以原式转化为 $a^{n-1} \equiv b’ \pmod p$，使用 BSGS 求解即可。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int quick_pow(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*a%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return res;
}

int inv(int a,int p){//求逆元(费马小定理) 
    return quick_pow(a,p-2,p);
}

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int bsgs(int a,int b,int p){
    if(1%p==b%p)return 0;
    int k=sqrt(p)+1;
    unordered_map<int,int>hash;
    for(int i=0,j=b%p;i<k;i++){
        hash[j]=i;
        j=1ll*j*a%p;
    }

    int ak=1;
    for(int i=1;i<=k;i++)ak=1ll*ak*a%p;

    for(int i=1,j=ak;i<=k;i++){
        if(hash.count(j)) return 1ll*i*k-hash[j];
        j=1ll*j*ak%p;
    }
    return -2;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        int p,a,b,x1,t;
        cin >> p >> a >> b >> x1 >> t;
        if(a==0){
            if(x1==t)cout << 1 << endl;
            else if(b==t)cout << 2 << endl;
            else cout << -1 << endl;
        }
        else if(a==1){
            if(b==0){
                if(x1==t)cout << 1 << endl;
                else cout << -1 << endl;
            }
            else{
                int x,y;
                exgcd(b,p,x,y);
                cout << (1ll*x*(t-x1)%p+p)%p+1 << endl;
            }
        }
        else{
            int C=1ll*b*inv(a-1,p)%p;
            int A=(x1+C)%p;
            if(A==0){
                int u=(-C+p)%p;
                if(u==t)cout << 1 << endl;
                else cout << -1 << endl;
            }
            else{
                int B=(t+C)%p;
                cout << bsgs(a,1ll*B*inv(A,p)%p,p)+1 << endl;
            }
        }
    }
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~