1016: 제곱 ㄴㄴ 수

문제 보기
에라토스테네스의 체와 루트 N 검사를 혼합하여 1e7 범위 안쪽의 수들은 적당한 시간 내로 소수인지 판별하는 방법이 있었다.
같은 문제는 아니지만 이 방법의 시간 복잡도는 $O(Q\times \sqrt N)$이였었다.
사실 숨겨진 전처리 과정이 $O(\sqrt N)\; \text{by Eratosthenes' Sieve}$이였다.
체를 $\sqrt N$까지 설정하는 것이 핵심 포인트였다.

제곱 ㄴㄴ 수의 체

이 아이디어를 응용하면 이 문제도 시간 초과를 면할 풀이를 찾을 수 있다.
$O(\sqrt N)$의 체를 이용함과 동시에,
제곱 ㄴㄴ 수에 대한 새로운 체에 대해 연산을 한다.

이 sieve로 $[\min,\max]$ 범위에서 $p^2\mid u$인 모든 $u$를 체로 걸러주면 되는데,
이를 타이트한 범위로 잡아주면 이 수들을 검사하게 된다.
$\left \lceil\frac{\min}{p^2}\right \rceil\times p^2, \left \lceil\frac{\min}{p^2}\right \rceil\times p^2+p^2,\left \lceil\frac{\min}{p^2}\right \rceil\times p^2+2p^2,\cdots, \left \lfloor \frac{\max}{p^2} \right \rfloor\times p^2$

시간 복잡도를 분석해보자.

각 소수 $p$에 대해 (코드 내 if를 통과한 x) 진행되는 연산의 수를 확인해보자.

1. 에라토스테네스의 체

$\left \lfloor \frac{N}{p}\right \rfloor$번의 연산
$\therefore O(\frac{N}{p})$

2. 제곱 ㄴㄴ 수의 체

$\left \lfloor \frac{\max}{p^2} \right \rfloor-\left \lceil\frac{\min}{p^2}\right \rceil+1$번의 연산
$\therefore O(\frac{\max-\min}{p^2})$

3. 비교

문제를 풀기 위해 설정한 $N$은 $\sqrt {10^{12}+10^6}$였다.
wolframalpha에 넣어본 결과, 1.0000005e6 정도의 값이 나왔다.
사실상 $10^6+1$로 커버되는 값이다.
따라서 $max-min\leq N$이 항상 성립한다고 말할 수 있다.
그런데 분모의 차이는 더더욱 이 차이를 키워준다.
따라서 제곱 ㄴㄴ 수의 체 연산은 시간 복잡도에 드러나지 않게 된다는 것을 알 수 있다.