本文共 529 字，大约阅读时间需要 1 分钟。

题目链接：

题意：求解p的原根的个数，此题p是素数，φ(p) = p - 1;

题解：定理：设 p > 1是整数，如果模p存在一个原根g，则模p有φ(φ(p))个不同的原根

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int euler(int x){    int res = x;    for(int i = 2;i <= sqrt(x);i++)    {        if(x%i==0)        {            while(x%i==0) x/=i;            res = res/i*(i-1);        }    }    if(x > 1) res = res / x * ( x - 1);    return res;}int main(){    int n;    while(~scanf("%d",&n))    {        printf("%d\n",euler(n-1));    }}
       
      
     
    
   

转载地址：http://gfsgi.baihongyu.com/