[Python] 백준1629 곱셈

19 May 2023 in Study on Algorithm

백준1629 곱셈 링크

문제

예제 입력

---

코드

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

# 분할 정복
def sol(n):
    if n == 1:
        return a % c
    else :
        tmp = sol(n//2)
        if n % 2 == 0:
            return (tmp * tmp) % c
        else :
            return (tmp * tmp * a) % c

print(sol(b))

설명

파이썬을 통해서 사용자로부터 입력받아 분할 정복알고리즘을 사용하여 곱셈를 구현했습니다.

---

정리

* 지수 법칙
A^(m+n) = A^m x A^n

* 나머지 분배 법칙
(A x B) % C = (A%C) * (B%C) % C

이 문제의 예제에 적용을 해보면
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

n(10)이 짝수면 ((A^5)%C x (A^5)%C) % C 로
n(11)이 홀수면 ((A^5)%C x (A^5)%C x A) % C 로
나누면서 분할 정복하여 log(2) 시간이 걸리기 때문에 적합합니다.
처음에는 자연수(약21억) 이하 조건을 생각못하여 for문으로 시간초과가 발생했습니다.

---

결과