(파이썬) 백준 1629번 "곱셈"

---

# 문제상황

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

def R(B):
    global A, C
    ans = 0

    if B == 1:
        ans = A
    elif B % 2 == 1:
        ans = R(B // 2) ** 2 * A
    elif B % 2 == 0:
        ans = R(B // 2) ** 2

    return ans % C

print(R(B) % C)

 

 

 

 

 

---

# 풀이과정

 

어떤 수 A를 20억번 곱해야한다고 가정해봅시다.

무식하게 A를 정말 20억번 다 곱하고 있으면 시간이 오래 걸립니다.

 

생각해봅시다.

(A의 20억승)은 (A의 10억승)을 2번 곱한 것과 같습니다.

즉 A를 20억번 곱할 필요 없이, A를 10억번만 곱하고 그 결과를 제곱하면 연산횟수가 절반으로 줄어듭니다.

 

다른 예시를 생각해봅시다.

(A의 101승)은 어떻게 빨리 구할 수 있을까요?

(A의 50승)을 제곱해주고 거기에 A를 1번만 더 곱해주면 됩니다.

 

 

결론. (A의 B승)을 빨리 구하는 법

1) B가 짝수일 때  →  (A의 B승) == ((A의 B // 2승)의 2승)

2) B가 홀수일 때  →  (A의 B승) == ((A의 B // 2승)의 2승) * A