【模板库】原根

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

【51NOD 1135】原根

相关链接

题目传送门: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;
}