자기 자신을 제외한 약수의 합이 자기 자신과 같은 수를 완전수라 한다. \(6 = 1+2+3\), \(28 = 1+2+4+7+14\), 그다음은 \(496\), \(8128, \dots\)

유클리드가 기원전 300년경 「원론」에서 짝수 완전수의 형태(\(2^{p-1}(2^p-1)\), \(2^p-1\)은 소수)를 밝힌 이래, 지금까지 발견된 완전수 52개는 전부 짝수다.

홀수 완전수는 존재하는가? 이것은 수학 전체에서 가장 오래된 미해결 문제로 꼽힌다. 2300년 동안 아무도 찾지 못했고, 없다는 증명도 없다. 존재한다면 \(10^{2200}\)보다 커야 하고, 적어도 101개의 소인수(중복 포함)와 10개 이상의 서로 다른 소인수를 가져야 하며, 오일러가 증명한 형태 \(n = p^{a} m^2\) (\(p \equiv a \equiv 1 \pmod 4\))를 만족해야 한다는 것 등 "존재한다면 이래야 한다"는 조건만 수십 개 쌓여 있다.

홀수 완전수를 하나 출력하라. \(n\)이 거대할 것이므로, 채점기가 약수의 합 \(\sigma(n)\)을 직접 계산할 수 있도록 소인수분해를 증거로 함께 제출해야 한다. 채점기는 각 소인수의 소수성(밀러–라빈), 소인수 곱이 \(n\)과 일치하는지, 그리고 \(\sigma(n) = 2n\)인지를 검증한다.

\(6\)이나 \(28\)을 내 보는 것은 자유지만, 채점기는 홀수가 아니라는 사실을 유클리드보다 먼저 지적할 것이다.

\(n\)은 \(1\)보다 큰 홀수, \(\sigma(n) = 2n\). \(1 \le k \le 10^5\), 소인수분해 전체 크기는 약 \(4 \times 10^6\) 비트 이하.

첫째 줄에 정수 \(0\)이 주어진다. 이 값은 무시해도 좋다 (이 문제에 실질적인 입력은 없다).

첫째 줄에 홀수 완전수 \(n\)을 출력한다.

둘째 줄에 서로 다른 소인수의 개수 \(k\)를 출력한다.

이후 \(k\)개의 줄에 \(p_i\) \(e_i\)를 출력한다. \(n = \prod_i p_i^{e_i}\) 이어야 하며, 각 \(p_i\)는 서로 다른 소수, \(e_i \ge 1\)이다.

riseoj 작성

출처 Original