(Python/🥈1)백준알고리즘1629번:곱셈

문제 출처: https://www.acmicpc.net/problem/1629

1629번: 곱셈

풀이:

import sys


def func(A,B,C):
    if B == 1:
        return A % C
    else:
        half = func(A, B//2, C)
        if B % 2 == 0: # 짝수면
            return half * half % C
        else:
            return half * half * A % C

A,B,C =map(int,(input().split()))
print(func(A,B,C))

 

일단 예를들어서 ABC에 2 16 12 가 들어왔다고 생각을하면

2의 16승은 

2^16 로 2를 16번 곱해도 되지만.

((((2^2)^2)^2)^2) 이렇게 4 번만 연산해도 된다.

그거를 식으로 만들면 위에처럼나온다

 

half로 2의 16승을 2의 8승으로 내리고

그다음 재귀호출해서 2의4승 2의2승 2의 1승 이렇게 내려오면서

C로 나눈 나머지를 리턴해주면 되는 식이다

 

(2^2)^2 를 식으로보면 hlaf * half % C 다   그 다음도 쭊쭊 마찬가지,,