\(N\) についてのこの問題の答えを \(f(N)\) としましょう。

この時、中国剰余定理より \(f(n)\) は乗法的関数であり、正整数 \(a, b\) が互いに素ならば \(f(ab) = f(a)f(b)\) が成り立ちます。

よって、 \(N\) が \(\displaystyle \prod_i p_i^{e_i}\) (\(i \ne j\) ならば \(p_i \ne p_j\) 、 \(p_i\) は素数) と素因数分解できるとき、 \(\displaystyle f(N) = \prod_i f(p_i^{e_i})\) と表せます。

これより、素数の正整数乗の形の値について問題を解くことができれば \(f(N)\) は高速に求まります。

奇素数(\(p\) とする)の正整数乗の形の値

\(k^2 \equiv 1 \pmod {p^e}\) であることは \((k + 1)(k - 1) \equiv 0 \pmod {p^e}\) であることと同値です。

ここで、 \(k + 1\) と \(k - 1\) の差は \(2\) で、この値は \(p\) で割りきれないので、どちらも \(p\) の倍数であることはあり得ません。

よって、 \(k + 1\) または \(k - 1\) が \(p^e\) の倍数であることが \((k + 1)(k - 1) \equiv 0 \pmod {p^e}\) であることの必要十分条件となっています。

これを満たす \(k\) は \(1, -1 \pmod {p^e}\) の \(2\) つであり、条件よりこの二つの数は \(p^e\) を法にして異なる数であるため、答えは \(2\) 通りです。

\(2\) の正整数乗の形の値

ここでも、 \(k^2 \equiv 1 \pmod {2^e}\) であることは \((k + 1)(k - 1) \equiv 0 \pmod {2^e}\) であることと同値です。

ここで、 \(k + 1\) と \(k - 1\) の差は \(2\) で、この値は \(2^2\) で割り切れないので、どちらも \(2^2 (=4)\) の倍数であることはあり得ません。

よって、 \(k + 1\) または \(k - 1\) が \(2^{e - 1}\) の倍数であることが \((k + 1)(k - 1) \equiv 0 \pmod {2^e}\) であることの必要十分条件となっています。

これを満たす \(k\) は \(e = 1\) の場合 \(1\) つ、 \(e = 2\) の場合 \(2\) つ、 \(3 \le e\) の場合 \(4\) つありますので、それが答えになります。

結論

以上を踏まえると、 \(N\) が持つ異なる素因数の個数を \(\mathrm{cnt}\) として、

\(N\) が \(2\) で \(1\) 度も割り切れない場合 \(\cdots\) \(f(N) = 2^\mathrm{cnt}\)

\(N\) が \(2\) でちょうど \(1\) 度割り切れる場合 \(\cdots\) \(f(N) = 2^\mathrm{cnt - 1}\)

\(N\) が \(2\) でちょうど \(2\) 度割り切れる場合 \(\cdots\) \(f(N) = 2^\mathrm{cnt - 1} \times 2\)

\(N\) が \(2\) で \(3\) 度以上割り切れる場合 \(\cdots\) \(f(N) = 2^\mathrm{cnt - 1} \times 4\)

となります。以上より、 \(O(T\sqrt {N})\) の時間計算量で解くことができます。

実装例 (C++)