「POJ-1284」Primitive Roots-原根+欧拉函数

We say that integer x, 0 < x < p, is a primitive root modulo odd prime p if and only if the set { (xi mod p) | 1 <= i <= p-1 } is equal to { 1, …, p-1 }. For example, the consecutive powers of 3 modulo 7 are 3, 2, 6, 4, 5, 1, and thus 3 is a primitive root modulo 7.
Write a program which given any odd prime 3 <= p < 65536 outputs the number of primitive roots modulo p.

链接

POJ-1284

题解

结论题,一个质数 $p$ 的原根为 $phi(p - 1)$,然后就没有了…

证明?我也不会…

代码

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cctype>
#include <climits>
#include <ctime>
#include <cstdlib>
const int MAXN = 70000;
int phi[MAXN + 10], prime[MAXN + 10], mu[MAXN + 10], tot;
bool vis[MAXN + 10];
inline void init() {
mu[1] = phi[1] = 1;
for (register int i = 2; i <= MAXN; i++) {
if (!vis[i]) prime[++tot] = i, phi[i] = i - 1, mu[i] = -1;
for (register int j = 1; j <= tot && i * prime[j] <= MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j], mu[i * prime[j]] = 0;
break;
} else phi[i * prime[j]] = phi[i] * (prime[j] - 1), mu[i * prime[j]] = -mu[i];
}
}
}
int main() {
init();
register int t;
std::ios::sync_with_stdio(0), std::cin.tie(0);
while (std::cin >> t) std::cout << phi[t - 1] << "\n";
return 0;
}
# Math

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×