简答题
偏难
#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 。
输入样例
输出样例
数据范围
对于 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 >> 1, p)
return r * r * (b if e & 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 > 1:
if fpw(a, phi // v, p) == 1:
print("No")
return
print("Yes")
[solve() for _ in range(int(input()))]</pre>
这道题暂未补解析。