Sherlock and his girlfriend

Sherlock and his girlfriend

【问题描述】
N个点,标号2..n+1,给这些点染色,要求若a是b的素因子,则a和b的颜色不同,求一种颜色数最少的方案。
【输入格式】
一个整数n。
【输出格式】
第一行一个整数k,表示最少的染色数。第二行n个整数,表示2..n+1的点被染成的颜色。若有多种答案,输出任意一种。
【输入样例1】
3
【输出样例1】
2
1 1 2
【输入样例2】
4
【输出样例2】
2
1 1 2 1
【数据规模】
1 ≤ n ≤ 100000
限时1s,内存限制:256M
【算法分析】
注意到这是二分图,一边是素数,一边是合数,把素数都染成1,合数都染成2即可

Source

CF776B

信息

难度
7
分类
数学数论 点击显示
标签
递交数
20
已通过
8
通过率
40%
上传者

相关

在下列训练计划中:

素数的判定