概述
exBSGS（扩展大步小步法，ex Baby Step Giant Step）可以在 $\Theta\left(\sqrt p \log p\right)$ 的时间内求解关于 $x$ 的方程 $a^x \equiv b \pmod p$ （不要求 $a$ 与 $p$ 互质）的最小整数解。
前置知识
exBSGS
我们知道，$a^x \equiv b \pmod p$ 可以写成 $a^x + kp = b$。
设 $\gcd\left\{a, p\right\} = d$
根据斐蜀定理，这个式子有解的充要条件是 $d \mid n$，否则直接返回无解
那么上面的式子就是：
$$a^{x - 1} \cdot \frac ad + k \cdot \frac pd = \frac bd$$
此时，让 $x \gets x - 1, p \gets p \cdot d^{-1}, n \gets n \cdot d^{-1}$，递归求解，直到 $a$ 与 $p$ 互质，然后 BSGS 求解。
若此时一共递归 $t$ 次，设 $D$ 为所有 $d$ 的乘积，则原式就是：
$$a^{x - t} \cdot \frac{a^t}D \equiv \frac nD \pmod {\frac pD}$$
注意在跑普通 BSGS 的时候有一个系数 $\dfrac{a^t}D$ 要乘上。
代码
tp BSGS(tp a, tp b, tp p, tp c) {
tp t = ceil(sqrt(p)), val = 1;
unordered_map<tp, tp> m;
b = b % p;
for (tp i = 0; i < t; ++i) {
m[b * val % p] = i;
val = val * a % p;
}
a = val;
if (!a) return b ? -1 : 1;
for (tp i = 1, val = c; i <= t; ++i) {
val = val * a % p;
if (m.count(val)) return i * t - m[val];
}
return -1;
}
tp exBSGS(tp a, tp b, tp p) {
a = a % p; b = b % p;
if (b == 1 || p == 1) return 0;
tp t = 0, d, c = 1;
while ((d = gcd(a, p)) != 1) {
if (b % d) return -1;
++t;
b /= d; p /= d;
c = (a / d * c) % p;
if (c == b) return t;
}
tp ans = BSGS(a, b, p, c);
if (ans == -1) return -1;
return ans + t;
}
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp p, a, b;
while (bin >> a >> p >> b, a | b | p) {
tp ans = exBSGS(a, b, p);
if (ans == -1) bin << "No Solution\n";
else bin << ans << '\n';
}
}Barrett 优化的代码：
struct Barrett{typedef unsigned long long ull;typedef __uint128_t LL;ull m,B;Barrett()=default;Barrett(ull m):m(m),B((LL(1)<<64)/m){}friend ull operator%(ull a,const Barrett&mod){ull r=a-mod.m*(LL(mod.B)*a>>64);return r>=mod.m?r-mod.m:r;}};
tp gcd(tp a, tp b) {
while (b ^= a ^= b ^= a %= b);
return a;
}
tp BSGS(tp a, tp b, Barrett p, tp c) {
tp t = ceil(sqrt(p.m)), val = 1;
unordered_map<tp, tp> m;
b = b % p;
for (tp i = 0; i < t; ++i) {
m[b * val % p] = i;
val = val * a % p;
}
a = val;
if (!a) return b ? -1 : 1;
for (tp i = 1, val = c; i <= t; ++i) {
val = val * a % p;
if (m.count(val)) return i * t - m[val];
}
return -1;
}
tp exBSGS(tp a, tp b, tp p) {
a = a % p; b = b % p;
if (b == 1 || p == 1) return 0;
tp t = 0, d, c = 1;
while ((d = gcd(a, p)) != 1) {
if (b % d) return -1;
++t;
b /= d; p /= d;
c = (a / d * c) % p;
if (c == b) return t;
}
tp ans = BSGS(a, b, p, c);
if (ans == -1) return -1;
return ans + t;
}
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp p, a, b;
while (bin >> a >> p >> b, a | b | p) {
tp ans = exBSGS(a, b, p);
if (ans == -1) bin << "No Solution\n";
else bin << ans << '\n';
}
}