「POJ1284」Primitive Roots
Description
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.
Write a program which given any odd prime 3 <= p < 65536 outputs the number of primitive roots modulo p.
Input
Each line of the input contains an odd prime numbers p. Input is terminated by the end-of-file seperator.
Output
For each p, print a single number that gives the number of primitive roots in a single line.
Sample Input
|
1 2 3 |
23 31 79 |
Sample Output
|
1 2 3 |
10 8 24 |
Source
题意是求奇素数的原根个数
所有的奇素数有原根
若o有原根，则其有φ(φ(n))个模p不同余的原根
若p是素数，则其有φ(p-1)个模p不同余的原根（由2式显然可得）
证明2式好麻烦，先略
结论：p是素数，b = a0^t(mod p)，是一个原根的充要条件是t与p-1互质，所有的这些t的总个数就是φ(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 31 32 33 34 35 36 37 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define N 100000 #define ll long long using namespace std; int n,cnt; int pri[100005],phi[100005]; bool mark[100005]; void getphi() { for(int i=2;i<=N;i++) { if(!mark[i]){pri[++cnt]=i;phi[i]=i-1;} for(int j=1;pri[j]*i<=N&&j<=cnt;j++) { mark[i*pri[j]]=1; if(i%pri[j]==0) { phi[i*pri[j]]=phi[i]*pri[j]; break; } else phi[i*pri[j]]=phi[i]*(pri[j]-1); } } } int main() { getphi(); while(scanf("%d",&n)!=EOF) printf("%d\n",phi[n-1]); return 0; } |
Subscribe
计数器 9855330
OI 课件=>
OI 课件=>