355. Numbers Painting
Time limit per test: 0.25 second(s)Memory limit: 65536 kilobytes
input: standardoutput: standard
Dr. Vasechkin wants to paint all numbers from 1 toNin such a way that if numberAis divisible by numberB, numbersAandBhave different colors.Help Dr. Vasechkin to find such a painting, where the number of the colors used is minimal.
Input
The input contains integer numberN().
Output
Write the number of the colorsMin the desired painting in the first line of the output. In the second line of the output write the desired painting of numbers from 1 toN. The used colors should be represented by numbers from 1 toM. If there are several solutions, choose any of them.
Example(s)
sample inputsample output
1241 2 2 3 2 3 2 4 3 3 2 4
Online ContesterTeam 2002 – 2010. All rights reserved.
思路：给1到N的数字涂颜色，使得颜色数尽可能少，贪心…..
首先可以看出1可以整除任何数，即任何数都不可以与1相同颜色，然后可以发现互质的一群数可以相同颜色，而当两个数有大于1的约数时可以判断这两个数不同颜色，慢慢可以看出1,2,4,8,16,32……这些数的颜色都不一样，到32为止有6种颜色，可以验证是最小的颜色种类使用数，于是归纳出解决方案为一个筛法（与素数筛类似，具体看代码）
注意打印数字颜色的方法，对于数字i，从i~n*i(n*i为小于N的最大数),对于每个区间（m， m*2-1）取一种颜色（m为i的倍数）…….（自己想想为什么，有别的好的想法可以讨论）
AC代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int color[10005];int main() {int N;while(scanf("%d", &N) != EOF) {int ans = 1;for(int i = 2; i <= N / 2 + 1; i++) {//算出最小的颜色种类数int tmp = 1;for(int j = i; j <= N; j *= 2) {tmp++;}if(tmp > ans) ans = tmp;}memset(color, 0, sizeof(color));//记录每个数字的颜色 color[1] = 1;for(int i = 2; i <= N; i++) {if(color[i] == 0) {int c = 2;int t = i;for(int j = i; j <= N; j += i) {if(j >= t * 2) c++, t *= 2;color[j] = c;}}}printf("%d\n", ans);//输出结果 for(int i = 1; i < N; i++) printf("%d ", color[i]);printf("%d\n", color[N]);}return 0;}
，不要害怕错过什么，因为在路上你就已经收获了自由自在的好心情。
