Problem J: 看似简单的题目

$37.93\%$ 下一题

Description

众所周知，欧拉函数

$\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

AOJ

祝同学们学习进步，编程快乐！