<题目链接>
题目大意：
满足{ ( $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