ABC474 F - Increment All Divisors

考え方

全てを $T$ に揃えるとする。
どんな操作でも自身より後ろへの影響はないので、各操作回数は後ろから貪欲に決めてよい。
そうして、全ての $i$ についての操作回数を一次式として求め、pair か何かで記録しておく。

さて、逆の操作（$1$ を足すのではなく $1$ を引く）も許される場合は、これで任意の値に揃えられる。
問題では足す方しか許されていないので、これら一次式が非負の値を取る範囲を調べればよい。

各一次式、一次の係数が負なら $T$ の上界が、正なら下界が得られる。
上界の最小値と下界の最大値を見て、矛盾していれば不可能と判定できる。
また、一次の係数が $0$ の場合は、定数項が負だったら不可能となる。
可能である場合は、操作回数の最小値を求める必要があるが、これは簡単。
どんな操作でも $A_1$ は必ず $1$ 増えるので、操作回数は $T-A_1$ である。
つまり、可能である $T$ の最小値を選んで $T-A_1$ を答えればよい。

必要操作回数を調べるときに、ループをきちんと $i$ の倍数だけ回すようにすること。
そうすれば、ループ数合計は調和級数で抑えられ、計算量は $O(N\log N)$ である。

一見、$A$ の最大値を選べばよさそうに思えるが、実はそうではない。
理由は、別解の解説で。

入力例1での動作

入力を受け取る。

n: 3
a: {4, 7, 4}

最初は各項について必要操作回数を $T-A_i$ と考えるので、k1 は全て $1$、k0 は $A$ と同じ値から始まる。

後ろから順に必要操作回数を求める。

上界と下界がともに $7$ となるので、$T=7$ とすればよい。
このとき必要操作回数は、$i=3$ について $3$ 回、$i=2$ と $i=1$ について $0$ 回である。

実際、$i=3$ の操作では $A_1,A_3$ が $1$ ずつ増える。
これを $3$ 回行うと、$\{4,7,4\}\to\{5,7,5\}\to\{6,7,6\}\to\{7,7,7\}$ となる。

全操作回数は $T-A_1=7-4=3$ なので、答えは $3$ となる。

注意点

C++ では負の数の除算の仕様が壊れているため、上界や下界の値を正しく求めるのが非常に手間。
符号不明な $2$ 数の商（切り上げや切り下げ）を正しく行うには、以下の $6$ つに場合分けする必要がある。

• 分子が $0$
• 分母が $0$
• 分子・分母の符号の組み合わせ $4$ 通り

ただし、実際にはこの問題ではこれを簡略化できる。
つまり、分母が $0$ でない場合は分子・分母が同符号という前提で、意図的にバグったコードを書いてよい。
異符号だった場合はバグるが、上界の最小値や下界の最大値、最終判定のどこかでバグの影響が消える。

別解

数学的背景を踏まえて理論的に解く。

これは、行列演算により、$N$ 元 $1$ 次連立方程式を解く問題である。

まず、以下のように $Z$ を定義する。

$Z$ の $(i,j)$ 成分は、$i$ が $j$ の約数なら $1$、それ以外なら $0$ とする。

$$
Z=
\begin{pmatrix}
1&1&1&1&1&1&1&\cdots&1\\
0&1&0&1&0&1&0&\cdots&\\
0&0&1&0&0&1&0&\cdots&\\
0&0&0&1&0&0&0&\cdots&\\
0&0&0&0&1&0&0&\cdots&\\
0&0&0&0&0&1&0&\cdots&\\
0&0&0&0&0&0&1&\cdots&\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&0&0&0&0&\cdots&1
\end{pmatrix}
$$

また、以下のように $x,A,\mathbf{1}$ を定義する。

