概述
BSGS（大步小步法，Baby Step Giant Step）可以在 $\Theta\left(\sqrt p\right)$ 的时间内求解关于 $x$ 的方程 $a^x \equiv b \pmod p$ （要求 $a$ 与 $p$ 互质）的最小整数解。
BSGS
为了方便，我们设 $t = \left\lfloor \sqrt p \right\rfloor$。
对于一个合法的解 $x$，我们可以将 $x$ 拆成 $i \times t - j$ 的形式，其中 $0 \leq j < t$。这时有 $a^{i \times t - j} \equiv b \pmod p$。
根据同余性质，不难得到 $a^{i \times t} \equiv b \times a^j \pmod p$，而由于 $t$ 是固定的，我们可以把 $a^j$ 看作一个常数 $c$，则我们需要求解 $c^i \equiv b \times a^j \pmod p$。
考虑对于所有 $0 \leq j < t$，把 $b \times a^ j \bmod p$ 的值存在一个哈希表里。然后每次枚举 $0 \leq i \leq t$，计算出 $c^i \bmod p$，看看在哈希表里有没有，有的话就找到解了。
那么为什么解 $x$ 一定小于 $p$ 呢？因为 $\gcd\left\{a, p\right\} = 1$，满足欧拉定理。而 $\varphi\left(p\right) < p$，所以达到 $p$ 的 $x$ 一定不是最小的。
代码
long long qpow(long long x,long long y,long long mod){long long tar=1;while(y){if(y&1)tar=tar*x%mod;x=x*x%mod;y/=2;}return tar;}
tp BSGS(tp a, tp b, tp p) {
tp t = sqrt(p);
map<tp, tp> m;
b = b % p;
for (tp i = 0; i < t; ++i) m[b * qpow(a, i, p) % p] = i;
a = qpow(a, t, p);
if (!a) return b ? -1 : 1;
tp val = 1;
for (tp i = 1; i <= t; ++i) {
val = val * a % p;
if (m.count(val)) return i * t - m[val];
}
return -1;
}
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp p, a, b; bin >> p >> a >> b;
tp ans = BSGS(a, b, p);
if (ans == -1) bin << "no solution\n";
else bin << ans << '\n';
}常数优化
我们知道，非固定模的运算很慢，我们可以使用 Barrett 约减来优化常数。但是 Barrett 约减需要用到 128 位整数，因此对于一些不支持 128 位整数的 OJ，只能使用 蒙哥马利约减 了。
Barrett 的证明不重要，想知道的可以自行 Google。
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;}};
long long qpow(long long x,long long y,Barrett mod){long long tar=1;while(y){if(y&1)tar=tar*x%mod;x=x*x%mod;y/=2;}return tar;}
tp BSGS(tp a, tp b, Barrett p) {
tp t = sqrt(p.m);
map<tp, tp> m;
b = b % p;
for (tp i = 0; i < t; ++i) m[b * qpow(a, i, p) % p] = i;
a = qpow(a, t, p);
if (!a) return b ? -1 : 1;
tp val = 1;
for (tp i = 1; i <= t; ++i) {
val = val * a % p;
if (m.count(val)) return i * t - m[val];
}
return -1;
}
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp P, a, b; bin >> P >> a >> b;
Barrett p(P);
tp ans = BSGS(a, b, p);
if (ans == -1) bin << "no solution\n";
else bin << ans << '\n';
}从 296 ms 优化到了 226 ms，提升很大。