由 [SDOI2012]Longge的问题探讨欧拉函数和莫比乌斯函数的一些性质和关联-白红宇的个人博客

由 [SDOI2012]Longge的问题探讨欧拉函数和莫比乌斯函数的一些性质和关联

发布日期：2021-05-09 06:59:04 浏览次数：9 分类：博客文章

本文共 4330 字，大约阅读时间需要 14 分钟。

本题题解

题目传送门：

给定一个整数$n$，求

\[\sum_{i=1}^n \gcd(n,i)\]

蒟蒻随便yy了一下搞出来个$O(\sqrt{n})$的算法 ~~这题数据怎么这么水~~

首先看到gcd我们就下意识的对它反演一波对吧

第一步

\[\sum_{i=1}^n \gcd(n,i) = \sum_{d|n} \varphi(d) \frac{n}{d}\]

这里提供两种化法，得到的结果都是这个。

法一

根据欧拉函数和式

\[n = \sum_{d|n} \varphi(d)\]

暴力推导即可

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

法二

根据欧拉函数的定义式

\[\varphi(n) = \sum_{i=1}^n [\gcd(n,i) = 1]\]

PS：$\varphi(n)$表示$1$~$n-1$内与$n$互质的数，将和式上界提升到$n$不但不会影响正确性（$\gcd(n,n) = n \neq 1$），而且让$\varphi(1)$不用特判。

易得

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

这一步还是比较简单的。~~稍有基础的同学大概都会吧~~

第二步

令

\[g(n) = \sum_{i=1}^n \gcd(n,i) = \sum_{d|n} \varphi(d) \frac{n}{d}\]

我们希望求$g$的在$n$的函数值。容易发现右式是狄利克雷卷积$\varphi * Id$，也就是说$g$也是积性函数。所以考虑质因数分解$n$，最后用积性累乘出来

即

\[g(n) = g({p_1}^{c_1}) g({p_2}^{c_2}) ... g({p_n}^{c_n})\]

则只需求$g(p^c)$（这里省略下标）

$p^c$的因数分别为$1$，$p$，$p^2$，...，$ p^c$

所以有

\[\begin{aligned}g(p^c) &= \sum_{i=0}^{c} \varphi(p^i) \frac{p^c}{p^i} \\&= \sum_{i=0}^{c} \varphi(p^i) p^{c-i}\end{aligned}\]

求$\varphi(p^c)$

考虑先弄出上式中$\varphi(p^i)$的封闭形式，再带回原式看看

根据欧拉函数通式

\[\varphi(n) = n \prod_{i=1}^k (1 - \frac 1 {p_i})\]

（这个$\pi$指的是分解质因数）

易得

\[\begin{aligned}\varphi(p^c) &= p^c (1 - p) \\&= p^c - p^{c-1}\end{aligned}\]

注意这个式子需要在$c=0$时特判，因为$\varphi(1) = 1$（$1$可以视作分解不出任何质因数）

求$g(p^c)$

得到了$\varphi(p^c)$，带回之前未推完的$g(p^c)$的式子，得

\[\begin{aligned}g(p^c) &= \sum_{i=0}^{c} \varphi(p^i) p^{c-i} \\&= p^c + \sum_{i=1}^{c} (p^i - p^{i-1}) p^{c-i} \\&= p^c + \sum_{i=1}^{c} (p^c - p^{c-1}) \\&= p^c + c (p^c - p^{c-1}) \\&= (c+1)p^c - c \ p^{c-1}\end{aligned}\]

（中途对$i=0$进行了特殊讨论）（该式同样不适用于$c=0$的情况）

然后积性合并起来就完了

冷静分析一波时间复杂度。质因数分解消耗$O(\sqrt n)$的时间复杂度，分解出不超过$O(log_2 n)$个$p^c$，每个$g(p^c)$的计算是$O(1)$的。所以总时间复杂度为$O(\sqrt n)$

代码

非常简单的代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;ll p[1005],c[1005],g[1005];ll kN;void Div(ll n){ kN=0; for(ll i=2;i*i<=n;i++){ if(n%i==0){ kN++;p[kN]=i; g[kN]=1; ll e=0;while(n%i==0) e++,n/=i,g[kN]*=i; c[kN]=e; } } if(n!=1) kN++,p[kN]=n,c[kN]=1,g[kN]=n;}ll N;int main(){ cin>>N; Div(N); ll pdt=1; for(int i=1;i<=kN;i++) pdt=pdt*((c[i]+1)*g[i]-c[i]*g[i]/p[i]); cout<

~~这式子长得跟很像？~~

-- 愿君每日到此一游！

本题题解

第一步

法一

法二

第二步

求\(\varphi(p^c)\)

求\(g(p^c)\)

代码

更多思考

拓展到莫比乌斯函数

小小的总结

莫比乌斯函数与欧拉函数的相互关系

upd 2019/11/04 用狄利克雷卷积证明

发表评论

最新留言

关于作者

推荐文章