백준 1629번 C++

백준 1629번 곱셈
https://www.acmicpc.net/problem/1629

1629번: 곱셈

정답 코드

#include<iostream>
using namespace std;
long long int pow(long long a, long long b, long long m) {
	if (b == 1)
		return a % m;
	long long val = pow(a, b / 2, m);
	val = val * val % m;
	if (b % 2 == 0)
		return val;
	return val * a % m;

}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long int a, b, c;
	cin >> a >> b >> c;
	cout << pow(a, b, c);
	
}

문제 풀이

수학력을 요구하는 문제이면서 재귀를 이용하여 푸는 문제입니다. int형을 사용하면 오버플로우가 발생할 수 있기 때문에 long long int형을 사용하였습니다.
또한 b가 최대21억인 경우 시간초과가 나기 때문에 O(n)보다 낮은 시간복잡도를 사용해야 합니다.

먼저 b가 1인 경우, 바로 a를 m으로 나눈 나머지를 출력할 수 있도록 하였습니다. 그리고 다음 줄에
long long val = pow(a, b / 2, m);

그 다음 b가 짝수일 때와 홀수일 때를 나누어서 풀어야 합니다. b가 짝수일 경우에는 그냥 val값을 반환하면 되지만 b가 홀수일 경우에는 a를 한 번 더 곱해서 반환해야 합니다. 이렇게 풀 경우 시간복잡도는 O(logb)입니다.