BOJ 10916 Xtreme gcd sum

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

 

$$\sum^{b_1}_{x_1=a_1}\sum^{b_2}_{x_2=a_2}\cdots \sum^{b_n}_{x_n=a_n}\gcd(x_1,x_2,\cdots,x_n)$$

$$=\sum^{1,000,000}_{k=1}\sum^{b_1}_{x_1=a_1}\sum^{b_2}_{x_2=a_2}\cdots \sum^{b_n}_{x_n=a_n}[\gcd(x_1,x_2,\cdots,x_n)=k]k$$

$x_1=kx'_1,x_2=kx'_2,\cdots ,x_n=kx'_n$이라고 하면,

$$\sum^{1,000,000}_{k=1}k\sum^{\lfloor \frac{b_1}{k}\rfloor}_{x'_1=\lceil \frac{a_1}{k}\rceil}\sum^{\lfloor \frac{b_2}{k}\rfloor}_{x'_2=\lceil\frac{a_2}{k}\rceil}\cdots \sum^{\lfloor\frac{b_n}{k}\rfloor}_{x'_n=\lceil\frac{a_n}{k}\rceil}[\gcd(x'_1,x'_2,\cdots,x'_n)=1]$$

$$=\sum^{1,000,000}_{k=1}k\sum_{d|k}\mu(d)\sum^{\lfloor \frac{b_1}{k}\rfloor}_{x'_1=\lceil \frac{a_1}{k}\rceil}[d|x'_1]\sum^{\lfloor \frac{b_2}{k}\rfloor}_{x'_2=\lceil\frac{a_2}{k}\rceil}[d|x'_2]\cdots \sum^{\lfloor\frac{b_n}{k}\rfloor}_{x'_n=\lceil\frac{a_n}{k}\rceil}[d|x'_n]$$

이 때 $\lceil\frac{a_n}{k}\rceil=\lfloor\frac{a_n-1}{k}\rfloor+1$이므로

$$\sum^{1,000,000}_{k=1}k\sum_{d|k}\mu(d)\sum^{\lfloor \frac{b_1}{k}\rfloor}_{x'_1=\lfloor\frac{a_1-1}{k}\rfloor+1}[d|x'_1]\sum^{\lfloor \frac{b_2}{k}\rfloor}_{x'_2=\lfloor\frac{a_2-1}{k}\rfloor+1}[d|x'_2]\cdots \sum^{\lfloor\frac{b_n}{k}\rfloor}_{x'_n=\lfloor\frac{a_n-1}{k}\rfloor+1}[d|x'_n]$$

$$=\sum^{1,000,000}_{k=1}k\sum_{d|k}\mu(d)\left(\lfloor\frac{b_1}{kd}\rfloor - \lfloor\frac{a_1-1}{kd}\rfloor)\right)\left(\lfloor\frac{b_2}{kd}\rfloor - \lfloor\frac{a_2-1}{kd}\rfloor\right)\cdots\left(\lfloor\frac{b_n}{kd}\rfloor - \lfloor\frac{a_n-1}{kd}\rfloor\right)$$

$l=kd$라고 하면

$$\sum^{1,000,000}_{l=1}\sum_{d|l}\frac{l}{d}\mu(d)\left(\lfloor\frac{b_1}{l}\rfloor - \lfloor\frac{a_1-1}{l}\rfloor)\right)\left(\lfloor\frac{b_2}{l}\rfloor - \lfloor\frac{a_2-1}{l}\rfloor\right)\cdots\left(\lfloor\frac{b_n}{l}\rfloor - \lfloor\frac{a_n-1}{l}\rfloor\right)$$

$$=\sum^{1,000,000}_{l=1}\phi(l)\left(\lfloor\frac{b_1}{l}\rfloor - \lfloor\frac{a_1-1}{l}\rfloor)\right)\left(\lfloor\frac{b_2}{l}\rfloor - \lfloor\frac{a_2-1}{l}\rfloor\right)\cdots\left(\lfloor\frac{b_n}{l}\rfloor - \lfloor\frac{a_n-1}{l}\rfloor\right)$$

$\lfloor\frac{k}{l}\rfloor$이 바뀌는 횟수는 $2\sqrt k$번 이하이므로 합치면 $4000n$번 정도 바뀐다. 다 저장해두려면 메모리가 좀 부족해서... 메모리를 아끼면서 바뀌는 위치를 잘 처리해주면 된다.