@[IOI_ILJYT](/user/902351) [这里](https://www.luogu.com.cn/discuss/684623)挺详细的
by Parrhesiates @ 2024-01-25 13:57:30
@[Parrhesiates](/user/519824) 只不过我没有看懂 `不要用快速幂，是可以递推的` 这个是什么意思。。。
by IOI_ILJYT @ 2024-01-25 14:00:45
@[IOI_ILJYT](/user/902351)
已经有人了，我就不掺和了。
by wangguandingding @ 2024-01-25 14:01:22
@[wangguandingding](/user/1060446) 6
by IOI_ILJYT @ 2024-01-25 14:02:48
```cpp
#include <iostream>
#include <unordered_map>
#include <cmath>
std::unordered_map<int, int> m;
inline int read() {
int x = 0, ch;
while (!isdigit(ch = getchar()));
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
inline int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
inline int inv(int x, int p) {
int a, b;
exgcd(x, p, a, b);
return (a % p + p) % p;
}
inline int gcd(int x, int y) {
return !y ? x : gcd(y, x % y);
}
inline int qmi(int x, int k, int mod) {
int s = 1;
while (k) {
if (k & 1) s = 1ll * s * x % mod;
x = 1ll * x * x % mod;
k >>= 1;
}
return s;
}
inline int exbsgs(int a, int b, int p) {
b %= p;
m.clear();
if (b == 1 || p == 1)
return 0;
if (!a) {
if (!b) return 0;
else return -1;
}
int d = 1, g = gcd(a, p), cnt = 0;
while (g > 1) {
if (b % g)
return -1;
cnt++, p /= g, b /= g;
d = 1ll * d * a / g % p;
g = gcd(a, p);
if (d == p)
return cnt;
}
if (a == 1)
return (b == 1) - 1;
int prd = 1, sqr = (int)sqrt(p);
for (int i = 0; i < sqr; i++)
m[int(1ll * b * prd % p)] = i + 1, prd = 1ll * prd * a % p;
for (int i = 0; i <= sqr; i++) {
int k = i * sqr - m[d] + 1 + cnt;
if (m[d] && k > 0)
return k;
d = 1ll * prd * d % p;
}
return -1;
}
int main() {
int a, p, b;
a = read(), p = read(), b = read();
while (a || p || b) {
int res = exbsgs(a, b, p);
if (res < 0)
puts("No Solution");
else printf("%d\n", res);
a = read(), p = read(), b = read();
}
return 0;
}
```
by IOI_ILJYT @ 2024-01-25 14:04:06