6003 : 분할정복 — 거듭제곱

시간 2.000s · 메모리 256MB · 제출 1 · 정답 1

코드제출 문제 풀기

채점기록 통계 묻고답하기

세 정수 $a, n, m$이 주어질 때, $a^n \bmod m$을 고속으로 계산하십시오.

시간 복잡도 $O(\log n)$을 만족하는 분할 정복 알고리즘을 재귀 함수로 구현해야 합니다.

[제약 조건]
• 밑 $a$: $1 \le a \le 10^9$ (정수)
• 지수 $n$: $0 \le n \le 10^{18}$ (정수)
• 모듈러 $m$: $2 \le m \le 10^9$ (정수)

첫째 줄에 정수 $a, n, m$이 공백으로 구분되어 주어집니다.

[제약 조건]
• $1 \le a \le 10^9$
• $0 \le n \le 10^{18}$
• $2 \le m \le 10^9$

$a^n \bmod m$을 계산하여 출력합니다.

2 10 1000

지수 분할 법칙($a^n = (a^{n/2})^2$)을 이용한 분할 정복 빠른 거듭제곱($O(\log n)$)을 구현합니다.