BOJ 28263 - 하이퍼 가짜 초콜릿 (Python3?)

인생 두 번째 루비 문제다. 제2회 초콜릿컵 🍫번 문제인데, 대회 중에는 이게 내가 아는 그 개념을 쓰는 건 맞지만 어떻게 해야 할지 감을 못 잡아서 내버려 뒀었다. 에디토리얼을 보니 난이도가 Impossible이라고 매겨져 있더라. 그런데 148분만에 문제를 푼 사람이 나왔고. 어떻게 풀었는지 그 분의 코드를 까 봤지만 힌트를 얻을 수 있는 게 없었다.

에디토리얼에는 논문 하나가 나와 있었고, 그것대로 대충 구성했더니 답을 루비 치고는 간단하게 얻을 수 있었다. 다만 이 풀이가 시간 단위가 아닌, 1초 안에 답을 뱉는 풀이는 아니었다. 그렇게 되도록 최적화하는 것은 분명히 루비 난이도가 맞았다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

초콜릿과 숫자놀이를 좋아하는 코코는 "초콜릿 수"를 다음과 같이 정의하였다.

⊙ 어떤 양의 정수 \(n>1\)이 1과 자기 자신으로만 나누어 떨어질 때, \(n\)을 초콜릿 수라고 한다.

얼마 뒤 코코는 "코코 정리"를 발견하였다.

⊙ \(p\)가 초콜릿 수이면, \(p\)와 서로소인 모든 정수 \(a\)에 대해 \(a^{p-1}\equiv1\pmod{p}\)이다.

코코는 이를 이용해 어떤 수가 초콜릿 수인지 판별하는 방법을 떠올렸다. 구체적인 방법은 다음과 같다.

⊙ \(p\)와 서로소인 모든 정수 \(a\)에 대해 \(a^{p-1}\equiv1\pmod{p}\)이면, \(p\)는 초콜릿 수이다.

하지만 얼마 지나지 않아 코코는 561이 이 판별법의 조건을 만족하지만 초콜릿 수가 아니라는 사실을 발견하였다. 코코는 이러한 수를 "가짜 초콜릿 수"라고 부르기로 하고, 가짜 초콜릿 수를 찾는 방법을 연구하기 시작했다.

초콜릿 공장을 돌리는 것도 잊고 연구에 매달린 결과, 코코는 3개, 4개, …, 10개의 초콜릿 수를 곱한 가짜 초콜릿 수를 찾을 수 잇었지만, 11개를 곱한 것은 찾을 수 없었다. 코코 대신 이러한 가짜 초콜릿 수를 찾아 주자. 아무거나 찾는 것은 어렵지 않으니, 다음의 조건을 만족하는 수 \(N\)을 찾아보자.

⊙ \(N=a_1\times a_2\times\cdots\times a_{11}\)이라고 쓸 때, \(N\)은 가짜 초콜릿 수이고, \(1\le i\le 11\)에 대해 \(a_i\)는 \(10^7\le a_i<10^8\)을 만족하는 초콜릿 수이다.

 

입력

입력은 없다.

 

출력

문제의 조건을 만족하는 수를 초콜릿 수 11개의 곱으로 나타내었을 때, 그 11개의 초콜릿 수를 첫 줄에 오름차순으로 출력한다.

---

내 코드

 

이 문제는 코드를 공개하지 않을 예정이다. 내 풀이 방법대로 한다면 100%의 확률로 시간초과가 나기 때문에 나는 로컬에서 수 시간 동안 컴퓨터를 혹사시키는 방법으로 시간초과를 강제 회피했기 때문에다.

문제 서술은 혼란스럽지만, 묻는 것은 간단하다. "\(10^7\) 초과 \(10^8\) 미만의 소수 11개의 곱으로 이루어진 카마이클 수가 실존한다. 이 카마이클 수를 구성하는 소수들의 목록을 오름차순으 출력하라."

문제 속 초콜릿 수는 소수, 코코 정리는 페르마의 소정리, 그리고 초콜릿 수 판별법은 페르마의 소정리 역, 그리고 가짜 초콜릿 수는 카마이클 수이다. 카마이클 수란 모든 자연수 \(a\)에 대해서 \((a,p)=1\)이 성립한다면 \(a^p\equiv a\pmod{p}\)를 만족시키는 합수 \(p\)를 뜻한다.

 

카마이클 수에 대해서는 추후에 다른 게시글로 다루기로 하고, 여기서는 이 문제를 풀 수 있을 정도만큼 강력한 카마이클 수의 성질만 이용하기로 하자.

Korselt's criterion이라 이름붙은 강력한 정리에 의해서 어떤 수가 카마이클 수가 되기 위한 필요충분조건을 알 수 있다. 어떠한 정수 \(n\)이 합성수이고, 소수 제곱으로 나누어떨어지지 않으면서 모든 \(n\)의 소인수 \(p\)에 대해서 \(p-1\mid n-1\)가 성립함이 \(n\)이 카마이클 수이기 위한 필요충분조건이 된다.

물론 이걸 그대로 이용하기에는 상당한 무리가 있다. \(10^7<p<10^8\)인 소수 \(p\)는 정확히 \(5,096,876\)개가 존재하고, 이 중 랜덤하게 11개를 뽑는 경우의 수는 \(\binom{5096876}{11}\approx1.510\times10^{66}\)가지나 된다. 1초에 1억 번 계산한다고 근사하고 있으니, 이걸 계산하려면 대충 \(4.787\times 10^50\)년이라는 천문학적이고 비상식적인 시간이 필요하다. 더욱 시간단축이 필요하다.

 

논문 한 편(Alfotd et al, 2013)을 참조하면 Erdös Construction이라는 방식으로 카마이클 수를 찾을 수 있다. 내 풀이는 이 논문을 바탕으로 구성하였다.

우산 약수가 매우 많은 합성수 \(\Lambda\)를 하나 지정한다. 작은 소수의 곱으로 표현할 수 있는 수면 좋다. 이제 적당한 소수의 집합 \(P=\{p\mid p-1\mid\Lambda, p\not\mid\Lambda\}\)을 구성하고, \(P\)의 부분집합 \(S\)가 \(N=\prod_{p\in S}p\equiv1\pmod\Lambda\)이 성립되도록 구성한다면 이 \(N\)이 카마이클 수이다.

소인수가 모두 \(10^7\)보다 작은 적절한 수 \(\Lambda\)를 잡으면 \(P=\{10^7<p<10^8\mid p-1\mid\Lambda\}\)의 원소 수가 기껏해야 50개가 되도록 할 수 있으며, 그 중 11개를 뽑는 경우의 수는 \(\binom{50}{11}\approx3.735\times10^{10}\)이다. 제대로 선택했다면 경우의 수가 \(\varphi(\Lambda)\)보다 제법 크므로 정답이 되는 \(S\subset P\)가 존재할 가능성이 크다고 예상할 수 있다. 확률론적 방법이고 실패할 가능성이 있지만, 단순히 확률론적이라고 이 방법을 버릴 이유는 없다. 밀러-라빈 소수판정법도 이 방법으로 돌아가는데.

대충 373.5억번이고 1억번 당 3~4초가 소모된다고 가정하면 24시간 내에 답을 뱉어낼 수 있다. 루비 문제 하나에 24시간이면 나쁘지 않다. 안 그런가?

그렇게 얻은 답을 Python이든, txt든 담아서 출력만 해 주면 끝.

 

이로서 28263번의 풀이를 마친다.