质数原根判断算法与快速幂实现详解

1. 原根判断问题解析

这道题目要求我们判断给定的正整数g是否是质数p的原根。在数论中，原根是一个非常重要的概念，特别是在密码学等领域有着广泛应用。要理解这个问题，我们需要先明确几个关键概念。

首先，原根的定义是：对于质数p，如果g满足以下两个条件，则称g是p的原根：

1. g^(p-1) ≡ 1 mod p
2. 对于所有1 ≤ i < p-1，都有g^i ≢ 1 mod p

第一个条件实际上是费马小定理的直接应用，它告诉我们任何与p互质的数g都满足这个条件。因此，真正的难点在于第二个条件的验证。

2. 算法优化思路

直接按照定义实现这个判断显然效率太低，因为当p很大时（题目中p可以达到10^9），我们需要检查的i值会非常多。这就需要我们寻找更聪明的验证方法。

关键观察点在于：如果存在某个i使得g^i ≡ 1 mod p，那么i的所有倍数ix也会满足g^(ix) ≡ 1 mod p。反过来，如果我们能确保对于p-1的所有质因数d，都有g^d ≢ 1 mod p，那么就能保证g是原根。

这个观察让我们可以将需要检查的i值范围大大缩小 - 我们只需要检查p-1的质因数即可，而不需要检查所有1 ≤ i < p-1。

3. 快速幂算法实现

在实现过程中，快速幂算法(qpow)是核心。这个算法能在O(log y)时间内计算x^y mod p，效率非常高。其原理基于指数的二进制分解：

cpp复制int qpow(int x, int y){
    int res = 1;
    while(y){
        if(y&1) res = (ll)res * x % p;
        y >>= 1;
        x = (ll)x * x % p;
    }
    return res;
}

这个实现有几个关键点：

1. 使用位运算y&1和y>>=1来高效处理二进制位
2. 每次迭代都将x平方，对应指数的二进制位移动
3. 当遇到二进制位为1时，将当前的x乘入结果
4. 全程使用模运算防止溢出

4. 完整解题代码分析

让我们来看完整的解题代码：

cpp复制#include<iostream>
using namespace std;
typedef long long ll;
int t,