## 【模板库】原根

#include<bits/stdc++.h>
#define LL long long
using namespace std;

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() {
return 0;
}


## 【51NOD 1135】原根

### 解题报告

wiki上给出了这样一个上界：$O(n^{0.499})$，但$n$要大于$e^{e^{24}}$，所以对于OI题没什么用QwQ

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

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() {