浅谈BSGS和EXBSGS

我的 BSGS 和各位犇犇的差不多，但是不需要求逆元

Luogu [ TJOI2007 ] 可爱的质数

原题展现

题目描述

给定一个质数 p，以及一个整数 b，一个整数 n，现在要求你计算一个最小的非负整数 l，满足 bl≡n(modp)。

输入格式

仅一行，有 3 个整数，依次代表 p,b,n。

输出格式

仅一行，如果有 l 满足该要求，输出最小的 l，否则输出 no solution。

样例 #1

样例输入 #1

复制代码
1
er-hljs
5 2 3

样例输出 #1

复制代码
1
er-hljs
3

数据规模与约定

• 对于所有的测试点，保证 2≤b,n<p<231。

Baby Steps Giant Steps 详解

注意到互质，根据欧拉定理，我们易得l<p，枚举的时间复杂度为O(p)

其实可以优化到O(√p)，设 m=⌈√p⌉,r=b%m

于是我们可以将 原式写成

bkm+r≡n(modp)bkm≡nb−r(modp)

右边好像要求逆元啊，我们不想求逆元，怎么办呢？

只需将式子改成

bkm−r≡n(modp)bkm≡nbr(modp)

解决了问题

我们考虑找到一个 k 和 一个 r 使得上述式子成立，这个并不难

首先枚举 r ，显然有 r(1≤r≤m) 注意这里和广大打法不同

因为广大打法是枚举余数，这里枚举的是相反的

然后把右边式子的值哈希存下，枚举左边的 k(1≤k≤m)

对于左边枚举求出的值看看哈希数组是否存在对应的右边的值，如果有，那么就是一个解

搞出一个最小的解好像也不是很难吧.....

时间复杂度 O(m) ，也就是 O(√p)

然后注意一下，要打很多特判

上一下码风巨丑的代码

复制代码
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
cpp
inline ll ksc(ll x, ll y, const ll& p) { return (x * y - (ll)((long double)x / p * y) * p + p) % p; }
vector<pair<ll, int> > v[ 100013];
inline ll BSGS(ll a, ll b, const ll&p) {
        if (b == 1) {
        if (a == 0)
            return -1;
        return 1;
    }
    if (b == 0) {
        if (a == 0)
            return 1;
        return -1;
    }
    if (a == 0) {
        return -1;
    }
    ll m = ceil(sqrt(p)), cnt = 1, res = 1;
    for (int r = 1; r <= m; r++) {
        cnt = ksc(cnt, a, p);//这个龟速乘不是龟速乘
        v[(ksc(cnt, b, p)) % mod].push_back(make_pair(ksc(cnt, b, p), r));
    }
    for (int k = 1; k <= m; k++) {
        res = ksc(cnt, res, p);
        ll id=res%mod;
        if (v[id].size())
        {
            for (int j = v[id].size() - 1; j >= 0; j--)
            {
                if (v[id][j].first ==res)
                {
                    return m * k - v[id][j].second; 
                }                
            }                           
        }
    }
    return -1;
}

SPOJ3105 MOD

原题展现

题目描述

给定 a,p,b，求满足 ax≡b(modp) 的最小自然数 x 。

输入格式

每个测试文件中包含若干组测试数据，保证 ∑√p≤5×106。

每组数据中，每行包含 3 个正整数 a,p,b 。

当 a=p=b=0 时，表示测试数据读入完全。

输出格式

对于每组数据，输出一行。

如果无解，输出 No Solution，否则输出最小自然数解。

样例 #1

样例输入 #1

复制代码
1
2
3
er-hljs
5 58 33
2 4 3
0 0 0

样例输出 #1

复制代码
1
2
er-hljs
9
No Solution

数据范围

对于 100% 的数据，1≤a,p,b≤109 或 a=p=b=0。

扩展 Baby Steps Giant Steps 详解

注意到不互质，那我们就要想办法让它互质

ax≡b(modp)ax−kp=b设d=gcd(a,p)若d|b不成立，则无解式子除d得ax−1ad−kpd=bd改记为ax−1a′−kp′=b′即ax−1a′≡b′(modp′)

如此反复，直到互质为止，差不多就是

ax−cnta′≡b′(modp′)

