解説

NNの値によって場合分けをすることで、O(1)O(1)で答えを求めることができます。

  • Nが奇数Nが奇数

NNを偶数で割り切ることは出来ません。よって、NNの約数はすべて奇数になります。

  • N4の倍数ではない偶数Nが4の倍数ではない偶数

NNの任意の奇数の約数xxについて、2x2xNNの約数となります。よって、奇数と偶数のものが同数になります。

  • N4の倍数Nが4の倍数

NNの任意の奇数の約数xxについて、2x,4x2x, 4xNNの約数となります。よって、偶数のものが多くなります。