分析
由唯一分解定理可以得出，对于一个数(x)，其约数和为：
- (f(x)= (1+p_1+p_1^2+...+p_1^{a_1}) imes (1+p_2+p_2^2+...+p_2^{a_2}) imes ... imes (1+p_n+p_n^2+...+p_n^{a_n}))
显然如果(p)为(2)的话它的所有幂次和加上(1)的结果都是奇数，而其他的质数都是奇数，当它的最高幂次为偶数的时候，它的所有幂次之和加上(1)才是奇数，而只有上式中的所有每个括号里面的和都是奇数的情况下，(f(x))的值才会等于奇数。也就是说，如果(x)为一个平方数或者(x)为一个平方数乘以(2)的幂次的数，那么(f(x))的值一定是奇数。
具体实现
计算小于(n)的所有平方数好说，它为(sqrt(n))，但是还有乘以(2)的幂次的情况啊。其实，只要考虑乘以(2)的情况就行了，比如说一个平方数乘(4)，那么这个数肯定是一个平方数，前面已经计算过了，再比如说一个平方数乘(8)，其实就是乘(4)的那个平方数再乘(2)。所以排除掉平方数之后(f(x))为奇数的数的数量为(sqrt(n/2))。
int main(void) {
int t,kase=1;
scanf("%d", &t);
while(t--) {
ll n;
scanf("%lld", &n);
ll ans = n;
ans -= (ll)sqrtl(n);
ans -= (ll)sqrtl(n/2);
printf("Case %d: %lld
", kase++, ans);
}
return 0;
}