专栏文章

题解： 原根判断

ccjy0329
P11961题解参与者 164已保存评论 205

文章操作

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

当前评论
203 条
当前快照
1 份
快照标识符
@miptrf0g
此快照首次捕获于
2025/12/03 17:48
3 个月前
此快照最后确认于
2025/12/03 17:48
3 个月前
查看原文

题目背景

截止 2025 年 3 月，本题可能超出了 GESP 考纲范围。在该时间点下，原根是 NOI 大纲 8 级知识点（NOI 级），且不属于 GESP 大纲内容。需要注意，GESP 大纲和 NOI 大纲是不同的大纲。 若对题目中原根这一概念感兴趣，可以学习完成 【模板】原根。
~本萌新只是个五年级刚学oi的蒟蒻，本想考个五级，结果qwq……我的两道编程题都ac了 \(^v^)/~

题意：

对于质数 pp 而言，pp 的原根 gg 是满足以下条件的正整数：
  • 1<g<p1<g<p；
  • gp−1 mod p=1g^{p-1}\bmod{p}=1；
  • 对于任意 1≤i<p−11\le i<p-1 均有 gi mod p≠1g^i\bmod{p}\neq1。
其中 a mod pa\bmod{p} 表示 aa 除以 pp 的余数。
给出一个整数 aa 和质数 pp，判断 aa 是不是 pp 的原根。
保证 1≤T≤201\le T\le20，3≤p≤1093\le p\le10^9，1<a<p1<a<p，pp 为质数。

思路：

要想让 aa 是 pp 的原根，必须满足三个条件：
  1. 1<a<p1<a<p ，这条已被约束条件满足了，无需判断；
  2. ap−1 mod p=1a^{p-1}\bmod{p}=1，写个快速幂，O(log⁡n)O(\log n) 就能判断；
  3. 对于任意 1≤i<p−11\le i<p-1 均有 ai mod p≠1a^i\bmod{p}\neq1，如何判断？
枚举每个 ii，依次用快速幂判断，但还是慢了。
正难则反，只需要知道 ai mod p=1a^i\bmod{p}=1 的结果，就知道 ai mod p≠1a^i\bmod{p}\neq1。
在 [1,p−1)[1,p-1) 中，那个 ii 可能满足 ai mod p=1a^i\bmod{p}=1?
假设 ak mod p=1a^k\bmod{p}=1。
∴ak mod p=1,ak+1 mod p=a,ak+2 mod p=a2 mod p,…a2k mod p=1,…a3k mod p=1,…axk mod p=1x∈[0,∞]\therefore\\a^{k}\bmod p=1,\\\\a^{k+1}\bmod{p}=a,\\a^{k+2}\bmod{p}=a^2\bmod p,\\\dots\\a^{2k}\bmod p=1,\\\dots\\a^{3k}\bmod p=1,\\\dots\\a^{xk}\bmod p=1 \quad x\in[0,\infty]
wow，有周期，每 kk 个一循环，每个循环周期大小相等！
因为 ap−1 mod p≠1a^{p-1}\bmod{p}\not=1 我们提前判段为错误，并退出了，所以现在的 aa 和 pp 一定满足 ap−1 mod p=1a^{p-1}\bmod{p}=1。
诶，我们忽略了 00，a0 mod p=1a^0 \bmod p=1！
也就是说我们要将 11 到 p−1p-1 划分成若干段长度相同的循环周期，在 [1,p−1)[1,p-1) 中，只有每小段的末尾，也就是 p−1p-1 的因数的倍数，可能满足 ai mod p=1a^i\bmod{p}=1。
又知道 p−1p-1 的一个因数 xx，使得 ax mod p=1a^x\bmod{p}=1，那么，这个因数的任意一个倍数 yy，也都满足 ay mod p=1a^y\bmod{p}=1。
所以只用找 p−1p-1 的每一个因数 xx 是否满足 ax mod p=1a^x\bmod{p}=1，就可以推出"对于任意 1≤i<p−11\le i<p-1 均有 ai mod p≠1a^i\bmod{p}\neq1"这个条件了

代码（含注释）：

CPP
//c++
#include<iostream>
#include<vector>
#define ll long long
using namespace std;
vector<ll>yin;       //表示p-1的因数
ll fpow(ll a,ll b,ll p){//快速幂
	a%=p;
	if(b==1)return a;
	if(b==0)return 1;
	if(b&1)return a*fpow(a*a%p,(b>>1),p)%p;
	return fpow(a*a%p,(b>>1),p);
}
void find_yin(ll x){	//找因数
	while(yin.size())   //清空
		yin.pop_back();    
	for(ll i=2;i*i<=x;i++){
		if(x%i==0){
			yin.push_back(i);
			yin.push_back(x/i);
		}
	}
	return ;
}
void doing(){//求出每次答案
	ll p,a;
	cin>>a>>p;
	if(fpow(a,p-1,p)!=1){  //条件2
		puts("No");
		return ;
	}
	find_yin(p-1);         //找p-1的因数
	for(int i=0;i<yin.size();i++){
		ll y=yin[i];       //枚举每个因数
		if(fpow(a,y,p)==1){//满足条件4(不满足条件3)
			puts("No");
			return ;
		}
	}
	puts("Yes");
	return ;
}
int main(){
	int t; 
	cin>>t;
	while(t--){
		doing();
	}
	return 0;
}

复杂度：

  • 时间：O(T×(log⁡n×n+log⁡n+n))O(T\times(\log n\times\sqrt n+\log n+\sqrt n))
  • 空间：O(n)O(\sqrt n)

鸣谢

评论

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

正在加载评论...