夏洛克和他的女朋友

girlfriend

题面翻译

题目描述

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

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

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

输入输出格式：

输入格式：

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

输出格式

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

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

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

样例 #1

样例输入 #1

3

样例输出 #1

2
1 1 2

样例 #2

样例输入 #2

4

样例输出 #2

2
2 1 1 2

说明与提示

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

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

Translated by @皎月半洒花。

思路

如果是把每个数都当作一个点， 当一个数是另一个数的质因数时候就连一条边， 求一种染色方案使得存在边的两个点颜色不同， 是一个较难的图论问题。

考虑挖掘一下特殊性质： 2 3 4 5 6 7 8 9 10 连边只可能是 质数—合数， 也就是说该图是而二分图， 那么最多染两个颜色就行。

若都是质数就染一个颜色， 即有质数又有合数就染两个颜色， 只有合数也是染一个颜色。

那么就先埃氏筛打一个素数表， 然后O(1)判断就行。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int primes[N], cnt;
int res[N];
bool st[N], isprime[N];
 
 
void init()
{
    for(int i = 2; i < N; i++)
    {
        if(!st[i])
        {
            primes[cnt++] = i;
            st[i] = true;
            isprime[i] = true;
        }
        for(int j = 0; primes[j] * i < N; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
 
int main()
{
    init();
    int n;
    cin >> n;
    if(n >= 3) cout << 2 << endl;
    else cout << 1 << endl;
    
    for(int i = 1; i <= n; i++)
        if(isprime[i + 1])
            cout << 1 << " ";
        else cout << 2 << " ";
    return 0;
}