POJ 1284 Primitive Roots (欧拉函数+原根)

题目大意：

满足{ ( $x^{i}$ mod p) | 1 <=$i$ <= p-1 } == { 1, …, p-1 }的x称为模p的原根。给出p，求原根个数。

解题分析：

题意就是让我们求原根的个数，原根的个数为$φ(φ(p))$。

证明如下：转载于 >>>

因为本题p为素数，所以$φ(p)$为p-1。

 #include <cstdio>

 #define N int(1e5)

 int euler[N];

 void init(){

     euler[]=;

     for(int i=;i<N;i++)

         euler[i]=i;

     for(int i=;i<N;i++)

         if(euler[i]==i)

             for(int j=i;j<N;j+=i)

                 euler[j]=euler[j]/i*(i-);

 }

 int main(){

     init();

     int p;while(~scanf("%d",&p)){

         printf("%d\n",euler[p-]);

     }

 }

2019-02-11

巴特西

POJ 1284 Primitive Roots (欧拉函数+原根)

最新文章

热门文章