931. Totient Graph

For a positive integer $n$$n$ construct a graph using all the divisors of $n$$n$ as the vertices. An edge is drawn between $a$$a$ and $b$$b$ if $a$$a$ is divisible by $b$$b$ and $a/b$$a/b$ is prime, and is given weight $\varphi (a)-\varphi (b)$$\phi(a)-\phi(b)$, where $\varphi$$\phi$ is the Euler totient function.
Define $t(n)$$t(n)$ to be the total weight of this graph.
The example below shows that $t(45)=52$$t(45) = 52$

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

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

931. 欧拉总计函数图

对一个正整数 $n$$n$，我们按如下规则建一张带权图：将 $n$$n$ 的所有约数作为结点；对于 $n$$n$ 的约数 $a$$a$、$b$$b$，若 $b$$b$ 整除 $a$$a$ 且 $a/b$$a/b$ 是质数，则在 $a$$a$、$b$$b$ 之间连一条权为 $\phi (a)-\phi (b)$$\varphi(a) - \varphi(b)$ 的边，其中 $\phi$$\varphi$ 代指欧拉总计函数 (Euler totient function)。我们记 $t(n)$$t(n)$ 为该图的边权和。例如，下图说明了 $t(45)=52$$t(45) = 52$。

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

求 $T({10}^{12})$$T(10^{12})$ 模 $715827883$$715827883$ 的值。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。