[백준/BOJ]#1629:곱셈 [분할정복/수학/파이썬/python]

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

1629번: 곱셈

 

분할정복 divide n conquer 과 수학 문제다.

수학의 분배법칙을 분할정복에 적용하여 재귀로 풀어나가면 된다.

 

 

호기심에 재귀 호출 순서가 궁금해서 프린트문을 여러번 찍어보았는데

마지막 홀수인 경우, ..(10^1)%12 x 10) %12 x 10이 마지막으로 호출된다.

그러므로 12로 다 나누면 남는 건 10 * 10 숫자만 남아서 결론적으론 답이 4가 나온다. 

#1629_곱셈
a,b,c=map(int,input().split())

'''
수학의 분배법칙 => 분할정복
10^11 % 12
= ((10^5)%12 x (10^5)%12 x 10)% 12
= ((10^2)%12 x (10^2)%12 x 10) %12 x (10^2)%12 x (10^2)%12 x 10) %12 x 10) %12
'''
def mul(a,b):
    if b==1:
        return a%c
    elif b%2==0:
        muldiv = mul(a,b//2)
        return (muldiv * muldiv) % c
    elif b%2!=0:
        muldiv = mul(a,b//2)
        return (muldiv * muldiv * a) % c


print(mul(a,b))