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

을 구할 수 있다.