Codechef LCM

## 题目

Given $A$ and $B$, compute the sum of $lcm(a,b)$ over all pairs of positive integers $a$ and $b$ such that:

1. $a\leq A$ and $b\leq B$.
2. There is no integer $n>1$ such that $n^2$ divides both $a$ and $b$.

Answer % $2^{30}$. $A,B\leq 4\times 10^6$.

## 分析

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

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

$\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)$

$=\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)$

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

$=\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]$

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

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

$=\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)$

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

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

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

$=\sum_ {n|d}\mu(\frac{d}{n})d^2S(\left\lfloor\frac{A}{d}\right\rfloor)S(\left\lfloor\frac{B}{d}\right\rfloor)$

$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]$

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

$=\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)$

$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)$

$=\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=\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)$

$=\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$

$Ans=\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$

$=\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)$

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

$=\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{2^3}+...$

$=\frac{\pi^2}{6}$

Kerry Su