\(N\) 以下の良い整数の集合を \(S\) とします。
また、「\(N\) 以下であって、正の整数 \(b\) を用いて \(X=2\times b^2\) と書ける整数 \(X\) の集合」を \(T\) とし、「\(N\) 以下であって、正の整数 \(b\) を用いて \(Y=2^2\times b^2\) と書ける整数 \(Y\)の集合」を \(U\) とします。
このとき、\(T\cup U=S\) かつ \(T\cap U=\phi\) (\(\phi\) は空集合を表す) となることを示します。

まず、前者について明らかに \(T\subset S\), \(U\subset S\) であることから、\((T\cup U)\subset S\) です。一方で、\(X\in S\) ならば \(X=2^a\times b^2\) と書けますが、\(a\) が奇数、すなわち非負整数 \(a'\) を用いて \(a=2a'+1\) と書けるならば \(X=2^{2a'+1}\times b^2=2\times (2^{a'}\times b)^2\) と書けるため \(X\in T\) であり、\(a\) が偶数、すなわち非負整数 \(a'\) を用いて \(a=2a'+2\) と書けるならば \(X=2^{2a'+2}\times b^2=2^2\times (2^{a'}\times b)^2\) と書けるため \(X\in U\) となります。よって、\(S\subset (T\cup U)\) であり、先の \((T\cup U)\subset S\) とあわせて \(T\cup U=S\) が成り立ちます。

後者については、\(T\) に属する整数は \(2\) を素因数に奇数個持ち、\(U\) に属する整数は \(2\) を素因数に偶数個持つことから両方に属する整数は存在せず、\(T\cap U=\phi\) となります。
ここで、正の整数 \(X\) が \(2\) を素因数として \(k\) 個持つとは、奇数 \(B\) を用いて、\(X=2^k\times B\) と書けることを指し、各整数に対して、その整数が \(2\) を素因数として持つ個数は一意に定まります。（\(X\) を \(2\) で繰り返し割ったときに、割り切れる最大の回数とも言い換えられます。）

よって、\(T\cup U=S\) かつ \(T\cap U=\phi\) であり、これより \(\lvert S\rvert=\lvert T\rvert + \lvert U\rvert\) が成り立ちます。ここで、\(\lvert S\rvert, \lvert T\rvert, \lvert U\rvert\) はそれぞれ\(S,T,U\) の要素数を表します。

正の整数 \(b\) を用いて \(X=2\times b^2\) と書ける整数 は小さい方から \(2=(2\times 1^2)\), \(8=(2\times 2^2)\), \(18=(2\times 3^2)\), \(\ldots\) となるため、 \(\lvert T\rvert \) は \(2\times b^2\leq N\) であるような最大の非負整数 \(b\) の値となります。 同様に、\(\lvert U\rvert \) は \(2^2\times c^2\leq N\) であるような最大の非負整数 \(c\) の値となります。

\(2\times b^2\leq N\) であるような最大の非負整数 \(b\) について、\(2\times b^2\) は \(b\) に対して非負整数の範囲で狭義単調増加となることから、例えば二分探索によって求めることができます。\(b\) は少なくとも高々 \(\sqrt{N}\) であることから、\(O(\log N)\) の計算量で求めることが可能です。「\(2^2\times c^2\leq N\) であるような最大の非負整数 \(c\) 」についても同様に二分探索などで求めることが可能です。

よって、\(\lvert T\rvert, \lvert U\rvert\) の値が求まったため、これらの和をとることによって答えを求めることができます。時間計算量は \(O(\log N)\) であり、十分高速です。
よって、この問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;


int main(void){
	long long n;
	long long l,r,m,ans=0;
	const long long inf = (long long)1e9;
	cin >> n;

	l=0;r=inf;
	while((l+1)<r){
		m=(l+r)/2;
		if((m*m*2)<=n)l=m;
		else r=m;
	}
	ans+=l;

	l=0;r=inf;
	while((l+1)<r){
		m=(l+r)/2;
		if((m*m*4)<=n)l=m;
		else r=m;
	}
	ans+=l;

	cout << ans << endl;
	return 0;
}