$\text{BSGS}$ 算法
概念
BSGS 算法用于求解离散对数同余方程
$$
a^t\equiv b\pmod{p}
$$
算法
我们先讨论 $a$ 和 $p$ 互质的情况。
首先由欧拉定理可以知道
$$
a^{t}\equiv a^{t\mod{\varphi(p)}}\pmod{p}
$$
而又知 $\varphi(p)<p$ ,那么考虑暴力枚举 $1\sim p$,一定可以找出最小的非负整数 $t$
设 $k=\sqrt{p}+1$ ,$t=kx-y$ ,其中
$$
\begin{aligned}
x\in[1,\ k],\quad y\in[0,\ k-1]
\end{aligned}
$$
这样通过枚举 $x,y$ ,一定可以遍历到 $1\sim p$ 。当然开始时要对 $x=0$ 进行特判。
发现 $x,y\sim \Theta(\sqrt{p})$ 。那么考虑优化:首先将问题转化为求解
$$
a^{kx}\equiv b\cdot a^y\pmod{p}
$$
用一个 Hash 表将右边所有的取值与 $y$ 的对应存下来,然后枚举 $x$ ,在 Hash 表中查找是否有与 $a^{kx}$ 对应的 $y$ 即可。预处理和枚举的时间复杂度都是 $\Theta(\sqrt{p})$ 级别,因此总复杂度就是 $\Theta(\sqrt{p})$ 。
Q & A
Q : 为什么 $x$ 一定要从 $1$ 开始枚举?
A : 考虑 $x=0$ 的情况,如果继续上面的枚举,那么相当于求 $1\equiv ba^y\pmod{p}$ ,这样的 $y$ 一定是负数,而 BSGS 求解的 $t$ 经常要求是非负整数。所以从 $1$ 开始枚举。
exBSGS
此时不要求 $a,p$ 互质,那么怎么求解呢?
注意到
$$
a^t\equiv b\pmod{p} \Leftrightarrow a^t+kp=b
$$
令 $d=\gcd(a,p)$ ,等式的左边显然能被 $d$ 整除,那么可分为两种情况
-
$d\nmid b$ ,此时无解
-
$d \mid b$ ,那么将等式两边同时除 $d$ 得
$$ \begin{aligned} &\dfrac{a}{d}a^{t-1}+k\dfrac{p}{d}=\dfrac{b}{d}\\ \Leftrightarrow & \dfrac{a}{d}a^{t-1}\equiv \dfrac{b}{d}\pmod{\dfrac{p}{d}}\\ \Leftrightarrow & a^{t-1}\equiv \dfrac{b}{d}\cdot\left(\dfrac{a}{d}\right)^{-1}\pmod{\dfrac{p}{d}}\\ \end{aligned} $$
如果 $a$ 和 $\dfrac{p}{d}$ 已经互质了,那么直接用 BSGS 求解即可,如果不互质,递归执行步骤。事实上,由于因数有限,递归次数一定不会超过 $\mathcal{O}(\log p)$
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
int a, b, p;
unordered_map<int, int> hs;
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;
hs.clear();
for (int y = 0, r = b % p; y < k; y++) {
hs[r] = y;
r = (LL)r * a % p;
}
int ak = 1;
for (int i = 1; i <= k; i++) ak = (LL)ak * a % p;
for (int x = 1, l = ak; x <= k; x++) {
if (hs.count(l)) return k * x - hs[l];
l = (LL)l * ak % p;
}
return -INF;
}
int exBSGS(int a, int b, int p) {
b = (b % p + p) % p;
if (1 % p == b % p) return 0;
int x, y;
int d = exgcd(a, p, x, y);
if (d > 1) {
if (b % d) return -INF;
exgcd(a / d, p / d, x, y);
return exBSGS(a, (LL)b / d * x % (p / d), p / d) + 1;
}
return BSGS(a, b, p);
}
int main() {
while (~scanf("%d%d%d", &a, &p, &b), a || b || p) {
int res = exBSGS(a, b, p);
if (res < 0) puts("No Solution");
else printf("%d\n", res);
}
return 0;
}
$nb$