题面
我一开始是有一个假的10分做法的
正解
如果$a,p$互质，直接BSGS就好了
不互质？搞互质就好了
首先如果$b\neq1,\gcd(a,p)\not|b$的话无解
显然嘛，你怎么幂都是$\gcd(a,p)$的倍数
于是令$g=\gcd(a,p)$,那么$g|b$
然后递归就好了
最多log层
$O(log^2n+\sqrt n)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;
inline int BSGS(int a, int b, int mod, int k = 1) {
int q = sqrt(mod) + 1;
unordered_map<int, int> mp;
int now = 1, tmp;
for(int i = 0; i < q; i++, now = 1ll * now * a % mod) {
mp[1ll * now * b % mod] = i;
}
tmp = now;
for(int i = 1; i <= q; i++, now = 1ll * now * tmp % mod)
if(mp.count(1ll * k * now % mod) != 0) return i * q - mp[1ll * k * now % mod];
return -1;
}
inline int gcd(int a, int b) {return a == 0 || b == 0 ? a | b : gcd(b, a % b);}
inline int exBSGS(int a, int b, int mod, int k = 1) {
if(b == k) return 0;
if(a == 0 && b == 0) return 1;
if(a == 0) return -1;
if(b == 0) {
int now = k, ans = 0;
int g = gcd(k, mod);
for(int tmp = mod / g; tmp != 1; tmp /= g) {
g = gcd(tmp, a);
if(g == 1) return -1;
}
while(now) now = 1ll * now * a % mod, ans++;
return ans;
}
int g = gcd(a, mod);
if(b % g) return -1;
if(g == 1) return BSGS(a, b, mod, k);
int ans = exBSGS(a % (mod / g), b / g, mod / g, 1ll * k * (a / g) % (mod / g));
return ~ans ? ans + 1 : ans;
}
int main() {
int a, b, mod;
while(1) {
scanf("%d%d%d", &a, &mod, &b);
if(a + b + mod == 0) return 0;
int ans = exBSGS(a % mod, b % mod, mod);
~ans ? printf("%d\n", ans) : puts("No Solution");
}
return 0;
}