CF2081G2.Hard Formula (Hard Version)

这是本题的困难版本。两个版本的区别在于此版本对 $n$ 的限制和时间限制更高。只有当您解决了该问题的所有版本时才能进行 hack。

给定一个整数 $n$，你需要计算 $(\sum_{k=1}^n k \bmod \varphi(k)) \bmod 2^{32}$，其中 $\varphi(k)$ 表示不大于 $k$ 且与 $k$ 互质的正整数的数量。

输入仅包含一个整数 $n$（$1 \le n \le 10^{12}$）。

输出一个整数，表示 $(\sum_{k=1}^n k \bmod \varphi(k)) \bmod 2^{32}$ 的值。

翻译由 DeepSeek R1 完成