$$
x=
\begin{pmatrix}
x_1\\
x_2\\
\vdots\\
x_N
\end{pmatrix},
\qquad
A=
\begin{pmatrix}
A_1\\
A_2\\
\vdots\\
A_N
\end{pmatrix},
\qquad
\mathbf{1}=
\begin{pmatrix}
1\\
1\\
\vdots\\
1
\end{pmatrix}
$$

すると、$A$ に対して $x$ で表される分だけ操作をすると、結果は $A+Zx$ となる。
これが全て整数 $T$ になっているというのは、$A+Zx=T\mathbf{1}$ という意味である。

ということは、$x=TZ^{-1}\mathbf{1}-Z^{-1}A$ の各成分が非負となる $T$ を考えればよいことになる。

ここで、$Z$ の逆行列を考える。（以下、1-indexed で考える）
まず、$Z$ は単上三角行列なので、同じく単上三角行列である $Z^{-1}$ が存在する。
その第 $i$ 行目は、$Z$ の $i$ 列目との内積は $1$、それ以外の列との内積は $0$ である。
つまり、$i$ の約数番目だけ合計すれば $1$、それ以外の数の約数番目だけ合計すれば $0$ ということ。
これは、メビウス関数 $\mu(n)$ の性質を利用して、$Z^{-1}$ の $i$ 行目を以下のように構成すれば実現できる。

• $ki$ 列目は $\mu(k)$ とする
• 列番号が $i$ の倍数でないところは $0$ とする

そして、当然逆行列は一意なので、これが $Z^{-1}$ であるとしてよい。

$$
Z^{-1}=
\begin{pmatrix}
1&-1&-1&0&-1&1&-1&\cdots&\\
0&1&0&-1&0&-1&0&\cdots&\\
0&0&1&0&0&-1&0&\cdots&\\
0&0&0&1&0&0&0&\cdots&\\
0&0&0&0&1&0&0&\cdots&\\
0&0&0&0&0&1&0&\cdots&\\
0&0&0&0&0&0&1&\cdots&\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&0&0&0&0&\cdots&1
\end{pmatrix}
$$

$C=Z^{-1}\mathbf{1}$ の $i$ 行目の値は、メルテンス関数（メビウス関数の累積和）の $\lfloor N/i \rfloor$ 項目の値となる。
$x=TC-Z^{-1}A$ が全て非負になる条件は、この $C$ の値が鍵を握っている。
$C_i$ が正であれば、$T$ の下限が出る。
$C_i$ が $0$ であれば、$T$ の値に変化はなく、常に OK か常に NG かどちらか。
$C_i$ が負であれば、$T$ の上限が出る。

ここで、メルテンス関数に関する奇妙な性質が、この問題をややこしくしている。
メルテンス関数の最初の $100$ 項を $10$ 個区切りで書くと、以下のようになる。

001-010 :  1,  0, -1, -1, -2, -1, -2, -2, -2, -1
011-020 : -2, -2, -3, -2, -1, -1, -2, -2, -3, -3
021-030 : -2, -1, -2, -2, -2, -1, -1, -1, -2, -3
031-040 : -4, -4, -3, -2, -1, -1, -2, -1,  0,  0
041-050 : -1, -2, -3, -3, -3, -2, -3, -3, -3, -3
051-060 : -2, -2, -3, -3, -2, -2, -1,  0, -1, -1
061-070 : -2, -1, -1, -1,  0, -1, -2, -2, -1, -2
071-080 : -3, -3, -4, -3, -3, -3, -2, -3, -4, -4
081-090 : -4, -3, -4, -4, -3, -2, -1, -1, -2, -2
091-100 : -1, -1,  0,  1,  2,  2,  1,  1,  1,  1

これの初項は $1$ であるが、これは数列の後半部分に対応する。
つまり、他の項を指定した操作の影響を一切受けない項。
よって、下界が出るが、これは $A_{\max}$ を超えることはない。

そして、$2$ 項目から $93$ 項目までは、全て $0$ 以下。
よって、ここから下界が出ることはない。

