문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
풀이
곱셈을 그대로 B번 반복하면 너무 느리기 때문에 지수를 반으로 나누는 빠른 거듭제곱을 써야 한다. A^B mod C를 구할 때 B가 짝수면 절반 결과를 제곱하고, 홀수면 거기에 A를 한 번 더 곱하는 식으로 줄여 나가면 된다.
코드는 재귀적으로 절반 문제를 푼 뒤 매 단계에서 mod C를 취해 수를 관리한다. 지수가 한 번 호출될 때마다 절반으로 줄어드니 전체 복잡도는 까지 내려간다.
코드
#include <iostream>
using namespace std;
long long pow(long long a, long long b, long long c) {
if (b == 0) return 1;
if (b == 1) return a % c;
long long half = pow(a, b/2, c) % c;
half = half * half % c;
if (b % 2)
return half * a % c;
else
return half;
}
void solve() {
long long a, b, c;
cin >> a >> b >> c;
long long ans = pow(a, b, c);
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도: 지수를 절반씩 줄이는 빠른 거듭제곱이므로 이다.
- 공간 복잡도: 재귀 호출 스택 기준 이다.
마무리
곱셈을 그대로 B번 반복하면 너무 느리기 때문에 지수를 반으로 나누는 빠른 거듭제곱을 써야 한다.
