[Divide and Conquer] 1629 곱셈

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

1629번: 곱셈

# 2023.01.01
import sys
input = sys.stdin.readline

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

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

print(DAC(a, b, c))

1. b==1일때 a

2. b는 짝수일때 DAC*DAC

3. b는 홀수일때 DAC*DAC*a

 

나눠서 계산 -> 이를 활용해서 계산하기

-> 연산횟수를 줄일 수 있음