Luogu 2303 – Longge的问题

题目链接:Luogu – 2303

对于${\rm gcd}(i,n)分类讨论$:

$$\begin{aligned}  \sum_{i = 1}^{n} {\rm gcd }(i,n)  & = \sum_{d | n} d \sum_{i = 1}^{n} [{\rm gcd}(i,n) = d] \\ &= \sum_{d | n} d \sum_{i = 1}^{\frac{n}{d}} [{\rm gcd}(i,\frac{n}{d}) = 1] \\ &= \sum_{d | n} d \varphi (\frac{n}{d})  \end{aligned} $$

那么我们可以$O(\sqrt{n})$的时间枚举$d$,对于每一个$d$,可以$O(\sqrt{n})$的时间内求出$\varphi (\frac{n}{d})$,满足条件的$d$很少,因此这里的复杂度是$O(k \times\sqrt{n})$,$k$为$n$的因数个数。

 

说点什么

avatar
50
  Subscribe  
提醒