【模板库】原根

参考例题：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135
时间复杂度：能跑1e9
相关限制：此份代码仅能求素数的原根，合数的原根还需要求一个欧拉函数
参考代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline int Get_Primitive_Root(int w) {
    vector<int> pri;
    for (int i=2,lim=ceil(sqrt(w)),cur=w-1;i<lim;i++) {
        if (cur % i == 0) {
            pri.push_back(i);
            while (cur % i == 0) 
                cur /= i;
        }
        if (cur > 1 && i == lim - 1) 
            pri.push_back(cur);
    }
    static auto Pow = [](int w, int t, int MOD) {
        int ret = 1;
        for (;t;t>>=1,w=(LL)w*w%MOD) 
            if (t & 1) ret = (LL)ret * w % MOD;
        return ret;
    };
    if (!pri.size()) return 2;
    for (int i=2;i<=w;i++) {
        for (int j=pri.size()-1;~j;j--) {
            if (Pow(i,w/pri[j],w) == 1) break;
            if (!j) return i;
        }
    }
}
 
int main() {
    printf("%d\n",Get_Primitive_Root(read())); 
    return 0;
}