BSGS
(y^x = z(mod p)) [(p in prime)]
令
(y^{(x+k)} = z imes y^k(mod p))
然后预处理 (k = [1, sqrt p])
BSGS 就是大块枚举 ((x+k)),就做完了。
exBSGS
(p
otin prime)
((A, p)
ot| B) (and) (B != 1) 则无解。
令 (G = (A, p))
使得 (A^{x-1}frac{A}{G} = frac{B}{G} (mod frac{p}{G}))
(A^{x-1} = AB(mod frac{p}{G})
递归即可。
#include <bits/stdc++.h>
const int mod = 233333;
struct Hash_Table {
Hash_Table() { clear(); }
struct List { int id, val, nxt; } e[233333];
int head[mod], cnt = 0;
void add(int u, int v, int w) { e[++cnt] = {v, w, head[u]}; head[u] = cnt; }
void clear() { memset(head, 0, sizeof(head)); cnt = 0; }
void insert(int x, int i) { int k = x % mod; add(k, x, i); } // mp[x] = i
int query(int x) {
for (int i = head[x % mod]; i; i = e[i].nxt) if (e[i].id == x) return e[i].val;
return -1;
}
} hash;
int qpow(int x, int y, int mod) {
int result = 1;
while (y) {
if (y & 1) { result = 1ll * result * x % mod; }
x = 1ll * x * x % mod; y >>= 1;
}
return result;
}
void NoAnswer() { std::cout << "No Solution" << '
'; return; }
void exbsgs(int y, int z, int p) {
if (z == 1) { std::cout << 0 << '
'; return; }
int k = 0, qwq = 1; hash.clear();
for (int g = std::__gcd(y, p); g != 1; g = std::__gcd(y, p)) {
if (z % g) { NoAnswer(); return; }
z /= g; p /= g; ++k;
qwq = 1ll * qwq * (y / g) % p;
if (qwq == z) { std::cout << k << '
'; return; }
}
int t = sqrt(p) + 1, s = z, base = y;
hash.insert(s, 0);
for (int i = 1; i <= t; i++) { s = 1ll * s * base % p; hash.insert(s, i); }
base = qpow(y, t, p); s = qwq;
for (int i = 1; i <= t; i++) {
s = 1ll * s * base % p;
if (!~hash.query(s)) { continue; }
qwq = hash.query(s);
std::cout << i * t - qwq + k << '
';
return;
}
NoAnswer();
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
int a, p, b;
while (std::cin >> a >> p >> b && a && b && p) { exbsgs(a, b, p); }
return 0;
}