문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

• 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

---

1. 처음 소스코드 및 실수

• 기본 아이디어)
  a mod x를 a를 x로 나눴을 때의 나머지라고 표현하면,
  (a × b) mod x = {(a mod x) × (b mod x)} mod x가 성립한다.
• 이 아이디어를 이용하여 temp에 반복적으로 temp * (A % C)를 곱하고 C로 나눈 나머지를 저장했다.
• 하지만 이 방법은 B까지 한 단계 한 단계 천천히 올라가는 것이므로 시간 초과가 발생하였다. 조금 더 빨리 B에 도달할 수 있는 계산 방법을 알아내야 했다.

#include <iostream> int main() { int A, B, C; scanf("%d %d %d", &A, &B, &C); int temp = A % C; for (int i = 0; i < B - 1; i++) { temp = (temp * (A % C)) % C; } printf("%d\n", temp); }

2. 최종 소스코드 및 해결방법

• 변형 아이디어: 이진수 활용(2의 거듭제곱 활용)
  위의 mod 관련 공식을 사용하는 것은 똑같으나, 시간을 더 줄이기 위해 2의 거듭제곱을 사용하는 방법을 채택했다.
  즉, $10^{11}$ 을 $12$ 로 나눈다고 하면, ingredients라는 배열에 $(10$ % $12)$, $(10^2$ % $12)$, $(10^4$ % $12)$, $\cdots$ 를 저장해두고, 11을 이진수로 바꿔서 위의 ingredients 배열에서 필요한 값만 뽑아다가 쓰는 방식이다.
• 그렇게 되면 위의 1번 방법처럼 하나 하나 곱해나가는 것 보단 훨씬 빠르게 된다.
• 자세한 것은 주석 참고

#include <iostream> int MAX_LENGTH = 100; int main() { //result: 최종결과 //start: 최종결과를 구하기 위해 필요한 인덱스 long long A, B, C; long long result = 1; long long start; scanf("%lld %lld %lld", &A, &B, &C); //toBinary: B를 이진수로 바꿔 저장한다. //binIndex: toBinary에서 사용할 인덱스 변수 int toBinary[MAX_LENGTH] = { 0, }; int binIndex = 0; //ingredients: 답을 구하기 위한 계산의 재료들이 저장됨. //재료들이란, A%C, (A^2)%C, (A^4)%C, (A^8)%C 등을 일컫는다. //temp: 재료들을 만들 임시 변수 long long ingredients[MAX_LENGTH]; long long temp = A % C; ingredients[0] = temp; //B를 이진수로 바꿔 저장하는 작업 while (B > 0) { toBinary[binIndex] = B % 2; binIndex++; B /= 2; } //재료들을 필요한만큼(binIndex만큼) 계산하여 준비해두는 과정 for (int i = 1; i < binIndex; i++) { ingredients[i] = (ingredients[i - 1] * ingredients[i - 1]) % C; } //toBinary에서 처음 1이 나온 칸에 대응하는 수를 result에 저장 //최종 결과를 구하기 위해 start에 binIndex를 탐색할 인덱스를 저장 for (int i = 0; i < binIndex; i++) { if (toBinary[i]) { result = ingredients[i]; start = i + 1; break; } } //toBinary에서 1이 나올때마다 result를 업데이트 for (int i = start; i < binIndex; i++) { if (toBinary[i]) { result = (result * ingredients[i]) % C; } } printf("%d\n", result); }