문제 링크
https://www.acmicpc.net/problem/1629
A^(m+n) = A^m * A^n
(A*B)%C = (A%C)*(B%C)%C
위의 지수법칙. 분배 법칙을 알아두어야 한다.
정답 코드
A,B,C = map(int,input().split())
def solution(a,b,c):
if b == 1: #a의 1제곱이면.
return a%c
N = solution(a,b//2,c) # a^(b//2) 구하기
if b % 2 == 0: #b가 짝수
return N*N%c #지수 법칙 사용
else: #b가 홀수
return N*N*a%c #지수 법칙 사용
print(solution(A,B,C))
728x90
'파이썬 알고리즘 문제 풀이' 카테고리의 다른 글
Baekjoon Online Judge 2875번. 그리디 (0) | 2023.01.05 |
---|---|
Baekjoon Online Judge 11047번 파이썬. 그리디 (0) | 2023.01.05 |
Baekjoon Online Judge 1780번 파이썬. 분할 정복. (0) | 2022.12.27 |
Baekjoon Online Judge 1992번 파이썬. 분할 정복. (0) | 2022.12.27 |
Baekjoon Online Judge 2630번 파이썬. 분할정복 (0) | 2022.12.26 |