けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 115 C - ℕ Coloring (茶色, 500 点)

AtCoder AtCoder500点 茶色diff 彩色問題 Dilworthの定理 DAG 最大安定集合問題 数学(整数問題) クリーク 最適化テク:自明な上界が最適解 素因数分解 mex グラフ 構築 どれか1つ求める 数列 復元 最大値の最小化 非自明な線形時間 ARC-C

これ茶色はさすがにびっくりした！

問題概要

整数 N が与えられる。

正の整数からなる数列 A_{1}, \dots, A_{N} であって、

  • i が j の約数であるような任意の i, j に対して A_{i} \neq A_{j}

という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるようなものを一つ求めよ。

考えたこと

たとえば N = 24 のとき、1, 2, 4, 12, 24 というように、隣接する二要素が約数倍数関係であるようなものをとってくると、どの 2 つも約数倍数であるようになっている。

つまりこの場合、

  • A_{1} = 1
  • A_{2} = 2
  • A_{4} = 3
  • A_{12} = 4
  • A_{24} = 5

というように、絶対に「5」までは必要になるのだ。

一般に、 N 以下の整数のうち、「素因数分解したときの指数の和の最大値 + 1」だけの値までは必ず必要になることが示せる。たとえば

24 = 2^{3} \times 3^{1}

なので、24 を含むなら 3 + 1 + 1 = 5 までは必ず必要というわけだ。

十分性

逆に、 N 以下の整数のうち、「素因数分解したときの指数の和の最大値 + 1」が答えとなるような数列を具体的に作ることもできる。

具体的には、各 n に対して

としてあげれば、条件を満たすことになる！！！

p が q の約数であるとき、 p を素因数分解したときの指数の和は、 q を素因数分解したときの指数の和よりも真に小さいことからわかる。

コード

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

int main() {
    auto calc = [&](long long n) -> long long {
        long long res = 1;
        if (n == 1) return res;
        for (long long p = 2; p * p <= n; ++p) {
            while (n % p == 0) {
                ++res;
                n /= p;
            }
        }
        if (n > 1) ++res;
        return res;
    };
    
    int N;
    cin >> N;
    for (long long n = 1; n <= N; ++n) cout << calc(n) << " ";
    cout << endl;
}