jiry_2's Blog

寒假一直在浪浪浪，起点文看看钱骗骗...后来听说唐老师发了一篇关于杜教筛的博客，于是就去学姿势啦..

感觉这些问题还是非常有趣的..所以就写篇博客来装作自己的寒假没有被浪掉好啦。

唐老师的博客地址在这里http://blog.csdn.net/skywalkert/article/details/50500009

嘛..有一类问题差不多长这样：

首先，出题人不知道干了些什么，YY出了一下奇怪的函数[tex]f(x)[/tex]，正常点的话有[tex]\mu(x)[/tex]，[tex]\phi(x)[/tex]，有些时候也有一些奇形怪状的函数比如[tex]f(n)=\prod (p_i^{a_i}+1)[/tex]，其中[tex]p_i[/tex]是质数，[tex]a_i>0[/tex]且[tex]n=\prod p_i^{a_i}[/tex]。

接着，出题人给了你一个挺大的[tex]n[/tex]，[tex]n[/tex]一般来说都有[tex]10^{10}[/tex]左右。

最后，他想让你输出[tex]\sum_{i=1}^n f(i)[/tex]的值（可能会对一个大数取模）。

杜教筛差不多就是拿来解决这类问题哒..它给出了一个比较通用的技巧使得可以在[tex]O(n^{\frac{2}{3}})[/tex]或者[tex]O(n^{\frac{3}{4}})[/tex]的时间复杂度内求的答案。

比如我们现在要求[tex]S(n)=\sum_{i=1}^n f(i)[/tex]，可能直接求非常困难，可以采用的一个方法是找出另外一个函数[tex]g(x)[/tex]，我们考虑[tex](f*g)(x)[/tex]的前缀和：

[tex]\sum_{i=1}^n \sum_{j|i} f(\frac{i}{j})g(j)=\sum_{ij\leq n}f(i)g(j)=\sum_{i=1}^n g(i)S(\lfloor \frac{n}{i} \rfloor)[/tex]

这样我就得到了一个关于[tex]S(n)[/tex]的递推式：

[tex]g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S(\lfloor \frac{n}{i} \rfloor)[/tex]

如果[tex](f*g)(x)[/tex]的前缀和以及[tex]g(x)[/tex]的前缀和都很好计算，那么我们可以直接通过这个递推式来一波记忆搜，这样的复杂度是[tex]O(n^{\frac{3}{4}})[/tex]的，如果我们对不超过[tex]\sqrt n[/tex]的[tex]x[/tex]都预处理[tex]S(x)[/tex]，那么复杂度就是[tex]O(n^{\frac{2}{3}})[/tex]啦。

通过这种方法，我们非常容易的求出[tex]\mu(x)[/tex]和[tex]\phi(x)[/tex]的前缀和（让[tex]g(x)=1[/tex]即可）。但是通常题目中的函数都不会那么简单，而对于较复杂一点的函数有这样两个比较基本的形式：

1.求[tex]S(n)=\sum_{i=1}^n (f \cdot g)(i)[/tex]的值且[tex]g(x)[/tex]为完全积性函数。这时有：

[tex]S(n)=\sum_{i=1}^n[(f*1) \cdot g](i)-\sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor)g(i)[/tex]

2.求[tex]S(n)=\sum_{i=1}^n (f*g)(i)[/tex]的值。这时有：

[tex]S(n)=\sum_{i=1}^n g(i)\sum_{ij \leq n}(f*1)(j)-\sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor)[/tex]

用这几个工具，就能非常轻易的解决一些这一类问题啦..接下来是几个栗子（其实都是从唐老师博客下面抓来的）：

【例1】求[tex]\sum_{i=1}^n\sum_{j=1}^n \text{lcm}(ij)[tex]。

首先先对这个柿子进行化简：

[tex]A(n)=\sum_{i=1}^n\text{lcm}(in)=n\sum_{i=1}^n\frac{i}{(n,i)}=n\sum_{d|n}\sum_{id\leq n}i[(i,\frac{n}{d})=1][/tex]

因为有[tex]\sum_{i=1}^n i[(i,n)=1]=\frac{1}{2}([n=1]+n\phi(n))[/tex]，所以我们实际要求的是[tex]B(n)=n\sum_{d|n}d\phi(d)[/tex]的前缀和，即求[tex]id \cdot [(id \cdot \phi) * 1][/tex]的前缀和。

这儿有两种处理方法。第一种如下：

[tex]\sum_{i=1}^n B(i)=\sum_{i=1}^ni\sum_{j|i}j\phi(j)=\sum_{i=1}^n i^2 \phi(i) \sum_{ij\leq n}j[/tex]

