[c++/백준] 1629번: 곱셈

문제 링크

1629번: 곱셈

풀이

분할 정복을 이용하는 문제

1. b가 반으로 계속 나눠 1이 될 때까지 재귀 호출을 한다.
   1-1. 반으로 나누어 떨어지면 func(a,b/2,c) * func(a,b/2,c)를,
   1-2. 안 떨어지면 func(a,b/2,c) * func(a,b/2+1,c)를 호출
2. 나머지는 계산 중간마다 해주어도 결과가 바뀌지 않기 때문에 계속해서 구해준다.

코드

#include <iostream>
#include <vector>

using namespace std;

long long func(long long a, long long b, long long c) {
	if (b == 1) return a % c;
	
	if (b % 2 == 1) return ((func(a, b / 2, c) % c) * (func(a, b / 2 + 1, c) % c)) % c;
	else return ((func(a, b / 2, c) % c) * (func(a, b / 2, c) % c)) % c;
}

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	
	cout << func(a, b, c);

	return 0;
}