例6：

求：(sumlimits_{i=1}^nsumlimits_{j=1}^md(i imes j))

这里有一个式子：(d(i imes j)=sumlimits_{x|i}sumlimits_{y|j}[gcd(x,y)=1])

很显然，它是成立的，然后就可以将一个陌生的式子转换成我们所熟悉的(gcd)啦。

(=sumlimits_{i=1}^nsumlimits_{j=1}^msumlimits_{x|i}sumlimits_{y|j}[gcd(x,y)=1])

(=sumlimits_{x=1}^nsumlimits_{y=1}^m[gcd(x,y)=1] imeslfloorfrac n x floor imeslfloorfrac m y floor)

(=sumlimits_{i=1}^nsumlimits_{j=1}^m[gcd(i,j)=1] imeslfloorfrac n i floor imeslfloorfrac m j floor)

(=sumlimits_{d=1}^nmu(d)sumlimits_{i=1}^{lfloorfrac n d floor}lfloorfrac n{id} floorsumlimits_{j=1}^{lfloorfrac m d floor}lfloorfrac m{jd} floor)

我们设(S(n)=sumlimits_{i=1}^nlfloorfrac n i floor) 。

(=sum_{d=1}^nmu(d) imes S[lfloorfrac n d floor] imes S[lfloorfrac m d floor])

然后就能做到(O(sqrt{n}))求解每一个问题，(O(n imessqrt{n}))预处理啦。

例7：

求：(sumlimits_{i=1}^nsumlimits_{j=1}^mvarphi(i imes j))

先来推导一个式子：

(varphi(i) imesvarphi(j)=iprodlimits_{P|i}frac{P-1}Pjprodlimits_{P|j}frac{P-1}P)

(~~~~~~~~~~~~~~~~~~~~=ijprodlimits_{P|i}frac{P-1}Pprodlimits_{P|j}frac{P-1}P)

(~~~~~~~~~~~~~~~~~~~~=ijprodlimits_{P|i~or~P|j}frac{P-1}Pprodlimits_{P|i~and~P|j}frac{P-1}P)

(~~~~~~~~~~~~~~~~~~~~=ijprodlimits_{P|ij}frac{P-1}Pprodlimits_{P|gcd(i,j)}frac{P-1}P)

( hereforevarphi(i) imesvarphi(j) imesgcd(i,j)=varphi(gcd(i,j)) imesvarphi(ij))

然后我们就可以对式子进行进一步的转换啦：

(egin{aligned}&sum_{i=1}^nsum_{j=1}^mfrac{varphi(i) imes varphi(j) imesgcd(i,j)}{varphi(gcd(i,j))}\=&sum_{d=1}^nfrac{d}{varphi(d)}sum_{i=1}^{lfloorfrac{n}{d} floor}sum_{j=1}^{lfloorfrac{m}{d} floor}varphi(id) imesvarphi(jd) imes[gcd(i,j)=1]\=&sum_{d=1}^nfrac{d}{varphi(d)}sum_{k=1}^{lfloorfrac n d floor}mu(k)sum_{i=1}^{lfloorfrac n{kd} floor}sum_{j=1}^{lfloorfrac m{kd} floor}varphi(ikd)varphi(jkd)\=&sum_{T=1}^nsum_{d|T}frac{d}{varphi(d)} imesmu(frac T d)sum_{i=1}^{lfloorfrac n T floor}varphi(iT)sum_{j=1}^{lfloorfrac m T floor}varphi(jT)end{aligned})

我们引进几个函数：

(egin{aligned}F(n)=sum_{d|n}frac{d}{varphi(d)} imesmu(frac T d)end{aligned})

我们可以在(O(nlog n))的时间得到这个东西。
(egin{aligned}G(y,x)=sum_{i=1}^xvarphi(iy)end{aligned})

我们有递推式：(G(y,x)=G(y,x-1)+varphi(xy))

也可以在(O(nlog n))的时间内得到。
(egin{aligned}S(y,z,x)=sum_{T=1}^xsum_{d|T}frac{d}{varphi(d)} imesmu(frac T d)sum_{i=1}^{y}varphi(iT)sum_{j=1}^{z}varphi(jT)end{aligned})

也有递推式：(S(y,z,x)=S(y,z,x-1)+F(x) imes G(x,y) imes G(x,z))

预处理完这三个函数显然是不现实的，内存会炸。

我们设一个上限(B)：

所有(lfloorfrac n d floor)，(lfloorfrac m d floor)小于(B)的都预处理，这样就能在(O(sqrt{n}))的时间内求解这一部分。
大于(B)时，我们发现(d<B)，这样的话我们直接爆算即可，能在(O(lfloorfrac n B floor))的时间内求解。

分析总的时间复杂度为：

(O(nlog n+n imes B^2+q imes(sqrt n+lfloorfrac n B floor)))

发现当(B=35)时取到最值，大功告成！

要期末考了，再加上最近还有一些人打游戏被抓了，所以明天就不让上机房来了。

“莫比乌斯反演的一些简单应用#4”，应该是要搁置许久了，有空再更吧。