概要

約数の集合の包括関係を考えると，貪欲に答えを決定していくことができます．

問題原案：uni_kakurenbo

解説

操作によって $f(n) \scriptsize \;(n \in \Z^+)$ の値がそれぞれどのように変化するかを考えてみましょう．

$f$ の定義から，非負整数 $x$ の追加によって $f(n) \scriptsize \;(n \in \Z^+)$ の値が増加するとき，「$x$ は $n$ の(正の)約数」です．

なお，いかなる操作によっても $f(n) \scriptsize \;(n \in \Z^+)$ の値が減少することはありませんし，ここでは $N$ 以下の正整数 $n$ に関してのみ $f(n)$ の値に関心があるので，列 $X$ に $N$ 以上の数を追加することは考えなくてよいことが分かります．$N$ 以上の整数を追加したとき $f(n)$ の値が増加するような $N$ 以下の正整数 $n$ は存在しないからです．

さらに，「$x$ は $n$ の(正の)約数」であることは「$n$ が $x$ の(正の)倍数」であることに等しいですから，この問題を次のように読み替えることもできます：

• 長さ $N$ の列 $X' = (X'_1, X'_2, \ldots, X'_N)$ があり，はじめ $X'_1 = X'_2 = \cdots = X'_N = 0$ である．
• $X'$ に対して以下の操作を何度でも行うことができる：
  • $1 \leq x \leq N$ なる整数 $x$ を自由に選び，$i = kx \scriptsize \; (k \in \Z^+ \land kx \leq N)$ と表されるようなすべての相異なる $i$ について $X'_i$ に $1$ を加算する．
• $A = X'$ とするための操作回数の最小値を求めよ．

この言い換えは必ずしも必要ではないですが，こうすることで少しばかり見通しがよくなるかもしれません．以下では，読み替える前の元の問題を主に扱います．

ここで，操作はどんな順番で行ってもよいので，$X$ に追加すべき正整数 $x$ の個数を $T_x$ として，この問題の答えは $\displaystyle \sum_{1 \leq n \leq N} T_n$ 回と表されます．

さて，$1$ の(正の)約数は $1$ のみですから，$f(1)$ の値は $X$ に含まれる $1$ の個数に一致する，すなわち $T_1 = A_1$ であることが分かります．

同様に，

• $2$ の(正の)約数は $1, 2$ のみだから，$T_1 + T_2 = A_2$．
• $3$ の(正の)約数は $1, 3$ のみだから，$T_1 + T_3 = A_3$．
• $4$ の(正の)約数は $1, 2, 4$ のみだから，$T_1 + T_2 + T_4 = A_4$．
• $\vdots$
• $\displaystyle \sum_{\substack{m|n \\m \,\in\, \Z^+}} T_m = A_n$．

を得ます．

さて，$T_1 = A_1$ であることが分かっていますから，$T_2 = A_2 - T_1$ が分かります．

同様に，

• $T_3 = A_3 - T_1$．
• $T_4 = A_3 - (T_1 + T_2)$
• $\vdots$
• $\displaystyle T_n = A_n - \sum_{\substack{m|n \\ m < N \\ m \,\in\, \Z^+}}$

と，$T_n \scriptsize \; (1 \leq n \leq N)$ の値をすべて確定させることができます．
任意の正整数 $p$ について，$p$ の $p$ 以外の正の約数はすべて $p$ 未満であることから従います．

このようにして求めた $T_1, T_2, \ldots, T_N$ の値がすべて非負の整数であるかを調べることで，条件を満たせるかどうかを $\Theta(N \sqrt N)$ 時間などで判定できますが，$N \leq 10^6$ のもとで実行時間制限に間に合わせることは少々厳しいです．

ここで先ほどの読み替えが役に立つかもしれません．約数よりも倍数の方がプログラムによる列挙が (実装的にも計算量的にも) 簡単なので，より効率よく解くことができるでしょう．
詳しくは実装例も参照してください．

倍数の列挙によって $T_x$ の値を求めていくと，実装にも依りますが大抵の場合，計算量(のオーダー)は調和級数の発散速度(のオーダー) $(O(\log N))$ の $\Theta(N)$ 倍と同程度になります．

解説：uni_kakurenbo

実装例