問題概要
正整数 $n \in \mathbb Z_{ {} > 0 }$ が与えられる．$n$ 以下の正整数 $x \in \mathbb Z_{ {} > 0 }$ であって，次の条件を満たすものの個数を求めよ：
- $2^a b^2 = x$ を満たす正整数 $a, b \in \mathbb Z_{ {} > 0 }$ が存在する．
制約
- $1 \leq n \leq 10^{ 18 }$
解法
「基本は全探索」というのが（わたしの中に）あるので変量である $a, b$ を全探索すれば，計算時間はともかく正しい答えは得られるのではないかと期待したいところですが，実はうまくいきません．例えば $x = 72$ を例にすると，
\begin{align*}
72 &= 2^3 3^2 \\
&= 2^1 2^2 3^2 \\
&= 2^1 ( 2^2 3^2 ) \\
&= 2^1 ( 2 \cdot 3 )^2
\end{align*}
と $2$ 通りの表示ができてしまうので，重複して数え上げてしまいます．なので，重複を排除するために表示を正規化したい気持ちになります．
落ち着いて考えると，$3 \leq a$ のとき，$b' = 2b$ として
\begin{equation*}
2^a b^2 = 2^{ a - 2 } (b')^2
\end{equation*}
です．表示が一意的でなかった理由はこれなのですが，よくある話として「極端な方に寄せる」ということをすると正規化できたりします．ここでは，$x$ の素因数としての $2$ を可能な限り $b$ に吸収させることにすると，$x$ は $a \in \{ 1, 2 \}, b \in \mathbb Z_{ {} > 0 }$ で $2^a b^2$ と表せるということになります．
$a$ が異なれば $x$ の奇遇が異なるので，$a$ が $1$ の場合と $2$ の場合を独立に数えて足し合わせれば正しく数えられます．$a = 1$ のとき，
\begin{align*}
2 \cdot b^2 &\leq n \\
b^2 &\leq \frac n 2 \\
b &\leq \sqrt { \frac n 2 }
\end{align*}
を満たす $b \in \mathbb Z_{ {} > 0 }$ の個数（＝$b$ の値そのもの）が欲しい値で，$a = 2$ の場合も同様にして
\begin{align*}
2^2 \cdot b^2 &\leq n \\
b^2 &\leq \frac n { 2^2 } \\
b &\leq \sqrt { \frac n { 2^2 } } \\
b &\leq \sqrt { \frac n 4 }
\end{align*}
が欲しい値です．従って（"個数"は整数なので）ちゃんと言えば，欲しいのは
\begin{equation*}
\left\lfloor \sqrt { \frac n 2 } \right\rfloor + \left\lfloor \sqrt { \frac n 4 } \right\rfloor
\end{equation*}
です．よって，平方根を（誤差などに関して）適切に計算できれば，問題に正当できます
コード
main = do n <- readInteger print $ isqrt ( n `div` 2 ) + isqrt ( n `div` 4 ) isqrt 1 = 1 isqrt n = isqrt' 0 n n where isqrt' lb ub n | lb + 1 < ub = let mid = ( lb + ub ) `div` 2 in if mid * mid <= n then isqrt' mid ub n else isqrt' lb mid n | otherwise = lb
