「一本通 6.2 练习 4」Sherlock and His Girlfriend

题目描述

Sherlock 买了 $n$ 件珠宝，第 $i$ 件的价值是 $i+1$ ，即价值分别为 $2,3,4,\cdots,n+1$ 。他要给珠宝染色，使得一件珠宝的价值是另一件的质因子时，两件珠宝颜色不同，并最小化使用的颜色数。输入：一行一个整数 $n$ 。输出：第一行一个整数 $k$ 表示最少染色数；第二行 $n$ 个整数表示第 $1$ 到第 $n$ 件珠宝的颜色。若有多种答案，输出任意一种。 样例输入：3。 样例输出：

text

1
22
1 1 2

数据范围： $1 \leqslant n \leqslant 10^5$ 。

思路

一件珠宝是质因子时它本身必是质数，而被整除的一方必是合数，所以冲突只发生在「质数—合数」之间：质数全涂颜色 1、合数全涂颜色 2 即合法。 $n \leqslant 2$ 时价值只有 $2,3$ ，没有冲突边，答案为 1； $n \geqslant 3$ 时 $2$ 与 $4$ 冲突，答案必为 2。因此只需用埃氏筛标记 $[2, n+1]$ 内的质数即可。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 22:43
# update_at: 2026-09-30 22:43

import sys
from math import isqrt

COLOR_PRIME = 1  # 珠宝价值本身是质数时用的颜色
COLOR_COMPOSITE = 2  # 珠宝价值是合数时用的颜色


def prime_table(limit: int) -> bytearray:
    """table[m] == 1 表示 m 是质数，覆盖 0 到 limit。

    埃氏筛：p 只需扫到 sqrt(limit)，命中质数时把它从 p*p 起的倍数整片涂 0
    （整片切片赋值，不在 Python 层写内层循环）。
    """
    table = bytearray(b"\x01") * (limit + 1)
    table[0:2] = b"\x00\x00"
    for p in range(2, isqrt(limit) + 1):
        if table[p]:
            table[p * p :: p] = bytes(len(range(p * p, limit + 1, p)))
    return table


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 输入只有一行一个整数
    table = prime_table(n + 1)

    # 第 i 件珠宝的价值是 v = i + 1：质数涂 1 号色，合数涂 2 号色。
    colors = [COLOR_PRIME if table[v] else COLOR_COMPOSITE for v in range(2, n + 2)]

    # v = 2 与 v = 4 同色会冲突（2 是 4 的质因子），所以 n >= 3 时两种颜色都在用。
    count = 2 if n >= 3 else 1

    print(count)
    print(*colors)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:25
 * update_at: 2026-10-06 01:25
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 100005;

int n;
bool is_composite[MAXN]; // is_composite[v] = true 表示 v 是合数（筛掉的数）
int color[MAXN];         // color[i] = 第 i 件珠宝（价值 i+1）的颜色

// 埃氏筛：把 [2, n+1] 里的合数标记出来
void sieve() {
    for (ll p = 2; p * p <= n + 1; p++) {
        if (!is_composite[p]) {
            // 从 p*p 开始划掉，更小的倍数已被更小的质数处理过
            for (ll v = p * p; v <= n + 1; v += p) {
                is_composite[v] = true;
            }
        }
    }
}

int main() {
    scanf("%d", &n);

    sieve();

    // 冲突边只存在于质数与它的倍数之间：质数涂 1，合数涂 2
    // n <= 2 时价值只有 2,3，没有冲突边，全部涂 1，答案为 1
    int k = 1;
    for (int i = 1; i <= n; i++) {
        int v = i + 1;
        if (v >= 4 && is_composite[v]) { // 价值 2,3 是质数，直接涂 1
            color[i] = 2;
            k = 2;
        } else {
            color[i] = 1;
        }
    }

    printf("%d\n", k);
    for (int i = 1; i <= n; i++) {
        printf("%d%c", color[i], i == n ? '\n' : ' ');
    }
    return 0;
}

「一本通 6.2 练习 4」Sherlock and His Girlfriend

目录

题目描述

思路

参考代码