淄博网站建设至信网络亚马逊提升关键词排名的方法
题目链接 ： 传送门
题目大意： 求一个质数的原根个数。
先普及一下原根的定义：
设m是正整数，a是整数，若a模m的阶等于euler(m)，则称a为模m的一个原根。
eg: m=7，euler（7） = 6（1，2，3，4，5，6）
则：
- 1 1^(n)mod7=1! = 6
- 2 2^(n)mod7={2 4 1}!=6
- 3 3^(n)mod7={3,2,6,4,5,1}==6 故3是模7的原根
- 4 4^(n)mod7={4,2,1}！=6
- 5 5^(n)mod7={5,4,6,2,3,1}==6 故5是模7的原根
- 6 6^(n)mod7={6,1}！=6
故7的原根有两个。
也可以这样来想： a^(p-1)mod(p)=1，(p-1)为最小的使得 a^(x) mod (1) = 1 满足的x。
判断方法：判断g^(m-1) = 1 (mod m)是否当且当指数为m-1的时候成立
模m有原根的充要条件是m= 1,2,4,p,2p,p^n，其中p是奇质数，n是任意正整数。
有一个规律，任何一个质数的原根个数都是等于euler(n-1)的值。
则本题的代码如下：
#include<iostream>
#include<stdio.h>
using namespace std;
//直接求解欧拉函数，返回euler(n)
int euler(int n){int res=n,a=n;for(int i=2;i*i<=a;i++){if(a%i==0){res=res/i*(i-1); //先进行除法是为了防止中间数据的溢出while(a%i==0) a/=i;}}if(a>1) res=res/a*(a-1);return res;
}int main ()
{int num;while(~scanf("%d",&num)){printf("%d\n",euler(num-1));}
}