영리한 개발자는 해결하고, 노련한 개발자는 회피한다.

이번에 풀어본 문제는 최소인수입니다.

기본적인 집합론 지식이 있으면 풀어볼 수 있는 고난도 문제이며, 일종의 잔꾀를 부려서 풀이를 최적화할 수도 있죠. \(P\)를 가장 작은 소인수로 갖는 \(N\)번째로 작은 수를 찾으면 됩니다. 문제 설명은 정말 짧은데, 겉으로 보는 것보다는 생각을 꽤 많이 해야 합니다.

문제의 정답이 \(10^9\)를 초과하는 경우는 고려하지 않는데, 이것이 문제를 풀 수 있는 열쇠를 제공합니다.

일단 \(P^2\)이 \(10^9\)보다 큰 경우를 생각해봅시다. 가장 작은 소인수가 \(P\)이므로, 자명하게 첫 번째 수는 \(P\), 두 번째 수는 \(P^2\)이 됩니다. \(N = 1\)인 경우에만 답이 존재하고, 나머지 모든 경우는 무시할 수 있습니다.

이제 고려해야 할 \(P\)의 범위를 꽤 많이 줄였습니다. \(P\)가 작을 때를 생각해봅시다.

문제의 답은 어쨌든 \(P\)를 소인수로 가져야 하므로, 제한된 범위 안에서 \(P\)의 배수여야 할 겁니다. 또한 조금 달리 생각해보자면 가장 작은 소인수가 \(P\)인 수를 모두 찾는 것은, \(P\)보다 작은 소인수를 갖는 모든 수를 제외하는 것으로 볼 수 있습니다. \(P\)의 배수들만을 모아놓고 모두 \(P\)로 나눠줍니다. 그러면 1, 2, … 가 되겠죠. 여기서 \(P\)보다 작은 소수의 배수들을 지워나가면 답을 찾을 수 있을 겁니다! 에라토스테네스의 체를 쓰는데, 대신 지워나가는 소수는 \(P\)보다 작은 것까지만 하면 됩니다. 여기서 문제는 에라토스테네스의 체 자체의 시간복잡도인데, \(O(N \log \log N)\)이라서 N이 충분히 작아져야 쓸 수 있습니다. 달리 말하자면, \(10^9 / P\)가 작아져야 하므로 \(P\)가 충분히 커져야 합니다.

아니면 뭔가 다른 방법은 없을까요? 집합론으로 접근해보면, 이건 포함-배제 원리를 써서 풀 수 있습니다. \(2\)의 배수를 지우고, \(3\)의 배수를 지우고, \(6\)의 배수는 두 번 지워지니까 다시 더해주고… 규칙을 정리하자면 다음과 같습니다.

  • 소인수가 홀수 개라면 배수들의 개수를 뺍니다.
  • 소인수가 짝수 개라면 배수들의 개수를 더합니다.

수식으로 정리하면 \(\sum_{p \mid \Pi} \lfloor K/p \rfloor \mu(p)\)인데 이걸 뭐 빠르게 구해줄 순 없을 것 같고, 결국 백트래킹으로 해주는 게 좋을 것 같습니다.

typedef long long ll;
int primes[30];
ll f(const int p, const int k, ll pro = 1, int mu = 1, int i = 0) {
	if (pro > k) return 0;
	if (primes[i] >= p) return mu * (k / pro);
	ll ret = 0;
	ret += f(p, k, pro, mu, i + 1);
	ret += f(p, k, pro * primes[i], mu * -1, i + 1);
	return ret;
}

\(f\) 함수의 시간복잡도는 \(P\)보다 작은 소수들의 개수 \(n\)에 대해 \(2^n\)이므로 n은 충분히 작아야 합니다. \(k\)는 이분탐색으로 빠르게 찾아줄 수 있겠지만 백트래킹은 마음대로 되는 게 아니니까요.

에라토스테네스의 체나 포함-배제 원리 둘 다 한계가 있는 것 같습니다. 그럼 어떻게 해야할까요? 사실 어느 한 쪽을 버릴 필요가 없습니다. \(P\)가 충분히 크다면 에라토스테네스의 체를 쓰면 됩니다. \(P\)가 충분히 작다면 백트래킹을 돌리면 됩니다! 적절히 나은 방식을 선택하는 것이죠. 이제 적절한 경계를 설정해주면 되는데, 이건 \(70 \sim 100\) 정도가 적당합니다. 이 경계보다 \(P\)가 커지면 \(10^9 / P \lesssim 10^7\)이 되어 에라토스테네스의 체를 돌릴 수 있습니다. 경계보다 작아지면 \(P\)보다 작은 소수가 20개 정도가 되므로 \(2^{20} \approx O(10^6)\)이 되어 백트래킹으로도 해결할 수 있습니다.