题意:对一个给定的n,从1到n,他们的σ[n]中有几个是偶数。pi 是n的素数因子,ei 是对应素因子的个数。
分析:对所有的素数,如果p为2,则那一项一定为奇数,对于不是2的素数,可以发现当ei+1为奇数的时候(因式分解你就懂了),即pi这个素因子出现偶数次时,那一项项也为奇数。

若使得那一整个式子为奇数,那么对于每一项只有两种方式,要么为2,要么p的为偶数次,再进一步思考,这完全可以通过n^2 和 2*n^2来得到所有满足的数。

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int main()
{
   
    int t, p = 0;
    ll n;
    scanf("%d", &t);
    while(t--)
    {
   
        p++;
        ll x, y;
        scanf("%lld", &n);
        x = (ll)sqrt(n);//计算n中x^2的个数
        y = (ll)sqrt(1.0 * n / 2);//计算n中2*x^2的个数
        printf("Case %d: %lld\n", p, n - x - y);
    }
    return 0;
}

参考博客:https://www.cnblogs.com/hchlqlz-oj-mrj/p/4703593.html
https://www.cnblogs.com/qq2424260747/p/4930861.html