Squarefree Number

http://www.spoj.com/problems/IE3

쿼리당 Sqrt(N)lgN에 풀 수 있다.

N 이하의 Square 수가 모두 Sqrt(N)개 있을 텐데, 이걸 단순히 포함배제로 하면 -

* 2^2의 배수 더해주고 -

* 3^2의 배수 더해주고 -

* 6^2의 배수 빼주고 -

* 4^2의 배수는 냅두고 -

* 5^2의 배수 더해주고 -

 ( ..... )

말도 안되는 시간 복잡도가 나오겠지만 이 때를 위해서 뫼비우스 함수라는 것이 존재한다.

뫼비우스 함수 f(n)은 :

 * f(n)이 제곱수로 나눠지면 0

 * f(n)의 소인수 수가 홀수면 -1

 * 아니면 1

으로 정의되는데 이걸 쓰면 저걸 어떻게 해주면 되나면

 * f(6) * 6^2의 배수 더하고

 * f(5) * 5^2의 배수 더하고

(....)

이렇게 깔끔하게 정의한다. 이걸로 K 이하의 squarefree number를 열거할 수 있고 이제 이거 가지고 parametric search하면 됨.