收藏
关注设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）
给出1个质数P，找出P最小的原根。
Input
输入1个质数P(3 <= P <= 10^9)
Output
输出P最小的原根。
Input示例
3
Output示例
2
原根的求法：
求原根目前的做法只能是从2开始枚举，然后暴力判断g^(P-1) = 1 (mod P)是否当且仅当指数为P-1的时候成立。而由于原根一般都不大，所以可以暴力得到。
具体在博客书签文件夹中...
#include<map>
#include<stack>
#include<queue>
#include<math.h>
#include<vector>
#include<string>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#define maxn 50005
#define inf 0x3f3f3f
#define ll long long
#define mod 1000000007
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int tot;
int prime[maxn];
int p[maxn];
int x[maxn];
void init(){tot=0;
for(int i=2;i<maxn;i++){
if(p[i]==0){prime[tot++]=i;
for(int j=2;j*i<maxn;j++)p[i*j]=1;
}
}
}
int f(int n){
int l=0;
for(int i=0;i<tot;i++){
if(n%prime[i]==0){x[l++]=prime[i];
while(n%prime[i]==0)n/=prime[i];
}
}
if(n!=1)x[l++]=n;
return l;
}
ll pow_mod(ll a,ll i,ll n){
if(i==0)return 1%n;
ll temp=pow_mod(a,i>>1,n);
temp=temp*temp%n;
if(i&1)temp=(ll)temp*a%n;
return temp;
}
int main(){
ll p;init();//cout<<tot<<endl;
while(cin>>p){
int n=f(p-1);//cout<<n<<endl;
for(ll i=2;i<p;i++){
int flag=0;
for(int j=0;j<n;j++){
if(pow_mod(i,(p-1)/x[j],p)==1){flag=1;break;}
//cout<<"11"<<endl;
}
if(flag==0){cout<<i<<endl;break;}
}
}
}版权声明：本文为lpeaceminusone原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。