这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$n$$$ 的限制和 时间限制 更高。只有解决了该问题的所有版本,您才能破解。
给定一个整数 $$$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}$$$。
示例
输入复制
5
输出复制
2
输入复制
10000000
输出复制
2316623097
输入复制
10000000000
输出复制
282084447