poj1284——Primitive Roots（欧拉函数）-白红宇

poj1284——Primitive Roots（欧拉函数）

阅读量：2345 次

发布时间：2019-05-10

本文共 1207 字，大约阅读时间需要 4 分钟。

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.

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

Sample Output

看了会欧拉函数的内容，准备自己独立做一个题目，结果就碰上这种题，想了半天想不出来，百度了才知道还有个定理。。。我果然不适合搞数学

定理：如果p有原根，则它恰有φ(φ(p))个不同的原根，p为素数，当然φ(p)=p-1,因此就有φ(p-1)个原根

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #define INF 0x3f3f3f3f#define MAXN 100using namespace std;int euler(int n){ int ans=n,m=sqrt(n+0.5); for(int i=2;i<=m;++i) { if(n%i==0) { ans=ans/i*(i-1); while(n%i==0) n/=i; } } if(n!=1) ans=ans/n*(n-1); return ans;}int main(){ int p; while(~scanf("%d",&p)) { printf("%d\n",euler(p-1)); } return 0;}

转载地址：http://xicvb.baihongyu.com/

你可能感兴趣的文章