[백준/C++] 1629번 - 곱셈

 

문제

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

 

자연수 A를 B번 곱한 수를 알고 싶다.

 

단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

 

 

입력

 

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

 

 

출력

 

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

 

 

풀이

 

제곱의 횟수가 매우 많기 때문에 이를 구하기 위해서는 제곱하는 횟수 B를 B/2 로 나눈 뒤, B/2번 제곱했을 경우의 값을 구하고 B/2를 곱하는 방법으로 문제를 풀었다.

 

B/2번 곱하는 것은 재귀로 만들었다.

 

그리고 C로 나눈 나머지를 구할 것이므로 C보다 큰 경우 C로 나눈 나머지만 곱해주면 된다.

(C보다 큰 수는 C+"나머지"의 형태로 표현할 수 있고 (C+나머지)의 제곱을 C로 나누면 결국 나머지의 제곱을 나눈 값과 같기 때문이다.)

 

 

Code

 

 

#include<iostream>
using namespace std;

// 1629 곱셈
long long A, B, C, now = 0;
long divd(long cnt) {
	long mid=0;
	long long m = 0;
	if (cnt ==1) {
		return A % C;
	}
	mid = cnt/2;
	m = divd(mid);
	if (cnt % 2) {
		m *= m;
		m %= C;
		m *= A;
		m %= C;
		return m;
	}
	else {
		m *= m;
		m %= C;
		return m;
	}
}

int main() {
	cin >> A >> B >> C;
	cout<<divd(B);
	return 0;
}

 

---

 

역시 이분 탐색...

 

1629번: 곱셈