原根判断

#include<bits/stdc++.h>
using namespace std;

long long pow_mod(long long a,long long x,long long mod)
{
    long long m=1;
    while(x)
    {
        if(x%2)
            m=m*a%mod;
        a=a*a%mod;
        x/=2;
    }
    return m;
}

int main() {

    
    int T;
    cin >> T;
    while (T--) {
        long long g, p;
        cin >> g >> p;
        
        // 条件1：1 < g < p
        if (!(g > 1 && g < p)) {
            cout << "No\n";
            continue;
        }
        // 条件2：费马小定理（质数p下必然成立，保留作为保险）
        if (pow_mod(g, p - 1, p) != 1) {
            cout << "No\n";
            continue;
        }
        
        bool f = 1;
        long long m = p - 1;
        // 试除法分解 p-1 的质因子
        for (long long i = 2; i * i <= m; i++) {
            if (m % i == 0) {
                // 核心判定：g^((p-1)/质因子) % p 不能等于 1
                if (pow_mod(g, (p - 1) / i, p) == 1) {
                    f = 0;
                    break;
                }
                while (m % i == 0) m /= i; // 除尽该质因子
            }
        }
        // 处理剩余的大质因子（如果有）
        if (f && m > 1) {
            if (pow_mod(g, (p - 1) / m, p) == 1)
                f = 0;
        }
        
        cout << (f ? "Yes\n" : "No\n");
    }
    return 0;
}

---

逐行原理详解

1. 数学原理（原根判定定理）

对于质数 p，g 是原根的充要条件是：

g^(p-1) ≡ 1 (mod p)，且对于 p-1 的每一个质因子 q，都有 g^((p-1)/q) ≢ 1 (mod p)。

为什么？
如果存在某个质因子 q 使得 g^((p-1)/q) ≡ 1，说明 g 的阶（最小正周期）小于 p-1，那就不是原根。反之，若所有质因子检验都不等于1，则阶必为 p-1，即为原根。

2. 代码映射

代码段	对应数学/算法逻辑
if(!(g>1 && g<p))	题目定义的第一条件
pow_mod(g,p-1,p)!=1	费马小定理检验（保险步骤）
for(long long i=2;i*i<=m;i++)	试除法找 p-1 的质因子
if(m%i==0)	找到一个质因子 i
pow_mod(g,(p-1)/i,p)==1	代入判定定理：若成立则 g 不是原根
while(m%i==0) m/=i;	去掉 m 中所有的 i 因子，避免重复检验合数
if(f && m>1)	循环结束后，若 m>1 说明剩下一个大质因子，需单独检验

---

🧪 模拟运行过程（以 g=3, p=7 为例）

1. g=3, p=7，满足 1<3<7 ✅
2. 3^(7-1) % 7 = 729 % 7 = 1 ✅
3. m = 6。进入循环 i=2：
   • 6%2==0 → 质因子 2
   • 检验 3^((7-1)/2) % 7 = 3^3 % 7 = 27 % 7 = 6 ≠ 1 ✅（不是1，通过）
   • while 循环：6/2=3，m 变为 3
4. i 变为 3，3*3 <= 3 不成立，循环结束。
5. m=3 > 1，检验剩余质因子：
   • 3^((7-1)/3) % 7 = 3^2 % 7 = 9 % 7 = 2 ≠ 1 ✅
6. f 始终为 1，输出 Yes。正确！（3确实是模7的原根）

---