백준 1557 - 제곱 ㄴㄴ

 문제를 요약하자면, k번째 무승수를 구하는 것이다. 원래는 포함 배제 원리를 통해 해결하는 풀이가 있는 것으로 알고 있지만, 본 글에서는 다른 방식으로 해결하는 방법을 서술할 것이다.

 우선, 해당 문제를 알아야 한다. 특정 구간이 주어졌을 때 그 내부에 있는 무승수의 개수를 구하는 것이다. 이 문제의 제한은 1<= min <= 1000000000000이고, min<= max <= 1000000이다. 해당 문제의 해를 구할 수 있다면 문제의 해결은 매우 단순해진다. 우선, 현재 우리고 풀고자 하는 문제는 K<=1000000000이다. 넉넉잡아 범위를 20억까지 잡고(사실 이 bound는 완벽히 기억나지 않는다. 10억번째 무승수까지 잡으면 된다.), 해당 구간을 길이 100만의 구간들로 쪼갠다. 이제 각각의 구간들에 대해 제곱ㄴㄴ수 문제를 해결해준다. 그렇다면 약 2000개의 구간이 나타날 것이며, 이들을 계산하는 데에는 많아봐야 4000초, 조금 더 효율적으로 구할 수 있다면 그보다 빠르게 모든 구간에 대한 값을 알아낼 수 있을 것이다.

 이제, 이렇게 구한 모든 값들을 미리 하나의 배열에 넣어두고, 누적합을 계산한다. K가 주어지면, 해당 배열을 순차적으로 확인하면서 현재까지의 합이 K보다 작은 최대의 구간을 찾는다. 그렇다면 우리는 길어봐야 길이 100만인 구간에서 k번째 무승수를 찾는 문제를 풀면 된다. 이 또한 비교적 간단하게 해결될 수 있는데, 어떤 수가 무승수가 아니라면 그 수가 포함하는 제곱수의 크기가 제한되어있기 때문이다. 대충 10만까지 그 제곱을 확인한다고 해도 벌써 100억 이하의 모든 제곱수들을 표시할 수 있게 된다. 따라서 i를 2부터 100만까지 i의 제곱인 수들을 표시하되, 한번 건너뛸 때 i^2씩 건너뛰도록 한다. 이때, 표시하는 수들의 개수는 절대로 100((pi^2)/6)을 넘길 수 없는데, 그 이유는 바젤 문제의 결론을 통해 이해할 수 있다. 따라서 문제를 푸는 시간이 부족할 일은 없다.