Editorial

---

E

summary:

$a+b+c=n$인 모든 $(a,b,c)$ 에 대해 $\sum{lcm(c,gcd(a,b))}$를 구하는 문제

solution:

$\sum{lcm(c,gcd(a,b))}$

$=\sum{lcm(c,gcd(a,n-a-c))}$

$=\sum{lcm(c,gcd(a,n-c))}$이므로

$gcd(a,n-c) = d$라고 하면

d는 n-c의 약수이다.

이때 $a= d*\alpha$라고 하면, gcd의 정의에 의해 $\frac{a}{d}$와 $\frac{n-c}{d}$는 서로소이므로 $\alpha$의 개수(=$a$의 개수)는 $\phi(\frac{n-c}{d})$개이다.

$\sum{lcm(c,d)*\phi(\frac{n-c}{d})}$이다.