[백준 1629] 곱셈

문제 

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

1629번: 곱셈

---

아이디어

$f(n)$을 $x^n$을 계산하기 위해 필요한 최소 계산 횟수라고 하자.

 

$2^16$을 계산하기 위해 필요한 최소 계산 횟수를 구해보자. 

• 직접 계산하면 2를 16번 곱해야 하기 때문에 16번의 계산이 필요하다. 

이 경우 n이 2,147,483,647이 되면 계산 횟수가 너무 많아진다. 이럴 때 분할 정복을 이용한다. 

 

$f(16)$

= $f(8)+1$ : $2^{16} = 2^8 * 2^8$이기 때문  

 

 

$f(8)$

= $f(4)+1$ : $2^{8} = 2^4 * 2^4$이기 때문  

 

 

$f(4)$

= $f(2)+1$ : $2^{4} = 2^2 * 2^2$이기 때문  

 

$f(2) = 2$

 

결론적으로 

$f(16) = f(8)+1 = (f(4)+1)+1 = ((f(2)+1)+1)+1 = ((2+1)+1)+1 = 5$가 된다. 

 

이렇게 분할 정복을 이용해서 계산 횟수를 줄여야 한다. 

 

그리고, 나머지에 대한 분배법칙을 확인해보자. 

$a = k_1 m + l_1, b = k_2m + l_2$라고 하면 $a\%m = l_1, b\%m = l_2$이다.

그리고, $a+b = (k_1+k_2)m + (l_1+l_2)$가 된다. 

$(k_1+k_2)m$은 $m$으로 나누어 떨어지고, $(l1+l2)$가 $m$보다 큰 경우 나머지는 $(l_1+l_2)\%m$ 이기 때문에

$(a+b)\%m = (l_1+l_2)\%m$이 된다. (뺄셈도 똑같이 진행하면 됨)

 

곱셈도 마찬가지인데, $ab = (k_1k_2)m^2 + k_1l_2m + k_2l_1m + (l_1l_2)$가 된다. 

$k_1k_2m^2$, $k_1l_2m$, $k_2l_1m$  은 $m$으로 나누어 떨어지고, $(l_1l_2)$가 $m$보다 큰 경우 나머지는 $(l_1l_2)\%m$ 이기 때문에

$ab\%m = (l_1l_2)\%m$이 된다.

 

이를 코드로 구현하면 다음과 같다. 

---

Solution

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

def f(a, b) : 
    if b == 1 : 
        return a % c
    else : 
        rec = f(a, b//2)
        if b % 2 == 0 : 
            return rec**2%c
        else : 
            return a*rec*rec%c

print(f(a, b))