문제https://www.acmicpc.net/problem/1629자연수 A를 B번 곱한 값을 C로 나눈 나머지 구하기A, B, C는 모두 2,147,483,647 이하의 자연수풀이A, B, C가 매우 큰 값이므로 직접 A^B%C를 구할 수 없다. (오버플로우 발생)A^B라는 매우 큰 값을 작은 값으로 분할하여 나머지 연산을 해야 한다.분할 : A^B를 작은 값들의 곱으로 치환(아래 그림처럼 B가 짝수일 때, 홀수일 때 다르게 치환됨)-> A^1 될 때까지 분할하기2. 합병 : 작은 값들을 연산한 후 합쳐서 큰 값의 해를 구하기를 반복한다. 여기서 중요한 작업 : 작은 값들을 합쳐 큰 값의 해를 구할 때 [모듈러 연산의 분배 법칙]을 적용해준다.모듈러 연산의 분배 법칙(a + b) % m = ((a %..
