NNNの値によって場合分けをすることで、O(1)O(1)O(1)で答えを求めることができます。
NNNを偶数で割り切ることは出来ません。よって、NNNの約数はすべて奇数になります。
NNNの任意の奇数の約数xxxについて、2x2x2xもNNNの約数となります。よって、奇数と偶数のものが同数になります。
NNNの任意の奇数の約数xxxについて、2x,4x2x, 4x2x,4xもNNNの約数となります。よって、偶数のものが多くなります。