【Codeforces 665D. Simple Subset】思维题

Simple Subset

题目链接：

https://codeforces.com/contest/665/problem/D

Description

Input

Output

Sample Input

2
2 3

Sample Output

2
2 3

题意

给你n个数字，在这n个数字中选择最多的数字，使这些数字中选择任意两个相加都是质数。

题解：

首先要发现如果选出的数中存在两个奇数或者两个偶数都是不行的，但是这里要特殊考虑1的情况。
那么答案就分为两种
第一种便是没有1的时候，答案最多为2，找是否存在两个数相加为质数即可。
第二种是包含1的情况，我们可以把所有的1放在答案中，之后看是否存在一个不是1的数与1相加为质数即可。
如果以上两种情况答案都是1，那么随便输出数组中的一个数即可。

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define dbg(x) cout<<#x<<" = "<<x<<endl
#define dbg2(x,x2) cout<<#x<<" = "<<x<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x,x2,x3) cout<<#x<<" = "<<x<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
typedef long long ll;
const int maxn =2e6+10;
int a[maxn];
int cnt[maxn];
int main()
{
    //freopen(".in","r",stdin);for(int i=1;i<=2000000;i++){
    for(int j=i;j<=2000000;j+=i){
    cnt[j]++;}}int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n);int sum=0,flag=0;;for(int i=1;i<=n;i++) if(a[i]==1) sum++;for(int i=1;i<=n;i++){
    if(a[i]!=1&&cnt[a[i]+1]==2) flag=i;}if(flag!=0) sum++;int sum2=0;for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    if(i==j) continue;if(cnt[a[i]+a[j]]==2) sum2=1;}}if(sum>2){
    printf("%d\n",sum);for(int i=1;i<=n;i++) if(a[i]==1) printf("1 ");if(flag!=0) printf("%d",a[flag]);}else if(sum2==1){
    printf("2\n");for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    if(i==j) continue;if(cnt[a[i]+a[j]]==2){
    printf("%d %d\n",a[i],a[j]);return 0;}}}}else{
    printf("1\n%d\n",a[1]);}return 0;
}