← 返回题单
题单练习 GESP五级真题-编程题
← 上一题 下一题 →

A5113 | [GESP202503 五级] 原根判断

来源2025
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

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

  • $1 g p$;
  • $g^{p-1} \mod p = 1$;
  • 对于任意 $1 \leq i p - 1$ 均有 $g^i \mod p \neq 1$。
其中 $a \mod p$ 表示 $a$ 除以 $p$ 的余数。

小 A 现在有一个整数 $a$，请你帮他判断 $a$ 是不是 $p$ 的原根。

输入格式

  • 第一行，一个正整数 $T$，表示测试数据组数。
  • 每组测试数据包含一行，两个正整数 $a, p$。

输出格式

  • 对于每组测试数据，输出一行，如果 $a$ 是 $p$ 的原根则输出 Yes，否则输出 No。

输入输出样例

输入 #1
3
3 998244353
5 998244353
7 998244353
输出 #1
Yes
Yes
No
C++ 编辑器
输入
输出