[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; // 快速幂函数，计算 (base^exponent) % modulus long long fastPower(long long base, long long exponent, long long modulus) { long long result = 1; base = base % modulus; while (exponent > 0) { if (exponent % 2 == 1) { result = (result * base) % modulus; } base = (base * base) % modulus; exponent = exponent >> 1; } return result; } // 判断 a 是否为 p 的原根 bool isPrimitiveRoot(int a, int p) { // 条件1: 1 < a < p if (a <= 1 || a >= p) { return false; } // 条件2: a^(p-1) mod p = 1 if (fastPower(a, p - 1, p) != 1) { return false; } // 条件3: 对于任意 1 ≤ i < p - 1 均有 a^i mod p != 1 for (int i = 1; i < p - 1; i++) { if (fastPower(a, i, p) == 1) { return false; } } return true; } int main() { int T; cin >> T; while (T--) { int a, p; cin >> a >> p; if (isPrimitiveRoot(a, p)) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; } ``` 这段代码实现了判断一个整数 `a` 是否为质数 `p` 的原根的功能。首先定义了快速幂函数 `fastPower` 用于高效计算幂取模运算，然后定义 `isPrimitiveRoot` 函数来检查 `a` 是否满足原根的三个条件。在 `main` 函数中，读取测试数据组数 `T`，对于每组数据调用 `isPrimitiveRoot` 函数进行判断并输出结果。 [2026-02-03 17:11:00 | AI问答 | 511点数解答]