我的算法书 - Sherlock and his girlfriend

这份题目的解析侧重于数论逻辑和贪心策略。虽然题目看起来像是复杂的图论（图着色问题），但实际上它的核心数学规律非常简单。

以下是针对 CF776B Sherlock and his girlfriend 的详细解析：

1 题目核心翻译

题目给定 $n$ 个珠宝，价格分别是 $2, 3, 4, \dots, n+1$ 。 约束条件：如果珠宝 A 的价格是珠宝 B 的价格的素因子（质因子），那么 A 和 B 的颜色必须不同。目标：用最少的颜色数量给所有珠宝上色。

2 数学规律分析

我们需要分析数字之间的冲突关系。

质数（Prime）的性质：质数没有除 1 和自身以外的因子。因此，一个质数不可能拥有另一个（不等于它自身的）质因子。 $\rightarrow$ 结论：任意两个质数之间不会产生冲突。我们可以把所有的质数染成同一种颜色（比如颜色 1）。
合数（Composite）的性质：合数一定可以分解质因数。也就是说，合数一定有至少一个质因子。例如： $6$ 的质因子是 $2, 3$ ； $4$ 的质因子是 $2$ 。根据题目规则，合数必须和它的质因子颜色不同。既然我们将质数染成了颜色 1，那么合数必须染成颜色 2。
合数与合数之间会冲突吗？ 题目说：“当一件珠宝的价格是另一件珠宝的价格的素因子时…”。合数本身不是素数（质数），所以合数永远不可能充当“素因子”的角色。 $\rightarrow$ 结论：任意两个合数之间不需要根据此规则区分颜色。所有的合数都可以染成同一种颜色（比如颜色 2）。

3 最终策略

基于以上分析，我们只需要两种颜色就足够解决绝大多数情况：

颜色 1：分配给所有质数。
颜色 2：分配给所有合数。

验证逻辑：

质数 vs 质数：无冲突（颜色相同）。
合数 vs 合数：无冲突（颜色相同）。
质数 vs 合数：如果质数 $P$ 是合数 $C$ 的因子，它们颜色不同（ $1 \neq 2$ ）。符合规则。

4 特殊边界情况（坑点）

虽然理论上最多需要 2 种颜色，但我们需要考虑 $n$ 特别小的情况：

当 $n=1$ 时：价格序列为 $\{2\}$ 。只有一个质数，没有合数。只需要 1 种颜色。
当 $n=2$ 时：价格序列为 $\{2, 3\}$ 。两个都是质数，互不冲突。只需要 1 种颜色。
当 $n \ge 3$ 时：价格序列为 $\{2, 3, 4, \dots\}$ 。出现了合数 $4$ 。此时必须使用 2 种颜色。

5 算法实现思路

由于数据范围是 $n \le 100,000$ ，我们需要一种快速的方法来判断每个数是质数还是合数。

埃氏筛法（Sieve of Eratosthenes） 是最佳选择：

建立一个布尔数组或标记数组 del[]，初始化为 0（假设都是质数）。
从 2 开始遍历到 $n+1$ 。
如果当前数 $i$ 是质数（del[i] == 0）：
- 将它的所有倍数（ $2i, 3i, 4i \dots$ ）标记为合数（del[j] = 1）。
最后输出时：
- 如果 del[i] == 0（质数），输出 1。
- 如果 del[i] == 1（合数），输出 2。

6 复杂度分析

时间复杂度：埃氏筛法的时间复杂度是 $O(N \log \log N)$ ，对于 $10^5$ 的数据量，这几乎是线性的，运行非常快（远小于 1 秒）。
空间复杂度： $O(N)$ ，需要一个数组存储标记。

7 代码

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

        #include <bits/stdc++.h>
using namespace std;
typedef  long long ll;

const int maxn = 1e5+5;
int del[maxn];
int n;

int main (int argc, char *argv[]) {
    std::cin >> n;
    n++;

    for(int i = 2;i<=n;i++) {

        if( del[i] == 0) {
            // std::cout << i << "\n";

            if( i > n / i ) continue;

            for(int j = i * i; j <=n;j +=i) {
                del[j] = 1;
            }
        }
    }
    // std::cout << "-----------"<< "\n";

    if( n <=3) {
        cout <<  1 << endl;
    }
    else 
        cout << 2 << endl;

    for(int i = 2;i<=n;i++) {

        if( del[i] == 0) {
            std::cout << 1 << " ";
        }
        else {
            std::cout << 2 << " ";
        }
    }
    
    return 0;
}

目录