[C/C++] 백준 1629번 - 곱셈 (분할 정복)

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

<코드>

#include<iostream>
#include<cmath>
using namespace std;

long long A, B, C;
long long sum = 1;
long long half;

long long solve(int x)
{
	if (x == 0) return 1;
	if (x % 2 == 1) return A * solve(x - 1) % C;
	else
	{
		half = solve(x / 2);
		return half * half % C;
	}
}

int main()
{
	cin >> A >> B >> C;
	cout << solve(B) % C;
}

 

문제풀이

B가 짝수일 경우 A^B = A^(B/2) * A^(B/2) 이고

(A*B) % C = (A%C * B%C) %C 의 성질을 이용

 

 

www.acmicpc.net/problem/1629

1629번: 곱셈