BOJ 11691 LCM(i, j)

https://www.acmicpc.net/problem/11691

 

$$2\sum^{n-1}_{i=1}\sum^n_{j=i+1}\text{lcm}(i,j)=\sum^n_{i=1}\sum^n_{j=1}\text{lcm}(i,j)-\frac{n(n+1)}{2}$$

이므로 $\sum^n_{i=1}\sum^n_{j=1}\text{lcm}(i,j)$를 구하면 된다.

(코드포스 블로그 : https://codeforces.com/blog/entry/53925에 있는거랑 같은 내용)

 

$$\sum^n_{i=1}\sum^n_{j=1}\text{lcm}(i,j)=\sum^n_{i=1}\sum^n_{j=1}\frac{ij}{\gcd(i,j)}=\sum^n_{k=1}\sum^n_{i=1}\sum^n_{j=1}[\gcd(i,j)=k]\frac{ij}{k}$$

$i=ak$, $j=bk$라고 하면

$$\sum^n_{k=1}\sum^{\lfloor\frac{n}{k}\rfloor}_{a=1}\sum^{\lfloor\frac{n}{k}\rfloor}_{b=1}[\gcd(a,b)=1]abk=\sum^n_{k=1}\sum^{\lfloor\frac{n}{k}\rfloor}_{a=1}\sum^{\lfloor\frac{n}{k}\rfloor}_{b=1}\sum^{\lfloor\frac{n}{k}\rfloor}_{d=1}[d|a][d|b]\mu(d)abk$$

$$=\sum^n_{k=1}k\sum^{\lfloor\frac{n}{k}\rfloor}_{d=1}\mu(d)\sum^{\lfloor\frac{n}{k}\rfloor}_{a=1}[d|a]a\sum^{\lfloor\frac{n}{k}\rfloor}_{b=1}[d|b]b$$

$a=dp$, $b=dq$라고 하면

$$\sum^n_{k=1}k\sum^{\lfloor\frac{n}{k}\rfloor}_{d=1}\mu(d)\sum^{\lfloor\frac{n}{kd}\rfloor}_{p=1}dp\sum^{\lfloor\frac{n}{kd}\rfloor}_{q=1}dq=\sum^n_{k=1}k\sum^{\lfloor\frac{n}{k}\rfloor}_{d=1}\mu(d)d^2\sum^{\lfloor\frac{n}{kd}\rfloor}_{p=1}p\sum^{\lfloor\frac{n}{kd}\rfloor}_{q=1}q$$

$$=\sum^n_{k=1}k\sum^{\lfloor\frac{n}{k}\rfloor}_{d=1}\mu(d)d^2\left(\frac{\lfloor\frac{n}{kd}\rfloor(\lfloor\frac{n}{kd}\rfloor+1)}{2}\right)^2$$

$l=kd$라고 하면

$$\sum^n_{l=1}\left(\frac{\lfloor\frac{n}{l}\rfloor(\lfloor\frac{n}{l}\rfloor+1)}{2}\right)^2\sum_{d\mid l}\mu(d)ld$$

이 때, $\sum_{d\mid l}\mu(d)ld=g(l)$이라고 하면 $g(p^k)=p^k-p^{k+1}$이고 $g(l)$은 곱셈적 함수이다. $O(n)$만에 $g(l)$을 구해두면

$$\sum^n_{l=1}\left(\frac{\lfloor\frac{n}{l}\rfloor(\lfloor\frac{n}{l}\rfloor+1)}{2}\right)^2g(l)$$

을 구할 수 있다.