创建时间：2025-05-29
大步小步算法
大步小步算法（Baby Step Giant Step,BSGS）运用了 Meet in the Middle 的思想，用根号的时间求出 \(a\)、\(p\) 互质时方程 \(a^x \equiv b \pmod p\) 的最小非负整数解，过程如下：
由欧拉定理知：\(a^{\varphi(p)} \equiv 1 \pmod p\)，所以 \(a^{\varphi(p)+x} \equiv a^x \pmod p\)，\(a^{k\varphi(p)} \equiv a^v \pmod p(k \in \N)\)，所以当 \(a^x \equiv b \pmod p\) 有解时，一定也存在一个 \(x \in [0, \varphi(p))\) 的解。
令 \(x=At-B(A,B\in \N^*,t \in N^*,B \le t)\)，则 \(a^{At-B} \equiv a^x \equiv b \pmod p\)，同乘 \(a^B\) 得 \(a^{At} \equiv a^Bb \pmod p\)。我们可以先从小到大枚举 \(B\)，计算出 \(a^Bb \bmod p\) 的值，并将每个值对应的最大的 \(B\) 存入哈希表（因为 \(x=At-B\)，所以 \(B\) 越大 \(x\) 越小）。再从小到大枚举 \(A\)，计算 \(a^{At}\) 的值，并试着在哈希表中找到一个 \(a^{At}\) 对应的 \(B\)，若找到了则立即返回答案 \(At-B\)（当 \(A'>A\) 时，\(A't-B'\) 一定大于 \(At-B\)）。因为 \(x<\varphi(p)<p\)，所以只需从 \(1\) 枚举到 \(p\) 即可，若还没找到答案，则原方程无解。
这个算法的复杂度为 \(O(\frac p t+t)\)，显然，当 \(t=\sqrt p\) 时复杂度最小，为 \(O(\sqrt p)\)。不过为了保险起见，通常取 \(t=\sqrt p + 1\)。
PS：由于枚举 \(A\) 时 \(a^{At}\) 每次扩大到原来的 \(a^t\) 倍，称之为“大步”；枚举 \(B\) 时 \(a^Bt\) 每次扩大到原来的 \(a\) 倍，称之为“小步”。故该算法得名“大步小步”。
代码：
int qpow(int a, int k, int p) {int res = 1;while (k) {if (k & 1)res = res * a % p;a = a * a % p;k >>= 1;}return res;
}int BSGS(int a, int b, int p) {unordered_map<int, int> hs;int t = sqrt(p) + 1, bs = b * a % p;for (int B = 1; B <= t; B++) {hs[bs] = B;bs = bs * a % p;}int pw = qpow(a, t, p), gs = pw;for (int A = 1; A <= t; A++) {if (hs.count(gs))return A * t - hs[gs];gs = gs * pw % p;}return -1;
}
注：之所以要求 \(a \perp p\) 互质是因为在求出 \(a^{At} \equiv a^Bb \pmod p\) 后需要通过两边同时除以 \(a^B\) 才能得到 \(a^x(a^{At-B})\) 的解，而为了保证同余式仍然成立，必须有 \(a^B \perp p\)，所以 \(a \perp p\)。
扩展大步小步算法
扩展大步小步（Extend Baby Step Giant Step,exBSGS），将求解方位扩展到了 \(a\) 和 \(p\) 不互质的情况，下面是它的求解过程：
将高次同余方程 \(a^x \equiv b \pmod p\) 变形为 \(a \cdot a^{x-1}+p \cdot y=b\)，我们可以先用裴蜀定理判定它是否有解，即 \(\gcd(a,p) \mid b\) 是否成立，若不成立，即无解，直接返回 \(-1\) 即可。若成立，则令 \(d=\gcd(a,p)\)，再将其变形为 \(\frac a d \cdot a^{x-1}+ \frac p d \cdot y=\frac b d\)，这个方程又与同余方程 \(\frac a d \cdot a ^{x-1} \equiv \frac b d \pmod {\frac p d}\) 是等价的。显然 \(\frac a d\) 和 \(\frac p d\) 是互质的，所以 \(\frac a d\) 存在模 \(\frac p d\) 意义下的逆元，所以可以将方程变为 \(a^{x-1} \equiv \frac b d (\frac a d)^{-1} \pmod {\frac p d}\)，继续并向下递归求出该高次同于方程的解，直至 \(\gcd(a,p)=1\) 时，直接用大步小步算法求解并返回；若下层方程无解，则本层的方程也无解，返回 \(-1\)；否则将解加 \(1\) 并返回即可。
由于每向下递归一层 \(p\) 都要除以 \(d\)，而 \(d\) 至少是 \(2\)，所以一共有 \(\log p\) 层，每层都要求解最大公约数和逆元，再加上最后一层的普通大步小步，总的复杂度为 \(O(\log^2 p+\sqrt p)\)。
代码：
int qpow(int a, int k, int p) {int res = 1;while (k) {if (k & 1)res = res * a % p;a = a * a % p;k >>= 1;}return res;
}int exgcd(int a, int b, int& x, int& y) {if (b == 0) {x = 1, y = 0;return a;}int x0, y0, d = exgcd(b, a % b, x0, y0);x = y0, y = x0 - a / b * y0;return d;
}int BSGS(int a, int b, int p) {unordered_map<int, int> hs;int t = sqrt(p) + 1, bs = b * a % p;for (int B = 1; B <= t; B++) {hs[bs] = B;bs = bs * a % p;}int pw = qpow(a, t, p), gs = pw;for (int A = 1; A <= t; A++) {if (hs.count(gs))return A * t - hs[gs];gs = gs * pw % p;}return -1;
}int exBSGS(int a, int b, int p) {a %= p, b = (b % p + p) % p;if (b == 1 || b == 0 && p == 1)return 0;int x, y, d = exgcd(a, p, x, y);if (b % d)return -1;if (d == 1)return BSGS(a, b, p);b /= d, p /= d;exgcd(a / d, p, x, y);int tmp = exBSGS(a, b * x % p, p);return tmp == -1 ? -1 : tmp + 1;
}大步小步算法&扩展大步小步算法的应用
大步小步算法可以较快的求出 \(a_x \equiv b \pmod p\) 的解，但部分特殊无解情况大步小步算法无法判定出来，故使用时需谨慎判断有没有特殊情况；扩展大步小步算法的约束条件很少，但代码较为复杂且大多数情况大步小步算法已经足够解决问题，所以扩展大步小步算法在 OI 赛场上比较冷门，题目也很少。
P3846 [TJOI2007] 可爱的质数/【模板】BSGS；
P4454 [CQOI2018] 破解D-H协议；
P4028 New Product；
P2485 [SDOI2011] 计算器；
P3306 [SDOI2013] 随机数生成器（数学归纳法+等比数列+大步小步算法）；
P4884 多少个 1？（等比数列+大步小步算法）；
P4195 【模板】扩展 BSGS/exBSGS（扩展大步小步算法模板）。