[GESP202503 五级] 原根判断 显示标签 时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 256MB，其他语言 512MB 难度：未知 分数：100 OI排行榜得分：20(0.1*分数+2*难度) 出题人： 描述 小 A 知道，对于质数 p 而言，p 的原根 g 是满足以下条件的正整数： 1<g<p； g p−1 modp=1； 对于任意 1≤i<p−1 均有 g i modp  =1。 其中 amodp 表示 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 提示 【数据范围】 对于 40% 的测试点，保证 3≤p≤10 3 。 对于所有测试

```cpp #include <iostream> using namespace std; // 快速幂函数，计算 a^b % mod long long quickPow(long long a, long long b, long long mod) { long long res = 1; while (b) { if (b & 1) { res = res * a % mod; } a = a * a % mod; b >>= 1; } return res; } // 判断 a 是否为 p 的原根 bool isPrimitiveRoot(long long a, long long p) { // 检查 g^(p - 1) % p 是否等于 1 if (quickPow(a, p - 1, p) != 1) { return false; } // 检查对于任意 1 <= i < p - 1，g^i % p 是否不等于 1 for (long long i = 1; i < p - 1; i++) { if (quickPow(a, i, p) == 1) { return false; } } return true; } int main() { int T; cin >> T; while (T--) { long long a, p; cin >> a >> p; if (isPrimitiveRoot(a, p)) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; } ``` 代码解释 1. 快速幂函数 `quickPow`：用于高效计算 `a^b % mod`，通过二进制拆分指数 `b`，将时间复杂度从 $O(b)$ 降低到 $O(log b)$。 2. 判断原根函数 `isPrimitiveRoot`： - 首先检查 `g^(p - 1) % p` 是否等于 1，如果不等于 1，则 `a` 不是 `p` 的原根。 - 然后遍历 `1` 到 `p - 2` 的所有整数 `i`，检查 `g^i % p` 是否等于 1，如果存在等于 1 的情况，则 `a` 不是 `p` 的原根。 3. 主函数 `main`： - 读取测试数据组数 `T`。 - 对于每组测试数据，读取 `a` 和 `p`，调用 `isPrimitiveRoot` 函数判断 `a` 是否为 `p` 的原根，并输出结果。 复杂度分析 - 时间复杂度：对于每组测试数据，快速幂函数的时间复杂度为 $O(log(p))$，判断原根需要遍历 `p - 2` 个指数，因此总的时间复杂度为 $O(p log(p))$。 - 空间复杂度：代码只使用了常数级的额外空间，因此空间复杂度为 $O(1)$。 [2026-02-02 17:30:47 | AI问答 | 668点数解答]