決定的に解く方法を記します。

\(i=1,2,...,N-1\) の順に以下を行えば、 \(N\) が偶数のときは答えが出ます。

• \(|A_{i}-A_{i+1}|\) の約数のうち、 \(3\) 以上の素数もしくは \(4\) が存在するなら、それを \(M\) として、 \(|A_{i}-A_{j}|\) が \(M\) の倍数になる \(j\) の数が \(N\) の過半数を超えるかを調べる。

理由としては、\(N\) が偶数ならば、 \(N\) 個の横並びの白のボールから過半数のボールを赤く塗ったとき、必ず、赤いボールが隣り合う場所があるからです。

\(N\) が奇数のときは、\(1,3,5,...,N-2,N\) という選び方がコーナーケースとなっているので、 \(M\) が \(|A_{1}-A_{N}|\) の約数である場合のみ、別途で調べればいいです。

計算量は \(O(N^{2}\log(\max A)+N\sqrt{\max A}))\) です。

提出例 c++ 156ms

提出例 pypy3 1094ms

この提出例では \(A\) をソートしています。これによって、素因数分解する整数の和が高々 \(2\max A\) になります。(ソートしないと高々 \(N\max A\) ) ソートするときの計算量は \(O(N\log N)\) でそんなに大きくないので、ソートしない場合に比べて \(2\) 倍ほど速くなってます。