[BaekJoon] 백준 1629번 곱셈

[BaekJoon] 백준 1629번 곱셈 문제: www.acmicpc.net/problem/1629 내코드 이 문제는 일단 brute force 방식으로 접근하면 O(n) 시간 복잡도로 풀수 있지만 이 경우에 시간 초과가 남 분할 정복 방식으로 풀어야하는 문제: 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 간단하게 생각하면 a^b mod c를 풀어야 하는 문제 여기서 b=2k+1 일때 a^b = (a^k)^2xa이고 b=2k일때 a^b = (a^k)^2임을 생각해보자 예를 들어 2의 16제곱이면 brute force 방식은 16번 계산해줘야하지만 분할 정복을 하면 2의 8제곱한 결과를 제곱해주면 된다. 즉, 2의 8제곱은 2의 4제곱의 제곱이고, 2의 4제곱은 2의 제곱의 제..