原根总结 (poj 1284)

原根小结 (poj 1284)

关于原根的一些知识点：

定义1：设，，使得成立的最小的，称为对模的阶，记为。

定理1：如果模有原根，那么它一共有个原根。

定理2：若，，，则。

定理3：如果为素数，那么素数一定存在原根，并且模的原根的个数为。

定理4：设是正整数，是整数，若模的阶等于，则称为模的一个原根。

   假设一个数对于模来说是原根，那么的结果两两不同,且有，那么可以称为是模的一个原根，归根到底就是当且仅当指数为的时候成立。（这里是素数）

定理5：模有原根的充要条件：，其中是奇素数。

 

求模素数原根的方法：对素因子分解，即是的标准分解式，若恒有

          

成立，则就是的原根。（对于合数求原根，只需把换成即可）

以上内容转自http://blog.csdn.net/acdreamers/article/details/8883285

求原根的代码：

/*求原根模板 */ #include<iostream> #include<cstdio> #include<vector> using namespace std; #define LL __int64 vector<ll> a; LL Ext_gcd(LL a,LL b,LL &x,LL &y){ if(b==0) { x=1, y=0; return a; } LL ret= Ext_gcd(b,a%b,y,x); y-= a/b*x; return ret; } LL Inv(LL a,int m){ //求逆元 LL d,x,y,t= (LL)m; d= Ext_gcd(a,t,x,y); if(d==1) return (x%t+t)%t; return -1; } LL a_b_MOD_c(LL a,LL b,LL mod){ LL ret = 1; a %= mod; while(b){ if(b & 1) ret = ret * a % mod; a = a * a % mod; b >>= 1; } return ret; } bool g_test(LL g,LL p){ for(LL i=0;i<a.size();++i) if(a_b_MOD_c(g,(p-1)/a[i],p)==1) return 0; return 1; } LL pri_root(LL p){ LL tmp=p-1; for(LL i=2;i<=tmp/i;++i) if(tmp%i==0){ a.push_back(i); while(tmp%i==0) tmp/=i; } if(tmp!=1) a.push_back(tmp); LL g=1; while(true){ if(g_test(g,p)) return g; ++g; } } int main(){ LL p=(479<<21)+1; cout<<p<<endl; LL g=pri_root(p); cout<<g<<endl; return 0; }

题目：

poj 1284
题意：
给出一个数n,求原根数目。
限制：
3 <= n < 65536; n为奇素数。
思路：
因为n是素数，所以模n的原根数=phi(phi(n))=phi(n-1)。
phi(i) 可以预处理出来。

/*poj 1284 题意： 给出一个数n,求原根数目。 限制： 3 <= n < 65536; n为奇素数。 思路： 因为n是素数，所以模n的原根数=phi(phi(n))=phi(n-1)。 phi(i) 可以预处理出来。 */ #include<iostream> #include<cstdio> using namespace std; const int N=100005; int pri[N],pcnt; int phi[N]; void getphi(){ phi[1]=1; for(int i=2;i<N;++i){ if(!phi[i]){ pri[pcnt++]=i; phi[i]=i-1; } for(int j=0;pri[j]*i<N && j<pcnt;++j){ if(i%pri[j]==0){ phi[i*pri[j]]=phi[i]*pri[j]; break; } else phi[i*pri[j]]=phi[i]*(pri[j]-1); } } } int main(){ int n; getphi(); while(scanf("%d",&n)!=EOF) printf("%d\n",phi[n-1]); return 0; }