[BOJ 19549] 레이저 연구소

원점에서 $(n,m)$으로 레이저를 쏘는 상황을 생각해보자. 집은 몇 개가 부숴질까? $y=\frac{m}{n}x$를 생각해보자. 이 직선에서 $x,y$가 모두 정수인 점이 집이 있는 구간이다. 결국 $mx=ny$의 정수 해의 개수가 된다. $(m,n)=d$라 하면 $m'=m/d,\ n'=n/d$ 일 때 $m'x=n'y$이고 따라서 $x=\alpha n',\ y=\alpha m'(1\le \alpha \le d)$이다. 그러므로 총 $d$개 의 집이 부숴진다. 원점도 집이 있으므로 $d+1$개 부숴진다. 벽을 지난다는 것은 무엇을 의미할까? 세로 벽을 생각하면 위에서 생각한 직선이 $(a,b)$와 $(a,b+1)$의 사이를 지난다는 것을 의미한다 그렇다는 것은 $b<\frac{am}{n}<b+1$이고 $\frac{am}{n}-1<b<\frac{am}{n}$에서 다음을 얻는다 $\lfloor\frac{am}{n}\rfloor-1<b\le \lfloor\frac{am}{n}\rfloor$. 이는 $\frac{am}{n}$이 정수가 아닐 경우 벽의 개수는 각 $a$마다 1개씩 존재함을 의미한다. $\frac{am}{n}$이 정수일 경우는 결국 집의 경우이므로 세로 벽의 개수는 $m-d$개 임을 알 수 있다. 마찬가지로 가로 벽의 개수는 $n-d$개 이다. 따라서 집의 수리 비용을 $A$ 벽의 수리 비용을 $B$라고 하면 $A+(A-2B)d+B(n+m)$가 총 비용임을 알 수 있다. 그럼 전체 $N\times M$ 직사각형에서 $n\times m$ 직사각형은 총 몇 개나 있을까? 정답은~ $(N+1-n)(M+1-m)$개 있다. 또, 레이저를 우측 상향, 우측 하향, 좌측 상향, 좌측 하향으로 총 4번 쏠 수 있기 때문에 다음을 구하는 것이 우리의 정답이다.

$$4\sum_{i=1}^{N}\sum_{j=1}^{M}(N+1-i)(M+1-j)(A+(A-2B)d+B(i+j))$$

이때 $d=(i,j)$를 의미한다. 결국 문제의 핵심은 $\sum \sum d,\ \sum \sum id,\ \sum \sum jd,\ \sum \sum ijd$를 어떻게 구하냐 이다. $id$의 합을 구하는 과정을 살펴보자. 

$$\begin{align}\sum_{i=1}^{N}\sum_{j=1}^{M} i\gcd(i,j) &= \sum_{d=1}^{\min(N,M)}d \sum_{i=1}^{N}\sum_{j=1}^{M} i[\gcd(i,j)=d] \\ &=\sum_{d=1}^{\min(N,M)} \sum_{i=1}^{N/d}\sum_{j=1}^{M/d} id^{2}[\gcd(i,j)=1] \\ &= \sum_{s=1}^{\min(N/d,M/d)} \mu(s)\sum_{d=1}^{\min(N,M)} \sum_{i=1}^{N/ds}\sum_{j=1}^{M/ds} isd^{2} \\ &= \sum_{s=1}^{\min(N/d,M/d)} \sum_{d=1}^{\min(N,M)} \mu(s)sd^{2} \frac{\lfloor\frac{N}{ds}\rfloor(\lfloor\frac{N}{ds}\rfloor+1)}{2} \lfloor\frac{M}{ds}\rfloor \\ &= \sum_{k=1}^{\min(N,M)} k (\sum_{s|k} \mu(s) \frac{k}{s})  \frac{\lfloor\frac{N}{k}\rfloor(\lfloor\frac{N}{k}\rfloor+1)}{2} \lfloor\frac{M}{k}\rfloor \\ &= \sum_{k=1}^{\min(N,M)} k \phi(k) \frac{\lfloor\frac{N}{k}\rfloor(\lfloor\frac{N}{k}\rfloor+1)}{2} \lfloor\frac{M}{k}\rfloor\end{align}$$

이제 나머지도 같은 방법으로 계산하면 된다. $\phi(k),\ k\phi(k), k^{2}\phi(k)$들은 모두 곱셈적 함수이므로 xudyh's sieve를 쓸 수 있다. $g(n)=n$이고 $f(n)=n\phi(n)$일 때

$$(f*g)(n)=\sum_{d|n}f(n)g(n/d)=\sum_{d|n} d\phi(d)\frac{n}{d}=n\sum_{d|n} \phi(d)=n^{2}$$

임을 이용하자.