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 翻译