CodeForces776B Sherlock and his girlfriend

题目描述

Sherlock has a new girlfriend (so unlike him!). Valentine’s day is coming and he wants to gift her some jewelry.
He bought $n$ pieces of jewelry. The $i$ -th piece has price equal to $i+1$, that is, the prices of the jewelry are $2,3,4,… n+1 $ .
Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don’t have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used.
Help Sherlock complete this trivial task.

输入输出格式

输入格式

The only line contains single integer $n $ $(1<=n<=100000)$ — the number of jewelry pieces.

输出格式

The first line of output should contain a single integer $k $ , the minimum number of colors that can be used to color the pieces of jewelry with the given constraints.
The next line should consist of $n$space-separated integers (between $1$ and $k$ ) that specify the color of each piece in the order of increasing price.
If there are multiple ways to color the pieces using $k$ colors, you can output any of them.

INPUT & OUTPUT’s examples

Input’s eg #1

Output’s eg #1

1
2

2
1 1 2

Input’s eg #2

Output’s eg #2

1
2

2
2 1 1 2

说明

In the first input, the colors for first, second and third pieces of jewelry having respective prices 2
3 and 4 are 1 , 1 and 2 respectively.
In this case, as 2 is a prime divisor of 4 , colors of jewelry having prices 2 and 4 must be distinct.

题意翻译

自己看原链接傲娇脸。

分析

裸的二分图染色应用对吧。

不了解二分图染色算法的推荐看一下HandwerSTD的讲解。

把题意简化一下就是，在一张图上有$n$个点，标号$2…n+1$,给这些点染色，要求若$x$是$y$的素因数，则$x$和$y$的颜色不同，求一种染色最少的方案。

注意：
1.这是一张二分图，一边是素数，一边是和数。
2.把所有素数染成$1$,所有合数染成$2$即可。

这里判断的素数的方式是埃拉托斯特尼筛法，基本思想是素数的倍数一定不是素数。

实现：用一个$bool$数组存储对于数的判定情况，先假设所有数都是素数，从第一个素数2开始，把2的倍数都设置为非素数，然后是2后面的素数3，进行同样处理。

时间复杂度：$$ O ( \sum_{p}^{n-1} \frac np )$$

代码

/* Headers */
#include<cstdio>
#include<cctype> 
#include<cstring>
#include<cmath>
/* define */
const int MAXN = 1e6+10;
using namespace std;
namespace FastIO{
    const int BUFSIZE=(1<<20);
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void write(int x){
    	if(x<0) putchar('-'),x=-x;
    	if(x>9) write(x/10);
    	putchar(x%10+'0');
    }
    inline void space(int x){
        if(x!=0) putchar(' ');
        else putchar('\n');
    }
} 
using namespace FastIO;
/* definitions */
int n;
bool f[MAXN];
/* functions */
inline void init(){
	scanf("%d",&n);
	memset(f,0,sizeof(f));
	f[0]=1;f[1]=1;
	for(register int i=2;i*i<=n+1;i++){
		if(!f[i]){
			for(register int j=2*i;j<=n+1;j+=i){
				f[j]=1;
			}
		}
	} 
}
inline void work(){
	init();
	if(n<3)puts("1");
	else puts("2");
	for(register int i=2;i<=n+1;i++){
		printf("%d ",f[i]+1);
	}
}
int main(int argc,char *argv[]){
	work();
	return 0;
}