D - Sigma Function 1~n内有多少个约数和为偶数

/**
题目：D - Sigma Function
链接：https://vjudge.net/contest/154246#problem/D
题意：求1~n内约数和为偶数的数的个数。
思路：一个数的约数和为那个数的每个素因子的等比和相乘。如题目所给公式就是等比和化简之后的式子。
那么要判断一个数约数和是否为偶数，可以通过观察它的各个素因子等比和来判断。如果存在某个素因子的等比和为偶数。
那么这个约数和肯定是偶数。否则为奇数。
素因子只有2是偶数，其他都是奇素数。

含素因子2的等比和一定为奇数。其他都是奇素数，只有奇数次方，等比和才是偶数。（未化简之前的式子更好用来判断奇偶）
为了更好处理，求所有奇数约数和的个数。然后总的减去即可得偶数约数和的个数。
奇数约数和：
1，如果素因子不含2，那么肯定是一个平方数。各个素因子次方为偶数。
2，如果素因子含2，那么仍然是与2的若干次方相乘的那个数必须是平方数，他们的乘积是奇数约数和。

于是：假定这里的平方数不再包含2这个素因子。
2^0 * 平方数 为奇数约数和
2^1 * 平方数
2^2 * 平方数
2^3 * 平方数
.
.
2^e * 平方数

观察发现。2^2 * 平方数其实已经包含在2^0 * 平方数里面了；
2^3 * 平方数也包含在2^1 *平方数里面了。实质上把2^2转移到那个平方数里面了。

因此只要考虑 一个平方数，以及2*一个平方数 这两种情况都是奇数约数和，且不会重复因为一个2*平方数结果肯定不是平方数。

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+100;
ll n;
int main()
{
int T, cas=1;
    cin>>T;
while(T--)
    {
        scanf("%lld",&n);
        ll ans = (ll)sqrt(n/2)+(ll)sqrt(n);///开根号可能有浮点数误差，有时候要特别处理。
        printf("Case %d: %lld\n",cas++,n-ans);
    }
return 0;
}