题面描述

在疫情过后，希望小学的三年二班重新开学。班级任务是将黑板上的 $N$ 个正整数分别上色。为了使黑板报美观且有学习意义，老师规定同种颜色的所有数必须能被该颜色中最小的数整除。你需要计算出最少需要多少种颜色来完成这个任务。

思路

从小到大排序后直接枚举一遍即可，将$n$个数划分为若干子集，标准是是否都能被各自子集的最小整数整除。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N; // 输入数字个数
    vector<int> nums(N);
    for (int i = 0; i < N; ++i) {
        cin >> nums[i]; // 输入每个正整数
    }

    sort(nums.begin(), nums.end()); // 将数字排序
    vector<bool> colored(N, false); // 记录数字是否已上色
    int colors = 0; // 记录颜色种类数量

    for (int i = 0; i < N; ++i) {
        if (!colored[i]) { // 如果当前数字未上色
            colors++; // 增加颜色计数
            for (int j = i; j < N; ++j) {
                if (nums[j] % nums[i] == 0) { // 如果能被最小数字整除
                    colored[j] = true; // 上色
                }
            }
        }
    }

    cout << colors << endl; // 输出结果
    return 0;
}

python

def min_colors(nums):
    nums.sort()  # 对数字进行排序
    colored = [False] * len(nums)  # 记录数字是否已上色
    colors = 0  # 记录颜色种类数量

    for i in range(len(nums)):
        if not colored[i]:  # 如果当前数字未上色
            colors += 1  # 增加颜色计数
            for j in range(i, len(nums)):
                if nums[j] % nums[i] == 0:  # 如果能被最小数字整除
                    colored[j] = True  # 上色

    return colors  # 返回结果

# 输入处理
N = int(input())
nums = list(map(int, input().split()))
print(min_colors(nums))  # 输出结果

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 输入数字个数
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = scanner.nextInt(); // 输入每个正整数
        }

        Arrays.sort(nums); // 将数字排序
        boolean[] colored = new boolean[N]; // 记录数字是否已上色
        int colors = 0; // 记录颜色种类数量

        for (int i = 0; i < N; i++) {
            if (!colored[i]) { // 如果当前数字未上色
                colors++; // 增加颜色计数
                for (int j = i; j < N; j++) {
                    if (nums[j] % nums[i] == 0) { // 如果能被最小数字整除
                        colored[j] = true; // 上色
                    }
                }
            }
        }

        System.out.println(colors); // 输出结果
        scanner.close();
    }
}

题目描述

疫情过后，希望小学终于又重新开学了，三年二班开学第一天的任务是将后面的黑板报重新制作。

黑板上已经写上了 $N$ 个正整数，同学们需要给这每个数分别上一种颜色。

为了让黑板报既美观又有学习意义，老师要求同种颜色的所有数都可以被这种颜色中最小的那个数整除。

现在请你帮帮小朋友们，算算最少需要多少种颜色才能给这 $N$ 个数进行上色。

输入描述 第一行有一个正整数 $N$，其中。

第二行有 $N$ 个 $int$ 型数(保证输入数据在 $[1,100]$ 范围中)，表示黑板上各个正整数的值。

输出描述

输出只有一个整数，为最少需要的颜色种数。

样例1

输入

3
2 4 6

输出

1

说明

所有数都能被 $2$ 整除

样例2

输入

4
2 3 4 9

输出

2

说明

$2$ 与 $4$ 涂一种颜色，$4$ 能被 $2$ 整除；

$3$ 与 $9$ 涂另一种颜色，$9$ 能被 $3$ 整除。

不能 $4$ 个数涂同一个颜色，因为 $3$ 与 $9$ 不能被 $2$ 整除。

所以最少的颜色是两种。