博客

题目

题意翻译

将1到n分成若干组数，要求每组数的和均为质数，若存在一种分配方式，输出每个数所在的组的编号，有多组解输出任意一组解，若不存在，输出-1

感谢@he_____he 提供的翻译

题目描述

In Berland prime numbers are fashionable — the respectable citizens dwell only on the floors with numbers that are prime numbers. The numismatists value particularly high the coins with prime nominal values. All the prime days are announced holidays!

Yet even this is not enough to make the Berland people happy. On the main street of the capital stand n n houses, numbered from 1 to n n . The government decided to paint every house a color so that the sum of the numbers of the houses painted every color is a prime number.

However it turned out that not all the citizens approve of this decision — many of them protest because they don’t want many colored houses on the capital’s main street. That’s why it is decided to use the minimal possible number of colors. The houses don’t have to be painted consecutively, but every one of n n houses should be painted some color. The one-colored houses should not stand consecutively, any way of painting is acceptable.

There are no more than 5 hours left before the start of painting, help the government find the way when the sum of house numbers for every color is a prime number and the number of used colors is minimal.

输入输出格式

输入格式：

The single input line contains an integer n n ( 2<=n<=6000 2<=n<=6000 ) — the number of houses on the main streets of the capital.

输出格式：

Print the sequence of n n numbers, where the i i -th number stands for the number of color for house number i i . Number the colors consecutively starting from 1. Any painting order is allowed. If there are several solutions to that problem, print any of them. If there’s no such way of painting print the single number -1.

输入输出样例

输入样例#1：

8

输出样例#1：

1 2 2 1 1 1 1 2

思路

每个大于2的偶数可以拆成两个质数之和

我们首先算出1-n的和m=(n+1)*n/2

然后分三种情况

１．m本身是质数，那么所有的屋子可以刷同一颜色

２．m是偶数，那么所有屋子最少刷两种颜色，我们可以O(n)的找到哪一间屋子需要刷第二种颜色

３．m是奇数，如果可以拆成一个２和一个奇质数的形式，就只需要两种颜色；否则我们将m减去３，然后此时mm一定是偶数，我们再用讨论二即可

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int _=6005;
inline int read()
{
    char ch='!';int z=1,num=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')z=-1,ch=getchar();
    while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
    return z*num;
}
int n,ans[_];
void Print()
{
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
    puts("");
}
bool check(int x)
{
    int q=sqrt(x);
    for(int i=2;i<=q;++i)
        if(!(x%i))return 0;
    return 1;
}
int main()
{
    n=read();
    int m=(n+1)*n/2;
    for(int i=1;i<=n;++i)ans[i]=1;
    if(check(m)){Print();return 0;}
    if(m&1&&!check(m-2))ans[3]=3,m-=3;
    for(int i=2;i<=n;++i)
        if(check(i)&&check(m-i))
        {ans[i]=2;break;}
    Print();
    return 0;
}