백준 1629 곱셈 C++ / 구현(분할정복)

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

1629번: 곱셈

 

1. 핵심 아이디어

분할정복을 이용한 거듭제곱 문제

 

A^10은 A*A*A*A*A*A*A*A*A*A로 곱하기연산을 총 9번 반복해야한다.

 

이걸 분할정복하기 위해

(A^2)^5로 바꾸면 A^2계산 1번, 그 후 제곱연산을 위한 4번의 계산으로 5번으로 줄어든다.

여기서 A^2를 A`라고 부른다면 (A`)^5가 되는데 이건 A` * (A`)^4와 같다.

그럼 또 (A`)^4를 (A`^2)^2로 분할정복 가능하다.

 

즉 정리하자면

지수가 짝수라면 (A^(지수/2))^2

지수가 홀수라면 A * (A^(지수/2))^2

 

2. 코드구현

1) 재귀방식으로 구현

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

int A, B, C;
int recursion(int B)
{
	if (B == 0) return 1;

	long long temp = recursion(B / 2);
	temp = (temp * temp) % C;

	if (B % 2 == 0) return temp;
	else return (A * temp) % C;
}

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

	cin >> A >> B >> C;
	cout << recursion(B);
	
	return 0;
}

B의 0승은 1로 return

B의 1승부터는 (A * temp) % C로 나머지연산으로 값 줄여가면서 분할정복

 

2) 반복문으로 구현

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

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

	long long A, B, C;
	cin >> A >> B >> C;

	long long answer = 1;
	while (B > 0) {
		if (B & 1) answer = (answer * A) % C; // 남는 한번 미리 곱해두고

		A = (A * A) % C;
		B /= 2; // A ^ 2로 만들면서 B는 반으로 줄임
	}

	cout << answer;

	return 0;
}