[BOJ] 1629번 : 곱셈

1. problem : 

https://www.acmicpc.net/problem/1629

 

2. solution 1 :

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

long long recursion(long long base,long long exp, long long mod) {
	if (exp == 1) return 1;
	long long half = recursion(base, exp / 2, mod) % mod;
	long long result = (half * half) % mod;
	if (exp % 2 != 0) result = (base * result) % mod;
	return result;
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	long long a, b, c;
	cin >> a >> b >> c;
	long long ans = recursion(a,b,c) % c;
	cout << ans << '\n';
}

모듈러 곱셈을 이용한 재귀함수의 구현이다. 모듈러 곱셈을 이용하는 이유는 처음부터 다 곱하는 방식을 채택할 경우 시간초과가 난다. 하지만 이 방식을 사용할 경우 O(logb)의 시간복잡도를 가지게 된다. 

a^4 % mod = (a^2 % mod) ( a^2 % mod) % mod라는 식이 성립한다. 

또한, 지수가 홀수일 경우는 a^5 = a * a^4로 변환해서 구한다.