题目：
设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
分析：
原根的板子题了。
原根知识详解： 点我萌萌哒
实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100000 + 131;
vector<LL> Primes;
bool Jug[maxn];
void Make_Primes() { /// 素数打表
Primes.clear();
memset(Jug, false, sizeof(Jug));
for(LL i = 2; i <= maxn; ++i)
{
if(Jug[i] == false) {
Primes.push_back(i);
for(LL j = i + i; j <= maxn; j += i)
Jug[j] = true;
}
}
}
vector<LL> Pi;
void GetPi(LL X) { /// 获得 x 的质因子
Pi.clear();
LL mx = Primes.size();
for(LL i = 0; i < mx && Primes[i] * Primes[i] <= X; ++i)
{
if(X % Primes[i] == 0) {
Pi.push_back(Primes[i]);
while(X % Primes[i] == 0) X /= Primes[i];
}
}
if(X > 1) Pi.push_back(X);
}
LL Pow(LL a, LL n, LL mod) { /// 快速幂取摸
LL ret = 1;
while(n) {
if(n & 1) ret = ret * a % mod;
a = a * a % mod;
n >>= 1;
}
return ret;
}
bool JugAx(LL tmp, LL P) { /// 判断 tmp 是否是 P 原根
for(int i = 0; i < Pi.size(); ++i)
{
if(Pow(tmp, (P-1)/ Pi[i], P) == 1)
return false;
}
return true;
}
int main() {
LL P;
Make_Primes();
while(cin >> P) {
GetPi(P-1);
for(LL i = 2; i <= P-1; ++i)
{
if(JugAx(i, P)) {
cout << i << endl;
break;
}
}
}
return 0;
}