专栏文章

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

FFall_Dream
P11961题解参与者 7已保存评论 8

文章操作

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

当前评论
8 条
当前快照
1 份
快照标识符
@mipthob3
此快照首次捕获于
2025/12/03 17:41
3 个月前
此快照最后确认于
2025/12/03 17:41
3 个月前
查看原文
普及组选手表示不需要什么费马小定理，只需要快速幂即可（？）
首先，显然的，axy=(ax)ya^{xy} = (a^x) ^y。然后可以假设其中 ax≡1(modp)a^x\equiv 1\pmod p，则有 axy=(ax)y≡1y≡1(modp)a^{xy}=(a^x)^y\equiv 1 ^ y\equiv1\pmod p。所以我们可以 O(p)O(\sqrt{p}) 分解 p−1p-1 的质因数，然后检查 p−1p-1 的每一个因数 ff 是否满足 af≡1(modp)a^f\equiv 1\pmod p，如果有任意一个因数满足上述条件，直接输出 No。如果所有因数均不满足，输出 Yes。总复杂度 O(Tplog⁡p)O(T \sqrt{p}\log p)。

代码不刻意压 25 行

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int qpow(int a,int b,int p){
	int res=1;
	while(b){
		if(b&1)res=res*a%p;
		b>>=1,a=a*a%p;
	}
	return res;
}
void solve(){
	int a,p;
	cin>>a>>p;
	for(int i=2;i<=sqrt(p-1);i++)
		if((p-1)%i==0)
			if(qpow(a,i,p)==1||qpow(a,(p-1)/i,p)==1){
				puts("No");return;
			}
	puts("Yes");
}
signed main(){
	int T;cin>>T;
	while(T--) solve();
}

评论

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

正在加载评论...