背景

28 号就要考五级了

---

来源：洛谷P11961 [GESP202503 五级] 原根判断

P11961 [GESP202503 五级] 原根判断

题目描述

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

• $1<g<p$；
• $g^{p-1}\bmod{p}=1$；
• 对于任意 $1\le i<p-1$ 均有 $g^i\bmod{p}\neq1$。

其中 $a\bmod{p}$ 表示 $a$ 除以 $p$ 的余数。

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

输入格式

第一行，一个正整数 $T$，表示测试数据组数。

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

输出格式

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

输入输出样例 #1

输入 #1

3
3 998244353
5 998244353
7 998244353

输出 #1

Yes
Yes
No

说明/提示

数据范围

对于 $40\%$ 的测试点，保证 $3\le p\le10^3$。

对于所有测试点，保证 $1\le T\le20$，$3\le p\le10^9$，$1<a<p$，$p$ 为质数。

---

题解

其实写完才发现，好像考的知识也不是很难，就是快速幂和质因数分解。如果没了解过，赶紧去请教一下D老师。

先一条一条地看原根的判断条件：

• $1<g<p$；
• $g^{p-1}\bmod{p}=1$；
• 对于任意 $1\le i<p-1$ 均有 $g^i\bmod{p}\neq1$。

$1<g<p$

这一条并不难，数据范围已经保证了这一点。

$g^{p-1}\bmod{p}=1$

只要会快速幂，这一点也不难。这要根据描述来判断就好了。

对于任意 $1\le i<p-1$ 均有 $g^i\bmod{p}\neq1$

难点就在这了。首先想到的就是 for 循环，遍历 1 到 p-2 ，如果检查到一个 $g^i\bmod{p}=1$ ，就直接 return false; 就好了。但是数据很大， $O(n)$ 的算法肯定会超时。看到数据很大，一定会想到 $O(\log{n})$ 的算法。（好像我们已经学了的就是贪心、数学和二分了）二分应该不行，因为 $i$ 的分布行不是有序的。 剩下就是贪心和数学。

反过来想，要保证 $[1,p-1)$ 中均有 $g^i\bmod{p}\neq1$ ，其实只需要在$[1,p-1)$ 中找到一个 $i$ ，使 $g^i\bmod{p}=1$ 就好了。那如何找呢？

$g^i\bmod{p}=1$ ，那么 $g^{2i}\bmod{p}$ 等于多少呢？很显然也是 $1$ 。那么 $g^{3i}\bmod{p}$ ， $g^{4i}\bmod{p}$ ， $g^{5i}\bmod{p}$ 等都为 $1$ 。即 $g^{ki}\bmod{p}=1$ 。根据第二条条件，可以发现， $g^{p-1}\bmod{p}=1$ 。根据前面的 $g^{ki}\bmod{p}=1$ ，那么 $p-1$ 一定是这个 $i$ 的倍数。而且可以证明，如果 $p-1$ 不是 $i$ 的倍数如图1，是不成立的：

这样就变简单了，只需要判断 $p-1$ 的因子中有没有一个 $i$ 能使 $g^i\bmod{p}=1$ 。这很容易想到质因数分解。只需要把 $p-1$ 进行质因数分解，在逐个判断就好了。时间复杂度： $O(\log{n})$ 。代码：

VIP内容