6006 : 분할정복 — 카라추바 곱셈
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
매우 큰 두 개의 자연수 $X$와 $Y$가 주어질 때, 분할 정복을 이용한 카라추바(Karatsuba) 알고리즘을 사용해 두 수의 곱을 구하십시오.
시간 복잡도는 일반 곱셈 $O(N^2)$보다 빠른 $O(N^{\log_2 3}) \approx O(N^{1.58})$을 만족해야 합니다.
[제약 조건]
• 두 수 $X, Y$: 각각 최대 $10{,}000$자리 비음수 정수
• 카라추바 알고리즘으로 구현해야 합니다.
입력 설명
첫째 줄에 두 자연수 $X, Y$가 공백으로 구분되어 주어집니다.
[제약 조건]
• 각 수의 자릿수는 최대 $10{,}000$자리
출력 설명
두 큰 수의 곱 $X \times Y$를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
12345 67890
출력 예시
COPY
복사되었습니다!
복사되었습니다!
838102050도움
카라추바(Karatsuba) 분할 정복 곱셈 알고리즘을 사용하거나 파이썬의 임의 정밀도 곱셈을 활용합니다.