求解 满足 a^x = b (mod p) 的最小自然数x 模板
#include <bits/stdc++.h> #define ll long long using namespace std; const ll mod = 13331; ll a, b, p, ans; ll qpow(ll a, ll b, ll mod = 1e9 + 7) { if (b < 0) return 0; ll ret = 1; a %= mod; while (b) { if (b & 1) ret = (ret * a) % mod; b >>= 1; a = (a * a) % mod; } return ret; } ll inv(ll a) { int mo = p; return qpow(a, mo - 2, mo); } ll Bsgs(ll a, ll b, ll p) { // a ^ x ≡ b(mod p) map<ll, ll> hash; hash.clear(); b %= p; int t = (int)sqrt(p) + 1; for (int j = 0; j < t; j++) { ll val = b * qpow(a, j, p) % p; hash[val] = j; } a = qpow(a, t, p); if (a == 0) return b == 0 ? 1 : -1; for (ll i = 0; i <= t; i++) { ll val = qpow(a, i, p); ll j = hash.find(val) == hash.end() ? -1 : hash[val]; if (j >= 0 && i * t - j >= 0) return i * t - j; } return -1; } void solve1() { while (~scanf("%lld%lld%lld", &a, &b, &p)) { cout << qpow(a, b, p) << endl; } } void solve2() { while (~scanf("%lld%lld%lld", &a, &b, &p)) { if (a % p == 0) cout << "Orz, I cannot find x!" << endl; else { a = inv(a); // cout << inv(a) << endl; cout << (a * b) % p << endl; } } } void solve3() { while (~scanf("%lld%lld%lld", &a, &b, &p)) { ans = Bsgs(a, b, p); ans == -1 ? puts("Orz, I cannot find x!") : printf("%lld\n", ans); } } int main() { int t, k; cin >> t >> k; if (k == 1) solve1(); else if (k == 2) solve2(); else solve3(); return 0; }