---

Problem 931

---

Totient Graph

For a positive integer $n$ construct a graph using all the divisors of $n$ as the vertices. An edge is drawn between $a$ and $b$ if $a$ is divisible by $b$ and $a/b$ is prime, and is given weight $\varphi (a)-\varphi (b)$, where $\varphi$ is the Euler totient function.

Define $t(n)$ to be the total weight of this graph.

The example below shows that $t(45)=52$:

Let $T(N)={\displaystyle \sum _{n=1}^{N}t(n)}$. You are given $T(10)=26$ and $T({10}^2)=5282$.

Find $T({10}^{12})$. Give your answer modulo $715827883$.

---

欧拉函数图

对于正整数$n$，以$n$的所有因数为顶点构造图。若$a$能被$b$整除，且$a/b$是素数，则在$a$和$b$对应的顶点之间作一条边，该边的权重为$\varphi (a)-\varphi (b)$，其中$\varphi$表示欧拉函数。

定义$t(n)$为该图的总权重。

下图展示了$t(45)=52$：

令$T(N)={\displaystyle \sum _{n=1}^{N}t(n)}$。已知$T(10)=26$，$T({10}^2)=5282$。

求$T({10}^{12})$，并对$715827883$取余作为你的答案。

---