AT_xmascon19_d.Sum of (-1)^f(n)

对于正整数 $n$，定义 $f(n)$ 为 $n$ 的素因数（计重，即带有重复）的个数。例如，$200 = 2^3 \times 5^2$，因此 $f(200) = 5$。

给定一个正整数 $N$，请计算 $\sum_{n=1}^N (-1)^{f(n)}$ 的值。

$N$

请输出 $\sum_{n=1}^N (-1)^{f(n)}$ 的值，输出一行。

限制

• $1 \leq N \leq 10^{11}$。

部分得分

• 若能正确解决 $N \leq 10^{10}$ 的数据集，则可获得 $45$ 分。
• 若能正确解决无额外限制的数据集，则可获得另外 $55$ 分。

样例解释 1

$f(1) = 0$，$f(2) = 1$，$f(3) = 1$，$f(4) = 2$，$f(5) = 1$，$f(6) = 2$，因此答案为 $(-1)^0 + (-1)^1 + (-1)^1 + (-1)^2 + (-1)^1 + (-1)^2 = 0$。

由 ChatGPT 4.1 翻译