\(BSGS\)用于解决这样一类问题：
求解\(A^x ≡B(modP)\)的最小\(x\)，其中\(P\)为质数。
这里我们采用分块的方法，把\(x\)分解为\(i *t-b\)（其中\(t\)是分块大小） 。根据模意义下逆元的性质，\(x\)的大小一定\(<=phi(p)\)即\(p - 1\)，所以经过移项和进行存在性对比，我们就可以\(O(N)\)求出答案。
int BSGS (int A, int B, int P) {
int t = (int) ceil (sqrt (P));
for (int j = 0; j < t; ++j) {
mp[_mul (B, _pow (A, j, P), P)] = j;
//mp[ B * A ^ j ] = j;
}
A = _pow (A, t, P);
for (int i = 1; i <= t; ++i) {
int val = _pow (A, i, P);
//val = A^{i*t};
int j = mp.find (val) == mp.end () ? -1 : mp[val];
if (j >= 0) {
return i * t - j;
}
}
return -1;
}
上面这份代码中其实还可以把快速幂的\(log\)优化掉，可能会被卡常。
几个要注意的关键点：
- 避免快速幂
- 优化快速乘
- 小心取模和\(longlong\)
- \(p\)一定要是质数！
- 建议手写哈希不然会多一个\(log\)（\(unordered\_map\)是不允许使用的）
\(exBSGS\)其实就是一个简单的扩展，把情况扩展到了\(p\)不是质数的情况，这种情况我们要先把\(P\)和\(A\)化为互质的状态。也就是说：对\(A\)和\(P\)取\(gcd\)直到其互质为止，从而化为如下形式：
\[(A/d)^{cnt} * A^{x}≡B/d^{cnt} (mod P/d^{cnt})
\]
\]
其中，当\(B\)不能被二者的\(gcd\)整除时，就意味着原方程无解。
几个注意点：
- 前面的\((A/d)^{cnt}\)同样需要统计进去
- 要使用\(exgcd\)求解，因为可能不存在逆元。
- 可能存在\(x==0\)的情况，记得特判
- 快速乘，\(longlong\)，取模，务必小心。
int exbsgs (int A, int B, int p) {
if (B == 1) return 0;
int _gcd, cnt = 0, res = 1;
while ((_gcd = gcd (A, p)) != 1) {
if (B % _gcd) return -1;
B /= _gcd, p /= _gcd, ++cnt;
res = ((res % p) * (A / _gcd)) % p;
if (res == B) return cnt;
}
int t = sqrt (p) + 1, tmp = 1;
Hash.clear ();
for (int i = 0; i < t; ++i) {
Hash[(tmp * B) % p] = i;
tmp = (tmp * A) % p;
}
res = (res * tmp) % p;
for (int i = 1; i <= t; ++i) {
if (Hash.find (res) != Hash.end ()) {
return i * t - Hash[res] + cnt;
}
res = (res * tmp) % p;
}
return -1;
}