3802. [JZOI 2022 day2]鲍勃的数学题

【题目描述】

继上次鲍勃在排序算法的研究上遭遇失败之后，这次他开始研究数论问题。他学习了欧拉函数的定义：$ϕ(n)$ 等于小于等于 $n$ 的与 $n$ 互质的正整数的个数。

鲍勃又发现了一种神奇的数字，这些数字 $x$ 满足 $ϕ(x)$ 的最大质因子不超过 $5$。

鲍勃想让你帮忙计算一下，$1 ∼ n$ 内神奇数字的和是多少？由于答案过大，请你输出答案对 $2^{32}$ 取模后的值。

【输入格式】

第一行一个整数 $n(1 ≤ n ≤ 10^{12})$，代表题目中的范围。

【输出格式】

对于每组数据，输出一行一个答案，代表 $1 ∼ n$ 内神奇数字的和对 $2^{32}$ 取模后的值。

【样例1输入】

1000000000000 
23

【样例1输出】

939087315
253

【样例2输入】

9165831229

【样例2输出】

3835468396

【数据规模与约定】

第 $i$ 组数据，$n \leq 10^{i+2}$。

【提示】

第一个不神奇的数字是 $23$，$ϕ(23) = 22 = 2 \times 11$

【来源】

焦作一中 NOIP 2022 模拟赛2022.11.23 pro2