条件を満たす \(M\) が存在すると仮定します。このとき、操作によって \(A\) の過半数を占める整数を \(X\) と置きます。そして、\(A_i \bmod M =X\) を満たす \(i\) の集合を \(S\) とします。

\(i,j\) が \(S\) に含まれると仮定すると、\(A_i \equiv A_j \pmod M\) であるため \(M\) は \(|A_i - A_j|\) の約数となります。なので、\(|A_i - A_j|\) の \(3\) 以上の約数を全て試すことによって条件を満たす \(M\) を得ることができます。

ここで、\(i,j\) を \(1\) 以上 \(N\) 以下の整数からランダムに選びます。\(i,j\) がともに \(S\) に含まれる可能性は \(\frac{1}{4}\) 以上です。正しい解を返す確率を \(L\) としたとき、\(\log_{\frac{3}{4}}(1-L)\) 回乱択を行えばよいです。よって、以下のアルゴリズムを行うことによって期待計算量 \(\mathrm{O}(\log_{\frac{3}{4}}(1-L) \times N\sqrt{\max A})\) でこの問題を解くことができます。また、\(10^9\) 以下の正整数の約数の個数の最大値は \(1344\) 個であるため、実際はより高速に動作します。

条件を満たす \(M\) が存在しない場合は、もし上記の乱択を行った回数がある決められた回数を超えたら条件を満たす \(M\) は存在しないと出力すればよいです。

\(U \bmod V =0\) のとき、\(M=U\) としたとき \(M\) が条件を満たすのであれば、\(M=V\) としたときも \(M\) が条件を満たします。

よって、実際に試すのは \(|A_i-A_j|\) の \(3\) 以上の約数全てではなく、\(|A_i-A_j|\) の \(2\) 以外の素因数または \(4\) としてもよいです。