BSGS 算法
给定一个质数 ，以及一个整数 ，一个整数 。
现在要求你计算一个最小的非负整数 ，满足 。保证 。
因为 ，并且 是质数，我们很容易就得到了 和 是互质的。
根据扩展欧拉定理：当 时，。于是我们可以得出，最小的非负整数 一定在 之间。可以看作在 之间一定可以找出答案。
这个算法就是利用了把 拆开，在 的时间复杂度内计算出答案。具体地说就是：
我们把 拆为 ，这里令 。
那么变换一下原式：
于是可以发现 的值域最多只有 即 个，可以首先把这 个值域先插入到哈希表内。
具体地、从 到 枚举 ，然后计算出每一个 对应的 ，然后把它当作哈希表的 ，其对应的 就是 。如果后面有覆盖，那么取更大的那个。因为 ， 更大，相应的 就可以更小了。这一步操作就相当于是婴儿一小步。
然后从 到 枚举 ，计算这个时候的 。如果有在哈希表内存在 ，那么我们就得出来答案了。最小的 就是 。这一步操作就可以看作巨人一大步。
如果遍历完了 还是没有找到那个 ，那么无解。
由于这种方法算不出来 的情况，所以当 的时候，就特判，然后直接输出 。
所以这种方法非常之妙，把原本 的复杂度直接砍到 。
只有 676 Bytes 的简短 Code:
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
| #include<bits/stdc++.h>
using namespace std;
int p, b, n;
typedef long long ll;
unordered_map<int, int> hashtb;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int p, a, b;
cin>>p>>a>>b;
if(b == 1) return cout<<'0', 0;
int m = ceil(sqrt(p));
ll bas = b;
ll stt = 1;
for(int i=0;i<m;i++){
hashtb[bas] = i;
bas = bas * a % p;
stt = stt * a % p;
}
ll now = 1;
for(int i=1;i<=m;i++){
now = now * stt % p;
if(hashtb.count(now)){
cout<<i*m-hashtb[now]<<'\n';
return 0;
}
}
cout<<"no solution\n";
return 0;
}
|
所以其实，普通的 BSGS 算法只要求 和 互质即可。不要求 p 为质数。
例题
P4884 多少个 1？
给定整数 和质数 ，求最小的正整数 ，使得 （ 个 ）。
说人话：就是 。
的数据保证 ，，保证 是质数。
从这个鬼玩意想到 BSGS 还是比较有难度的。
具体来说，就是 个 组成的数 ，把它乘上 就变成了 个 组成的数，再加上 就变成了 。
于是原式就可以转化为：
然后移项：
然后就变成了板子。就可以做了。但是因为 ，所以我的代码中使用了龟速乘。
Ex-BSGS 算法
给定一个整数 ，以及一个整数 ，一个整数 。
现在要求你计算一个最小的非负整数 ，满足 。保证 。
和之前的题目有什么不同？这里的 不再和 互质了。也就是说，我们不能再直接用 BSGS 算法来计算出答案了。但是我们可以对 BSGS 算法稍微加以改造，就可以过这道题。
首先还是原式 ，如果 ，那么直接搞 BSGS。否则按照以下步骤进行：
原式它可以等价于 。这个方程可以看成 exgcd 状物，有解的条件显然就是 。如果 ，那么原方程就无解。
如果有解的话，设 ，可以把这个方程化为 。然后就等价于 。就变为了一个新的类似 的式子。
然后继续检查 是否为 ，如果不是，那么就继续按照上面的步骤进行。
最终，等到最大公约数为 之后，令 ，就得到了一个形如 的式子。这里的 就是转化 的次数。
令 。原式就变为了 。
由于此时的 和 是互质的，，所以 也和 互质。所以 就有了模 意义下的逆元（但是千万不要用快速幂求！因为 P 不一定是质数！！！）。
然后求出 的指数了之后，加上 就是我们要求的 了。
核心代码 - Ex-BSGS 和改装后的 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
| void bsgs(ll a, ll b, ll mod, ll k, ll A){
a %= mod, b %= mod;
unordered_map<int, int>mp;
ll m = ceil(sqrt(mod));
ll bas=1, now=b;
for(int i=0;i<m;i++){
mp[now] = i;
now=now*a%mod;
bas=bas*a%mod;
}
now = A;
for(int i=1;i<=m;i++){
now = now*bas%mod;
if(mp.count(now)){
cout<<i*m-mp[now]+k<<'\n';
return ;
}
}
cout<<"No Solution\n";
}
void exbsgs(ll a, ll b, ll mod){
a %= mod, b %= mod;
if(b==1||mod==1) return cout<<"0\n", void();
ll g = gcd(a, mod);
ll k = 0;
ll A = 1;
while(g^1){
if(b%g) return cout<<"No Solution\n", void();
k ++;
b /= g, mod /= g;
A = (A*(a/g)) % mod;
g = gcd(a, mod);
if(A == b) return cout<<k<<'\n', void();
}
bsgs(a, b, mod, k, A);
}
|
Link：BSGS 算法练习题单
