[BOJ / C++] 곱셈 (재귀)

문제링크: https://www.acmicpc.net/problem/1629

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll POW(ll a, ll b, ll m) {
	if (b == 0) return 1 % m;
	if (b == 1) return a % m;

	ll val = POW(a, b/2, m);
	val = val * val % m;
	if (b % 2 == 0) return val;
	return val * a % m;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	ll a, b, c;
	cin >> a >> b >> c;
	cout << POW(a, b, c);
}

 

 

2. 분석

1. Base Condition

if (b == 0) return 1 % m;
if (b == 1) return a % m;

지수(b)가 0이면 a^0 = 1이므로 1%m을 리턴해줘야한다. 지수(b)가 1이면 a^1 = a이므로 a mod m을 리턴한다.

 

2. 재귀호출 (반으로 나누기)

ll val = POW(a, b/2, m);

지수를 절반 (b/2)으로 줄여서 먼저 계산한다. 즉, a^(b/2) mod m을 계산한다.

 

3. 제곱 and modulo

val = val * val % m;

그 값을 제곱한 뒤 다시 m으로 나눈다.

 

4. 홀짝 보정

if (b % 2 == 0) return val;
return val * a % m;

b가 짝수면 끝, 홀수면 위 val에 a를 한번 더 곱해서 a^2(b/2)+1 = a^b를 완성해 다시 m으로 나눈다.

 

3. 시간복잡도

재귀 깊이가 절반씩 줄어들어 log b이므로 시간복잡도는 O(log b)이다.