백준 1629/c++ )) 곱셈 - divde and conquer, 재귀함수

그대로 주는대로 계산하면 연산시간이 너무 길어서 시간 초과하는 문제이다

재귀 함수로 분할정복 divde and conquer를 사용하여 연산 수를 줄이고,

각 입력의 최대값이 int 의 최대치 값 이므로 long long 을 사용하여 결과값의 오버플로우를 1차로 막는다

분할한 값을 합칠때 큰 수끼리의 곱셈을 해야하므로 long long 뿐 아니라 %c 로 모듈러 연산을 해줘서 

2차로 오버플로우를 막아야 하는 문제이다

 

재귀함수라지만 내가 gr로 작성한 부분이 gr=gr*gr 이고 gr=gr*a%c 이라는 부분에서 왜인지 이해하느라 머리가 터졌고

시간도 몇시간을 걸려서 이해했지만, 이해했으니 비슷한 유형도 이제 익숙해질것이다

내일을 공부를 위해 더 늦기전에 자자...

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

ll a, b, c;

ll tok(ll a, ll b, ll c){
	//재귀함수이므로, 기저 사례 처음에 기술   
	if(b==1)
		return a%c;
	//  tok 함수의 b가 절반인 gr을 정의하기 위해 재귀함수를 사용함. 계속 분할됨  
	ll gr = tok(a, b/2, c);
	// b값이 반인 gr 끼리 곱해서 다시 원상태의 a^b로 만들어준다. 오버플로우를 막기 위해 c로 모듈러 처리해준다  
	gr = (gr*gr)%c;
	// 홀수일 경 우  
	if(b%2)
	// 예를들어 5를 나누면 2씩 나눠지고 1을 더해줘야 원래 크기가 되듯이
	// 홀수면 반씩 나눈 gr을 곱해줘도 a^1 을 곱해줘야 원상복구된다. 모듈러 처리 해주자  
		gr=(gr*a)%c;
	// 그러면 짝수인 경우, 홀수인 경우 모두 gr이 원래의 a^b와 같아진다  
	return gr;	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> a >> b >> c;
	cout << tok(a, b, c) << "\n";
	
	return 0;
}