[알고리즘] 백준 1629 곱셈 힌트 및 정답

---

[알고리즘] 백준 1629 곱셈 문제 힌트

1. 모듈러(%) 연산의 기본 성질

a를 b번 곱하는 것을 c로 나눴을 때 나머지를 식으로 표현하면 다음과 같다.

a(b번제곱)%c = x;

b를 2라고 하면 다음과 같다

(a*a)%c = x;

이는 다음과 같이 표현해도 같다

a%c * a%c = x;

즉, 2제곱을 이런식으로 나눠 표현할 수 있다는 것에서 힌트를 얻을 수 있다.

 

2. 재귀 함수로 표현

이를 재귀함수로 표현해서 식을 작성해보자.

 

---

문제 정답

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll a,b,c;
ll result;
ll make_result(ll a, ll b){
	// 기저사례 
	if(b == 1) return a%c; // 그냥 10 1이 들어왔다고 생각하면 뭘 return 해줘야할지 떠올리면 된다. 
	
	result = make_result(a, b/2);
	result = (result * result) %c; // 실제 유효 연산 
	
	if(b % 2) { // b가 홀수인 경우 
		result = (result * a) %c;
	}
	return result; 
}

int main() {
	cin >> a >> b >> c;
	cout << make_result(a, b) << "\n";
	
	
	return 0;
}