Problem J: 看似简单的题目
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$29$ |
正确数量 |
$11$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
数论 数学 |
当前分类(单击移除)：
数论数学
单击选择分类：
众所周知，欧拉函数$\phi(n)$表示小于或等于$n$ 的正整数中与$n$互质的数的个数。现在定义$f(n)$如下： $$f(n)=(\sum_{i=1}^{n}\phi(n^i))\mod(n+1)$$ 如果要是让你求$f(n)$，那非常简单，现在需要求的是它的前缀和$g(n)$。$g(n)$的定义如下： $$g(n)=\sum_{i=1}^{n}f(i)$$ 当然这仍然是非常简单的，你可以告诉我是多少吗？
第一行输入正整数$T$，表示数据的组数。
每组数据为一个正整数n。
数据范围: $1 \le n$,$T \le 10^6$ 。
对于每组数据，输出一行，格式为'Case #t: x'，t 为数据的组
号，$x$ 为$g(n)$的值。
Case 1: 19
Case 2: 20263333
Case 3: 3