poj 1284 Primitive Roots（原根+欧拉函数）-白红宇

poj 1284 Primitive Roots（原根+欧拉函数）

阅读量：6938 次

发布时间：2019-06-27

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

题意：对于奇素数p,假设存在一个x(1<x<p),(x^i)%p两两不同(0<i<p)，且解集等于{1,2....,p-1}。

称x是p的一个原根。

输入p问p的原根有多少个。

直接枚举的，TLE了。

看到discuss里面说是求原根。答案直接是phi[p-1]。百度百科上直接就给出答案了。m有原根的充要条件是m= 1,2,4,p,2p,p^n,当中p是奇素数，n是随意正整数。它所含原根的个数是phi[phi[m]],由于phi[m]=m-1,所以答案是phi[m-1]。

#include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define LL long long#define _LL __int64#define eps 1e-12#define PI acos(-1.0)using namespace std;const int maxn = 65540;int flag[maxn];int prime[maxn];int phi[maxn];void init(){ memset(flag,0,sizeof(flag)); phi[1] = 1; prime[0] = 0; for(int i = 2; i < maxn; i++) { if(flag[i] == 0) { phi[i] = i-1; prime[++prime[0]] = i; } for(int j = 1; j <= prime[0]&&prime[j]*i

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

你可能感兴趣的文章