Codeforces Round #632 (Div. 2) F. Kate and imperfection

問題概要

正整数 $n$ が与えられ、集合 $S = \lbrace 1, 2, ..., n\rbrace$ と定める。要素数2以上である $S$ の部分集合 $s$ について、 $f(s)$ の値を「 $s$ に含まれる相異なる2要素 $a, b$ に対する $\gcd(a, b)$ の最大値」と定める。

$k=2, ..., n$ に対して、要素数が $k$ である $S$ の部分集合 $s$ についての $f(s)$ の最小値を求めよ。

制約

$2 \le n \le 5\times 10^{5}$

解法

色々考え方があるとは思いますが、まずは $s$ として考えるべきものの範囲を絞ります。

仮に集合 $s$ にある値 $x$ が含まれず、かつ $x$ の倍数 $cx$ が含まれているとします。このとき $cx$ を $x$ に置き換えると、要素数は変わらず、 $f(s)$ の値は変わらないか減少します。

この置き換え操作を有限回繰り返すと、 $f(s)$ を増やすことなく、このような $x, cx$ の組が存在しないような集合に変換することができます。つまり考えるべき $s$ はこのような $x, cx$ が存在しないものに限定することができます。

これは言い換えると、1より大きい値 $x$ について「 $x$ 自身より小さい $x$ の約数が全て $s$ に入るまでは、 $x$ が $s$ に追加されることはない」と考えてしまって良い、ということです。以降は、このルールに従って構成した集合だけを考えることにします。

このルールに従うと、集合 $s$ に $x$ を追加する時点で $s$ には $x$ の倍数は含まれず、 $x$ より小さい $x$ の約数は必ず含まれています。つまり $x$ より小さい最大の約数を $d_{x}$ とすると、値 $x$ を追加することで $f(s)$ は $\max(f(s), d_{x})$ に置き換えられます。