BOJ 23260 - 최대공약수가 뭔데

image.png

백만까지 μ(i)\mu(i) 를 구해준다.

최대공약수가 11인 것의 개수는 결국 GCD가 11로나뉘는것 개수 - 22로나뉘는것 개수 - 33로나뉘는것 개수 + 66로나뉘는것 개수 … 처럼 포함배제의 원리로 풀 수 있고 이걸 나타내는 것이 결국 μ\mu 이다.

xx의 배수 중 MM 보다 작은건 ⌊Mx⌋\left\lfloor \dfrac{M}{x} \right\rfloor 이고 따라서 (⌊Mx⌋K)\dbinom{\left\lfloor \dfrac{M}{x} \right\rfloor}{K} 를 하는게 위에서 각 항의 값이다.

Tags:

Categories:

Updated:

Comments

You may also enjoy