牛客多校3
H
思路
这里涉及了哥德巴赫猜想
需要知道的知识:哥德巴赫猜想
哥德巴赫猜想的现代陈述为:任一大于5的整数都可写成三个质数之和。
由此可以得到两种情况:
1.强哥德巴赫猜想(强哥猜):即任一大于2的偶数都可写成两个质数之和;(未被证明,但是同时也没有被推翻,即在本题的范围内强哥猜成立)
2.弱哥德巴赫猜想(弱哥猜):任何一个大于5的奇数都能被表示成三个奇质数的和。(一个质数可以被多次使用);(已经被证明)
我们可以用强哥猜和弱哥猜来判断所给的数组是否符合条件
n>2&&sum>=2*n时
-
当数组的和为sum和且数组的个数为奇数时
我们可以将当前的 sum 分配出一个3,这样就改变了 sum的奇偶性,而且剩余分配个数就变为偶数了,那么接下来我们不断分配2, 知道剩余个数为2时,此时sum也依旧是偶数(因为不断分配偶数2,sum依旧还是偶数) 可以用强哥猜分配
-
数组的和为sum为奇数,数组个数为偶数时
我们可以用弱哥猜,不断分配2,知道数组个数为3时,用弱哥猜,将剩下的值变为3个奇质数
-
当数组和sum为偶数时,数组个数为偶数
类似情况1,我们可以直接分配2,知道剩余分配个数为2时,我们可以用强哥猜,将sum直接分解为两个质数
-
当数组和sum为偶数,数组个数为奇数时
我们可以分配出一个3,将sum变为奇数,数组待分配个数变为偶数,接下来可以类似情况2操作即可
所以在(sum >= 2*n&&n>2时) 我们总可以构造出符合条件的数组
在n==1时 直接判断是否为质数
在n==2时 如果sum为偶数,直接强哥猜分解,奇数时可以分配成2 和另一个质数
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int dive(ll x)
{
if(x<2) return 0;
for(ll i =2; i<=x/i;i++)
{
if(x%i==0) return 0;
}
return 1;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin>>n;
ll sum = 0;
for(int i = 1;i<=n;i++)
{
int x;
cin>>x;
sum+=x;
}
//sum-=2*n;
//cout<<sum<<endl;
if(sum<2*n) cout<<"No\n";
else
{
if(n==1)
{
if(dive(sum)) cout<<"Yes\n";
else cout<<"No\n";
}
else if(n==2)
{
if(sum%2)
{
if(dive(sum-2)) cout<<"Yes\n";
else cout<<"No\n";
}
else
{
cout<<"Yes\n";
}
}
else cout<<"Yes\n";
}
}