BOJ 23260 - 최대공약수가 뭔데
백만까지 $\mu(i)$ 를 구해준다.
최대공약수가 $1$인 것의 개수는 결국 GCD가 $1$로나뉘는것 개수 - $2$로나뉘는것 개수 - $3$로나뉘는것 개수 + $6$로나뉘는것 개수 … 처럼 포함배제의 원리로 풀 수 있고 이걸 나타내는 것이 결국 $\mu$ 이다.
$x$의 배수 중 $M$ 보다 작은건 $\left\lfloor \dfrac{M}{x} \right\rfloor$ 이고 따라서 $\dbinom{\left\lfloor \dfrac{M}{x} \right\rfloor}{K}$ 를 하는게 위에서 각 항의 값이다.
Comments