C - N Coloring

题意

整数 $N$ が与えられます。以下の条件を満たす長さ $N$ の正の整数の列 $A_1,A_2,\ldots,A_N$ であって、数列に現れる値の最大値が最小になるものを一つ出力してください。

• $i$ が $j$ の約数ならば、$A_i\neq A_j$ ($1\le i<j\le N$)

解析

令 $f(n)$ 表示 $n$ 的所有素因数的指数和，由于对于任何 $i\mid j\land i\neq j$，都有 $f(j)>f(i)$，则 $a_i=f(i)+1$ 是一组合法的构造。在这样的构造中出现的最大数为 $\lfloor\log_2N\rfloor+1$。由于 $2,4,8,16\ldots$ 等 $2$ 的整次幂都要分配不同的数，则也不存在比该构造更优的解。

由于 $f(i)=\max\limits_{d\mid i}f(d)+1$，我们可以用每个 $i$ 去更新 $i$ 的倍数的 $f$ 的值，总复杂度为 $O(\frac{N}{1}+\frac{N}{2}+\frac N3+\ldots)=O(N\log N)$。

实现

#include <bits/stdc++.h>

int main(){
    int N; std::scanf("%d", &N);
    std::vector<int> f(N + 1);
    for(int i = 1; i <= N; ++i){
        ++f[i]; std::printf("%d ", f[i]);
        for(int j = i; j <= N; j += i)
            f[j] = std::max(f[j], f[i]);
    }
    return 0;
}

来源

AtCoder Regular Contest 115 C - N Coloring

评论