题解

考虑直接枚举 $i$ 作为 $\sqrt x$，那么接下来只需要判定 $i^2$ 的每一位是否为偶数即可。

我们只需要把这个数拆掉每一位单独去判就行，这个时间复杂度是 $O(\log_{10} i^2)$ 的。

总时间复杂度是 $O(\sqrt n \log_{10} x)$。

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main()
{
    fst
    ll n; cin >> n;
    ll ans = 0;
    for (ll i = 0; i * i <= n; i += 2) {
        ll x = i * i; bool ok = 1;
        while (x) {
            if ((x % 10) & 1) {
                ok = 0;
                break;
            }
            x /= 10;
        }
        ans += ok;
    }
    cout << ans;
    return 0;
}