【题意】给定p，求p的原根g。3<=p<=10^9。
【算法】数学
【题解】p-1= p1^a1 * p2^a2 * pk^ak，g是p的原根当且仅当对于所有的pi满足g^[ (p-1)/pi ] ≠ 1 (%p)
g一般很小，暴力求。
#include<cstdio>
#include<cmath>
using namespace std;
int p,b[],tot;
int power(int x,int k){
int ans=;
while(k){
if(k&)ans=1ll*ans*x%p;
x=1ll*x*x%p;
k>>=;
}
return ans;
}
int main(){
scanf("%d",&p);
int sq=(int)(sqrt(p)+0.5),P=p-;
for(int i=;i<=sq;i++)if(P!=){
if(P%i==){
b[++tot]=i;
while(P%i==)P/=i;
}
}
if(P!=)b[++tot]=P;
for(int i=;i<=p;i++){
bool ok=;
for(int j=;j<=tot;j++){
if(power(i,(p-)/b[j])==){ok=;break;}
}
if(ok){printf("%d",i);return ;}
}
return ;
}