(出題: noimi)

条件式を変形します。

\(A_j - A_i\) が \(j - i\) で割り切れるというのは、ある整数 \(k\) が存在して、\(k(j - i) = A_j - A_i\) と書けるということです。この式は、

\(A_i - ki = A_j - kj\) と、\(i, j\) を分離した式に書き直すことができます。

ここで、\(k\) の値によって場合分けをします。

• \(|k| \le T\) のとき

  • \(A_i - ki\) の値を全ての \(i\) について求めることで個数を計算できます。これは、配列やハッシュマップを用いることで \(O\left(NT\right)\) で計算できます。

• \(|k| > T \) のとき

  • \(|A_j - A_i| < A_{max}\) であることから、\(j - i < \dfrac{A_{max}}{T}\) が従います。よって、この範囲の \(i, j\) の組を全て調べることで \(O\left(\dfrac{NA_{max}}{T}\right)\) で計算することができます。

\(T = \sqrt{A_{max}}\) とすることで、全体で \(O\left(N\sqrt{A_{max}}\right)\) で計算することができます。