H.Until the Blue Moon Rises

数学题

题目大意

对于给定的 $nn$ 个数，每次操作可以使一个数 $-1-1$ ，另一个数 $+1+1$

可以操作任意次，问是否可以使这些数全部成为质数

前置知识点

哥德巴赫猜想：任一大于5的整数都可写成三个质数之和，任一大于2的偶数都可写成两个素数之和

解题思路

题设操作任意次的效果即：把所有数的和 $sumsum$ 分成 $nn$ 个数

问是否有一种分法使得这 $nn$ 个数都是质数

1. $nn$ 个数都是质数时，最小情况是所有的数全为 $22$

   因此，当 时一定不可以构成

2. $n=1n=1$

   只有一个数，直接判断它是否为质数即可

3. $n=2n=2$

   如果它们的和是偶数，根据哥德巴赫猜想一定可以构成；

   如果它们的和是奇数，分成两个数一定是一奇一偶，众嗦粥汁，偶数中只有2是质数，因此判断 $n-2n-2$ 是否为质数即可

4. $n=3n=3$

   由于 的情况已经在 $11$ 中筛去，故根据哥德巴赫猜想一定可以构成

5. $n>3n>3$

   每次分出 $22$ 直到剩余 $33$ 个数，利用上一条可知一定可以构成

参考代码

bool checkprime(ll n){
    if(n<2) return false;
    if(n==2||n==3) return true;
    ll t=sqrt(n)+1;
    FORLL(i,2,t) if((n/i)*i==n){
        return false;
    }
    return true;
}
#define N 100005
void solve()
{
    ll t,sum=0;
    ll n;
    cin >> n;
    FORLL(i,1,n){
        cin >> t;
        sum+=t;
    }
    if(sum<2*n) {cout << NO ;return;}
    if(n==1){
        if(checkprime(sum))
        {
            cout << YES;
            return;
        }
        cout << NO ;
        return;
    }
    if(n==2){
        if(sum&1){
            if(checkprime(sum-2)) {cout << YES ;return;}
            cout << NO;
            return;
        }
        cout << YES;
        return;
    }
    cout << YES;
}