백준 1629번 곱셈 파이썬

리뷰

모듈러 연산을 통한 재귀 풀이

 

문제 풀이

1. 모듈러 연산의 성질을 활용하여 재귀를 통해 값을 구하였다.
2. 초기 입력받은 a, b, c를 재귀를 사용할 함수에 보내준다.
3. a가 밑, b가 지수이므로 b가 0이 될때까지 실행을 하고 b가 0일 경우 a^b는 1이므로 1을 리턴해 준다.
4. b가 0보다 클 경우 b를 0으로 나눈 값을 재귀 시킨다, 이후 짝수일 때는 a^(b/2) * a^(b/2)를 c로 나눈 나머지 값을 half로 정의, 홀수일 때는 짝수에서 나온 값 half에 밑 a를 한번 더 곱해준 후 c로 나눈 나머지 값을 half로 정의한다.
5. 이후 half를 리턴해 주면 된다.

 

참고 사항

모듈러 연산 정보

1. 덧셈: (a+b)%m=((a%m)+(b%m))%m
2. 곱셈: (a×b)%m=((a%m)×(b%m))%m
3. 거듭제곱: (a^b)%m=((a%m)^b)%m

 

정답 코드

import math


def prod(a, b, c):
    if b == 0:
        return 1
    half = prod(a, b // 2, c)
    half = (half * half) % c
    if b % 2:
        half = (half * a) % c
    return half


a, b, c = map(int, input().split())
print(prod(a, b, c))