7268 : 재귀 거듭제곱
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
분할 정복을 이용한 거듭제곱 $A^B \bmod C$를 계산하십시오.
$B$가 짝수이면 $A^B = (A^{B/2})^2$, 홀수이면 $A^B = A \times A^{B-1}$로 분할합니다.
시간 복잡도: $O(\log B)$
[제약 조건]
• 입력되는 모든 수는 정수입니다.
$B$가 짝수이면 $A^B = (A^{B/2})^2$, 홀수이면 $A^B = A \times A^{B-1}$로 분할합니다.
시간 복잡도: $O(\log B)$
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 밑 $A$, 지수 $B$, 나누는 수 $C$가 주어집니다. ($1 \le A, B, C \le 2^{31}-1$)
출력 설명
$A^B \bmod C$를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2 10 1000
출력 예시
COPY
복사되었습니다!
복사되었습니다!
24도움
Python의 내장 함수
pow(A, B, C)가 이 연산을 효율적으로 수행합니다. 직접 구현 시 if B % 2 == 0: half = power(A, B//2, C); return (half * half) % C를 사용합니다.