[C++] 1629번 곱셈

문제

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

 

 

 

 

 

 

코드

#include <iostream>

using namespace std;

// 거듭제곱을 분할정복 방식으로 계산하는 함수
long long power(const long long& a, const long long& b, const long long& c) {
	if (b == 0)
		return 1;  // b가 0이면 a^0 = 1이므로 1을 반환

	// b를 절반으로 나누어 재귀적으로 계산
	long long half = power(a, b / 2, c);
	half = (half * half) % c;  // 모듈로 연산을 통해 계산된 값을 c로 나눈 나머지

	// b가 홀수인 경우 a를 한 번 더 곱해주어야 함
	if (b % 2 == 1)
		half = (half * a) % c;
	
	return half;  // 최종 결과 반환
}

int main() {
	long long a, b, c;

	cin >> a >> b >> c;  // 입력: a^b % c 계산을 위한 a, b, c 값

	cout << power(a, b, c);  // 결과 출력

	return 0;
}

 

 

 

풀이

 

1. 분할정복을 이용한 거듭제곱:
   • A^B를 직접 계산하지 않고, 거듭제곱의 성질을 이용하여 B를 반으로 나눠가며 계산한다.
   • 짝수일 경우: A^B=A^(B/2) × A^(B/2)
   • 홀수일 경우: A^B=A × A^(B/2) × A^(B/2)
   • 재귀적으로 나누면서 계산하여 O(log⁡B)의 시간 복잡도로 문제를 해결할 수 있다.
2. 모듈러 연산:
   • 중간 계산에서 값이 매우 커질 수 있으므로, 매 단계마다 C로 나눈 나머지를 적용한다.
   • 모듈러 연산의 성질을 이용하여 (A×B)%C=((A%C)×(B%C))%C를 적용하면, 중간 값이 커지지 않도록 할 수 있다.