可以发现[tex]\sum_{ij\leq n}j[/tex]的柿子只有[tex]O(\sqrt n)[/tex]种取值。所以问题就转化成了对所有的[tex]i[/tex]，求出[tex]id^2 \cdot \phi[/tex]的前[tex]\lfloor \frac{n}{i} \rfloor[/tex]项的和。这只需要直接套用[tex]f(x) \cdot g(x)[/tex]的公式就好啦。

接着来分析复杂度，可以发现在求解前[tex]n[/tex]项的前缀和的时候，我们已经对所有的[tex]i[/tex]都求出来了前[tex]\lfloor \frac{n}{i} \rfloor[/tex]项的和，所以时间复杂度和只求一次是完全一样的。

第二种处理方法如下：

[tex]id \cdot [(id \cdot \phi) * 1]=(id^2 \cdot \phi) * id[/tex]

我们采用最原始的方法，给这个函数卷上[tex]id^2[/tex]，那么就有：

[tex](id^2 \cdot \phi) * id * id^2=[(id^2 \cdot \phi)*id^2]*id=id \cdot (id^2 * 1)[/tex]

这个柿子的前缀和是非常好求的，所以直接套用前面的公式就可以解决了。

【例2】求[tex]S(n)=\sum_{i=1}^n\sum_{j=1}^n f(ij)[/tex]。其中[tex]f(x)[/tex]指[tex]x[/tex]的约数个数。

可以直接套用陈老师r老师等式：

[tex]S(n)=\sum_{i=1}^n\sum_{j=1}\lfloor \frac{n}{i} \rfloor \lfloor \frac{n}{j} \rfloor [(i,j)=1][/tex]

然后反演一下可以得到：

[tex]S(n)=\sum_{d=1}^n\mu(i)(\sum_{id \leq n}\lfloor \frac{n}{id} \rfloor)^2[/tex]

可以发现后半部分的取值只有[tex]O(\sqrt n)[/tex]种，每一段分别求[tex]\mu(i)[/tex]的前缀和就行了。

【例3】求[tex]S(n)=\sum_{i=1}^n\sum_{j=1}^n f(ij)[/tex]。其中[tex]f(x)[/tex]指[tex]x[/tex]的约数和。

因为有[tex]f(ij)=\sum_{a|i}\sum_{b|j}\frac{aj}{b}[(a,b)=1][/tex]，所以就可以将柿子化简然后反演一波得到：

[tex]S(n)=\sum_{d=1}^n \mu(k)k\sum_{ak \leq n}\sum_{aki \leq n}a \sum_{bk \leq n} \sum_{bkj \leq n}j[/tex]

可以发现后半部分的两个柿子的取值都只有[tex]O(\sqrt n)[/tex]种，每一段分别求[tex]\mu(i)i[/tex]的前缀和就行了。

【例4】求[tex]f(n)=\prod (p_i^{a_i}+1)[/tex]的前缀和，其中[tex]p_i[/tex]是质数，[tex]a_i>0[/tex]且[tex]n=\prod p_i^{a_i}[/tex]

观察[tex]f(n)[/tex]可以发现[tex]f(n)=\sum_{i|n}i[(i,\frac{n}{i})=1][/tex]，于是就有：

[tex]S(n)=\sum_{i=1}^n f(i)=\sum_{i=1}^ni\sum_{ij \leq n}[(i,j)=1][/tex]

这个时候有两种处理方法，第一种是将这个柿子反演：

[tex]S(n)=\sum_{i=d}^n \mu(d)d \sum_{id \leq n}i\lfloor \frac{n}{id} \rfloor[/tex]

这样就能直接求解了，但是这样常数比较大。第二种方法是暴力容斥，枚举[tex]i[/tex]和[tex]j[/tex]的公约数：

[tex]S(n)=\sum_{ij \leq n}i-\sum_{k=2}^nkS(\lfloor \frac{n}{k^2} \rfloor)[/tex]

显然[tex]k[/tex]不能超过[tex]\sqrt n[/tex]，所以直接记忆搜即可。

【例5】求[tex]f(n)=\prod (p_i^{a_i}-1)[/tex]的前缀和，其中[tex]p_i[/tex]是质数，[tex]a_i>0[/tex]且[tex]n=\prod p_i^{a_i}[/tex]

观察[tex]f(n)[/tex]可以发现[tex]n=\sum_{i|n}f(i)[(i,\frac{n}{i})=1][/tex]。

然后我就不会啦QAQ听说过的都是打表的？如果有老司机想出来非打表做法欢迎来找我讨论owo