每日一题[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$,求和即得.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复