[15907] Acka의 리듬 세상

마지막 수정 시각: 2021-01-08 18:13:58

문제 링크

문제가 막 아주 어렵다거나 그런 것은 아닌데, 다른 사람들이랑 좀 다른 풀이로 풀었고 정리해둘만한 것 같아서 정리해둔다.

수의 최대 크기를 \( M \) 이라고 하고, \( M \) 이하의 모든 수에 대해 그 수의 최소 소인수를 에라토스테네스의 체 방식으로 구해두자. 이렇게 전처리해둘 경우 특정 수 \( K \)가 주어졌을 때 \( K \)의 모든 소인수를 \( O(logK) \) 시간에 구할 수 있다(자세한 방법은 rkm님의 정수론 가이드 글 참조).

이렇게 구해놓고 나서, \( N \)개의 수 중 \( f(k, l) \)에 포함시킬 수를 하나 고정하고 이 수를 \(a_1 \cdot k + l\) 이라고 하자. 이 수와 포함할 다른 수 \(a_2 \cdot k + l, a_3 \cdot k + l, \dots\) 들과 이 수와의 차이를 기준으로 생각해보면, 빼고 난 다음에는 덧셈 항 \(l\)이 날아가므로 차이값은 전부 \( k \)의 배수가 되어야 한다(차이값은 각각 \((a_2 - a_1) \cdot k, (a_3 - a_1) \cdot k, \dots\) 가 되므로).

또 이 때 \( k > 1 \) 이어야 하고 \( k \)가 소수가 아니라면 소수가 될 때까지 나누어주어도 답에는 변화가 없으므로(선택했던 수들을 그대로 다시 선택할 수 있으므로), \( k \) 의 후보는 소수만 고려해도 된다.

따라서 (모든 차이값의 소인수 중에 가장 많이 등장한 것) + 1 이 임의의 수 하나를 고정했을 때 고를 수 있는 수 개수의 최대값이 된다. 모든 수에 대해서 이 과정을 반복해주면 되므로, \(O(MloglogM + N^2logM)\) 시간에 문제를 해결할 수 있다.