Sigma Function (数论）

http://https://cn.vjudge.net/problem/LightOJ-1336

题意:

输入一个数n，求在1到n的范围内因子之和位偶数的数的个数。

解题思路:

首先我们需要知道一个数k可以写成k=(p1^e1)*(p2e2)…(pi^ei),
然后根据题目给的公式可以知道因子之和为θ(n)=(1+p1+p1^2+…+p1e1)…(1+p2+p2^2+…+p2e1).  
因此，若要因子和为偶数，只需要任意K=(1+pi+pi^2+…+piej)%2==0即可，  
然后我们讨论到pi,ej为什么数的时候为偶数,然后我们可以知道  
1. pi为奇，ei为奇时，K为偶数；  
2. pi为奇，ei为偶时，K为奇数；  
3. pi为偶，ei为奇时，K为奇数；  
4. pi为偶，ei为偶时，K为奇数；  
此时，我们想，是不是只要遍历1到n，然后在质因数分解，只要有pi，ei同时为奇数就可以求出来了。但问题是时间限制为2000ms,并且n<=10^12。并且这个条件，明显是会tle的。于是，我们要想另外想方法。  
我们可以反过来求，求不满足条件的。  
那要找到不满足条件的数，那样的数的组成可以根据我们上面找到的规律分类。2和4可以归类为平方数，3可以看成一个平方数2(因为偶素数只有2)，那么三种情况随机组合有：平方平方；平方平方2；平方2平方2(还是平方)。就可以归类成平方数和平方数2的集合。  
我们知道n里面肯定有sqrt(n)个平方数，有sqrt(n/2)个平方数*2,那么这题就解出来了。

#include<string.h>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
	long long n,T;
	while(cin>>T)
	{
		for(int i=1;i&lt;=T;i++)
		{
			cin>>n;
			cout<<"Case "<<i<<": "<<n-(long long)sqrt(n)-(long long)sqrt(n/2)<<endl;
		}
	}
	
} 

Q.E.D.