[알고리즘][Python] 백준 1629 곱셈 문제 풀이

문제 출처 : www.acmicpc.net/problem/1629

1629번: 곱셈

---

문제 해석 : A ** B % C를 구하는 문제이다.

 

문제 풀이 : 단순하게 A ** B % C를 수행하면 시간 초과가 난다. 수학적인 접근이 필요하지만 pow에는 나누어 나머지를 구하는 연산이 포함되어 있기 때문에 이를 활용한다. (최적화가 적용되어 있음)

 

가능한 다른 풀이 : 실제로 문제가 의도한 것은 분할 정복이다. 예를 들어 200000 ** 2000000 은 굉장히 많은 시간이 소모 되기 때문에 수학적 풀이 방식으로 풀 수 있다. 다음과 같은 수식을 보자

 

--> A = XxC + R : A는 어떤 수 X을 C로 곱하고 R을 더한것 (여기서 우리는 R을 구해야 한다.)

--> A^2 = (XxC)^2 + 2(XxC)xR + R^2 : 2차 방정식

--> 따라서 A^2를 C로 나눈 나머지는 R^2 % C와 같다.

 

이를 재귀적으로 프로그래밍 하면 문제를 풀 수 있다.

---

풀이 코드

A, B, C = map(int, input().split())
print(pow(A, B, C))

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.