[백준 파이썬 1629번 곱셈] 분할 정복

지수 법칙

A^m+n = A^m x A^n

나머지 분배 법칙

(AxB)%C = (A%C) *(B%C) % C

 

예제 문제

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

1629번: 곱셈

분할 정복

→ 11 이면 5, 6으로 스플릿

→ 6 이면 3, 3으로 스플릿해서 계산한다

 

ex)

a = 10 , b = 11 , c = 12

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

 

11 -> 5 -> 2 -> 1 분할 정복

import sys

A, B, C = map(int, sys.stdin.readline().split())

def cal(a, b):
    if b == 1:
        return a % C
    else:
        tmp = cal(a, b//2)
        if b % 2 == 0:
            return (tmp * tmp) % C
        else:
            return (tmp * tmp * A) % C

print(cal(A, B))

 

+ int max = 2,147,483,647