公式解説では、\(d\) という名前の異なる変数が定義されていて非常に読みづらいです(というか意味不明です)。

答え(\(d\)とします)

で用いられている \(d\) を \(R\)に置き換えると下記のようになります。

まず、\(K\)回の操作で\(A\)に対してどのような操作ができるか考えてみましょう。\(A_1+d_1, A_2+d_2, \dots A_N+d_N\)になるとします。

このとき、各操作で和が変化しないことに注目すると、\(d_1+d_2+\dots+d_N= 0\)である必要があります。また、dのうち正のものの和が\(K\)より大きい場合はありえません。負についても同様であり(和が\(0\)の時は自動的に満たされますが)、これら全てが満たされる場合はそのように操作可能であることが帰納的に示せます。

答え(\(R\)とします)の候補としては、\(S=A_1+A_2+\ldots+A_N\)としたとき、\(R\)が\(S\)の約数である必要があります。\(R\)を\(S\)の約数全て試すことにして固定しましょう。このような\(R\)の候補は\(O(sqrt(N max(A)))\)個あります。

まず、\(A_1,\ldots A_N\)を\(R\)で割った余りを\(r_1, r_2,\ldots r_N\)としましょう。\(0\)であるものはなく、これは小さい順にソートされているとします。このとき、\(d\)を正にするものについては最低(\(R−r_i\))の和の回数の操作が必要です。\(d\)を負にするものについては最低\(r_i\)の和の回数の操作が必要です。それぞれ、\(R\)の倍数回の操作は余分に行うことができます。よって、\(r\)の小さい方から途中までを\(d\)を負に設定し、そこからは正になるようにする形のみを考えればよく(\(r\)の和が\(R\)の倍数であることに注意しましょう)、累積和などを用いて全ての区切り方の\(d\)が正のものの回数の和と負のものの回数を求めることができます。

よって、\(R\)を固定した場合には\(O(N logN)\)で解けるので、この問題は\(O(sqrt(N max(A)) N logN\))で解けました。