Đếm số màu tối thiểu để tô mảng thỏa mãn điều kiện chia hết bằng C++

Mô tả bài toán

Cho mảng A n phần tử. Tô màu các phần tử sao cho: với mỗi màu, mọi phần tử có màu đó đều chia hết cho phần tử nhỏ nhất của màu đó. Tối thiểu số màu.

Ví dụ

A = [10,2,3,5,4,2] → Output: 3. (Màu 1: 10,5; Màu 2: 3; Màu 3: 2,4,2).

Thuật toán

Sắp xếp mảng. Duyệt từ nhỏ đến lớn: nếu phần tử hiện tại không chia hết cho bất kỳ phần tử nào trước đó (đã được gán màu) thì cần màu mới. Đếm số lần cần màu mới.

Code C++

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

int solve(vector<int> A) {
    sort(A.begin(), A.end());
    int ans = 0;
    for (int i = 0; i < (int)A.size(); i++) {
        int ok = 1;
        for (int j = 0; j < i; j++) {
            if (A[i] % A[j] == 0) {
                ok = 0;
                break;
            }
        }
        ans += ok;
    }
    return ans;
}

int main() {
    vector<int> A = {10,2,3,5,4,2};
    cout << solve(A) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: {10,2,3,5,4,2}

Output: 3