H - 花心的hjh
题目描述
hjh有了新女友。情人节就要到了,他想送她一些珠宝。
他买了 $n$ 件珠宝。第 $i$ 件的价格等于 $i$ $+$ $1$ ,即首饰的价格为 $2$ , $3$ ,$4$ ,… $n$ $+$ $1$ 。sls给hjh出了一个难题,让他给这些珠宝上色,如果其中一件的价格是另一件价格的素因子,那么这两件的颜色就不能一样了。此外,sls要求他尽量减少不同颜色的使用数量。
请你帮hjh完成这个艰巨的任务。
输入格式
仅一行,$1$ 个整数 $n$ —— 首饰件数。
输出格式
第一行为一个整数k,即在给定约束条件下可用于为珠宝着色的最小颜色数。
第二行由 $n$ 个整数( $1$ 到 $k$ 之间)组成,它们 $1$ − $n$ 的顺序指定每件物品的颜色。如果有多种方法可以使用 $k$ 种颜色为这些珠宝上色,则只需输出其中的任何一种。
样例 #1
样例输入 #1
3
样例输出 #1
2
1 1 2
样例 #2
样例输入 #2
4
样例输出 #2
4
2 1 1 2
思路:线性筛素数的实际应用
线性筛素数见 https://www.acwing.com/blog/content/38968/
显然,对于素数价值与素数价值的珠宝之前,显然一个不可能是另一个的素因子,所有素数价值的珠宝可以涂一个颜色
而对于其他的合数价值的珠宝,其价值本身就不是素数,故所有合数价值的珠宝可以涂一个颜色
所以我们只需用到两个颜色, 而对素数价值的珠宝输出 $1$, 对于合数价值的珠宝输出 $2$
我的码码
#include<iostream>
#include<cstring>
#include<map>
const int N = 1e5 + 10;
using namespace std;
bool a[N];
int n;
int zmc[N];
int sum[N];
void fghjh(int n)
{
int hhhjh = 0;
memset(a, 1, sizeof(a));
for (int i = 2; i <= n; i++)
{
if (a[i])
hhhjh++, zmc[hhhjh] = i;
for (int j = 1; (i * zmc[j]) <= n && j <= hhhjh; j++)
{
a[zmc[j] * i] = 0;
if (i % zmc[j] == 0)
break;
}
}
}
int main()
{
cin >> n;
fghjh(n + 1);
if (n <= 2)
cout << 1 << endl;
else
cout << 2 << endl;
for (int i = 2; i <= n + 1; i++)
{
if (a[i])
cout << "1 ";
else
cout << "2 ";
}
return 0;
}