题解：P11961 [GESP202503 五级] 原根判断

· · 题解

第二次场切蓝题，发题解纪念一下

前置知识：费马小定理，快速幂，O(\sqrt{x}) 的求 x 的因数

分析：

题目告诉我们原根的定义：

题目保证 p 是质数，1<g<p。根据费马小定理，g^{p - 1}\bmod{p}=1 总是成立的，题目也保证 1<g<p，我们只要判断第三条就行了。

打表可以观察到对于任意 1\leq i<p - 1 均有 g^i\bmod{p}\neq0。这也很好理解：如果出现 0 的话，就有 g^{p - 1}\bmod{p}=0，不符合费马小定理了。

如果 g 是 p 的原根，则对于 1\leq i\leq p - 1 ，g^i\bmod{p} 是 1\sim p 的排列，如果不是 p 的原根，则对于 1\leq i\leq p - 1 ，g^i\bmod{p} 存在循环节，且循环节的长度是 p - 1 的因数，循环节以 1 结尾（请你思考这是为什么）。

接下来就简单了，枚举 p - 1 的因数（假设为 x）（不包含 p - 1 自己），判断 g^{x}\bmod{p} 是否为 1，是则 g 不是 p 的原根。

时间复杂度：

求 p - 1 的因数时间复杂度大致为 O(\sqrt{p}) ，每次判断的时间复杂度为 O(\log p)，总时间复杂度为 O(T\sqrt{p}\log p)。

code

仅供对拍。

//Do not hack it
#include <bits/stdc++.h>
#define endl cerr<<"------------------I Love Sqrt Decomposition------------------\n";
#define int long long
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#endif

#ifndef __linux__
#define gc getchar
#define pc putchar
#endif

#define ds(x) (x=='\r'||x=='\n'||x==' ')
#define MAX 20
namespace G {
    template<typename T>inline void r(T& a) { a = 0; char ch = gc(); bool ok = 0; for (; ch < '0' || ch>'9';)ok ^= (ch == '-'), ch = gc(); for (; ch >= '0' && ch <= '9';)a = (a << 1) + (a << 3) + (ch ^ 48), ch = gc(); if (ok)a = -a; }
    template<typename T>inline void w(T a) { if (a == 0) { pc('0'); return; }static char ch[MAX]; int till = 0; if (a < 0) { pc('-'); for (; a;)ch[till++] = -(a % 10), a /= 10; } else for (; a;)ch[till++] = a % 10, a /= 10; for (; till;)pc(ch[--till] ^ 48); }
    struct Srr {
        inline Srr operator>>(int& a) { r(a); return{}; }
        inline Srr operator>>(char& ch) { ch = gc(); for (; ds(ch);)ch = gc(); return{}; }
        inline Srr operator>>(string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; !(ds(ch) || ch == EOF);) { s.push_back(ch); ch = gc(); }return{}; }
        template<typename T>inline Srr operator<<(T& a) { r(a); return{}; }
        inline void is(int n, string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; n--;) { s.push_back(ch); ch = gc(); } }
    }in;
    struct Sww {
        inline Sww operator<<(const int a) { w(a); return{}; }
        inline Sww operator<<(const char ch) { pc(ch); return{}; }
        inline Sww operator<<(const string s) { for (int i = 0; i < s.size(); i++)pc(s[i]); return{}; }
        template<typename T>inline Sww operator>>(const T a) { w(a); return{}; }
    }out;
    namespace __STL {
        const bool __is_P[] = { 0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1 };
        inline bool IP(const int a) { if (a <= 29)return __is_P[a]; if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0)return 0; for (int i = 6;; i += 6) { if (((i + 1) * (i + 1)) > a)return 1; if (a % (i + 1) == 0)return 0; if (((i + 5) * (i + 5)) > a)return 1; if (a % (i + 5) == 0)return 0; } }
        inline int power(int a, int b, const int mod = -1) { int ans = 1; if (mod == -1) { for (; b;) { if (b & 1)ans *= a; b >>= 1; a *= a; }return ans; }for (; b;) { if (b & 1)ans = ans * a % mod; b >>= 1; a = a * a % mod; }return ans; }
    }
}
using G::in; using G::out;
#undef ds
using namespace G::__STL;
#define eout cerr

signed main() {
    int T;
    in>>T;
    for(;T--;){
        int x,p;
        in>>x>>p;
        bool ok=1;
        for(int i=2;i*i<=p-1;i++){
            if((p-1)%i){
                continue;
            }
            if(power(x,i,p)==1||power(x,(p-1)/i,p)==1){
                ok=0;
                break;
            }
        }
        out<<(ok?"Yes":"No")<<'\n';
    }
    return 0;
}

提交记录

update:

2025/3/28 增加图片cdn.luogu.com.cn/upload/image_hosting/kob6h9zc.png