So far, there is no English solution for this problem, so I wrote one.

Below are two different approaches to solve the problem:

\(O(\log n)\) Solution

Since the function \(2^a\) grows very quickly, we can consider enumerating values of \(a\) and calculate the valid range of \(b\) accordingly.

The original condition is:

\[ 1 \le 2^a \times b^2 \le n \]

If we fix a value of \(a\), we can move \(2^a\) to the right-hand side:

\[ 1 \le b^2 \le \frac{n}{2^a} \]

As \(b^2\) increases with \(b\), we can binary search to find the maximum valid \(b\).

However, this approach may count some values multiple times. Notice that when we compute for \(a = 2\), we already count all cases where \(a\) is divisible by \(2\), and when \(a = 1\), we cover all \(a\) where \(2 \nmid a\). So we only need to calculate for \(a = 1\) and \(a = 2\).

Thus, the overall time complexity is \(O(\log n)\), which is efficient enough for this problem.

#pragma GCC optimize(3,"Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
int a[N];
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int n;cin>>n;int cnt=0;
    for(int i=1;i<=2;++i){
        int k=(1ll<<i);
        if(k>n)break;
        if(k==n)++cnt;
        else{
            int l=1,r=n,best=0;
            while(l<=r){
                int mid=l+r>>1;
                __int128 val=(__int128)k*mid*mid;
                if(val<=n)best=mid,l=mid+1;
                else r=mid-1;
            }
            cnt+=best;
        }
    }
    cout<<cnt<<'\n';
    return 0;
}

\(O(1)\) Solution

We can further optimize the step where we calculate:

How many integers \(b\) satisfy \(1 \le b^2 \le \frac{n}{2^a}\)?

Taking the square root on both sides gives:

\[ 1 \le b \le \sqrt{\frac{n}{2^a}} \]

So the number of valid \(b\) is:

\[ \left\lfloor \sqrt{\frac{n}{2^a}} \right\rfloor \]

This value can be computed in \(O(1)\) time using built-in functions like sqrtl in C++ or math.isqrt in Python.

#pragma GCC optimize(3,"Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
int a[N];
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int n;cin>>n;
    int c1=sqrtl(n/2),c2=sqrtl(n/4);
    cout<<c1+c2<<'\n';
    return 0;
}

import math
n=int(input())
c1=int(math.isqrt(n//2))
c2=int(math.isqrt(n//4))
print(c1+c2)