Codeforces Round #666 (Div. 2) C. Multiples of Length

長さ $N$ （ $1\leq10^5$ ）の配列 $a_n$ （ $-10^9\leq a_i \leq 10^9$ ）が与えられる。
操作を3回行って、全ての要素を0にせよ。

気づき

任意の長さの配列を3回の操作ですべて $0$ にできることが証明できると書いてあるので、選択肢は多くない。
選択した範囲の長さを $L$ とするとき、 $a_i$ をゼロにできるというのは、 $a_i$ が $L$ の倍数であること。
全ての要素を $N$ の倍数にできれば良さそう

2.については自明とする

1.について
まず、すべての要素について少なくとも2回は操作しないといけない。（ $\because$ 一回の操作で0になるのは、 $a_i$ が運良く $L$ の倍数のときだけ）
よって考えられる範囲の決め方として、

任意の位置 $x$ で区切って、「左、右、全体」
「全体、全体、全体」

しか考えられない（いまは順番のことは考えていない）
しかし、同じ範囲を連続で2回えらぶのは明らかに損なので、前者しか候補にならない。
（ $\because$ 全体を選ぶということは $a_i$ に $N$ の倍数を足すことなので、連続で選ぶなら、一回目で $2 \times N$ の倍数を足せば同じ結果になる）

3.について
任意の位置 $x$ で区切ったとき、左の範囲の長さを $L$ 、右の範囲の長さを $L2$ とする。

$a_i$ に全体の長さ $N$ の倍数を足して、左側を $L$ の倍数に、右側を $L2$ の倍数にする。
左側の範囲に $L$ の倍数を足して、右側の範囲に $L2$ の範囲をたして、全体を $N$ の倍数にする

のうち、どちらが実現できそうかを考える。
直感的に、一つの操作で2つの状態（ $L$ の倍数、 $L2$ の倍数）へ遷移するより、1つの状態（ $N$ の倍数）へ遷移したほうが素直な操作だと考える（微粒子レベルのエスパー）
よって、「左、右、全体」の順番で操作して、全体を0にすることを考える。
つまり、左側に $L$ の倍数を足して、右側に $L2$ の倍数をたして、全体を $N$ の倍数にすることを考える。

以上より、全体を $N$ の倍数にすることを考える
単純に $N$ の倍数にするなら全ての $a_i$ を $a_i \times N$ に変換できれば良い。（この問題のエスパー部分）
ひとまず、 $K$ を $L2$ の倍数として立式してみると、

$\displaystyle{K+a_i=N \times a_i}$

$\displaystyle{K=a_i(N-1)}$

となり、 $K$ は $L2$ の倍数なので、 $A$ を任意の整数として、

$\displaystyle{L2 \times A = a_i(N-1)}$

$\displaystyle{L2=\frac{N-1}{A}}$

$L2$ は自然数かつ $N-1$ は任意の自然数なので、（ $N-1$ は素数かもしれない）
$A=N-1,\ 1$
よって、 $L2=N-1$ のとき $L=1$ となり、 $L=1$ のとき $a_i$ は必ず0にすることができる（ $\because$ 任意の $a_i$ は $1$ の倍数）ので、 $L=1$ 、 $L2=N-1$ で全ての $a_n$ について0にできることがわかる。
（ $L2=N-1$ のとき $L=1$ 、 $L2=1$ のとき $L=N-1$ となり片方を考えれば良い）

したがって、