专栏文章

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

DDFM_O
P11961题解参与者 11已保存评论 13

文章操作

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

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

P11961 题目

解题思路

由原根的性质，当 p≥3p\ge3 时，gg 为 pp 的原根，当且仅当 gcd⁡(g,p)=1\gcd(g,p)=1 且对于所有 φ(p)\varphi(p) 的质因数 qq，都有 gφ(p)q mod p≠1g^{\frac{\varphi(p)}{q}}\bmod p\not=1，因为若 gcd⁡(g,p)≠1\gcd(g,p)\not=1，则 gφ(p) mod p≠1g^{\varphi(p)}\bmod p\not=1。
而对于 gφ(p)q mod p≠1g^{\frac{\varphi(p)}{q}}\bmod p\not=1 这个条件，必要性是显然的，下面对于充分性进行证明：若存在一个最小的 ii 满足 i<φ(p)i<\varphi(p) 且 gi mod p=1g^i\bmod p=1，则 ii 一定为 φ(p)\varphi(p) 的因数，又因为 i≠φ(p)i\not=\varphi(p)，所以一定存在一个 φ(p)\varphi(p) 的质因数 qq，满足 φ(p)q\frac{\varphi(p)}{q} 为 ii 的倍数，此时 gφ(p)q mod p=1g^{\frac{\varphi(p)}{q}}\bmod p=1，于是我们便知道，只要对于所有的 φ(p)\varphi(p) 的质因数 qq，都有 gφ(p)q mod p≠1g^{\frac{\varphi(p)}{q}}\bmod p\not=1，那么就不会存在 i∈[1,φ(p)−1]i\in[1,\varphi(p)-1]，满足 gi mod p=1g^i\bmod p=1。
在本题中，由于 pp 为质数，于是 φ(p)=p−1\varphi(p)=p-1，枚举 p−1p-1 的质因数并检查即可。

Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline bool pd(int a)
{
	if(a<2)
		return false;
	for(int i=2;i*i<=a;i++)
	{
		if(a%i==0)
			return false;
	}
	return true;
}
inline long long poww(long long a,long long b,long long p)
{
    long long ss=1;
    while(b)
    {
        if(b&1)
            ss=ss*a%p;
        a=a*a%p;
        b>>=1;  
    }
    return ss;
}
signed main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		int g,p;
		cin>>g>>p;
		int phi=p-1;
		if(__gcd(g,p)!=1)
		{
			cout<<"No\n";
			continue;
		}
		int pdd=0;
		for(int i=1;i<=sqrt(phi);i++)
		{
			if(phi%i==0)
			{
				if(pd(i)==1&&poww(g,phi/i,p)==1||pd(phi/i)==1&&poww(g,i,p==1))
				{
					pdd=1;
					break;
				}
			}
		}
		if(pdd==0)
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
	return 0;
}

评论

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

正在加载评论...