自动搬运

查看原文

来自洛谷，原作者为

	cjy0329 数学可以改变未来，编程能够改变世界。

搬运于2025-08-24 23:11:41，当前版本为作者最后更新于2025-03-23 23:30:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目背景

截止 2025 年 3 月，本题可能超出了 GESP 考纲范围。在该时间点下，原根是 NOI 大纲 8 级知识点（NOI 级），且不属于 GESP 大纲内容。需要注意，GESP 大纲和 NOI 大纲是不同的大纲。 若对题目中原根这一概念感兴趣，可以学习完成 【模板】原根。

~本萌新只是个五年级刚学oi的蒟蒻，本想考个五级，结果qwq……我的两道编程题都ac了 \(^v^)/~

题意：

对于质数 $p$ 而言，$p$ 的原根 $g$ 是满足以下条件的正整数：

• $1<g<p$；
• $g^{p-1}\bmod{p}=1$；
• 对于任意 $1\le i<p-1$ 均有 $g^i\bmod{p}\neq1$。

其中 $a\bmod{p}$ 表示 $a$ 除以 $p$ 的余数。

给出一个整数 $a$ 和质数 $p$，判断 $a$ 是不是 $p$ 的原根。

保证 $1\le T\le20$，$3\le p\le10^9$，$1<a<p$，$p$ 为质数。

思路：

要想让 $a$ 是 $p$ 的原根，必须满足三个条件：

1. $1<a<p$ ，这条已被约束条件满足了，无需判断；
2. $a^{p-1}\bmod{p}=1$，写个快速幂，$O(\log n)$ 就能判断；
3. 对于任意 $1\le i<p-1$ 均有 $a^i\bmod{p}\neq1$，如何判断？

枚举每个 $i$，依次用快速幂判断，但还是慢了。

正难则反，只需要知道 $a^i\bmod{p}=1$ 的结果，就知道 $a^i\bmod{p}\neq1$。

在 $[1,p-1)$ 中，那个 $i$ 可能满足 $a^i\bmod{p}=1$?

假设 $a^k\bmod{p}=1$。

$\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，有周期，每 $k$ 个一循环，每个循环周期大小相等！

因为 $a^{p-1}\bmod{p}\not=1$ 我们提前判段为错误，并退出了，所以现在的 $a$ 和 $p$ 一定满足 $a^{p-1}\bmod{p}=1$。

诶，我们忽略了 $0$，$a^0 \bmod p=1$！

也就是说我们要将 $1$ 到 $p-1$ 划分成若干段长度相同的循环周期，在 $[1,p-1)$ 中，只有每小段的末尾，也就是 $p-1$ 的因数的倍数，可能满足 $a^i\bmod{p}=1$。

又知道 $p-1$ 的一个因数 $x$，使得 $a^x\bmod{p}=1$，那么，这个因数的任意一个倍数 $y$，也都满足 $a^y\bmod{p}=1$。

所以只用找 $p-1$ 的每一个因数 $x$ 是否满足 $a^x\bmod{p}=1$，就可以推出"对于任意 $1\le i<p-1$ 均有 $a^i\bmod{p}\neq1$"这个条件了

代码（含注释）：

//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\times(\log n\times\sqrt n+\log n+\sqrt n))$
• 空间：$O(\sqrt n)$

鸣谢

• @Ultra_Pitcher
• @Chase12345