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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include <bits/stdc++.h>
#define ll long long
#define int ll
std::unordered_map<int, int> h;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int mul(int a, int b, int p)
{
ll ret = 0;
while(b)
{
if (b & 1)
ret = (ret + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ret;
}
void exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return;
}
exgcd(b, a % b, x, y);
int t = x;
x = y, y = t - (a / b) * y;
}
int solve1(int a, int b, int p)
{
ll ret = 1;
while (b)
{
if (b & 1)
ret = mul(ret, a, p);
a = mul(a, a, p);
b >>= 1;
}
return ret;
}
int solve2(int a, int b, int p)
{
int x = 0, y = 0;
int g = gcd(a, p);
if (b % g)
return -1;
exgcd(a, p, x, y);
x *= (b / g);
x = (x % p + p) % p;
return x;
}
int solve3(int a, int b, int p)
{
if (b == 1)
return 0;
int cnt = 0, d, k = 1;
while ((d = gcd(a, p)) ^ 1)
{
if (b % d)
return -1;
b /= d, p /= d, ++cnt;
k = mul(k, a / d, p);
if (k == b)
return cnt;
}
int t = sqrt(p) + 1, tmp = 1;
h.clear();
for (int i = 0; i < t; i++)
{
h[mul(tmp, b, p)] = i;
tmp = mul(tmp, a, p);
}
k = mul(k, tmp, p);
for (int i = 1; i <= t; i++)
{
if (h.find(k) != h.end())
return i * t - h[k] + cnt;
k = mul(k, tmp, p);
}
return -1;
}
signed main()
{
int T, op;
scanf("%lld%lld", &T, &op);
while (T--)
{
int a, b, p;
scanf("%lld%lld%lld", &a, &b, &p);
if (op == 1)
printf("%lld\n", solve1(a, b, p));
if (op == 2)
{
b %= p;
int ans = solve2(a, b, p);
if (ans == -1)
printf("Orz, I cannot find x!\n");
else
printf("%lld\n", ans);
}
if (op == 3)
{
b %= p;
int ans = solve3(a, b, p);
if (ans == -1)
printf("Orz, I cannot find x!\n");
else
printf("%lld\n", ans);
}
}
return 0;
}
|