---

题目描述

一个整数x(0 < x < p)是奇素数p的原根，当且仅当集合{(xi mod p)|1<=i<=p-1}与集合{1,…,p-1}是相同的。例如，3的连续的次幂对7取模的结果是3,2,6,4,5,1，所有3是7的原根。 　　给出一个奇素数p(3<=p<65536)，编程求出p的原根的个数。

---

输入格式

输入包括多行，每行一个奇素数p。

---

输出格式

对应每组输入，输出占一行为原根的个数。

---

样例数据

样例输入

23 31 79

样例输出

10 8 24

---

题目分析

x的原根就是φ(φ(x))，因为是奇素数，故φ(x)=x-1，原根就是φ(x-1)

---

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const long long Get_Int() { long long num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } int Phi[100005]; void Euler_Table(int n) { //筛选法求欧拉函数 memset(Phi,0,sizeof(Phi)); Phi[1]=1; for(int i=2; i<=n; i++) if(Phi[i]==0) for(int j=i; j<=n; j+=i) { if(Phi[j]==0)Phi[j]=j; Phi[j]=Phi[j]/i*(i-1); } } int n; int main() { Euler_Table(100000); while(cin>>n)printf("%d\n",Phi[n-1]); return 0; }

---