建议与上一篇欧拉函数介绍结合食用。
知识点:
1.阶：a和模m互质，使a^d≡1(mod m)成立的最小正整数d称为a对模m的阶(指数)
例如：
2^2≡1(mod3),2对模3的阶为2;
2^3≡1(mod7),2对模7的阶为3;
2.欧拉函数φ(m)：在[1,m)的区间内与m互质的数的个数。可见前一篇blog
3.设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。
求模素数p的原根a的方法：
对质数 p, φ(p) = p-1, 这题就是要找最小的a使得 a^(p-1)%p = 1 成立（根据费马小定理，该式一定成立，且a可取大于 1 的任意整数），所以只需要验证没有比 p-1 小的数 k 令 a^k%p = 1 。
而 k 不需要全部枚举 ，只需枚举 p-1 除去1和它本身的质因子即可。（如果x为p-1的质因子，且a^x%p = 1,那么x的倍数nx显然也满足a^nx%p = 1 ，所以没必要考虑了。反之同理。）
所以重点就到回到了找质因子上，1e9，还是筛。
参考了很多dalao的博客，但链接没记下来，不好意思。
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 50000
using namespace std;
typedef long long ll;
int prime [maxn];//存素数
int ppri [maxn];//存p-1的质因子
void getprime(){//打表
int cnt = ;
memset(prime,,sizeof(prime));
for(int i=;i<maxn;i++){
if(!prime[i]) prime[++cnt]=i;//如果没被标记过，就是质数
for(int j=i;j<maxn;j+=i) prime[j] = ;//此质数的倍数都标记为1
}
}
ll pow(ll x,ll n,ll mod){//快速幂
ll res=;
while(n>){
if(n%) res=res*x%mod;
x=x*x%mod;
n/=;
}
return res;
} 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];
}
return cnt;
} int main(){
int p,a,t,flag,cnt;
cin>>p;
getprime();
cnt=divide(p-);//p-1 的质因子个数
for(a = ; a <= p - ; ++a){//a 从 2 到 p-1 枚举
flag=;
for(int i=; i <= cnt; ++i){
t = (p - ) / ppri[i];
if(pow(a, t, p)==){
flag=;
break;
}
}
if(flag){
cout<<a<<endl;
break;
}
}
return ;
}