[c++] 백준 1629, 곱셈

백준 1629

🌲 문제 요약

A를 B번 곱한 수를 C로 나눈 나머지를 출력하는 문제.

🌲 문제 풀이

자칫 높아질 수 있는 시간 및 공간 복잡도를 해결하기 위해 재귀 함수 및 모듈로 연산을 활용한다.
재귀 함수 go를 통해, B의 값을 반으로 나누어가며 A의 B제곱을 분할 계산한다. 이때 과정 중간중간, 계산 값을 C로 나누어, 값이 너무 커지는 위험을 방지한다.

🌲 주의

마지막 결괏값에서만 C로 나눈 나머지를 구하는 것이 아니라, 과정 속에서 수시로 모듈로 연산을 통해 값을 작게 만들어주어야 함에 주의하자.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll A, B, C;

ll go(ll a, ll b) {
	if (b == 1) return a % C;
	
	ll ret = go(a, b / 2);
	if (b % 2)  return ((ret * ret) % C * a) % C;
	else return (ret * ret) % C;
}

int main() {
	cin >> A >> B >> C;
	cout << go(A % C, B) << '\n';
	
	return 0;
}