E.质数电脑？

题目要意:你需要判断一些长度为,数在间随机生成的数组的质数多还是偶数多

解法一大胆猜测

每场比赛都应该有脑洞大开的猜猜环节

题目中提到了随机生成，我们可以想到一些随机数的性质

众所不周知，以内的质数个数约为个，所以，我们可以大致计算一下概率，发现单组出现质数比合数多的概率约为,所以，共有10个测试点，1000组数据，出现不是全为合数比质数多的概率可以忽略不计，大胆输出YES即可通过此题。

实际中，我们发现绝大部分同学都是通过筛一些小质数来判断，这样问题也不大。

解法二 Miller–Rabin素性测试

你可以点击此处对此算法进行了解，单组数据时间复杂度约为,约为,可以通过本题。

场上并没有同学使用该方法。

以下为出题人代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void init() {}
i64 mul(i64 a, i64 b, i64 m) { return static_cast<__int128>(a) * b % m; }
i64 power(i64 a, i64 b, i64 m)
{
    i64 res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
        if (b & 1)
            res = mul(res, a, m);
    return res;
}
bool isprime(i64 n)
{
    if (n < 2)
        return false;
    static constexpr int A[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    int s = __builtin_ctzll(n - 1);
    i64 d = (n - 1) >> s;
    for (auto a : A)
    {
        if (a == n)
            return true;
        i64 x = power(a, d, n);
        if (x == 1 || x == n - 1)
            continue;
        bool ok = false;
        for (int i = 0; i < s - 1; ++i)
        {
            x = mul(x, x, n);
            if (x == n - 1)
            {
                ok = true;
                break;
            }
        }
        if (!ok)
            return false;
    }
    return true;
}
void solve()
{
    int n;
    cin >> n;
    int cnt0 = 0, cnt1 = 0;
    for (int i = 1; i <= n; i++)
    {
        int tp;
        cin >> tp;
        if (isprime(tp))
            cnt0++;
        else
            cnt1++;
    }
    if (cnt1 >= cnt0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int __ = 1;
    std::cin >> __;
    init();
    while (__--)
    {
        solve();
    }
    return 0;
}

出题人题解

E.质数电脑？

解法一 大胆猜测

解法二 Miller–Rabin素性测试

解法一大胆猜测