ABC400 C - 2^a b^2【備忘録】

久しぶりにABCに参加してきました。

お恥ずかしながら、A、Bの２完でした・・・

C問題がわからなかったので復習しようと思います。

C - 2^a b^2

問題文

問題文
正の整数
X は、次の条件をみたすときかつその時に限り、良い整数と呼ばれます。

正の整数の組 (a,b) を用いて、
$X= 2^a × b^2$

と書ける。
例えば、400は$400=2^2×10^2$ と書けるため、良い整数です。
正の整数N が与えられるので、1 以上N 以下の良い整数の個数を求めてください。

制約

$1≤N≤10^{18} $
$ N は整数 $

まず何を考えるか

制約がやたらデカいので、全探索は無理だと考える。
おそらく素数判定の時と同じように探索範囲は$ \sqrt{N}$　は数くらいになるのでは？
と考える。対数を取ったらどうだろうか？とかゴニョゴニョ考える。
$2=2^1×1^2$(a,b)=(1,1)
$4=2^2×1^2$(a,b)=(2,1)
$8=2^3×1^2$(a,b)=(3,1)
$16=2^4×1^2$(a,b)=(4,1)
$18=2^1×3^2$(a,b)=(1,3)
おそらく次は$32=2^5×1^2$(a,b)=(5,1)
みたいな感じで具体例をあげてみるが時間がなくなってしまう．．．

解説を見て

bは奇数になるというところが正直ピンと来なかった。
おそらくXが$ 2^a$を含んでいるので、必ず偶数($ 2^a $)と奇数($ b^2$)の組み合わせとなる。（$b^2$が偶数だった場合、$2^{a+n}$というような形に変形できるため、自ずと$ b^2$は奇数となると理解）
式変換すると $ b^2 \leq \frac{N} {2^a} $となり aを固定すると$ b \leq \sqrt\frac {N}{2^a}\ $
奇数となるbは$ \frac{\sqrt\frac {N}{2^a}+1 } {2}$を満たすとき

らしい．．．

解(a,b)は組み合わせのため、重複を選ばないようにする必要がある。

aはどこまで探索するばいいのか？

temp.py

for i in range(1000):
    if 2**i>=10**18:
        #aは最大でも60
        a = i
        break
#aは最大でも60
print (a)

これを動かしてみるとわかるが$2^a$が$10^{18}$を超える時は60乗なのでaは1から61までを探索すれば良いことがわかる。

temp.py

N = int(input())
from math import isqrt

ans = 0
for i in range(1,61):
    ans+= (isqrt(N//(2**i))+1)//2
print (ans)

ちなみに以下だとACできません。。。
たぶん誤差の問題だと思います

temp.py

N = int(input())
import math

ans = 0
for i in range(1,61):
    ans+= int(math.sqrt(N//(2**i))+1)//2
print (ans)

誰かわかる方教えてください．．．．