参考例题: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; }