BSGS与exBSGS学习笔记

短命女 2022-01-05 15:05 212阅读 0赞

\\(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; }

转载于:https://www.cnblogs.com/maomao9173/p/10489374.html