《CF776B Sherlock and his girlfriend》

题目描述

Sherlock 有一个新女朋友。现在情人节就要到了，他想送给她一些珠宝。

他买了几件首饰。第 i 件的价格等于 i+1，也就是说，珠宝的价格分别为 2,3,4,…,n+1 。

现在需要给这些珠宝首饰上色。当一件珠宝的价格是另一件珠宝的价格的素因子时，这两件的颜色就不允许相同。此外，要最少化使用的颜色数量。

输入格式

一行，包含单个整数 n(1≤n≤100000) 指珠宝的数量。

输出格式

第一行的输出包含一个整数 K，指最少颜色的颜色种类数。

第二行由 n 个整数（1 到 k）组成，按价格从小到大来表示每件珠宝的颜色。

如果有多种方法，则可以输出它们中的任何一种。

显示翻译

题意翻译

输入输出样例

输入 #1复制

3

输出 #1复制

2 1 1 2

输入 #2复制

4

输出 #2复制

2 2 1 1 2

说明/提示

在第一个样例中，第一、第二和第三件首饰的价格分别为 2、3、4,它们的颜色分别为 1 、1 和 2。

在这种情况下，由于 2 是 4 的因子，所以具有因数 2 和 4 的珠宝的颜色必须是不同的。

Translated by @皎月半洒花。

代码实现：

#include<bits/stdc++.h> using namespace std; int n, arr[100005]; bool vis[100005]; inline void gen() { for(int i=2; i<=n+1; ++i) { if(!vis[i]) { printf("%d ", 1); for(int j=i*2; j<=n+1; j+=i) vis[j] = 1; } else { printf("%d ", 2); } } return; } int main() { scanf("%d", &n); if(n-1 == 0) { printf("1\n1"); exit(0); } if(n-2 == 0) { printf("1\n1 1"); exit(0); } printf("2\n"); gen(); return 0; }