wisadel

注意：这是本题的第二个部分，在这里提交将评测第 $5$ 个 subtask 的数据，并获取对应分数，需要测试样例的请在 wisadel_sub1 中提交。

在这个子任务中：时间限制 $6\text{s}$，空间限制 $1024\text{MiB}$。

题目背景

$\color{black}{\text{W}}\color{red}{\text{iš'adel}}$ 有 $n$ 个祖宗，第 $k$ 个祖宗的攻击力为 $k\bmod\varphi(k)$，其中 $\varphi(n)$ 为 $[1,n]$ 中与 $n$ 互质的非零自然数个数。

由于 $\color{black}{\text{D}}\color{red}{\text{octor}}$ 是看血狼破军看的，热衷于计算干员的 $\text{DPS}$。他想计算 $\color{black}{\text{W}}\color{red}{\text{iš'adel}}$ 的 $\text{DPS}$ 就得先计算她所有祖宗的攻击力之和，但是 $\color{black}{\text{D}}\color{red}{\text{octor}}$ 最近沉迷萨卡兹的无终奇语无法自拔，于是他请你来帮他计算 $\color{black}{\text{W}}\color{red}{\text{iš'adel}}$ 所有祖宗的攻击力之和。

因为 $\color{black}{\text{D}}\color{red}{\text{octor}}$ 是前文明最后的人类，实力非凡，所以你只需要输出答案对 $2^{32}$ 取模的结果他就可以计算出 $\color{black}{\text{W}}\color{red}{\text{iš'adel}}$ 的 $\text{DPS}$。

题目描述

请计算：

$$(\sum_{k=1}^N k\bmod\varphi(k))\bmod 2^{32}$$

输入输出样例

【样例 $1$ 输入】

10

【样例 $1$ 输出】

8

【样例 $2$ 输入】

10000000000

【样例 $2$ 输出】

282084447

【样例 $3$ 输入】

1000000000000

【样例 $3$ 输出】

3875137357

【样例 $4$ 输入】

5

【样例 $4$ 输出】

2

数据规模与约定

• Subtask 1（10pts）: $N\leq 10^{8}$。
• Subtask 2（30pts）: $N\leq 10^{10}$。
• Subtask 3（5pts）: $N\leq 10^{11}$。
• Subtask 4（40pts）: $N\leq 10^{12}$。
• Subtack 5（15pts）: $N\leq 10^{13}$。

提示

$\text{PRTS}$ 认为，整形除法的常数远大于浮点除法，因此在大量需要整形除法的场景中请尽可能地使用浮点除法。

受评测机限制，出题人下发一个筛 $\varphi$ 的小常数杜教筛模板。

使用方法：

调用 SIEVE::SIEVE(long long,std::vector<unsigned>&,std::vector<unsigned>&) 时，传入的第一个参数为执行杜教筛的范围，传入的 std::vector 为空。

运行结束后会将两个传入的 std::vector 填充杜教筛结果。std::vector 长度为 $\sqrt{\lfloor n\rfloor}+1$，填充方式为：第一个 std::vector 中下标为 $i$ 的位置储存 $S_\varphi(\lfloor\frac{n}{i}\rfloor)$ 的值，第二个 std::vector 中下标为 $i$ 的位置储存 $S_\varphi(i)$ 的值。特别的，两个 std::vector 中下标为 $0$ 的位置均为 $0$。