GESP202503五级：判断整数a是否为质数p原根的代码实现

```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` 函数进行判断并输出结果。 ######[AI问答 | 511点数解答 | 2026-02-03 17:11:00]