1. BSGS
例题：P3846 【模板】BSGS / [TJOI2007] 可爱的质数
BSGS 的 oi wiki 介绍：链接
但是我感觉还是 chebs大佬的博客 更好理解。
示例程序：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;ll p, b, n, s;
unordered_map<ll, ll> mp;int main() {cin >> p >> b >> n;if (n == 1) {cout << 0 << endl;return 0;}s = ceill(sqrtl(p));for (ll i = 0, t = n; i < s; i++, t = t * b % p) {mp[t] = i;}ll bs = 1;for (int i = 0; i < s; i++) {(bs *= b) %= p;}for (ll i = 1, t = bs; i <= s; i++, t = t * bs % p) {auto it = mp.find(t);if (it != mp.end()) {ll l = i * s - (it->second);cout << l << endl;return 0;}}cout << "no solution\n";return 0;
}
双倍经验
2. 扩展BSGS（exBSGS）
例题：P4195 【模板】扩展 BSGS / exBSGS
exBSGS 的 oi wiki 介绍：链接
示例程序：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;ll gcd(ll a, ll b) {return b ? gcd(b, a%b) : a;
}// 返回 a^x = b(mod m) 的最小非负整数x，没有则返回-1
ll exBSGS(ll a, ll b, ll m) {a %= m, b %= m;if (b == 1 || m == 1)return 0;ll d, ax = 1, cnt = 0;while ((d = gcd(a, m)) > 1) {if (b % d)return -1;m /= d;b /= d;cnt++;(ax *= a / d) %= m;if (ax == b)return cnt;}unordered_map<ll, ll> mp;ll s = ceill(sqrt(m));for (ll i = 0, t = b; i < s; i++, t = t * a % m) {mp[t] = i;}ll base = 1;for (int i = 0; i < s; i++) {(base *= a) %= m;}for (ll i = 1, t = ax; i <= s; i++) {(t *= base) %= m;auto it = mp.find(t);if (it != mp.end())return cnt + i * s - (it->second);}return -1;
}ll a, p, b;int main() {while (~scanf("%lld%lld%lld", &a, &p, &b) && a+p+b) {ll res = exBSGS(a, b, p);if (res == -1)puts("No Solution");elseprintf("%lld\n", res);}return 0;
}