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)\)의 구간합을 이용해서 빨리 구할 수 있다.