ルジャンドルの定理を用いると以下がわかります。

\[ F(N, p) = \sum_{i=1}^{\infty} \left\lfloor \frac{N}{p^i} \right \rfloor < \sum_{i=1}^{\infty} \frac{N}{p^i} \]

\(N - F(N, p)\) に注目します。

\[x = N - F(N, p) > N - \sum_{i=1}^{\infty} \frac{N}{p^i} \geq \left\{ \begin{array}{l} \displaystyle 0 & \text{if} ~~ p=2 \\ \frac{N}{2} & \text{if} ~~ p>2 \end{array} \right. \]

よって \(p \neq 2\) のとき、\(N\) は高々 \(2x\) であることがわかるので、 そのテストケースにおいて \(O(x \log N)\) で求めることができます。

\(p=2\) の場合について考えます。実験すると答えをすぐエスパーできますが、あえて考察してみましょう。

\(N\) を \(2\) 進数で考えます。ルジャンドルの定理をにらむと、下から数えて \(1\) ビット目が \(0\) か \(1\) かによって、\(F(N, p)\) には変化がないことがわかります。つまり、\(N\) の \(1\) ビット目を立たせると \(N - F(N, p)\) は \(1\) 増えます。同様に、\(2\) ビット目を立たせると、\(N\) は \(2\) 増えるのに対して、\(F(N, p)\) は \(1\) しか増えないため、 \(N - F(N, p)\) は \(1\) 増えます。

\(N\) の下から \(i\) ビット目を立たせると \(N - F(N, 2)\) が \(1\) 増えることは、\(N=2^{i-1}\) とすると \(F(N, 2) = \frac{N}{2} + \frac{N}{4} + ... + 1 = N-1 \) になることからわかります。

以上から、\(N\) の立ってないビットを立てれば \(N- F(N, 2)\) は \(1\) 増え、逆だと \(1\) 減ります。\(N=0\) のとき \(N- F(N, 2) = 0\) であることと合わせると、\(N- F(N, 2)\) はpopcountに等しいことがわかります。したがって、popcountが \(x\) になるような最小の非負整数を求めればよく、これは \(2^x - 1\) となります。