[BOJ 16644] Easy Problem

이 문제는 제목이 거짓임을 1초만에 알아차릴 수 있다. 1557번의 제한이 제곱된 것인데 논리적인 흐름은 거의 비슷하다. 둘 다 이진탐색을 이용한다는 것? 이 문제가 어려운 이유는 시간제한이 말도 안되게 빡빡하기 때문... 연산 횟수를 무진장 줄이는 것이 포인트이다. 먼저 이 수가 몇 번째 square free number인지 알아보자. 다음 식을 이용한다.

\[\sum_{i=1}^{\sqrt{n}} \mu(i)\lfloor \frac{n}{i^{2}} \rfloor\]

이 식이 나온 이유는 포함 배제의 원리로 쉽게 생각할 수 있다. 1부터 천천히 생각해보자. 1인 경우 전체 $n$을 더한다. $2, 3$ 등 소수인 경우는 그 소수로 이루어진 제곱수의 개수를 빼준다. 제곱 ㅇㅇ수의 경우 개수를 아예 세지 않는다. 제곱 ㄴㄴ수지만 $6$과 같은 경우 $2,3$에 의해 double counting된 수를 1번만 세질 수 있도록 만드는 역할을 한다. 설명은 이 정도면 된 것 같다. 이제 최적화 방법을 알아보자. 우리는 harmonic lemma를 이용해 $O(\sqrt{N})$ 시간에 답을 구하는 것을 즐겨 쓴다. 하지만 저 위의 식은 square harmonic이 되었다. 시간 복잡도를 분석해보자. 다음은 익히 알려진 사실이다.

\[\lfloor \frac{n}{i^{2}} \rfloor = \lfloor \frac{\lfloor \frac{n}{i} \rfloor}{i} \rfloor \]

이때 $\lfloor \frac{n}{i} \rfloor$ 수가 $2\sqrt{N}$개 있다는 것이 harmonic lemma 였다. 그럼 평균적으로 각 $\lfloor \frac{n}{i} \rfloor$에 대해서 그 길이가 $\sqrt{N}$개 정도 있다는 말이다.  그럼 그 길이가 $\sqrt{N}$인 것에 대해서 또 다시 harmonic lemma를 적용하면 $\sqrt{\sqrt{N}}=N^{1/4}$만큼 있을 것이다. 따라서 합을 계산하는데 시간 복잡도가 $O(N^{3/4})$이 된다. $N=10^{9}$이 된다면 약 6백만번의 거대한 연산을 해야한다!! 물론 이때 $\mu(i)$의 합을 구하는 것까지 한다면 연산은 더 늘어난다. $\mu(i)$의 합은 xudhy's sieve로 빠르게 구할 수 있어서 다행이다. 하지만 이런 최적화로는 5초 안에 안된다. 뭔가 더 좋은게 필요하다. 그것은 바로! $N$까지의 square free number의 개수가 약 $\frac{6}{\pi^{2}}N$개 라는 거. $N$이 커질수록 $\frac{6}{\pi^{2}}$ 값에 수렴하기 때문에 숫자가 작을 때에는 텀을 좀 두어야 한다. 큰 수에 대해서는 텀을 작게 만들어 최대한 5초 안에 비빌 수 있도록 해보자. 필자는 20번정도 비볐더니 됐다. 깔깔