← 返回题目列表

Codeforces · 2081/G2

G2. 硬公式(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$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