Codechef LCM

题目

Given AA and BB, compute the sum of lcm(a,b)lcm(a,b) over all pairs of positive integers aa and bb such that:

  1. aAa\leq A and bBb\leq B.
  2. There is no integer n>1n>1 such that n2n^2 divides both aa and bb.

Answer % 2302^{30}. A,B4×106A,B\leq 4\times 10^6.

分析

BZOJ2440的思路可以把条件二搞定。

F(A,B)=i=1Aj=1Blcm(i,j),M=min(A,B)F(A,B)=\sum_ {i=1}^{A}\sum_ {j=1}^{B}lcm(i,j),M=min(A,B),那么答案就是

i=1Mμ(i)a=1Ai2b=1Bi2lcm(i2a,i2b)\sum_ {i=1}^{\sqrt{M}}\mu(i)\sum_ {a=1}^{\left\lfloor\frac{A}{i^2}\right\rfloor}\sum_ {b=1}^{\left\lfloor\frac{B}{i^2}\right\rfloor}lcm(i^2a,i^2b)

=i=1Mμ(i)i2F(Ai2,Bi2)=\sum_ {i=1}^{\sqrt{M}}\mu(i)\cdot i^2\cdot F(\left\lfloor\frac{A}{i^2}\right\rfloor,\left\lfloor\frac{B}{i^2}\right\rfloor)

这里好像不怎么能省时间,那先把FF求出来看看吧。

F(A,B)=i=1Aj=1Blcm(i,j)F(A,B)=\sum_ {i=1}^{A}\sum_ {j=1}^{B}lcm(i,j)

=d=1Mi=1Adj=1Bdijd[gcd(i,j)==1]=\sum_ {d=1}^{M}\sum_ {i'=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\sum_ {j'=1}^{\left\lfloor\frac{B}{d}\right\rfloor}i'j'd[gcd(i',j')==1]

为了求FF,再设S(n)S(n)11nn的和即S(n)=n(n+1)2S(n)=\frac{n\cdot(n+1)}{2}

g(A,B,n)=i=1Aj=1Bij[gcd(i,j)==n]g(A,B,n)=\sum_ {i=1}^A\sum_ {j=1}^Bij[gcd(i,j)==n]

G(A,B,n)=i=1Aj=1Bij[ngcd(i,j)]G(A,B,n)=\sum_ {i=1}^A\sum_ {j=1}^Bij[n|gcd(i,j)]

=i=1Anj=1Bn(in)(jn)=\sum_ {i'=1}^{\left\lfloor\frac{A}{n}\right\rfloor}\sum_ {j'=1}^{\left\lfloor\frac{B}{n}\right\rfloor}(i'n)\cdot(j'n)

=n2S(An)S(Bn)=n^2\cdot S(\left\lfloor\frac{A}{n}\right\rfloor)S(\left\lfloor\frac{B}{n}\right\rfloor)

显然:

G(A,B,n)=ndg(A,B,d)G(A,B,n)=\sum_ {n|d} g(A,B,d)

反演一波,

g(A,B,n)=ndμ(dn)G(A,B,d)g(A,B,n)=\sum_ {n|d}\mu(\frac{d}{n})G(A,B,d)

=ndμ(dn)d2S(Ad)S(Bd)=\sum_ {n|d}\mu(\frac{d}{n})d^2S(\left\lfloor\frac{A}{d}\right\rfloor)S(\left\lfloor\frac{B}{d}\right\rfloor)

代回去求FF

F(A,B)=d=1Mi=1Adj=1Bdijd[gcd(i,j)==1]F(A,B)=\sum_ {d=1}^{M}\sum_ {i'=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\sum_ {j'=1}^{\left\lfloor\frac{B}{d}\right\rfloor}i'j'd[gcd(i',j')==1]

=d=1Mdg(Ad,Bd,1)=\sum_ {d=1}^Md\cdot g(\left\lfloor\frac{A}{d}\right\rfloor,\left\lfloor\frac{B}{d}\right\rfloor,1)

=d=1Mdk=1Mdμ(k)k2S(Adk)S(Bdk)=\sum_ {d=1}^Md\sum_{k=1}^{\left\lfloor\frac{M}{d}\right\rfloor}\mu(k)k^2S(\left\lfloor\frac{A}{dk}\right\rfloor)S(\left\lfloor\frac{B}{dk}\right\rfloor)

