2023牛客暑期多校训练营3 H题补题题解

#H题 Until the Blue Moon Rises

由哥德巴赫猜想可知：
1.对于一个大于5的数而言，可以将其分为三个质数之和。
2.对于一个大于2的偶数而言，可以将其分解为两个质数之和。
综合题目可知可以对其进行分类讨论得：
1.n=1时，特殊判定是否为质数。
2.n=2时，首先判断两数之和为质数还是偶数。
如果两数之和为偶数，且和为2，不成立；如果两数之和为偶数，且和大于2，成立。
如果两数之和为奇数，则必须为2，x-2的形式，所以要判断x-2是否为质数。
3.n>2时，使用哥德巴赫猜想就ok了。
下面小编呈上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,mod=1e9+7,R=1e6;
const int inf=1e9;

int isP(LL n){
    if(n<2)return 0;
    for(LL i=2;i*i<=n;i++){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}
void solve() {
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    LL sum=0;
    for(int i=0;i<n;i++)sum+=a[i];

    if(n==1){
        if(isP(sum)){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
    }else if(n==2){
        if(sum%2==0){
            if(sum==2)cout<<"No\n";
            else cout<<"Yes\n";
        }else{
            if(isP(sum-2))cout<<"Yes\n";
            else cout<<"No\n";
        }
    }else{
        if(sum-2*(n-3)>5)cout<<"Yes\n";
        else cout<<"No\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}