つまり、この問題の $N$ の値が $93$ 以下であれば、$T=A_{\max}$ とする解があるかどうかだけ調べればよい。

しかし、$N=94$ で急に話が変わる。
$C_1$ の値はメルテンス関数の $94$ 項目の値で、$1$ となる。
つまり、$A_{\max}$ の値を超える下界が出てくる可能性がある。

実際に、$N=94$ として、以下のような数列を考える。

$$
A_1=1,\qquad
A_i=94-\left\lfloor\frac{94}{i}\right\rfloor\quad(2\le i\le94)
$$

具体的には次の数列になる。

1 47 63 71 76 79 81 83 84 85 86 87 87 88 88 89 89 89 90 90
90 90 90 91 91 91 91 91 91 91 91 92 92 92 92 92 92 92 92 92
92 92 92 92 92 92 92 93 93 93 93 93 93 93 93 93 93 93 93 93
93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93
93 93 93 93 93 93 93 93 93 93 93 93 93 93

このとき $A_{\max}=93$ であるが、$93$ では不可能で、$94$ では可能となる。
後ろから貪欲に $93$ に揃えていくと、$A_2$ まで処理した段階で $A_1$ が $94$ になってしまう。
一方、$94$ に揃える場合は、$2$ 以上の全ての $i$ についてちょうど $1$ 回ずつ操作すればよい。
$A_2$ まで処理した段階で、$A_1$ も $94$ になっている。

では、$A_{\max}$ で一度やってみて、$A_1$ がそれを超えた場合には改めてそれを目標にするのはどうか。
これも $N=95$ で反例がある。

$N=95$ として、以下のような数列を考える。

$$
A_1=1,\qquad
A_i=95-\left\lfloor\frac{95}{i}\right\rfloor\quad(2\le i\le95)
$$

具体的には次の数列になる。

1 48 64 72 76 80 82 84 85 86 87 88 88 89 89 90 90 90 90 91
91 91 91 92 92 92 92 92 92 92 92 93 93 93 93 93 93 93 93 93
93 93 93 93 93 93 93 94 94 94 94 94 94 94 94 94 94 94 94 94
94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94
94 94 94 94 94 94 94 94 94 94 94 94 94 94 94

このとき $A_{\max}=94$ である。
後ろから貪欲に $94$ に揃えていくと、$A_2$ まで処理した段階で $A_1$ が $96$ になってしまう。

そこで今度は $96$ に揃えようとしても、途中で必要操作回数が負になる。
例えば $i=19$ を処理する段階では、既に $A_{19}$ が $97$ になっている。
よって、$96$ に戻すには $-1$ 回の操作が必要になってしまう。

しかし、実は $95$ に揃えることは可能である。
この場合も、$2$ 以上の全ての $i$ についてちょうど $1$ 回ずつ操作すればよく、$A_1$ も $95$ になる。

ということで、$C=Z^{-1}\mathbf{1}$ と $D=Z^{-1}A$ を素直に求めるしかないことがわかった。
それぞれ、$ZC=\mathbf{1}$ と $ZD=A$ を下から順に考えれば、$C,D$ が逐次求まる。
これは、$Z$ が上三角行列であることから保証される。

結果として、コードは上に書いた考え方と同じものになる。

$N=94$ の反例での動作

先ほどの $N=94$ の反例を、最初の解法と同じように後ろから調べる。
この反例では、$A_1=1$ が最後に新しい下界を生み出すことがポイントである。

$i=2$ まで見た時点では、下界の最大値は $93$、上界の最小値は $94$ であり、$T=93$ も可能に見える。
しかし最後に $i=1$ を見ると、必要操作回数は $T-94$ となる。
ここで初めて $T\ge94$ という条件が追加され、下界の最大値が $93$ から $94$ に更新される。

したがって、この反例では $A_{\max}=93$ であるにもかかわらず、最小の $T$ は $94$ となる。