P6759: 鲍勃的数学题

---

【题目描述】

【题目描述】
继上次鲍勃在排序算法的研究上遭遇失败之后，这次他开始研究数论问题。他学习了欧拉函数的定 义：ϕ(n) 等于小于等于 n 的与 n 互质的正整数的个数。
鲍勃又发现了一种神奇的数字，这些数字 x 满足 ϕ(x) 的最大质因子不超过 5。
鲍勃想让你帮忙计算一下，1 ∼n 内神奇数字的和是多少？由于答案过大，请你输出答案对 2^32 取模后的值
【输入格式】
第一行一个整数 n(1 ≤ n ≤ 10^12)，代表题目中的范围。
【输出格式】
对于每组数据，输出一行一个答案，代表 1 ∼n 内神奇数字的和。对 2^32 取模后的值
样例

math.in	math.out
1000000000000	939087315
23	253

【数据范围与约束】 
共 10 组数据

测试点	n ≤
第 i 组数据	10^(i+2)

【提示】 
第一个不神奇的数字是 23，ϕ(23) = 22 = 2 ∗ 11 

题目类型~

NOIP模拟赛 

咻咻~

提交答案 状态 返回