\(A_i\) が \(N\) になっても \(0\) には戻さないようにします． その代わり目標を \(A_i \mod N\) がすべて異なる状態にすることとします．

まず，\(A\) を \(B\) にできるかという問題を考えます． この必要十分条件は以下のように書けます．

• \(A_i \leq B_i\)
• \(S=\sum (B_i-A_i)\) とおく．このとき
  • \(S\) は \(M\) の倍数
  • \(B_i-A_i \leq S/M\)

次に，元問題の最適解の様子について観察します． 今，\(A \to B\) という最適解が得られたとします． このような最適解の中で，\(\sum B_i^2\) が最小のものをとってきたと仮定します． このとき，ある \(x\) が存在し，\(B\) が \((x,x+1,\cdots,x+N-1)\) の順列になることが示せます．

これを背理法により証明します． まず，\(B_j-B_i>N\) を満たす \(i,j\) が取れます． ここで，\(B_i,B_j\) をそれぞれ \(B_j-N,B_i+N\) で置き換えてみます．すると，依然として\(A \to B\) は valid な解であり，かつ \(\sum B_i^2\) の値は以前より小さくなります． よって矛盾し，証明が完了します．

\(A\) を昇順ソートしておきます． \(B\) として考えるべきは，\((x,x+1,\cdots,x+N-1)\) の形のみです． あとは上で考えた \(B\) の条件を \(x\) に関する条件に直して，条件を満たす \(x\) の最小値を求めればよいです．

まず，\(A_i \leq B_i\) は単に \(x\) の下限を与えるだけです．

次に，\(S\) が \(M\) の倍数という条件がありますが，これは書き下すと \(\sum (i-1-A_i) + Nx \equiv 0 \mod M\) となります． \(g=\gcd(N,M)\) とおけば，\(x \mod M/g\) の 値を指定する条件になっています（この条件は常に不成立，という場合もありえます）．

最後に \(B_i-A_i \leq S/M\) ですが，これも式変形すれば，\(x\) の下限を与えるだけです．

よって結局，下限と \(x \mod M/g\) が指定されたときに条件を満たす最小の \(x\) を求めよ，という形になり，計算できます．

上記の議論をそのまま実装すれば，計算量 \(O(N)\) でこの問題は解けます．

解答例