ps:problems:boj:4464
Pride and Prejudice and Zombies
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 4464 |
| 문제명 | Pride and Prejudice and Zombies |
| 레벨 | 다이아몬드 5 |
| 분류 |
정수론 |
| 시간복잡도 | O(n^1/3 * logn) |
| 인풋사이즈 | n<=10^18 |
| 사용한 언어 | Python 3.13 |
| 제출기록 | 36852KB / 308ms |
| 최고기록 | 308ms |
| 해결날짜 | 2026/02/01 |
풀이
- 다이아급 사전지식(O(n^1/4) 시간복잡도의 소인수분해) + 실버급 활용 문제.
- 문제 앞부분의 이야기들은 다 필요 없고, 뱀파이어 수가 어떤 수인지 설명하는 부분부터만 읽으면 된다.
- 결국 N=a*b 로 썼을 때 a와 b가 특정 성질을 만족하는지를 찾으면 된다. a와 b의 길이가 각각 N의 길이의 절반이고, a에 있는 숫자들과 b에 있는 숫자들을 모으면 N에 있는 숫자들과 같고, 연속된 0을 포함하면 안되고 하는 성질들은, a와 b가 주어지면 O({a의 digit 개수} + {b의 digit 개수}) 에 모두 확인 가능하다. 대충 상수 시간으로 취급해도 되고, 굳이 정확하게 표현하자면 O(logN)으로 쓸 수도 있다. 아무튼 얼마 안걸린다.
- 그러면 N의 모든 약수에 a에 대해서, N=a*b로 표현한 뒤에 저 성질을 만족하는지를 확인하면 된다. 모든 약수를 이터레이션 하는것은, 폴라드 로에 기반한 O(n^1/4) 소인수분해를 사용하면, 약수의 개수인 O(n^1/3)에 바운드된다. 총 시간복잡도는 O(n^1/3 * logn).
코드
(다이아몬드 이상은 코드 생략)
- Dependency: teflib.numtheory.all_divisors
ps/problems/boj/4464.txt · 마지막으로 수정됨: 2026/02/01 13:15 저자 teferi
토론