牛客多校3

牛客多校3

H

思路

这里涉及了哥德巴赫猜想

需要知道的知识：哥德巴赫猜想

哥德巴赫猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。

由此可以得到两种情况：

1.强哥德巴赫猜想（强哥猜）：即任一大于2的偶数都可写成两个质数之和；（未被证明，但是同时也没有被推翻，即在本题的范围内强哥猜成立）

2.弱哥德巴赫猜想（弱哥猜）:任何一个大于5的奇数都能被表示成三个奇质数的和。（一个质数可以被多次使用）;（已经被证明）

我们可以用强哥猜和弱哥猜来判断所给的数组是否符合条件

n>2&&sum>=2*n时

1. 当数组的和为sum和且数组的个数为奇数时

   我们可以将当前的 sum 分配出一个3,这样就改变了 sum的奇偶性,而且剩余分配个数就变为偶数了,那么接下来我们不断分配2, 知道剩余个数为2时,此时sum也依旧是偶数(因为不断分配偶数2,sum依旧还是偶数) 可以用强哥猜分配

2. 数组的和为sum为奇数,数组个数为偶数时

   我们可以用弱哥猜,不断分配2,知道数组个数为3时,用弱哥猜,将剩下的值变为3个奇质数

3. 当数组和sum为偶数时,数组个数为偶数

   类似情况1,我们可以直接分配2,知道剩余分配个数为2时,我们可以用强哥猜,将sum直接分解为两个质数

4. 当数组和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";
	}
	
}