想定解
ペアの総数は NC2=N(N−1)/2 通りです.d(x)×d(y) が偶数となるペアを求めるために,偶奇で場合分けして奇数ペアの総数を引き算することを考えます.
ここで,d(x) の偶奇は下記のように定まります(証明後述).
d(x)={奇数偶数(x が平方数のとき)(otherwise)
M2≤N<(M+1)2 を満たす整数 M を計算することによって奇数ペアの総数は M(M−1)/2 と求められるので,答えは N(N−1)/2−M(M−1)/2 です.これは適切な実装により時間計算量 O(1) で求まります(愚直にシミュレートして M を計算しても十分間に合います).
証明
整数 z のある約数 d1 は z を割り切るため,d2=z/d1 と書いたとき d2 もまた z の約数となる.
-
すべての約数について d1=d2 を仮定すると,d1d2=z なる約数ペア (d1,d2) が必ず存在するため,整数 z の約数の個数は偶数になる.
-
d1=d2 なる約数が存在する場合,d1=d2=z となるため,このような約数は z が平方数の場合に限りただ一つ存在する.その他の約数についてはペアが必ず存在するため,整数 z の約数の個数は奇数になる.
以上により,z が平方数のとき d(z) は奇数となり,平方数でないときは偶数となる.