首页 > 其他 > 详细

POJ 1284 Primitive Roots (欧拉函数+原根)

时间:2019-02-12 00:26:56      阅读:209      评论:0      收藏:0      [点我收藏+]

<题目链接>

题目大意:

满足{ ( $x^{i}$ mod p) | 1 <=$i$ <= p-1 } == { 1, …, p-1 }的x称为模p的原根。给出p,求原根个数。

解题分析:

题意就是让我们求原根的个数,原根的个数为$φ(φ(p))$。

证明如下:    转载于 >>>

技术分享图片

因为本题p为素数,所以$φ(p)$为p-1。

 1 #include <cstdio>
 2 
 3 #define N int(1e5)
 4 int euler[N];
 5 void init(){
 6     euler[1]=1;
 7     for(int i=2;i<N;i++)
 8         euler[i]=i;
 9     for(int i=2;i<N;i++)
10         if(euler[i]==i)
11             for(int j=i;j<N;j+=i)
12                 euler[j]=euler[j]/i*(i-1);
13 }
14 
15 int main(){
16     init();
17     int p;while(~scanf("%d",&p)){
18         printf("%d\n",euler[p-1]);
19     }
20 }

 

 

2019-02-11

POJ 1284 Primitive Roots (欧拉函数+原根)

原文:https://www.cnblogs.com/00isok/p/10363656.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!