【数学】BSGS 算法

功能：

求解 $a^x\equiv b(\mathrm{mod}p)$，其中 $a$ 和 $p$ 互质。

算法流程：

由欧拉定理得，$a^t\equiv a^{t\mathrm{mod}\phi (p)}(\mathrm{mod}p)$

所以，最小的整数 $t$ 使得 $a^t\equiv b(\mathrm{mod}p)$，一定是小于 $\phi (p)$ 的，那么考虑枚举 $1\sim \phi (p)$，不过通常为了方便，直接枚举 $1\sim p$ 即可（因为求 $\phi (p)$ 比较麻烦）。

将 $1\sim p$ 分成 $\sqrt{p}$ 段，每一段的长度 $k=\sqrt{p}+1$，这时候 $t=kx-y$，其中 $x\in [1,k],y\in [0,k)$

此时问题转化为了求 $a^{kx-y}\equiv b(\mathrm{mod}p)$，即 $a^{kx}\equiv a^{y}b(\mathrm{mod}p)$。

那么，枚举 $x$ 后就是看最大的合法的 $y$ 是多少？这个可以通过哈希来解决，具体来说就是提前将 $a^{y}b\mathrm{mod}p$ 存入哈希表中，其中 $y\in [0,k)$，如果有相同的值选择较大的一个。

代码：

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

int BSGS(int a, int b, int p) {
	if (1 % p == b % p) return 0;
	unordered_map<int, int> hash;
	int k = sqrt(p) + 1;
	for (int i = 0, j = b % p; i < k; i ++)
		hash[j] = i, j = j * a % p;
	int ak = 1;
	for (int i = 1; i <= k; i ++) ak = ak * a % p;
	for (int i = 1, j = ak; i <= k; i ++) {
		if (hash.count(j)) return k * i - hash[j];
		j = j * ak % p;
	}
	return -1;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int a, b, p;
	while (cin >> a >> p >> b, a || p || b) {
		int res = BSGS(a, b, p);
		if (res == -1) cout << "No Solution" << endl;
		else cout << res << endl;
	}

	return 0;
}