\(2^a \times b^2\) の形において、 \(b\) が奇数である場合のみを数えることで漏れなくダブりなく数え上げられるという点は他の解説と同じです。

\(b\) を固定した際、条件を満たす整数 \(a\) は \(1,2,\dots,r\) となり (ある上限 \(r\) が存在して \(1\) 以上 \(r\) 以下の全ての整数で成り立つ) 、この \(r\) は \(b\) が増加していくごとに(広義)単調減少します。

よって、尺取り法の要領で \(b\) を増やしながら各 \(b\) に対する \(r\) を求めていくことで時間計算量 \(O(\sqrt{N})\) でこの問題に正解できます。
\(N\) に \(10^{18}\) を代入すると額面で \(10^9\) という時間計算量が得られますが、 2025 年現在の CPU は高速なのでかろうじて実行時間制限内に間に合います。 ( \(N=10^{18}\) をワーストケースとして容易に試すことができるので、提出前にこの実行時間をコードテストで確かめると良いでしょう。 )

実装例 (C++)

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n;
  cin >> n;
  long long a=60,res=0;
  for(long long b=1;a>0;b+=2){
    while(a>0 && (1ll<<a)*b*b > n){a--;}
    res+=a;
  }
  cout << res << "\n";
  return 0;
}