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
|
#include <cstdlib>
#include <map>
long long (long long a, long long b, long long mod) {
long long res = 0;
for (; b; b >>= 1, a = (a + a) % mod) if (b & 1) res = (res + a) % mod;
return res;
}
long long pow(long long a, long long n, long long mod) {
long long res = 1;
for (; n; n >>= 1, a = mul(a, a, mod)) if (n & 1) res = mul(res, a, mod);
return res;
}
long long pow(long long a, long long n) {
long long res = 1;
for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
return res;
}
long long gcd(long long a, long long b) {
return b ? gcd(b, a % b) : a;
}
bool isPrime(long long n) {
static int primes[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
long long s = 0, d = n - 1;
while (d % 2 == 0) d /= 2, s++;
if (s == 0) return n == 2;
for (int i = 0; i < 12 && primes[i] < n; i++) {
long long a = primes[i];
if (pow(a, d, n) != 1) {
bool flag = true;
for (int r = 0; r < s; r++)
if (flag && pow(a, d * (1 << r), n) == n - 1) flag = false;
if (flag) return false;
}
}
return true;
}
namespace PollardRho {
long long g(long long x, long long n, long long c) {
return (mul(x, x, n) + c) % n;
}
long long rho(long long n, long long c) {
long long x = rand() % n, y = x, d = 1;
for (long long i = 1, k = 2; d == 1; i++) {
x = g(x, n, c);
d = gcd(x > y ? x - y : y - x, n);
if (x == y) return n;
if (i == k) k <<= 1, y = x;
}
return d;
}
void find(long long n, long long c, std::map<long long, int> &res) {
if (n == 1) return;
if (isPrime(n)) {
res[n]++;
return;
}
long long p = n;
while (p == n) p = rho(p, c++);
find(p, c, res);
find(n / p, c, res);
}
std::map<long long, int> divide(long long n) {
std::map<long long, int> res;
find(n, 1, res);
return res;
}
}
long long phi(long long n) {
std::map<long long, int> fact = PollardRho::divide(n);
long long res = 1;
for (std::map<long long, int>::iterator it = fact.begin(); it != fact.end(); it++) {
res *= pow(it->first, it->second - 1) * (it->first - 1);
}
return res;
}
int main() {
srand(23333);
long long n;
scanf("%lldn", &n);
printf("%lldn", phi(n));
return 0;
}
|
近期评论