题型：编程题
原根判断
题目描述
小 A 知道，对于质数p 而言，p 的原根g 是满足以下条件的正整数：
·1＜g＜p
·gp-1 mod p=1
·对于任意1≤i＜p-1 均有 gi mod p≠1。
其中a mod p 表示a 除以 p的余数。
小 A 现在有一个整数a ，请你帮他判断 a是不是p 的原根。
输入格式
第一行，一个正整数 T，表示测试数据组数。
每组测试数据包含一行，两个正整数a ,p 。
输出格式
对于每组测试数据，输出一行，如果 a是 p的原根则输出 Yes ，否则输出 No 。
输入样例
3 3 998244353 5 998244353 7 998244353
输出样例
Yes Yes No
数据范围
对于 40% 的测试点，保证3≤p≤103 。
对于所有测试点，保证1≤T≤20 ，3≤p≤109，1＜a＜p ，p为质数。
更新时间：2025-06-19 13:04:06
|
【知识点】
CCF—GESP Python五级
抱歉! 您未登录, 不能查看答案和解析点击登录
相似题推荐
单选题
唯一分解定理描述的内容是（）。
| A． 任何正整数都可以表示为两个素数的和。 |
B． 任何大于1的合数都可以唯一分解为有限个质数的乘积。 |
| C． 两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。 |
D． 所有素数都是奇数。 |
2026-07-18
判断题
以下 fib 函数计算第 n 项斐波那契数（ fib(0)=0 , fib(1)=1 ），其时间复杂度为 O(n)。（）
def fib(n) : if n <= 1 : return n return fib(n - 1) + fib(n - 2)
| A．正确 | B．错误 |
2026-07-18
