想定解

ペアの総数は NC2=N(N1)/2{}_{N}\mathrm{C}_{2} = N(N-1)/2 通りです.d(x)×d(y)d(x) \times d(y) が偶数となるペアを求めるために,偶奇で場合分けして奇数ペアの総数を引き算することを考えます.

ここで,d(x)d(x) の偶奇は下記のように定まります(証明後述).

d(x)={奇数(x が平方数のとき)偶数(otherwise) d(x) = \begin{cases} \text{奇数} & (x \text{ が平方数のとき}) \\ \text{偶数} & (\text{otherwise}) \end{cases}

M2N<(M+1)2M^2 \leq N < (M+1)^2 を満たす整数 MM を計算することによって奇数ペアの総数は M(M1)/2M(M-1)/2 と求められるので,答えは N(N1)/2M(M1)/2N(N-1)/2 - M(M-1)/2 です.これは適切な実装により時間計算量 O(1)O(1) で求まります(愚直にシミュレートして MM を計算しても十分間に合います).

証明

整数 zz のある約数 d1d_1zz を割り切るため,d2=z/d1d_2 = z / d_1 と書いたとき d2d_2 もまた zz の約数となる.

  • すべての約数について d1d2d_1 \neq d_2 を仮定すると,d1d2=zd_1d_2 = z なる約数ペア (d1,d2)(d_1, d_2) が必ず存在するため,整数 zz の約数の個数は偶数になる.

  • d1=d2d_1 = d_2 なる約数が存在する場合,d1=d2=zd_1 = d_2 = \sqrt{z} となるため,このような約数は zz が平方数の場合に限りただ一つ存在する.その他の約数についてはペアが必ず存在するため,整数 zz の約数の個数は奇数になる.

以上により,zz が平方数のとき d(z)d(z) は奇数となり,平方数でないときは偶数となる.