2019年南京网络赛E题K Sum(莫比乌斯反演+杜教筛+欧拉降幂)
- 题目链接
- 思路
- 代码
题目链接
传送门
思路
首先我们将原式化简：
\[\begin{aligned} &\sum\limits_{l_1=1}^{n}\sum\limits_{l_2=1}^{n}\dots\sum\limits_{l_k=1}^{n}gcd(l_1,l_2,\dots,l_k)^2&\\ =&\sum\limits_{d=1}^{n}d^2\sum\limits_{l_1=1}^{n}\sum\limits_{l_2=1}^{n}\dots\sum\limits_{l_k=1}^{n}[gcd(l_1,l_2,\dots,l_k)=d]&\\ =&\sum\limits_{d=1}^{n}d^2\sum\limits_{l_1=1}^{\frac{n}{d}}\sum\limits_{l_2=1}^{\frac{n}{d}}\dots\sum\limits_{l_k=1}^{\frac{n}{d}}[gcd(l_1,l_2,\dots,l_k)=1]& \end{aligned} \]后面那一堆我们用经典反演套路进行反演得到：
\[\begin{aligned} \sum\limits_{d=1}^{n}d^2\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\lfloor\frac{n}{dp}\rfloor^k \end{aligned} \]我们枚举\(T=dp\)得：
\[\begin{aligned} \sum\limits_{T=1}^{n}\lfloor\frac{n}{k}\rfloor^k\sum\limits_{t|T}\mu(t)\lfloor\frac{T}{t}\rfloor^2 \end{aligned} \]因此题目要求的式子最后为：
\[\begin{aligned} &\sum\limits_{cnt=2}^{k}\sum\limits_{T=1}^{n}\lfloor\frac{n}{k}\rfloor^{cnt}\sum\limits_{t|T}\mu(t)\lfloor\frac{T}{t}\rfloor^2&\\ =&\sum\limits_{T=1}^{n}(\sum\limits_{cnt=2}^{k}\lfloor\frac{n}{k}\rfloor^{cnt})\sum\limits_{t|T}\mu(t)\lfloor\frac{T}{t}\rfloor^2&\\ =&\sum\limits_{T=1}^{n}(\frac{\lfloor\frac{n}{T}\rfloor\times(\lfloor\frac{n}{T}\rfloor^k-1)}{\lfloor\frac{n}{T}\rfloor-1}-\lfloor\frac{n}{T}\rfloor)\sum\limits_{t|T}\mu(t)\lfloor\frac{T}{t}\rfloor^2&\text{等比数列求和} \end{aligned}\\ \]比赛的时候我写到这里就不会了，主要是后面那个不知道该怎么卷积进行杜教筛，赛后看了这篇博客才懂，下面思路基本上都是参考这位大佬的。
首先我们知道\(\mu\)为积性函数，\(id^2\)为积性函数，两者相乘还是积性函数，因此\(f(n)=\sum\limits_{d|n}\mu(d)\lfloor\frac{n}{d}\rfloor^2=\sum\limits_{d|n}\mu(d)id(\frac{n}{d})^2\)。
对于这个\(f\)的前缀和我们可以用杜教筛进行求解，设\(I*h=I*f=I*\mu *id^2\)，将其化简：
\[\begin{aligned} &\sum\limits_{t|n}I(\frac{n}{t})f(t)&\\ =&\sum\limits_{t|n}I(\frac{n}{t})\sum\limits_{d|t}\mu(t)id(\frac{t}{d})^2&\\ =&\sum\limits_{d|n}id(\frac{n}{d})^2\sum\limits_{x|\frac{n}{d}}I(\frac{n}{xd})\mu(\frac{xd}{d})&\\ =&\sum\limits_{d|n}id(\frac{n}{d})^2\sum\limits_{x|\frac{n}{d}}\mu(x)&\\ =&\sum\limits_{d|n}id(\frac{n}{d})^2[\frac{n}{d}=1]&\\ =&n^2& \end{aligned} \]我当时看那篇博客时一直看不懂第二步到第三步是怎么来的，后面发现其实就是枚举\(x=\frac{t}{d}\)，然后那篇博客里面仍然用\(t\)来表示就导致看起来很迷。
然后进行杜教筛，设\(S(n)=\sum\limits_{i=1}^{n}f(i)=\sum\limits_{i=1}^{n}i^2-\sum\limits_{i=2}^{n}S(\frac{n}{i})=\frac{n(n+1)(2n+1)}{6}-\sum\limits_{i=2}^{n}S(\frac{n}{i})\)。
在杜教筛之前我们需要先预处理出\(n\leq1000000\)的情况，我们可以发现\(f(1)=1,f(p^c)=p^{2c}-p^{2c-2},f(p_1^{c_1}p_2^{c_2}\dots p_n^{c_n})=f(p_1^{c_1})f(p_2^{c_2})\dots f(p_n^{c_n})\)，然后就可以在线性筛时一并进行预处理掉辣~
对于最终答案里面的\(\sum\limits_{T=1}^{n}(\frac{\lfloor\frac{n}{T}\rfloor\times(\lfloor\frac{n}{T}\rfloor^k-1)}{\lfloor\frac{n}{T}\rfloor-1}-\lfloor\frac{n}{T}\rfloor)\)我们可以用数论分块进行处理，注意处理公比为\(1\)的情况，然后这题就做完了。
代码
#include
#include