题解

题目描述

小红需要构造一个长度为 $n$ 的数组，数组中的每个元素 $a_i$ 满足 $1 \leq a_i \leq n$。要求任意两个下标 $i$ 和 $j$（$i \neq j$ 且 $\gcd(i, j) \neq 1$）对应的元素 $a_i$ 和 $a_j$ 必须不同。求数组中最少需要多少种不同的数字。

解题思路

问题本质分析
我们需要确保所有满足 $\gcd(i, j) \neq 1$ 的不同下标 $i$ 和 $j$ 对应的元素不同。这可以转化为一个图着色问题，其中每个下标是一个节点，两个节点之间有边当且仅当它们的 $\gcd$ 不为 1。目标是最小化使用的颜色种类数，即图的色数。

关键观察
最大的颜色需求来源于偶数下标。所有偶数下标构成的集合中，任意两个下标的 $\gcd$ 至少为 2，因此这些下标必须使用不同的颜色。最大的偶数集合的大小为 $\lfloor \frac{n}{2} \rfloor$。其他下标（如奇数）可以通过合理分配颜色避免冲突，因为它们的 $\gcd$ 可能为 1。

结论
当 $n = 1$ 时，唯一元素无需考虑其他下标，直接输出 1。
当 $n > 1$ 时，最少需要的颜色种类数为 $\lfloor \frac{n}{2} \rfloor$。

代码实现

C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << 1 << endl;
    } else {
        cout << n / 2 << endl;
    }
    return 0;
}

Python

n = int(input())
print(1 if n == 1 else n // 2)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if (n == 1) {
            System.out.println(1);
        } else {
            System.out.println(n / 2);
        }
    }
}

题目内容

小红想构造一个长度为 $n$ 的数组 {$a_1,a_2,....,a_n$}，其中 $a_i$ 满足 $1≤ a_i ≤ n$ ，$[1,n]$ 的每个数字可以重复使用也可以不用。

她希望任意两个索引 $i,j$ 满足 $(i≠j$ 且 $gcd(i,j)≠1)$ 时，其两个位置的权值不相等，即 $a_i ≠ a_j$ ，请你帮助小红判断最少需要多少种不同的数字。

输入描述

一个整数 $n(1 ≤ n ≤ 10^9)$ ，表示小红希望你构造的数组长度。

输出描述

一个整数，表示数组中不同数字的个数的最小值。

样例1

输入

3

输出

1

说明

数组下标依次为 $[1,2,3]$ ，对于任意的两个索引 $i,j(i ≠ j)$ 都满足 $gcd(i,j) = 1$ ，所以我们可以只使用 $2$ 来填数组 ，为 $[2,2,2]$，当然 $[1,1,1]$ 或者 $[3,3,3]$ 也是正确的。

样例2

输入

4

输出

2