GESP202503五级：原根判断问题全解析，含代码与复杂度分析

```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)$。 ######[AI问答 | 668点数解答 | 2026-02-02 17:30:47]