[POJ1284] 原根

    xiaoxiao2021-03-26  35


    题目描述

    一个整数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; }
    转载请注明原文地址: https://ju.6miu.com/read-600019.html

    最新回复(0)