https://www.acmicpc.net/problem/1557

문제

어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, …과 같은 수이다.

K가 주어졌을 때, K번째 제곱ㄴㄴ수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 K가 주어진다.

출력

첫째 줄에 K번째 제곱ㄴㄴ수를 출력한다.

제한

• 1 ≤ K ≤ 1,000,000,000

풀이

$k = 10^9$이므로 1부터 하나하나 제곱 ㄴㄴ 수인지 확인하는 것은 불가능하다.

어떤 수가 제곱 ㄴㄴ 수인지 판별하는 것은 소인수분해를 하는 것과 같으므로 $O(\sqrt{n})$이다. 차라리 에라토스테네스의 체처럼 제곱 ㄴㄴ 수가 아닌 것을 걸러내며 푸는 것이 나아보였다.

소수 $p$에 대해 $p^2$의 배수는 제곱 ㄴㄴ 수가 아니고, 어떤 수 $x$보다 작거나 같은 수 중 $p^2$의 배수의 개수는 $\left\lfloor x / p^2 \right\rfloor$로 구할 수 있다.

소수를 미리 구해놓은 다음 포함-배제 원리를 써서 $x$보다 작거나 같은 제곱 ㄴㄴ 수의 개수를 구하는 함수 $f(x)$를 만들면 $f(x-1)=k-1 \ \land \ f(x)=k$인 $x$를 이진탐색 하듯 찾을 수 있을 것이라 생각했다.

$1,000,000,000$ 번째 제곱 ㄴㄴ 수가 얼마나 큰 수일지 궁금해서 일단 만들어서 구해보니 $1,644,934,081$가 나왔다. 소수를 $\left\lceil \sqrt{1,644,934,081} \right\rceil = 40558$까지 구하도록 고쳤다.

꽤 빨리 돌아가길래 제출해봤는데 시간 초과가 아니라 틀렸습니다가 나왔다. $40559$로 바꾸고 $f(x)$의 탐색 범위를 완화하니까 정답처리 되었다.