Editorial for Tô màu số học

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Khi biểu diễn dãy số thành một đồ thị một chiều, với mỗi phần tử là một node và cạnh ~(u, v)~ biểu diễn cho quan hệ ~v~ chia hết cho ~u~, ta sẽ nhận thấy độ cao của đồ thị, hay là đường đi dài nhất trong đồ thị, sẽ là đáp án của đề bài dựa trên định lý Dirichlet.

image

Đây cũng là nền tảng cho Định lý Dilworth.

#include <bits/stdc++.h>

using namespace std;

template<typename T>
void println(vector<T> v) {
    for(int x: v) {
        cout << x << " ";
    }
    cout << endl;
}

template<typename... Args>
void println(Args... args) {
    (cout << ... << args) << endl;
}

void solve() {
    int n; cin >> n;

    vector<int> c(n, -1);

    int cnt = 0;
    int sum = 0;
    while (sum < n) {
        int k = 1<<cnt;
        for(int i = sum; i < min(n, sum+k); ++i) {
            c[i] = cnt+1;
        }
        sum += k;
        cnt++;
    }

    println(cnt);
    println(c);
}

int main() {
    int n_test;
    cin >> n_test;

    for(int i_test = 1; i_test <= n_test; ++i_test) solve();

    return 0;
}

Comments

Please read the guidelines before commenting.


  • -2
    trankhvan  commented on June 1, 2026, 12:08 p.m. ← edited

    https://ideone.com/aV7zve