题目链接:51nod 1135 原根
设 m 是正整数，a是整数，若a模m的阶等于φ(m)，则称 a 为 模m的一个原根。（其中φ(m)表示m的欧拉函数）
阶：gcd(a,m)=1,使得
成立的最小的 r，称为 a 对 模m 的 阶。
φ(m)：在[1,m)的区间内与m互质的数的个数。
求模素数p的原根a的方法：
因为p为素数，所以φ(p)=p-1, 这题就是要找最小的a使得 a^(p-1)%p = 1 成立（根据费马小定理，该式一定成立），
先求p-1所有不同的 质因子 p1,p2…pm,
对任何整数 a ∈[1,p-1]， 检验 a 是否为 p 的原根，
检验方法：a^((p-1)/p1),a^((p-1)/p2),...a^((p-1)/pm) 中是否存在一个 模p 等于 1 ，
存在的话 a 就不是 模p 的一个原根（即p-1就不是a对模p的阶），否则a就为原根。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long ll;
const int N = ;
int prime[N];//prime[0] 存的是素数的个数
int ppri[N];//p-1的质因子
void getPrime(){
CLR(prime , );
for(int i = ;i < N; i++){
if(!prime[i])
prime[ ++prime[] ] = i;
for(int j = ; j <= prime[] && prime[j] <= N / i; j++){
prime[ prime[j] * i ] = ;
if(i % prime[j] == ) break;
}
}
}
ll pow_m(ll a, ll n, ll m){
ll t = a % m;
ll r = ;
while(n > ){
if(n & )
r = r * t % m;
t = t * t % m;
n >>= ;
}
return r;
}
int divide(int n){//分解合数n的质因子
int cnt = ;
for(int i = ; prime[i] * prime[i] <= n; ++i){
if(n % prime[i] == ){
ppri[++cnt] = prime[i];
while(n % prime[i] == ){
n /= prime[i];
}
}
}
if(n > ) ppri[++cnt] = n;
return cnt;
}
int main(){
int p, i, a, t, f;
getPrime();
scanf("%d", &p);
int cnt = divide(p - );//p-1 的 质因子个数
for(a = ; a <= p - ; ++a){//原根从 2 到 p-1 枚举
f = ;
for(i = ; i <= cnt; ++i){
t = (p - ) / ppri[i];
if( pow_m(a, t, p) == ){
//存在a^((p-1)/ppr[i]) mod p = 1， 则 a 不是质数p的原根
f = ; break;
}
}
if(f){
printf("%d\n",a);
break;
}
}
return ;
}