BSGS算法及其扩展算法
BSGS算法
所谓 Baby Step, Giant Step 算法，也就是暴力算法的优化
用于求出已知 \(a, b, p, p为质数\) 时 \(a^x \equiv b \pmod p\) 的一个最小正整数解 \(x\)
下文中 \(a \perp p\) 指的是 \(a, p\) 互质
有两种情况：
-
\(a, p\) 不互质，又由于 \(p\) 是质数，意味着 \(a\) 是 \(p\) 的倍数，所以 \(b\) 如果不为 \(0\) ，那么一定无解
-
两者互质……即 \(a \perp p\) :
考虑到 \(a \perp p\) 意味着 \(a\) 在 \(p\) 的完全剩余系中，也就是说 \(f(x) = a^x \pmod p\) 是一个周期为 |<a>| (……就是 \(a\) 在模 \(p\) 意义下的生成子群的大小) 的周期函数
实际上我们不会算出其周期的具体大小，我们只需要利用 |<a>| 恒 \(\le p\) 就行了
那么我们只需要枚举 \(x \in [0, p)\) 依次验证就可以求解了
但是暴力枚举没有那么优秀，对于出题人的数据可能过不了
所以我们就可以采用把毒瘤出题人吊起来打的方法BSGS算法进行优化
BSGS算法采用分块的思想 （分块？块大小就 \(\sqrt p\) 不就就行了吗，有什么好疑惑的？
假设块大小为 \(t\)
先参入 \(t\) 改写一下式子 \(a^x \equiv b \pmod p\)
得到 \(a^{it-j} \equiv b \pmod p\)
由于 \(a \perp p\) ，上述式子等价于 \(a^{it} \equiv (a^t)^i \equiv b a^j \pmod p\)
那么我们先预处理右式，枚举 \(j \in [0, t)\) 把 \(ba^j \mod p\) 插入到一个Hash表中
也就是说 \(HashMap: \quad ba^j\ mod\ p \Rightarrow j\)
那么枚举 \(i \in [0, \lceil \frac pt \rceil]\) 计算出 \(a^{it} \mod p\) ，查找是否有对应的 \(j\)，更新答案即可
时间复杂度为 \(O(t + \lceil \frac pt \rceil)\)
为了进一步优化时间复杂度，已知均值不等式 \(a + b \ge 2\sqrt{ab}\)，当且仅当 \(a=b\) 时等号成立，所以我们令 \(t = \lceil \sqrt p \rceil\)，那么时间复杂度就简化为了 \(O(\sqrt p)\)
常数为 \(2\) 可能还需要带一个 \(log\) ? QwQ
参考代码如下：仅供参考
template<typename data>
data BSGS(data a, data b, data p) {
b %= p;
static std::map<data, data> hash; hash.clear();
data t = std::ceil(std::sqrt(p)), v(1), j(0);
for (; j < t; ++j) {
// 此时 v = a^j % p
hash[v * b % p] = j;
v = v * a % p;
}
// 把 a 预处理成 a^t, 这样 (a^t)^i 就可以更快的算出了
a = qpow(a, t, p), v = 1;
// 如果此时 a 已经为 0 了，由于 t < p， p为质数所以 p|a (a为p的倍数)
// 那么此时，如果 b 不为 0 则一定无解
if (a == 0) return b == 0 ? 1 : -1;
for (data s(0); s <= t; ++s) {
// 此时 v = (a^t)^s
j = hash.find(v) == hash.end() ? -1 : hash[v];
if (~j && s * t >= j) return s * t - j;
v = v * a % p;
}
return -1;
}
扩展BSGS算法 (exBSGS)
其实问题一摸一样，只是 \(p\) 不为质数了，也就是说其中 \(a, p\) 不一定互质
那么我们需要想办法使之变得互质，然后通过普通的 BSGS 算法求解
具体的，令 \(d_1 = gcd(a, p)\)，如果 \(d_1 \nmid b\) 则原方程无解
这个我们可以将同余式转换：\(s a^x + tp = b\)
左式再转化为 \(d_1 (s a^{x-1} \frac a{d_1} + t \frac p {d_1}) = b\)
也就是说，如果 \(d_1 \nmid b\) ，那么一定无整数解
那么上述式子就可以转化为 \(sa^{x-1} \frac a{d_1} + t \frac p {d_1} = \frac b {d_1}\)
再换成同余式子，就变为了 \(\frac a {d_1}\cdot a^{x-1} \equiv \frac b {d_1} \pmod {\frac p {d_1}}\)
如果此时 \(a\) 与 \(\frac p {d_1}\) 任然不互质，那么继续上述转化，令\(d_2 = gcd(a, \frac p {d_1})\)
则 \(\frac a {d_1 d_2} \cdot a^{x-2} \equiv \frac b {d_1 d_2} \pmod {\frac p {d_1 d_2}}\)
同理不断处理，直到 \(a \perp \frac p {d_1 d_2 \dots d_k}\)
我们记 \(D = \prod_{i = 1}^k d_i\)
那么最终的方程就是 \(\frac {a^k} {D} \cdot a^{x-k} \equiv \frac bD \pmod {\frac pD}\)
这样，我们把 \(\frac {a^k}D\) 通过逆元丢到方程右边，就成为了一个普通的 BSGS 问题了
注意一个细节，不排除解小于等于 \(k\) 的情况，所以在消去 \(d_i\) 的时候还要判断一下 \(a^i \equiv b \pmod p\) 是否可行
还有一些细节问题我会放在代码之后解释
参考代码：仅供参考
// inv(i) i \equiv 1 mod p
// i * inv(i) + kp = 1 (kown i, p, 1)
template<typename T>
T inv(T i, T p) {
T iv, k;
exgcd(i, p, &iv, &k);
iv %= p;
// 注意点4
return iv < 0 ? iv + p : iv;
}
data exBSGS(data a, data b, data p) {
// 注意点 1
b %= p;
// 注意点 2
if (b == 1 || p == 1) return 0;
data d, ak(1), k(0);
while ((d = gcd(a, p)) != 1) {
if (b % d) return -1;
++k, p /= d, b /= d;
ak = a / d * ak % p;
// 注意点 3
if (ak == b) return k;
}
// 注意点 4
b = b * inv(ak, p) % p;
data res = BSGS(a, b, p);
// 注意点 5
if (~res) return res + k;
return -1;
}
注意点1：为什么需要一次
b %= p考虑这样一组数据
a = 10, b = 110, p = 100其实这个地方也可以加一句
a %= p，可以减少部分运算，也不会影响正确性，反正都是乘法，模意义下人人平等
注意点2：这里的特判是什么意思
如果p为1，相当于同余式恒成立，所以直接返回最小答案即可
如果b为1，考虑到 \(\forall a \ne 0, a^0 = 1\)，所以直接返回最小答案即可
注意点3：这就是上文中答案小于 \(k\) 情况的特判
注意点4：为什么需要逆元
由于是在模 \(\frac pD\) 意义下，所以需要通过逆元的方式调整
但是考虑到两者不知道是否互质，所以通过扩展欧几里得算法就行了
扩展欧几里得算法可以参考：算法学习笔记(1): 欧几里得算法及其扩展
标签：10,frac,算法,return,BSGS,data,equiv From： https://www.cnblogs.com/jeefy/p/17055264.html注意点5：
由于我们在求 \(D\) 的时候消耗了 \(k\) 个\(a\)，所以需要加上 \(k\) 才是正确答案