P17464 Wiš'adel

$\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 Lover}$，他想计算 $\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}$$

一个整数表示 $N$。

一个数字表示结果。

- Subtask1（10pts）$N\leq 10^{8}$，时间限制 $2s$。 - Subtask2（10pts）$N\leq 10^{10}$，时间限制 $2s$。 - Subtask3（20pts）$N\leq 10^{11}$，时间限制 $2s$。 - Subtask4（20pts）$N\leq 10^{12}$，时间限制 $3s$。 - Subtack5（40pts）$N\leq 10^{13}$，时间限制 $5s$。 $\text{PRTS}$ 认为，整形除法的常数远大于浮点除法，因此在大量需要整形除法的场景中请尽可能地使用浮点除法。