题意描述

给定一个整数 $N$ ，要求求出 $x\in[1, N]$ 中 $\sigma(x)$ 为偶数的 $x$ 的个数（$\sigma(x)$ 表示 $x$ 的正约数和）。

分析

将 $x$ 素因子分解之后得到
$$ x=\prod_{i=1}^{k}p_i^{\alpha_i} $$
则 $\sigma(x)$ 的计算公式：
$$ \sigma(x)=(p_1^0+p_1^1+\dots+p_1^{\alpha_1})\times(p_2^0+p_2^1+\dots+p_2^{\alpha_2})\times\dots\times(p_k^0+p_k^1+\dots+p_k^{\alpha_k}) $$
我们不方便研究 $\sigma(x)$ 为偶数的情况，我们可以研究 $\sigma(x)$ 为奇数的情况，再用总数减掉奇数的个数即可。

我们要让 $\sigma(x)$ 为奇数，则 $\sigma(x)$ 的每一个因子都要为奇数，所以可以分开考虑公式的每一项：

• 若 $2\mid x$，则 $(1+2^1+2^2+\dots+2^{\alpha})$ 这一项一定为奇数，因为 $2$ 的任何次幂都是偶数，加上 $1$ 就变成了奇数。
• 对于除了 $2$ 以外的其他素因子，我们想要让 $(1+p^1+p^2+\dots+p^{\alpha})$ 为奇数，即想让 $p^1+p^2+\dots+p^{\alpha}$ 为偶数，由于素因子的任何幂次都为奇数，所以只有当项数为偶数时，才能满足其为偶数，故可以得出其素因子的次数 $\alpha_i$ 都为偶数

综上所述，满足 $\sigma(x)$ 为奇数的数一定满足这样的形式：
$$ x=2^t\times\prod_{i=1}^{k}p_i^{\alpha_i}(p_i为素因子，且\alpha_i为偶数) $$
当次数都为偶数时，这个数其实就是一个完全平方数，所以可以简写成：
$$ x=2^t\times m^k $$
那么如何统计在 $[1, N]$ 中这样的数的个数呢？

• 当 $t$ 为偶数时，把 $2$ 这个质因子囊括进来，$x$ 就是一个完全平方数，这一部分就直接统计 $[1, N]$ 当中的完全平方数就可以。
• 当 $t$ 为奇数时，$\frac{x}{2}$ 就为完全平方数，所以再统计 $[1, N]$ 中满足形式为 $2\times a\times a$ 的形式的数即可。

Code：

// 原题链接：https://vjudge.net/problem/LightOJ-1336
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    for (int C = 1; C <= T; C ++ ) {
        LL n, res = 0; cin >> n;
        for (int i = 1; i <= n / i; i ++ ) {
            res ++ ;
            if ((LL)i * i * 2 <= n) res ++ ;
        }
        cout << "Case " << C << ": " << n - res << '\n';
    }
    return 0;
}