problem 512 // project euler

Sums of totients of powers
Let $phi(n)$ be Euler’s totient function.

Let $f(n)=(Sigma^n_{i=1}phi(n^i)) text{ mod } (n+1)$.

Let $g(n)=Sigma^n_{i=1}f(i)$.

$g(100)=2007$.

Find $g(5 times 10^8)$.

幂的欧拉总计函数和

记$phi(n)$为欧拉总计函数。

记$f(n)=(Sigma^n_{i=1}phi(n^i)) text{ mod } (n+1)$。

记$g(n)=Sigma^n_{i=1}f(i)$。

已知$g(100)=2007$。

求$g(5 times 10^8)$。