唯一分解定理，有点难，需要推理，也可以找规律。题意：定义T(n)为能整除n的所有正整数的和，S(n) = T(1) + T(2) + ... + T(n)。现在给你一个32位有符号整型范围类的数n，输出S(n)%2的值。
我的解题思路：首先根据定义T(n)为能整除n的所有正整数和，即T(n)就是n的所有正因子和。根据唯一分解定理的推论，一个整数n的唯一分解式是n = p1^a1 * p2^a2 * ... * pn^an，那么n的全体正因子和为(1 + p1 + p1^2 + ... + p1^a1) * (1 + p2 + p2^2 + ... + p2^a2) * ... * (1 + pn + pn^2 + ... pn^an)。
有了这个公式，现在我们要判断奇偶性，T(n)为偶数当且仅当至少有一个括号项内的值为偶数，因为偶数乘任何数都是偶数。
由于pi是质数，而质数里面只有2一个偶数，其他都是奇数，所以我们有必要单独讨论一下2是因子的情况。如果2是n的因子，那么n的分解是可以写成(1 + 2 + 2^2 + ... + 2^a1) * ... * (1 + pn + pn^1 + ... pn^an)。2的正整数次幂之和绝对是偶数，因此1 + 2 + 2^2 + ... + 2^a1必定是奇数。现在我们讨论一下pi是奇数的情况，奇数的正整数次幂必定是奇数，偶数个奇数的和必定是偶数，因此只有当ai是奇数时底数为pi的括号项为偶数。所以如果T(n)为奇数的话当且仅当pi不为2时ai为偶数。
当T(n)是奇数时由于唯一分解式中非2的的质因数的幂是偶数，所以n也可以分解成这样的形式n = 2^x * y^2，当x为奇数是可以表示成n = 2 * z^2，当x为偶数时可以表示成n = z^2。因此可以得出结论：如果n可以被分解成某个正整数的平方或者某个正整数平方的两倍，那么T(n)为奇数，否则为偶数。
现在，要判断S(n)的奇偶性，需要算出1到n中T(n)为奇数的个数然后判断奇偶就行了，一个一个枚举显然超时，我们可以枚举i^2和2*i^2，这样时间复杂度就降到了根号n了。
我的解题代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long Long;
int n, ans;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
ans = 0;
for (Long i=1; i*i<=n; ++i)
{
ans++;
if (2 * i * i <= n) ans++;
}
printf("%d\n", ans % 2);
}
return 0;
}