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
| #include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 100000;
const double EPS = 1e-5;
namespace Hash {
const int MOD = 99971;
int head[MAXN], nxt[MAXN], val[MAXN], data[MAXN], T;
inline void init() {
T = 0;
memset(head, 0, sizeof(head));
}
inline void insert(int w, int d) {
nxt[++T] = head[w % MOD];
val[T] = w; data[T] = d;
head[w % MOD] = T;
}
inline int find(int w) {
for (int i = head[w % MOD]; i; i = nxt[i])
if (val[i] == w) return data[i];
return -1;
}
};
inline int read() {
char c = getchar(); int ret = 0, f = 1;
while (c < '0' || c > '9') {if (c == '-')f = -1; c = getchar();}
while (c <= '9' && c >= '0') {ret = ret * 10 + c - '0'; c = getchar();}
return ret * f;
}
inline int quick_pow(int a, int b, int c) {
int ret = 1; while (b) {
if (b & 1) ret = ((LL)ret * a) % c;
a = (LL)a * a % c; b >>= 1;
} return ret;
}
int GCD(int a, int b) {return b ? GCD(b, a % b) : a;}
void EX_GCD(int a, int b, int &x, int &y) {
if (!b) x = 1, y = 0;
else EX_GCD(b, a % b, y, x), y -= a / b * x;
}
inline int EX_GCD(int a, int b, int c) {
int ret, tmp, gcd = GCD(a, b);
if (c % gcd) return -1;
else {
EX_GCD(a / gcd, b / gcd, ret, tmp);
ret = (((LL)c / gcd * ret) % b + b) % b;
return ret;
}
}
inline void solve(int a, int b, int c) {
int ret = EX_GCD(a, c, b);
if (~ret) printf("%d\n", ret);
else printf("Orz, I cannot find x!\n");
}
inline void BSGS(int a, int b, int c) {
Hash::init(); a %= c; b %= c;
if (!a && b > 1) {printf("Orz, I cannot find x!\n"); return;}
int lim = int(ceil(sqrt(c)) + EPS);
for (int i = 0, w = 1; i <= lim; i++) {
if (w == b) {printf("%d\n", i); return;}
Hash::insert(w, i);
w = ((LL)w * a) % c;
}
int w_ori = quick_pow(a, lim, c), rev_ori = quick_pow(w_ori, c - 2, c);
for (int i = 1, w = w_ori, rev = rev_ori; i <= lim; i++) {
int tmp = Hash::find(((LL)rev * b) % c);
if (tmp > -1) {printf("%d\n", i * lim + tmp); return;}
w = ((LL)w * w_ori) % c;
rev = ((LL)rev * rev_ori) % c;
}
printf("Orz, I cannot find x!\n");
}
int main() {
int T = read(), ty = read(); while (T--) {
int a = read(), b = read(), c = read();
if (ty == 1) printf("%d\n", quick_pow(a, b, c));
else if (ty == 2) solve(a, b, c);
else BSGS(a, b, c);
}
return 0;
}
|
