4679: 【GESP2503五级】原根判断

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：3 解决：2

题目描述


输入

第一行，一个正整数 ，表示测试数据组数。
每组测试数据包含一行，两个正整数$a,p$ 。

输出

对于每组测试数据，输出一行，如果$a$ 是$p$ 的原根则输出 Yes ，否则输出 No 。

样例输入 复制 

3
3 998244353
5 998244353
7 998244353

样例输出 复制 

Yes
Yes
No

提示

#include <cstdio>

using namespace std;
int a, p;
int ans;
int fpw(int b, int e) {
    if (e == 0)
        return 1;
    int r = fpw(b, e >> 1);
    r = 1ll * r * r % p;
    if (e & 1)
        r = 1ll * r * b % p;
    return r;
}
void check(int e) {
    if (fpw(a, e) == 1)
        ans = 0;
}
int main() {
    int T;
    scanf("%d", & T);
    while (T--) {
        scanf("%d%d", & a, & p);
        ans = 1;
        int phi = p - 1, r = phi;
        for (int i = 2; i * i <= phi; i++)
            if (phi % i == 0) {
                check(phi / i);
                while (r % i == 0)
                    r /= i;
            }
        if (r > 1)
            check(phi / r);
        printf(ans ? "Yes\n" : "No\n");
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 快速幂取模
long long powmod(long long a, long long b, long long p) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// 分解 n 的所有质因子
vector<long long> factorize(long long n) {
    vector<long long> factors;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            factors.push_back(i);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) factors.push_back(n);
    return factors;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long a, p;
        cin >> a >> p;

        // 费马小定理：a^(p-1) % p == 1 自动成立，但保险检查
        if (powmod(a, p - 1, p) != 1) {
            cout << "No\n";
            continue;
        }

        // 获取 p-1 的所有质因子
        vector<long long> primes = factorize(p - 1);

        bool is_primitive = true;
        for (long long q : primes) {
            if (powmod(a, (p - 1) / q, p) == 1) {
                is_primitive = false;
                break;
            }
        }

        cout << (is_primitive ? "Yes" : "No") << endl;
    }
    return 0;
}

来源/分类

提交提交记录统计露一手!