洛谷 CF776B & LOJ 10201 -「一本通 6.2 练习 4」Sherlock and His Girlfriend

题面

题目传送门

Sherlock 有了一个新女友(这太不像他了!)。情人节到了,他想送给女友一些珠宝当做礼物。

他买了 $n$ 件珠宝。第 $i$ 件的价值是 $i+1$ 。那就是说,珠宝的价值分别为 $2,3,4,.. ,n+1$ 。

Watson 挑战 Sherlock,让他给这些珠宝染色,使得一件珠宝的价格是另一件的质因子时,两件珠宝的颜色不同。并且,Watson 要求他最小化颜色的使用数。

请帮助 Sherlock 完成这个简单的任务。

输入格式

只有一行一个整数 $n$,表示珠宝件数。

输出格式

第一行一个整数 $k$,表示最少的染色数;
第二行 $n$ 个整数,表示第 $1$ 到第 $n$ 件珠宝被染成的颜色。若有多种答案,输出任意一种。

思路

对于这一段区间内的所有合数,他们一定不互为质因子(都不是质数了当然不互为质因子),所以只需要把区间内的质数全部染上一种颜色,合数染上另一种颜色,只需 2 种颜色。

注意:当 $n<=2$ 时,只需要一种颜色,所以要特判。

代码

暂无评论

发送评论


				
上一篇
下一篇