首页 > 代码库 > POJ1284_Primitive Roots【欧拉函数】
POJ1284_Primitive Roots【欧拉函数】
Primitive Roots
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 3032Accepted: 1734
DescriptionWe 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
23
31
79
Sample Output
10
8
24
Source
贾怡@pku
题目大意:p是奇素数,如果{x^i % p | 1 <= i <= p - 1} = {1,2,...,p-1},则称x是p的原根。
给出一个p,问它的原根有多少个。
思路:
{x^i% p | 1 <= i <= p - 1} = {1,2,...,p-1} 等价于
{x^i%(p-1) | 1 <= i <= p - 1} = {0,1,2,...,p-2},
即{x^1,x^2,x^3,…,x^(p-1)}为p的完全剩余系等价于
若x与p-1互质(gcd(x, p-1) = 1),则{x^0,x^1,x^2,…,x^(p-2)}为(p-1)的完全剩余系
下边证明:
如果x^i != x^j (mod p-1),那么 x*x^i != x*x^j (mod p-1),则gcd(x, p-1) != 0,与上边相悖。
则x^i = x^j(mod p-1)。
根据费马定理和欧拉定理知:i = φ(p-1)。
关于欧拉函数、费马定理和欧拉定理参考另一篇欧拉函数的题解:
http://blog.csdn.net/lianai911/article/details/40114675
参考博文:http://www.cnblogs.com/lnever/p/3969117.html
顺便膜拜推理出来的大神
#include <stdio.h> #include <math.h> int Euler(int n) { int i, ret = n; for(i = 2; i <= sqrt(1.0*n); i++) { if(n % i == 0) { n /= i; ret = ret - ret/i; } while(n % i == 0) n /= i; } if(n > 1) { ret = ret - ret/n; } return ret; } int main() { int p; while(~scanf("%d",&p)) { printf("%d\n",Euler(p-1)); //如果p为素数,Euler(Euler(p)) == Euler(p-1) } return 0; }
POJ1284_Primitive Roots【欧拉函数】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。