【POJ1284】Primitive Roots 欧拉函数

时间:2023-12-30 17:17:26

题目描述:

【POJ1284】Primitive Roots 欧拉函数

题意:

  定义原根:对于一个整数x,0<x<p,是一个mod p下的原根,当且仅当集合{ (xi mod p) | 1 <= i <= p-1 } 等于{ 1, ..., p-1 }.给定p,询问有多少个满足定义的原根。

这里有一个定理:如果p有原根,则它恰有φ(φ(p))个不同的原根

  证明不懂就算了,我也不懂啊TAT

证明如下

  【POJ1284】Primitive Roots 欧拉函数

  题目中说m是奇素数,所以φ(p)=p-1,故ans=φ(p-1)。

代码如下:

 #include<cstdio>
#include<cstring>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std; int phi(int x)
{
int xx=x,ans=x;
for(int i=;i<=x;i++)
{
if(xx==) break;
if(xx%i!=) continue;
while(xx%i==) xx/=i;
ans=ans/i*(i-);
}
return ans;
} int main()
{
int a;
while(scanf("%d",&a)!=EOF)
{ int ans=phi(a-);
printf("%d\n",ans);
}
return ;
}

poj1284

2016-02-05 16:12:25