专栏文章

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

ffkxr
P11961题解参与者 24已保存评论 26

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
26 条
当前快照
1 份
快照标识符
@miptpq3k
此快照首次捕获于
2025/12/03 17:47
3 个月前
此快照最后确认于
2025/12/03 17:47
3 个月前
查看原文
第二次场切蓝题，发题解纪念一下
前置知识：费马小定理，快速幂，O(x)O(\sqrt{x}) 的求 xx 的因数

分析：

题目告诉我们原根的定义：
  • 1<g<p1<g<p；
  • gp−1 mod p=1g^{p - 1}\bmod{p}=1；
  • 对于任意 1≤i<p−11\leq i<p - 1 均有 gi mod p≠1g^i\bmod{p}\neq1。
题目保证 pp 是质数，1<g<p1<g<p。根据费马小定理，gp−1 mod p=1g^{p - 1}\bmod{p}=1 总是成立的，题目也保证 1<g<p1<g<p，我们只要判断第三条就行了。
打表可以观察到对于任意 1≤i<p−11\leq i<p - 1 均有 gi mod p≠0g^i\bmod{p}\neq0。这也很好理解：如果出现 00 的话，就有 gp−1 mod p=0g^{p - 1}\bmod{p}=0，不符合费马小定理了。
如果 gg 是 pp 的原根，则对于 1≤i≤p−11\leq i\leq p - 1 ，gi mod pg^i\bmod{p} 是 1∼p1\sim p 的排列，如果不是 pp 的原根，则对于 1≤i≤p−11\leq i\leq p - 1 ，gi mod pg^i\bmod{p} 存在循环节，且循环节的长度是 p−1p - 1 的因数，循环节以 11 结尾（请你思考这是为什么）。
接下来就简单了，枚举 p−1p - 1 的因数（假设为 xx）（不包含 p−1p - 1 自己），判断 gx mod pg^{x}\bmod{p} 是否为 11，是则 gg 不是 pp 的原根。

时间复杂度：

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

code

仅供对拍。
CPP
//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:

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

评论

共 26 条评论，欢迎与作者交流。

正在加载评论...