1629

[1629] 곱셈 - Python

/* 문제 */ 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 분할 정복 문제다. 어떤 수의 거듭제곱을 단순히 모두 곱해서 구한다면 시간 복잡도는 O(n)이지만 분할 정복을 이용해 구하면 O(log n)으로 해결할 수 있다. a의 b제곱은 b가 짝수일 경우 a^b = a^(b/2) * a^(b/2) b가 홀수일 경우 a^b = a^((b-1)/2) * a^((b-1)/2) * a 로 나타낼 수 있다. 따라서 재귀를 이용해 b가 1이 될 때까지 문제를 쪼개서 풀도록 구현했다. 또한 이 문제는 단순히 거듭제곱을 구하는 것이 아니라 나머지를 구하는 문제다. a = cx + y (a를 c로 나눈 나머지는 y) 라고 한다면..