原根性质及求原根

原根：如果a模m的阶等于φ(m)，即是最小的满足的x，则a是m的一个原根。

由质数的欧拉函数值得到，模质数阶为p-1时为其原根，即费马小定理得为最小的x。

而在模质数下，原根mod质数的取值两两不同，为0,1,2……质数-1。

这个性质让原根有了用武之地。在快速数论变换中替换了单位根。

由此我们可以定义离散对数。将乘法转为加法，这是容易爆long long时的经典操作。

原根求法：（update10.27:FSYolanda指正p-1仅针对质数，真实为）

对于分解质因数。对于任何一个质因子，如果满足

则g不是原根。都不满足那就是。本质复杂度不到，实际上只要求到一个就可以直接return。而且一般来说，题目给的原根都很小。

这个做法的正确性就是因为对于p，原根模p的阶是，所以不能有比还小的满足模p=1的了。

如果p太大，对于快速求,使用通式,因为需要得到质因数，所以使用pollard-rho。这个东西的复健看这里

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
int modd;
int fac[233],cnt=0;
int ksm(int a,int b){
	int sum=1;
	while(b){
		if(b&1)sum=sum*a%modd;a=a*a%modd;b>>=1;
	}return sum;
	
}
void getg(){
	int mod=modd-1;
	for(int i=2;i*i<=mod;++i){
		if(mod%i==0){
			fac[++cnt]=i;
			while(mod%i==0)mod/=i; 
		}
	}if(mod>1)fac[++cnt]=mod;
	for(int i=2;;i++){
		int flag=0;
		for(int j=1;j<=cnt;j++){
			if(ksm(i,(modd-1)/fac[j])==1){
				
				flag=1;break;
			}
		}if(!flag){
			cout<<i;return;
		}
	}
}
signed main(){
	modd=in;
	getg();
	return 0;
}