Editorial

XXをデタラメに定めても大して意味のある値にならないことはわかると思います。 そこで、数列AAの中の数字を用いてXXを定める方法を考えます。

数列AAの最小値を達成したいなら数列AAの中で一番登場回数が多い因数をXXと定めることで最適になる気がします。 よってこの方針を考えてみることにします。

世の中には偶数が大量に溢れているのでだいたいの場合はX=2X = 2と定めると最小値を取ります。 ここで、偶数だけの数列BBを考えてみます。

N=5B={2,4,8,12,16}N = 5 \\ B = \{2, 4, 8, 12, 16\}

すべて偶数であるので2で割るのが最適であるように思います。 ここで実際にX=2X = 2であると定めXXで割ったあとの数列をXX'と定めると

X={1,2,4,6,8},Sn=i=15Xi=21X' = \{1, 2, 4, 6, 8\}, \quad Sn = \sum_{i = 1}^{5}X'_i = 21 となります。

しかし実はX=4X = 4とするのが上の数列では最適であり、X=4X=4のときSnS_nは以下のようになります。

X={2,1,2,3,4},Sn=i=15Xi=12X' = \{2, 1, 2, 3, 4\}, \quad Sn = \sum_{i = 1}^{5}X'_i = 12

このような例で実は一番多く登場する因数が最適なXXとは限らないことがわかります。

実際のところどの約数が最適かは試してみるしかありません。 だからといってすべての約数に対してNN回の割り算を繰り返すとかなり軽く見積もってもO(Nmax(Ai))O(Nmax(A_i))となりTLEしてしまいます。 そこで次に以下のようなことを考えてみます。

XXを定めた後の総和をSnXS_{n_X}, もとの数列の総和をSnS_nとすると

SnX=Sn変更されたAiの総和+変更後のAiの総和S_{n_X} = S_n - 変更されたA_iの総和 + 変更後のA_iの総和

が成り立つことを考えます。 先程の数列BBを例に取ると、

X=4のときSn=42SnX=12変更されたAiの総和=40変更後のAiの総和=10X = 4のとき \\ S_n = 42 \\ S_{n_X} = 12 \\ 変更されたA_iの総和 = 40 \\ 変更後のA_iの総和 = 10 \\ これを先程の式に当てはめてみると

12=4240+10=2+1012 = 42-40+10 = 2+10 一致します。

さて、これによって考えられるすべてのXXAiA_iを割るという操作をなくすことができます。 なぜなら、ある約数D(1Dmax(Ai))D (1 \le D \le max(A_i))でどれだけのAiA_iが影響を受けるのか。受けた結果の総和はいくつか。がわかれば試し割りをしなくても数列の総和は上の式を用いて計算することができるからです。

メモをした変位量を用いて数列の総和が最小になったときが最適なXXであり、そのときのSnXS_{n_X}が答えです。

ここで、NN及びAiA_iの成約は十分に小さいのですべてのAiA_iに対してO(Ai)O(\sqrt{A_i})だけ時間をかけて約数列挙を行っても問題はありません。 また、メモした配列(リスト型)を見て最小値を判定するのはすべて定数時間で行うことができるのでこの問題をO(Nmax(Ai))O(N\sqrt{max(A_i)})で解くことができました。(実際は定数倍が重いのでPythonでの実装には気をつけてください。ループが主なのでPyPy3などで実行すると高速化すると思います)

ちなみにテストケースのKillerたちの中身ですが、2が最適なXXでない場合です。

実はKiller以外のテストケースはすべてX=2X = 2で最小値を取ります。

回答例(C++)