백준 25821번 - Palindromic Primes
백준 25821번 문제 링크
문제 이름 : Palindromic Primes
주 언어 : Python
태그 : 브루트포스 알고리즘 / 수학 / 밀러-라빈 소수 판별법 / 정수론 / 소수 판정
solved.ac 등급 : Platinum IV (2023/10/15 확인)
문제 보기
문제 : (번역 및 요약)
팰린드롬 수는 앞에서부터 읽어도 뒤에서부터 읽어도 똑같은 수를 말합니다. (이 문제에서는 10진법에서)
소수란 $1$과 자기 자신으로만 나누어 떨어지는 수를 의미합니다.
$L$ 이상 $H$ 이하의 팰린드롬인 소수의 개수를 출력해주세요.
입력 :
첫 줄에 $L$, $H$가 공백을 두고 입력된다. ($H < 10^{12}$)
출력 :
$L$ 이상 $H$ 이하의 팰린드롬인 소수의 개수를 출력한다.
$10$진법에서 짝수자리인 펠린드롬 소수 는 $11$밖에 없습니다.
홀수자리 숫자의 합 = 짝수자리 숫자의 합이면 $11$의 배수라는 "$11$의 배수 판별법"이 있는데,
모든 짝수자리의 펠린드롬 수는 홀수자리 숫자의 합 = 짝수자리 숫자의 합인지라 $11$의 배수가 됩니다. 단, $11$ 그 자체는 소수이니 예외인 셈입니다.
따라서 $H < 10^{12}$이라는 제한 조건이 있지만 $10^{11} < x < 10^{12}$인 팰린드롬 소수는 존재하지 않고 (12자리 수) $10^{11}$까지만 따져보면 됩니다.
일반적인 문제가 시간 제한이 0.5초, 1초, 2초, 3초 정도인데 시간 제한을 12초나 주었다는 것은, 대학교의 오픈북 시험마냥 "풀 수 있으면 풀어봐라" 식으로 이해해야 합니다. 즉 시간이 엄청 오래 걸린다는 의미입니다.
따라서 최대한 최적화를 시킬 필요가 있습니다.
다른 부분은 접어두고 우선 $10^{10} < x < 10^{11}$ 사이의 펠린드롬 소수 (11자리수)가 몇개 있는지를 10초 정도 내에 찾아낼 수 있으면 범위 내에서는 넉넉하게 풀 수 있습니다.
두 가지 접근법이 있을 수 있는데, 소수를 먼저 찾고 팰린드롬인지 판단하는 것이냐, 혹은 팰린드롬인지 판단하고 소수인지 판단하는 것이냐가 있습니다.
이 범위 내에서의 모든 소수를 에라토스테네스의 체 같은걸로 만들어서 저장해놓으면 당연히 시간복잡도 $O(n \ln\ln{n})$에서 가능하지도 않고, 공간복잡도 $O(n)$에서 메모리 초과가 뜰 것입니다. (보통 파이썬에서는 크기 1억짜리 리스트도 만들기 힘듭니다.)
즉, 팰린드롬수를 만들어내서 그 수들을 소수인지 판단하는 것이 편하겠습니다.
11자리 수의 팰린드롬수 이므로, 그 수는 "a b c d e f e d c b a" 꼴의 수이고, a는 1부터 9까지, 나머지 수는 0부터 9까지 입니다.
a에 올 수 있는 수가 9가지이고, b, c, d, e, f에 올 수 있는 수가 각각 10가지이므로 90만번의 소수판별을 해야합니다.
아무래도 $2$부터 $\sqrt{N}$까지 나누어보는 소수판별법 같은걸 썼다가는 시간초과가 확실히 날 것 같습니다.
우선 줄일 수 있는만큼 줄여보자면, a에 올 수 있는 수는 사실 미리 처리할 수 있습니다.
a에 2, 4, 6, 8이 오면 "a b c d e f e d c b a"는 짝수가 되므로 무조건 소수가 아닙니다.
따라서 a에 올 수 있는 수는 1, 3, 5, 7, 9로 5가지가 되고, 이 경우에는 50만번 소수판별을 하면 됩니다.
사실 10만번 더 줄일 수 있습니다. a == 5이면 "a b c d e f e d c b a"는 5의 배수이므로 무조건 소수가 아닙니다. (일의 자리수가 $5$이기 때문) 따라서 a에 올 수 있는 수는 1, 3, 7, 9로 4가지가 되고, 40만번의 소수판별만 남습니다.
아파트 임대 (백준 5615)가 10만번의 소수판별인데, 그거보다 더 심한 문제인 셈입니다.
그래도 12초인 만큼, 밀러-라빈 소수 판별법 을 써주면 시간 내로는 풀 수 있을 것으로 보입니다.
isPrime + MRTest 함수에서 소수판별을 담당하고, PalindPrime 함수는 L이상 H이하의 2K + 1자리 소수의 개수를 세는 함수입니다.
파이썬 zfill 함수 에 따라 a = str(j).zfill(K)를 하면, 예를 들어 j = 3, k = 4라고 하면 0003을 만들어줍니다. a[::-1]은 문자열 슬라이싱 기법으로 문자열 a를 뒤집는 식입니다.
11의 경우가 짝수자리이면서 펠린드롬 소수인 유일한 예외인데 이거까지 감안해서 함수 만들기는 머리아파지니 그냥 2부터 11까지는 논외로 쳐주고 일일이 더해줍니다.
PyPy3도 아니고 Python3에서도 약간 지저분한 이 정도 코드로 6초 안에 통과하니 C나 C++ 같은 경우도 2K + 1자리의 팰린드롬 수를 어떻게 만들지만 신경쓰셔서 만드시면 시간 내로 넉넉하게 통과하실 수 있습니다.
사실 더 빠르게 푸는 법이 있습니다. Poulet Number (유사소수)를 이용한 풀이인데, 페르마의 소정리 에 따라 모든 홀수 소수 $p$는 $2^{p - 1} \equiv 1 \pmod{p}$를 만족합니다.
해당 문제에서 주어진 L, H 범위 ($H < 10^{12}$) 내에서 펠린드롬이면서, 일의자리가 1, 3, 7, 9이면서, 홀수자리이면서, $2^{N - 1} \equiv 1 \pmod{N}$이면서, 합성수인 $N$이 딱 한 개 존재하는데,
이것만 따로 처리해주고 isPrime(N) 함수를 "$2^{N - 1} \equiv 1 \pmod{N}$ is True?"로 바꿔주면 됩니다. 그 "어떤 합성수 $N$"을 여기다가 쓰면 문제가 너무 쉬워져버릴테니 한번 그 수를 직접 찾아보시는 것을 추천드립니다.
(사실 $H < 10^{12}$ 에서 펠린드롬이면서, 일의자리가 1, 3, 7, 9이면서, 홀수자리이면서, $q^{N - 1} \equiv 1 \pmod{N}$이기만 하면 $N$이 소수인 것이 확실한 어떤 정수 $q$도 있는데, 그것도 찾아보시는 것을 추천드립니다.)
원래 제가 이 문제를 처음 풀었을 때는 골드 1이어서 그래도 밀러-라빈 쓰는거 감안하고 5615번이 "소수판정 문제 + 소수판정 문제임을 알아차리는데 까지의 발상"이 합쳐져서 플레 1이니 플레 2는 줘야겠지...하면서 난이도 투표에서 플레 2를 줬습니다.
그랬더니 바로 문제 난이도가 플레 5로 올라가버렸습니다;
그 뒤에 한 분이 푸시고 플레 1을 투표하셔서 플레 4까지 오른걸 봤는데, 그 뒤에 또 한분이 플레 1을 투표하셔서 지금 이 문제가 갑자기 플레 3 문제까지 올라갔습니다.
아무리 그래도 소수판별 40만번 해야하는데 골드 1은 좀...아닌듯 합니다.
23년 03월 31일 추가) 중간에 플레 2까지 오른걸 봤는데, 현재는 미리 모든 소수의 리스트를 뽑아서 푸는 경우 (런타임 전의 전처리) 또한 존재하고, 일반적인 소수판별법 을 극한까지 밀어붙여서 10초 안에 어떻게든 푸는 케이스도 존재하여 플레 3 까지 떨어졌습니다.
23년 04월 05일 추가) 사실상 밀러 라빈 소수판별법 보다 런타임 전의 전처리나 극한의 효율을 추구한 소수 판별법이 정해가 되어가는 모습입니다. (덕분에 플레 4가 되었습니다.)
소수판별법 자체의 속도 보다는 얼마나 후보인 팰린드롬을 빠르게 만들 수 있는지 / 혹시 12자리 팰린드롬을 만들고 있지는 않은지가 더 중요한 문제인듯 보입니다.
23년 10월 15일 추가) 최근의 풀이는 아무래도 $10^{5.5}$ 정도까지의 소수까지만 에라토스테네스의 체 로 만들어서, 이 수 들로만 나누어보는 것이 대세가 되는 느낌입니다.
소수판별법에서 사실 $2$부터 $\sqrt{N}$까지 다 나눠볼 필요가 없는 이유를 응용한 셈입니다. ($2$로도 나눠보고 $3$으로도 나눠봤으면 $6$으로는 나눌 필요가 없음. $\sqrt{N}$ 까지의 "소수들"로만 나눠보면 충분)
-번째 푼 문제 (2023/--/--)