BSGS
简介
BSGS（Baby Step, Giant Step）算法，用于解决高次同余方程，即给定整数 \(a,b,p\)，其中 \(a \perp p\) （互质），求解最小非负整数 \(x\) 使得 \(a^x \equiv b \pmod p\)。
算法流程
将 \(a^x \equiv b \pmod p\) 化为 \(a^{\lceil \sqrt{p} \rceil \cdot k - s} \equiv b \pmod p\)，其中 \(0 \leq k,s \leq \lceil \sqrt{p} \rceil\)，因为 \(a^s \perp p\)，所以 \(a^{\lceil \sqrt{p} \rceil \cdot k} \equiv a^s \cdot b \pmod p\)。可以思考一下此处构造 \(-s\) 而非构造 \(+s\) 的目的：很显然，是为了方便处理才这么做的。
所以我们就可以使用哈希表预处理 \(a^s \cdot b\)，然后再把 \(a^{\lceil \sqrt{p} \rceil \cdot k}\) 丢进去看能否匹配即可。
时间复杂度应该是 \(\mathcal{O(\sqrt{p})}\)，如果使用 map 存的话会多一个 \(\log\)。
扩展 BSGS
简介
BSGS 显然只能解决 \(a \perp p\) 时的高次同余方程，那么考虑当 \(a\) 与 \(p\) 不互质的时候该如何处理，只能使用扩展 BSGS 来解决。
算法流程
对于 \(a^x \equiv b \pmod p\)，考虑将 \(a,p\) 变成互质的。
我们取 \(d = \gcd(a,p)\)，由模运算的性质，可得 \(a^x \cdot \cfrac{a}{d} \equiv \cfrac{b}{d} \pmod {\cfrac{p}{d}}\)，如果 \(b,d\) 不互质，那么可以证明无解；如果此时 \(a,\frac{p}{d}\) 仍然不互质，重复上述过程，记录 \(s\) 为次数。注意，此处我们需要进行优化，当 \(\frac{b}{\prod_{i = 1}^{k} d_i} = \frac{a^k}{\prod_{i = 1}^{k} d_i}\)，那么此时我们可以退出计算，并返回此时 \(s\) 的值。
经过上述过程，原式可转换为 \(a^{x - k} \cdot \cfrac{a^k}{\prod_{i = 1}^{k} d_i} \equiv \cfrac{b}{\prod_{i = 1}^{k} d_i} \pmod {\cfrac{p}{d}}\)，再转换成为 \(a^{x - k} \equiv \cfrac{b}{a^k} \pmod {\cfrac{p}{d}}\)
然后我们就可以把式子扔进 BSGS 里直接计算了。
$\tt{Link}$
il int qmi(int a,int b,int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
il 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;
}
il int inv(int x,int p) {
int invv,y;
int d = exgcd(x,p,invv,y);
return (invv % p + p) % p;
}
il int BSGS(int a,int b,int p) {
st.clear();
int cnt = (int)ceil(sqrt(p * 1.0));
b %= p;
rep(i,1,cnt) (b *= a) %= p,st[b] = i;
int val = qmi(a,cnt,p);
a = 1;
rep(i,1,cnt) {
(a *= val) %= p;
if (st.count(a)) return (i * cnt - st[a] + p) % p;
}
return -1;
}
il int exBSGS(int a,int b,int p) {
a %= p; b %= p;
if (b == 1 || p == 1) return 0;
int d = __gcd(a,p),s = 0,e = 1;
while (d > 1) {
if (b % d) return -1;
b /= d; p /= d; (e *= (a / d)) %= p; ++ s;
if (b == e) return s;
d = __gcd(a,p);
}
int res = BSGS(a,b * inv(e,p) % p,p);
if (res == -1) return -1;
return res + s;
}