hdu2608 0 or 1
题意：给你一个数N（N < 2^）, 问从 1--N 所有数的因子和S(N)，求 S(N)%2 的值。
链接：http://acm.hdu.edu.cn/showproblem.php?pid=2608
思路：参考了下其它博客，自己总结如下：
对于每一个数N，我们可以将其拆分为 N = 2^ * p^ * p^ * ... * p^ （e1可能是0）。其中p1, p2... 都是 N 质因子。因为 N = 2^ * p^ * p^ * ... * p^ ，我们可以的得到：
T[N]= [ ( 2^+2^+...+2^ ) * ( p^+p^+...+p^ ) * ... * ( p^+p^+...+p^ ) ]% 2；
（ N的因子数有K个， K = (e+1) * (e+1) * ... * (e+1)，排列组合原理，大家可以随便模拟一个数）;
我们知道 ( 2^+2^+...+2^ )% 2 = 1 恒成立（因为有2^=1），所以T[N]的值只取决与后面的乘式%2 是否出现了0，那么后面的式子怎样才会是零呢？很简单，因为所有的质素都是奇数，所以当除2以外的存在某一个质因子表达式为偶数项的时候就会为零了（偶数个奇数相加为偶数），也即只要满足至少存在一个 ei 的值为奇数（质因数 pi 项数为 ei- 0+ 1）。当然这题中，我们不会去直接计算为 0 的 T[i] 有多少多，这很困难，而是从反面求解，即计算 T[i] 为 1 的数的个数，这样，求 S[N] 也就转化为从 1-N 有多少个 T[i] 为1。回到前面，如果 T[i] 为 1，那么除了 2 之外所有质因子的 ei 都为偶数，这个条件就很好解决了，而不像前面的求解满足至少一项 ei 为奇数，既然除了 2 之外所有的 ei 都为偶数，所以：
i = 2^* p2^ * p3^ * ... * pm^ = (2^ * P2^ * P3^ * ... * pm^)^ = x^ ......(1)
或：i = 2^* p2^ * p3^ * ... * pm^ = 2*(2^ * P2^ * P3^ * ... * pm^)^ = 2 * x^ ......(2)
那么这个数一定会是 i = x^ 或者是 i= 2* x^ 的形式。所以统计从 1-N 之间有多少个满足 T[i] = 1 数吧。
那么 N 以内的数满足 (1) 和 (2) 式子的有多少呢？
首先，看一下满足(1)式子的个数： s1 = sqrt(n) 取下整，所以 ： s1 = (int)sqrt(n*1.0) ;
然后，再看一下满足(2)式子的个数： s2 = sqrt(n/2.0) 取下整，所以 ： s2 = (int)sqrt(n/2.0) 。
所以，1--N 内满足 T[i] = 1 的个数有 s1 + s2 个。
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std; int main()
{
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
printf("%d\n",((int)sqrt(n*1.0)+(int)sqrt(n/2.0))&);
}
return ;
}