注意，操作时如果两边值相等了，答案就是 cnt

然后就是个普通 BSGS ,变了一点点，左边需要乘上 a′，其他都是一模一样的

求出答案之后答案要加上 cnt ,因为我们求出的是 x−cnt

本题时限高达 4s ，就算不写哈希用 map 也能通过

参考如下实现

复制代码
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
cpp
vector<pair<ll, int> > v[ 1000013];
int vis[1000003];
inline ll exBSGS(ll a,ll b,ll p)
{
    memset( vis,0,sizeof(vis));
    if(p==0)return -1;
    if(p==1)
    {
        if(b==0)return 0;
        return -1;
    }
    if (b == 1) {
        if (a == 0)
            return -1;
        return 1;
    }
    if (b == 0) {
        if (a == 0)
            return 1;
        return -1;
    }
    if (a == 0) {
        return -1;
    }
    ll ak=0,t=1,d=gcd(a,p);
    while(d!=1)
    {
        ak++;
        t*=a;
        t/=d;
        p/=d;
        if(b%d!=0)return -1;
        b/=d;
        if(t%p==b%p)return ak;
        d=gcd(a,p);
        t%=p;
    }
    ll m = ceil(sqrt(p)), res=t%p,cnt=1;
    
    for (int r = 1; r <= m; r++) {
        cnt = ksc(cnt, a, p);
        ll hash=(ksc(cnt, b, p)) % mod;
        if(vis[hash]==0)
        {
            vis[hash]=1;
            v[hash].clear();
        }
        v[hash].push_back(make_pair(ksc(cnt, b, p), r));
    }
    for (int k = 1; k <= m; k++) {
        res = ksc(cnt, res, p);
        ll hash=res%mod;
        if (vis[hash])
        {
            for (int j = v[hash].size() - 1; j >= 0; j--)
            {
                if (v[hash][j].first ==res)
                {
                    return m * k - v[hash][j].second+ak; 
                }                
            }                           
        }
    }
    return -1;
}

---

大部分 BSGS 题都很明显，随便挑了几道

P4884 多少个 1？

原题展现

题目描述

给定整数 K 和质数 m，求最小的正整数 N，使得 $ 11\cdots1（N$ 个 1）≡K(modm)。

说人话：就是 111⋯1111modm=K。

输入格式

第一行两个整数，分别表示 K 和 m。

输出格式

一个整数，表示符合条件最小的 N。

样例 #1

样例输入 #1

复制代码
1
er-hljs
9 17

样例输出 #1

复制代码
1
er-hljs
3

提示

30% 的数据保证 m≤106。

60% 的数据保证 m≤5×107。

100% 的数据保证 6≤m≤1011，0<K<m，保证 m 是质数。

解法

将式子乘九，再加一，得到一个式子

10N+1=9∗k+1(modm)

然后 BSGS 即可

[SDOI2013] 随机数生成器

原题展现

题目背景

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

题目描述

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

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

我们用 xi 来表示通过这种方法生成出来的第 i 个数，也即小 W 第 i 天会读哪一页。这个方法需要设置 3 个参数 a,b,x1，满足 0≤a,b,x1<p，且 a,b,x1 都是整数。按照下面的公式生成出来一系列的整数：

xi+1≡a×xi+b(modp)

其中 mod 表示取余操作。

但是这种方法可能导致某两天读的页码一样。

小 W 要读这本书的第 t 页，所以他想知道最早在哪一天能读到第 t 页，或者指出他永远不会读到第 t 页。

输入格式

本题单测试点内有多组测试数据。

第一行是一个整数 T，表示测试数据组数。

接下来 T 行，每行有五个整数 p,a,b,x1,t，表示一组数据。

输出格式

对于每组数据，输出一行一个整数表示他最早读到第 t 页是哪一天。如果他永远不会读到第 t 页，输出−1。

样例 #1

样例输入 #1

复制代码
1
2
3
4
er-hljs
3
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1

样例输出 #1

复制代码
1
2
3
er-hljs
1 
3 
-1

提示

对于全部的测试点，保证：

• 1≤T≤50。
• 0≤a,b,x1,t<p，2≤p≤109。
• p 为质数。

解法

推式子，我还没做，等几天吧...