BOJ 1792 공약수

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

 

$$\sum^a_{i=1}\sum^b_{j=1}[\gcd(i,j)=d]$$

$i=\alpha d$, $j=\beta d$라고 하면

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

$$=\sum^{\min(\lfloor\frac{a}{d}\rfloor,\lfloor\frac{b}{d}\rfloor)}_{k=1}\mu(k)\lfloor\frac{a}{kd}\rfloor\lfloor\frac{b}{kd}\rfloor$$

인데, $\lfloor\frac{a}{kd}\rfloor\lfloor\frac{b}{kd}\rfloor$가 바뀌는 횟수는 $2\sqrt{\frac{a}{d}}+2\sqrt{\frac{b}{d}}$번 이하이니 $\mu(n)$의 구간합을 이용해서 빨리 구할 수 있다.