C - Sigma Function(LightOJ 1336)

传送门
Password: nefu

题目大意：
就是给你一个数 n 让你求<=n的所有 i 的因子的个数加起来是偶数的个数
比如 一个数 6： 6的因子有 1 2 3 6，所以1+2+3+6 = 12是偶数所以
符合条件

解题思路：
其实我刚开始的时候也没有什么思路，就想着将 <= n的数都进行素因子
分解，n = p1^e1 * p2^e2 * … * pk^ek
F(n) = (p1^(e1+1)-1)/(p1-1) * ^ (p2^(e2+1)-1)/(p2-1)… (pk^(ek+1)-1)/(pk-1)
首先保证其中一项有一个偶数，那考虑起来比较麻烦 所以 我们只需要考虑
奇数的情况就行啦，所以假设 这个 n 是一个平方数，那n == P*P,
F(n) == ((P^3)-1)/(p-1) == P^2+P+1，假设 P是奇数 F(n)是奇数
假设P是偶数 F(n)还是奇数 所以，当这个数是平方数的时候是不符合条件
的，同理当时平方数的2倍的时候，也是不行的，因为当n == 2的时候是
奇数 其实这些规律是在先打完表之后才看出来的看出来了 然后再推一遍
其实推完之后代码就几行。。。
上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;

#define MM(a) memset(a,0,sizeof(a))

typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 1e6+5;
const int mod = 1000000007;
const double eps = 1e-7;
/**
bool prime[MAXN];
LL p[MAXN];
LL k;
void isprime()
{
    k = 0;
    prime[1] = false;
    memset(prime, true, sizeof(prime));
    for(LL i=2; i<MAXN; i++)
    {
        if(prime[i])
        {
            p[k++] = i;
            for(LL j=i*i; j<MAXN; j+=i)
                prime[j] = false;
        }
    }
}
LL fac[MAXN/10],num[MAXN/10],cnt;
void Dec_prime(int m)
{
    cnt = 0;
    MM(num);
    for(LL i=0; p[i]*p[i]<=m&&i<k; i++)
    {
        if(m%p[i] == 0)
        {
            fac[cnt] = p[i];
            while(m%p[i]==0)
            {
                num[cnt]++;
                m /= p[i];
            }
            cnt++;
        }
    }
    if(m > 1)
    {
        fac[cnt] = m;
        num[cnt++] = 1;
    }
}
LL Cal(LL a, LL b)
{
    LL ans = 1;
    while(b--)
        ans *= a;
    return ans;
}
LL ret[MAXN/10];
void Init()
{
    for(int i=0; i<MAXN/10; i++)
        ret[i] = 1;
}
**/
int main()
{
    ///isprime();
    int T;
    LL n;
    cin>>T;
    for(int cas=1; cas<=T; cas++)
    {
        cin>>n;
        /**
        Init();
        for(int j=1; j<=100; j++)
        {
            Dec_prime(j);
            for(int i=0; i<cnt; i++)
            {
                ret[j] *= (Cal(fac[i],num[i]+1)-1)/(fac[i]-1);
            }
        }
        LL sum = 0;
        for(int i=1; i<=100; i++)
            if(ret[i] % 2 == 0)
                puts("YES");
            else
                puts("NO");
        **/
        LL ret = 0;
        for(int i=1; (LL)i*i<=n; i++)///去掉 n^2 和 2*n^2
        {
            ret++;
            if(2*(LL)i*i <= n)
                ret++;
        }
        printf("Case %d: %lld\n",cas,n - ret);
    }
    return 0;
}

去掉注释的那几行 只需要看主程序的就行，注释的是辅助理解的，是为了打表做准备的