思路

我们要求解的目标是 $S = \sum_{i=1}^{n} \sigma(i)$ 的奇偶性，其中 $\sigma(i)$ 表示正整数 $i$ 的所有正因子之和。

一个和的奇偶性取决于其中奇数项的个数。如果奇数项的个数是奇数，那么和就是奇数；如果奇数项的个数是偶数，那么和就是偶数。因此，问题转化为：在区间 $[1, n]$ 中，有多少个整数 $i$ 使得 $\sigma(i)$ 是奇数。设这个数量为 $C$，我们最终要求的就是 $C \pmod 2$。

接下来我们分析 $\sigma(i)$ 为奇数的条件。 一个整数 $i$ 的标准素数分解为 $i = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$。 其正因子之和的公式为：