---

Problem 512

---

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)$。

---