P11961 [GESP202503 五级] 原根判断-171主机测评

P11961 [GESP202503 五级] 原根判断

题目背景

对应的选择、判断题：https://ti.luogu.com.cn/problemset/1177

截止 2025 年 3 月，本题可能超出了 GESP 考纲范围。在该时间点下，原根是 NOI 大纲 8 级知识点（NOI 级），而相对简单的无需原根知识的做法中，使用的费马小定理与欧拉定理也属于 NOI 大纲 7 级知识点（提高级），且均未写明于 GESP 大纲中。需要注意，GESP 大纲和 NOI 大纲是不同的大纲。

若对题目中原根这一概念感兴趣，可以学习完成【模板】原根。

题目描述

小 A 知道，对于质数

$p$ 而言，

$p$ 的原根

$g$ 是满足以下条件的正整数：

$g^{p-1}\\bmod{p}=1 gp−1modp=1；$
对于任意 $1\\le i<p-1 1≤i<p−1 均有 g i m o d p ≠ 1 g^i\\bmod{p}\\neq1 gimodp=1。$

其中

a\\bmod{p}

$a mod p$ 表示

$a$ 除以

$p$ 的余数。

小 A 现在有一个整数

$a$ ，请你帮他判断

$a$ 是不是

$p$ 的原根。

输入格式

第一行，一个正整数

$T$ ，表示测试数据组数。

每组测试数据包含一行，两个正整数

a,p

$a, p$ 。

输出格式

对于每组测试数据，输出一行，如果

$a$ 是

$p$ 的原根则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

3
3 998244353
5 998244353
7 998244353

输出 #1

Yes
Yes
No

说明/提示

数据范围

对于

40\\%

$40%$ 的测试点，保证

≤

3\\le p\\le10^3

$3 \leq p \leq 1 0^{3}$ 。

对于所有测试点，保证

≤

1\\le T\\le20

$1 \leq T \leq 20$ ，

≤

3\\le p\\le10^9

$3 \leq p \leq 1 0^{9}$ ，

1<a<p

$1 < a < p$ ，

$p$ 为质数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[10010]; // 全局数组，名字为 a

/**
* 快速幂函数
* 计算 (a^b) % mod
*/
ll func(ll x, ll y, ll mod) {// 求x的y次方余p
ll res = 1;//底数
while (y) {
if (y % 2 != 0){
res = (res * x) % mod;
y—;
}
x = (x * x) % mod;
y /= 2;
}
return res;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int t;
cin >> t;

while (t—) {
ll base, p, cnt = 0;
cin >> base >> p;

ll m = p – 1;

// 试除法求真因数
for (ll i = 2; i * i <= m; i++) {
if (m % i == 0) {
a[++cnt] = i;
while (m % i == 0){
m /= i;
}
}
}
if (m > 1) {
a[++cnt] = m;
}

bool flag = true;

// 判断原根
for (ll i = 1; i <= cnt; i++) {
ll q = a[i];//指数即为p – 1的因数
if (func(base, p / q, p) == 1) {
flag = false;
break;
}
}

if (flag){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}

}

return 0;
}

P11961 [GESP202503 五级] 原根判断