[백준] 1629번 곱셈 (C++)

문제

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

 

자연수 A를 B번 곱한 수를 C로 나눈 나머지 값을 구하는 문제이다.

풀이

최대 연산 횟수는 약 21억이기 때문에, B번을 다 곱하면 시간 초과가 나온다.

 

그렇기 때문에 분할 정복을 이용해서 풀이해야한다.

 

예를들어서 입력이 2 8 5 일 때,

 

2를 8번 곱해서 256이 나오고 5를 나눈 나머지인 1이 출력될 것 이다.

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256

 

하지만 이 연산에도 규칙이 있다.

 

(((2^2)^2)^2)처럼 제곱을 이용하면 8번해야하는 연산을 3번으로 줄일 수 있다.

 

왜 그럴까 ?

 

위 식을 계산해보면 아래와 같다.

2^2 = 4

4^2 = 16

16^2 = 256

 

이 규칙을 적용해서 문제를 풀어봤다.

#include <bits/stdc++.h>

using namespace std;

long long a, b, c;

long long Solve(long long a, long long b, long long c)
{
	if(b == 0) return 1; 

	long long num = Solve(a, b / 2, c);
	num = num * num % c;
	
	if(b % 2 == 0) return num; // b가 짝수일 때
	return num * a % c; // b가 홀수라면 a를 곱한다. 
}

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

	cin >> a >> b >> c;

	cout << Solve(a,b,c);
	return 0;
}