[분할정복] 백준 1629번 곱셈 with Python3 ★★

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

정답 풀이

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

## a^b%c를 반환하는 함수
def solution(a, b):
    # 어떤 수든 재귀를 타면 b==1이 되게 된다.
    
    if b==1:
        return a%c
    ans = solution(a, b // 2) # 지수승 절반값의 %c한 값 호출
    
    if b%2==0: # 짝수
        return ans*ans%c
        
    else: # 홀수
        return ans*ans*(a%c)%c
        # 공식상으로는 ans*ans*(a%c)%c지만 ans*ans*a%c 랑 같다.
        # 나머지 연산 (a*b*c*d)%f 는 a,b,c,d를 각각 f로 나눈 나머지를 곱한뒤 f로 나눈 값이나, 몇개는 냅두고 몇개는 f로 나눈 나머지를 곱한 값을 f로 나눈값이나 같다.

print(solution(a,b))

출처: https://backtony.github.io/algorithm/2021/02/11/algorithm-boj-class4-7/

 

해석

자세한 설명은 링크에.

 

사실 완전히 이해하는데에는 실패했다..