简答题 偏难
#17776

原根判断 题目描述 小 A 知道,对于质数p 而言,p 的原根g 是满足以下条件的正整数: ·1<g<p ·g p-1 mod p=1 ·对于任意1≤i<p-1…

原根判断

题目描述

小 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为质数。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false">def fpw(b, e, p): if e == 0: return 1 r = fpw(b, e &gt;&gt; 1, p) return r * r * (b if e &amp; 1 else 1) % p def solve(): a, p = map(int, input().split()) phi, v = p - 1, p - 1 for i in range(2, int(phi ** 0.5) + 2): if v % i == 0: while v % i == 0: v //= i if fpw(a, phi // i, p) == 1: print("No") return if v &gt; 1: if fpw(a, phi // v, p) == 1: print("No") return print("Yes") [solve() for _ in range(int(input()))]</pre>
这道题暂未补解析。