题目描述:
题意:
定义原根:对于一个整数x,0<x<p,是一个mod p下的原根,当且仅当集合{ (xi mod p) | 1 <= i <= p-1 } 等于{ 1, ..., p-1 }.给定p,询问有多少个满足定义的原根。
这里有一个定理:如果p有原根,则它恰有φ(φ(p))个不同的原根
证明不懂就算了,我也不懂啊TAT
证明如下
题目中说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