思路
我们要求解的目标是 S=∑i=1nσ(i) 的奇偶性，其中 σ(i) 表示正整数 i 的所有正因子之和。
一个和的奇偶性取决于其中奇数项的个数。如果奇数项的个数是奇数，那么和就是奇数；如果奇数项的个数是偶数，那么和就是偶数。因此，问题转化为：在区间 [1,n] 中，有多少个整数 i 使得 σ(i) 是奇数。设这个数量为 C，我们最终要求的就是 C(mod2)。
接下来我们分析 σ(i) 为奇数的条件。
一个整数 i 的标准素数分解为 i=p1a1p2a2⋯pkak。
其正因子之和的公式为：
P3699.第3题-是0还是1
题目内容
给定一个正整数n。对于区间[1,n]，求区间内所有整数的正因子之和的奇偶性。
因子:对于正整数x，如果存在正整数p使得x能被P整除，则称p是x的因子。例如，12的因子有1,2,3,4,6,12
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≦T≦2×104)表示数据组数;
此后T行,每行输入一个整数n(1≦n≦1018)。
输出描述
对于每组测试数据，新起一行，输出一个整数，表示区间[1,n]内所有整数的正因子之和的奇偶性：奇数输出1，偶数输出0
样例1
输入
5
1
2
3
4
8
输出
1
0
0
1
0
说明
- 当n=1时:1的因子只有1，总和为1(奇数)，输出1;
- 当n=2时:在n=1的基础上再加上2的因子 1、2，总和变为4(偶数)，输出0;
- 当n=3时:再加上3的因子1、3，总和变为8(偶数)，输出0;
- 当n=4时:再加上4的因子1、2、4，总和变为15(奇数)，输出1;