观察发现dkdk出现的比较多,可以把他们合并成一个xx

F(A,B)=k=1Mμ(k)kkxxS(Ax)S(Bx)F(A,B)=\sum_ {k=1}^M\mu(k)\cdot k\sum_ {k|x}x\cdot S(\left\lfloor\frac{A}{x}\right\rfloor)S(\left\lfloor\frac{B}{x}\right\rfloor)

=x=1MxS(Ax)S(Bx)kxμ(k)k=\sum_ {x=1}^Mx\cdot S(\left\lfloor\frac{A}{x}\right\rfloor)S(\left\lfloor\frac{B}{x}\right\rfloor)\sum_ {k|x}\mu(k)\cdot k

让我们代回最终答案!

Ans=i=1Mμ(i)i2F(Ai2,Bi2)Ans=\sum_ {i=1}^{\sqrt{M}}\mu(i)\cdot i^2\cdot F(\left\lfloor\frac{A}{i^2}\right\rfloor,\left\lfloor\frac{B}{i^2}\right\rfloor)

=i=1Mμ(i)i2x=1MxS(Ai2x)S(Bi2x)kxμ(k)k=\sum_ {i=1}^{\sqrt{M}}\mu(i)\cdot i^2\sum_ {x=1}^Mx\cdot S(\left\lfloor\frac{A}{i^2x}\right\rfloor)S(\left\lfloor\frac{B}{i^2x}\right\rfloor)\sum_ {k|x}\mu(k)\cdot k

再使用一次刚才的技巧,发现i2xi^2x出现的比较多,整体代换成tt

Ans=t=1Mi2tμ(i)tS(At)S(Bt)kti2μ(k)kAns=\sum_ {t=1}^M\sum_ {i^2|t}\mu(i)\cdot t\cdot S(\left\lfloor\frac{A}{t}\right\rfloor)\cdot S(\left\lfloor\frac{B}{t}\right\rfloor)\sum_ {k|\frac{t}{i^2}}\mu(k)\cdot k

=t=1MS(At)S(Bt)(ti2tμ(i)kti2μ(k)k)=\sum_ {t=1}^MS(\left\lfloor\frac{A}{t}\right\rfloor)\cdot S(\left\lfloor\frac{B}{t}\right\rfloor)\cdot(t\cdot\sum_ {i^2|t}\mu(i)\cdot \sum_ {k|\frac{t}{i^2}}\mu(k)\cdot k)

前面一堆性质不明的东西看起来只能用分块加速了。如果要分块加速,要求后面的东西的前缀和必须先搞出来。

先看H(n)=dnμ(d)dH(n)=\sum_ {d|n}\mu(d)\cdot d,这个函数只和nn有关系。

因为μ(d)\mu(d)dd都是积性函数,所以μ(d)d\mu(d)\cdot d也是积性函数,故它与id(d)=1id(d)=1的狄利克雷卷积H(n)=dnμ(d)d1H(n)=\sum_ {d|n}\mu(d)\cdot d\cdot 1也是积性函数,那么H(n)H(n)就可以线性筛出来啦。

考虑枚举ti2tμ(i)H(ti2)t\cdot\sum_ {i^2|t}\mu(i)\cdot H(\frac{t}{i^2})中的ii对每一个tt的贡献,时间复杂度就为O(Mi=1M1i2)O(M\sum_ {i=1}^{\sqrt{M}}\frac{1}{i^2})

又有

limn+i=1n1i2\lim_ {n\rightarrow+\infty}\sum_ {i=1}^{n}\frac{1}{i^2}

=112+122+123+...=\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{2^3}+...

=π26=\frac{\pi^2}{6}

所以预处理后面的东西就是线性的了,询问O(1)O(1),加上分块的复杂度,总共是O(M+TM)O(M+T\sqrt{M})

额外的小技巧

其实这个技巧用不用无所谓。S(n)S(n)是要除以二的,如果不想算逆元的话,可以先乘二,用unsigned int自然溢出计算Ans4%232Ans*4\%2^{32}的值,再>>2即可。

一点小总结

把式子推出来了之后干什么?

想办法求出来啊!

不能因为看到形式复杂就直接放弃。这也体现字的整洁程度的重要性,如果草稿很乱,无法思考,也不想思考。

要尽可能把一些只和少量变量有关的东西分离,看能不能预处理出来。这题用了积性性质,还有的题目可以用杜教筛。

avatar
Kerry Su