一类含积性函数的前缀和

x=1ny=1n[gcd(x,y)==1](x+1)(y+1)\sum_ {x=1}^{n}\sum_ {y=1}^n[gcd(x,y)==1]*(x+1)(y+1)

这是GDKOI2017上一道要求的式子,需要低于O(n)O(n)的复杂度。看见[gcd(x,y)==1][gcd(x,y)==1],那就搞一通莫比乌斯反演吧。

x=1ny=1n[gcd(x,y)==1](x+1)(y+1)\sum_ {x=1}^{n}\sum_ {y=1}^n[gcd(x,y)==1](x+1)(y+1)

=d=1nμ(d)i=1ndj=1nd(id+1)(jd+1)=\sum_ {d=1}^{n}\mu(d)\sum_ {i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_ {j=1}^{\lfloor\frac{n}{d}\rfloor}(id+1)(jd+1)

这个式子似乎比用欧拉函数的O(n)O(n)还要慢。把东西都化开来会得到

=d=1nμ(d)i=1ndj=1nd[ijd2+(i+j)d+1]=\sum_ {d=1}^{n}\mu(d)\sum_ {i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_ {j=1}^{\lfloor\frac{n}{d}\rfloor}[ijd^2+(i+j)d+1]

=d=1nμ(d)(d2(nd(nd+1)2)2+2nd(nd+1)2+nd2)=\sum_ {d=1}^{n}\mu(d)(d^2(\frac{\lfloor\frac{n}{d}\rfloor(\lfloor\frac{n}{d}\rfloor+1)}{2})^2+2\frac{\lfloor\frac{n}{d}\rfloor(\lfloor\frac{n}{d}\rfloor+1)}{2}+\lfloor\frac{n}{d}\rfloor^2)

继续展开,会发现一些比较通用的形式,比如说

d=1nμ(d)dk\sum_ {d=1}^{n}\mu(d)\cdot d^k

或者

d=1nμ(d)ndk\sum_ {d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor^k

或者把它们中的每一个求和项乘起来……但是看起来每一个都不好求。

因为这一类函数直接在网上查肯定是没有直接的题解的,我灵机一动,决定查一下简单的莫比乌斯函数前缀和。感谢skywalkert的讲解,我现在终于理解了如下推导过程。

M(n)=i=1nμ(i)M(n)=\sum_ {i=1}^{n}\mu(i),也就是前缀和函数。

根据莫比乌斯反演的重要性质:

dnμ(d)={1n=10n>1\sum_ {d|n}\mu(d)=\left\{\begin{matrix} 1 & n=1\\ 0 & n>1 \end{matrix}\right.

可以得到

1=j=1ndjμd1=\sum_ {j=1}^{n}\sum_ {d|j}\mu{d}

除了第一项,其他都是0,所以和当然是1了。这一步非常巧妙。

再设i=jdi=\frac{j}{d},继续上面的式子有

1=j=1ndjμd1=\sum_ {j=1}^{n}\sum_ {d|j}\mu{d}

=i=1nd=1niμ(d)=\sum_ {i=1}^n\sum_ {d=1}^{\lfloor\frac{n}{i}\rfloor}\mu(d)

=i=1nM(ni)=\sum_ {i=1}^nM(\lfloor\frac{n}{i}\rfloor)

分离第一项,

1=M(n)+i=2nM(ni)1=M(n)+\sum_ {i=2}^nM(\lfloor\frac{n}{i}\rfloor)

所求即为

M(n)=1i=2nM(ni)M(n)=1-\sum_ {i=2}^{n}M(\lfloor\frac{n}{i}\rfloor)

后面的东西用分块加速,最好还要加上记忆化和预处理,这样才不会超时。网上说时间复杂度为O(n23)O(n^{\frac{2}{3}}),我表示严重怀疑。

谈谈上面证明过程中我的几个感悟吧。

第一步和第二步之间的变换我本来是这样想的:

1=d=1ni=1ndμ(d)1=\sum_ {d=1}^n\sum_ {i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(d)

=d=1nμ(d)nd=\sum_ {d=1}^n\mu(d)\cdot \lfloor\frac{n}{d}\rfloor

下面就变不下去了。这样没有很好地利用信息。同样是枚举倍数和因数,改变一下枚举顺序,就有可能得到化简。

最后本来十分完美的一个式子为什么突然要拆开来?除了第一项以外ni\lfloor\frac{n}{i}\rfloor都比nn小很多!所以能快速在递归过程中缩小nn

莫比乌斯函数能求前缀和,欧拉函数表示不服。我记得在GDKOI2017 Day2上出题人提到,有两种解决思路,一种是莫比乌斯,一种就是欧拉,因为他们有很多相似的性质。比如说:

dnφ(d)=n\sum_ {d|n}\varphi(d)=n

依葫芦画瓢可以得到:

i=1ni=i=1ndiφ(d)\sum_ {i=1}^ni=\sum_ {i=1}^n\sum_ {d|i}\varphi(d)

左边的式子是一个等差数列,一个公式的问题而已。故事还没有结束,但是已经可以猜到结局了。

小结一下,只要i=1ndif(d)\sum_ {i=1}^{n}\sum_ {d|i}f(d)可以轻易求出来的函数,前缀和也很容易求出来。

回到最初的问题,怎么求一个μ(x)\mu(x)乘上一堆式子?

先考虑求这个式子:

Gk(n)=d=1nμ(d)dkG_ k(n)=\sum_ {d=1}^{n}\mu(d)\cdot d^k

学习上面的变形方法,但是要乘上一点别的东西:

dnμ(d)dknkdk\sum_ {d|n}\mu(d)\cdot d^k\cdot \frac{n^k}{d^k}

=nkdnμ(d)=n^k\sum_ {d|n}\mu(d)

={1n=10n>1=\left\{\begin{matrix} 1 & n=1\\ 0 & n>1 \end{matrix}\right.

1=j=1ndjμ(d)dkjkdk\Rightarrow 1=\sum_ {j=1}^{n}\sum_ {d|j}\mu(d)\cdot d^k\cdot \frac{j^k}{d^k}

=i=1nd=1niμ(d)dkik=\sum_ {i=1}^{n}\sum_ {d=1}^{\lfloor\frac{n}{i}\rfloor}\mu(d)\cdot d^k\cdot i^k

=i=1nikGk(ni)=\sum_ {i=1}^ni^k\cdot G_ k(\lfloor\frac{n}{i}\rfloor)

=Gk(n)+i=2niGk(ni)=G_ k(n)+\sum_ {i=2}^ni\cdot G_ k(\lfloor\frac{n}{i}\rfloor)

Gk(n)=1i=2nikGk(ni)\Rightarrow G_ k(n)=1-\sum_ {i=2}^ni^k\cdot G_ k(\lfloor\frac{n}{i}\rfloor)

Gk(ni)G_ k(\lfloor\frac{n}{i}\rfloor)相同时,只要能O(1)O(1)求出ik\sum i^k就可以保持复杂度不变。

剩下的我实在不会化简了,nd\left\lfloor\frac{n}{d}\right\rfloor的项的取值最多不超过n\sqrt{n}个,所以直接暴力上应该就勉勉强强能过吧……

Update: 这个方法的俗名叫“杜教筛”。有一个更加强化的版本叫“洲阁筛”。

avatar
Kerry Su