每日一题[1572]递归

设 $\displaystyle g(n)=\sum\limits_{k=1}^{n}{(k,n)}$，其中 $n\in\mathbb N^{\ast}$，$(k,n)$ 表示 $k$ 与 $n$ 的最大公约数，则 $g(100)$ 的值为_______．

答案    $520$．

解析    根据函数 $g(x)$ 的定义，若正整数 $m$ 与 $n$ 互质，则 $g(mn)=g(m)\cdot g(n)$．因此

$$g(100)=g(2^2)\cdot g(5^2)=8\cdot 65=520.$$

备注    事实上，若 $p$ 为质数，则 $g(p^n)=n\cdot p^{n-1}(p-1)+p^n$，证明如下．在 $1,2,\cdots,p^n$ 中，与 $p^n$ 的最大公约数为 $p^k$（$k=0,1,\cdots,n-1$）有 $p^{n-k}-p^{n-k-1}$ 个．与 $p^n$ 的最大公约数为 $p^n$ 的只有一个，为 $p^n$，求和即得．