题目大意：f(n)为n的因子和,给出 n 求 1~n 中f(n)为偶数的个数.
题目思路:算数基本定理:
n=p1^e1*p2^e1 …… pn^en （p为素数）；
f(n)=（1+p1+p1^2+p^3……+p^e1）*(1+p2+p2^2……+p2^e2)……*(1+pn+pn^2……+pn^en)。
偶数个个奇数相乘仍为奇数，奇数个奇数相乘则为偶数，为了使f(n)为奇数，那么多项式中的每一项都应为奇数。
对于每个多项式内：偶数个奇数相加为偶数，奇数个奇数相加为奇数，为了使多项式为奇数，那么e应为偶数（因为前面还要加1）。
我们知道：
若 n=p1^e1*p2^e1 …… pn^en；
那么 n^2=（p1^e1*p2^e1 …… pn^en）^2 =p1^2e1*p2^2e1 …… pn^2en。
2为唯一一个偶素数，且p=2的项一定为奇数。
所以我们则需要统计1到n中的平方数个数和2倍的平方数的个数，得到的为1到n中f(n)为奇数的个数。
#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define MAX 1005 using namespace std; int main()
{
int cnt=,T;
long long n,sum;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
sum=;
for(long long i=;i*i<=n;i++)
{
sum++;
if(*i*i <= n)
sum++;
}
printf("Case %d: %lld\n",cnt++,n-sum);
}
}