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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pr[10] = {2, 3, 5, 7, 11, 13, 17, 19, 21, 23};
ll mod;
template<typename T>
inline void rd(T &x) {
x = 0; register int c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
}
inline ll quick_mul(ll base, ll index) {
ll ret = 0;
while (index) {
if (index & 1) ret = (ret + base) % mod;
base = (base + base) % mod;
index >>= 1;
}
return ret;
}
inline ll quick_power(ll base, ll index) {
ll ret = 1;
while (index) {
if (index & 1) ret = quick_mul(ret, base);
index >>= 1;
base = quick_mul(base, base);
}
return ret;
}
inline bool check(ll base, ll index, ll prime) {
while (!(index & 1)) {
ll tmp = quick_power(base, index);
if (tmp == 1ll) index >>= 1;
else if (tmp == (prime - 1ll)) return true;
else return false;
}
return true;
}
inline bool test(ll p) {
if (p == 2ll || p == 1ll) return true;
if (!(p & 1)) return false;
mod = p;
for (int i = 0; i < 10; ++i) {
if (p == pr[i]) return true;
if (!check(pr[i], p - 1, p)) return false;
}
return true;
}
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
ll get_fac(ll n, ll f) {
ll k = 2, x = rand() % n, y = x, g = 1;
for (int i = 1; g == 1; ++i) {
mod = n; x = (quick_mul(x, x) + f) % n;
g = gcd(ll(abs(x - y)), n);
if (i == k) y = x, k <<= 1;
}
return g;
}
ll P, Q, R, C, D, E, N;
void pollard_rho(ll x) {
if (x == 1) return;
if (test(x)) {
P = x; return;
}
ll G = x;
while (G == x) G = get_fac(x, rand() % (x - 1));
pollard_rho(G); pollard_rho(x / G);
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1; y = 0;
return a;
}
ll G = exgcd(b, a % b, x, y);
ll tmp = x;
x = y;
y = tmp - a / b * y;
return G;
}
int main() {
srand(19260817);
scanf("%lld%lld%lld", &E, &N, &C);
pollard_rho(N); Q = N / P; R = (P - 1) * (Q - 1);
ll xx, yy;
exgcd(E, R, xx, yy);
xx = (xx + R) % R;
mod = N; ll pwd = quick_power(C, xx);
printf("%lld %lld\n", xx, pwd);
return 0;
}
|
