题解 | 2023 年牛客多校第三场 H 题 Until the Blue Moon Rises

题意：给定一个长度为 $nn$ 的序列 $\{a{\}}_{i=1}^n\backslash \{a\backslash \}\_\{i=1\}^n$，一次操作可以选择两个不同的数字 $a_{i}a\_i$ 和 $a_{j}a\_j$ 执行 $a_i\leftarrow a_i+1,a_j\leftarrow a_j-1a\_i\; \backslash leftarrow\; a\_i+1,a\_j\; \backslash leftarrow\; a\_j-1$。问能不能有限次操作内让序列中每个数字都是质数。$1\le n\le 10^{3}1\; \backslash le\; n\; \backslash le\; 10^3$，$1\le a_i\le 10^{9}1\; \backslash le\; a\_i\backslash le\; 10^9$。

解法：当 $n=1n=1$ 时，显然和 $ss$ 为质数才行。

当 $n\ge 2n\; \backslash ge\; 2$ 时，$s\ge 2ns\; \backslash ge\; 2n$（每个数字都是最小的质数 $22$）。

当 $n=2n=2$ 时，如果 $ss$ 为偶数，则由哥德巴赫猜想一定成立。如果 $ss$ 为奇数，则必然是 $2+(n-2)2+(n-2)$。检查 $n-2n-2$ 是否为质数即可。

当 $n\ge 3n\; \backslash ge\; 3$ 时，可以首先先安排 $n-2n-2$ 个 $22$，问题退化到 $n=2n=2$ 的情形。当 $s-2ns-2n$ 为偶数时，哥德巴赫猜想使得一定有解。如果 $s-2ns-2n$ 是奇数，则可以让前面 $n-2n-2$ 个 $22$ 中其中一个 $22$ 变成 $33$，则此时 $s-2n-1s-2n-1$ 为偶数，如果 $s-2n-1\ge 4s-2n-1\; \backslash ge\; 4$，则同样利用哥德巴赫猜想可以证明成立。

#include <bits/stdc++.h>
using namespace std;
bool checkPrime(long long x)
{
    if (x == 1)
        return false;
    for (int i = 2; 1ll * i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}
int main()
{
    long long sum = 0;
    int n;
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++)
    {
        scanf("%d", &x);
        sum += x;
    }
    if (n == 1)
    {
        if (checkPrime(sum))
            puts("Yes");
        else
            puts("No");
        return 0;
    }
    if (sum < 2 * n)
    {
        puts("No");
        return 0;
    }
    long long res = sum - 2 * (n - 2);
    if (res % 2 == 0 || checkPrime(res - 2))
    {
        puts("Yes");
        return 0;
    }
    if (n > 2 && res - 1 >= 4)
        puts("Yes");
    else
        puts("No");
    return 0;
}