相关链接
题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135
神犇题解Ⅰ:http://blog.csdn.net/u013486414/article/details/47781857
神犇题解Ⅱ:http://littleclown.github.io/2016/05/16/Study-Math-Mod-Root/
解题报告
就是一个求原根的模板题
相关的证明在这里:http://blog.csdn.net/zhang20072844/article/details/11541133
值得注意的是,验证原根现在可以做到$O(logn)$了
不过找原根的复杂度似乎没有比较紧的上界?
wiki上给出了这样一个上界:$O(n^{0.499})$,但$n$要大于$e^{e^{24}}$,所以对于OI题没什么用QwQ
不过一般来讲,质数的原根都比较小,就直接枚举加验证啦!
Code
#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; }
楼下是疯子。哈哈
As I website owner I think the written content here is real good, thanks for your efforts.
great put up, very informative. I wonder why the opposite specialists of this sector don’t notice this. You must continue your writing. I’m confident, you’ve a huge readers’ base already!