首页 > 代码库 > poj 1284 Primitive Roots 【原根】【数论】

poj 1284 Primitive Roots 【原根】【数论】

2024-07-15 17:33:05   223人阅读

题目链接 ： 传送门

题目大意： 求一个质数的原根个数。

先普及一下原根的定义：

设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的原根有两个。
判断方法：判断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));
  }
}



联系
我们