北上广深算法 BSGS

又名百度谷歌算法、拔山盖世算法 其实叫大步小步算法。

给定 $a, p, b,$ 求满足 $a^{x} \equiv b\pmod p$ 的最小自然数 $x$。

普通的 BSGS 假设了 $p$ 为质数。

令 $x = i \times m -j$，其中 $m = \lceil \sqrt{p} \rceil$，注意是向上取整。那么原式为

$a^{i \times m - j} \equiv b \pmod p$

移项得到

$a^{i \times m} \equiv b \times a^j \pmod p$

枚举 $j \in [0,m]$，预处理出 $b \times a^j$ 并在一个桶中记录。

枚举 $i \in [1,m]$，找到第一个满足 $a^{i \times m} \equiv b \times a^j \pmod p$。

此时 $x = i \times m - j$ 即为答案。

证明略，我不会。可以发现 BSGS 复杂度为 $\sqrt{p}$，如果用 map 当桶的话加个 $\log$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
#define int long long
inline int read() {int x = 0, f = 0; char ch = 0;while (!isdigit(ch)) f |= ch == '-', ch = getchar();while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();return f ? -x : x;
}
//a^x = b (mod p)
map<int, int> mp;
int ksm(int a, int k, int p) {int res = 1;while (k) {if (k & 1) res = res * a % p;a = a * a % p;k >>= 1;}return res % p;
}
int BSGS(int a, int b, int p){int m = ceil(sqrt(p));for (int i = 1; i <= m; i++) mp[ksm(a, i, p) * b % p] = i;int t = ksm(a, m, p), ans = 1;for (int i = 1; i <= m; i++) {ans = ans * t % p;if (mp[ans]) return ((i * m - mp[ans]) % p + p) % p;}return -1;
}
signed main() {int p = read(), a = read(), b = read();int ans = BSGS(a, b, p);if (ans == -1) puts("no solution");else printf("%lld\n", ans);return 0;
}