백준 1629번: 곱셈

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

1629번: 곱셈

 

 

0. 알고리즘 분류

 수학, 분할 정복을 이용한 거듭제곱

 

 

1. 문제

 

 

2. 풀이

 간단한 문제라고 생각했지만, 머리가 굳어서그런지 꽤나 어려웠다. 오버플로우가 일어나지않게 c로 나누는 건 쉬웠지만, a를 b번 곱하는게 문제였다. 일반적인 곱셈으로 풀면 시간초과가 뜬다. 따라서 a의 거듭제곱을 다시 곱하는 방법으로 시간을 줄여줘야한다. answer = n^k == (n ^ k/2) * 2 == ... k가 짝수일때는 앞과 같이 처리하면 되지만, 1보다 큰 홀수일때는 다르다. k%2 == 1이면, (k-1)에 대해서 거듭제곱을 수행한 이후, 마지막에 a를 추가적으로 곱해주면 된다. 풀고보니 그렇게 어려운 문제는 아니었지만, 수학을 놓은지 오래되서 금방 생각해내지 못했다...

 

 

3. 코드

#include <bits/stdc++.h>

using namespace std;

int a,b,c;

int power(int n, int k) {
	if (k == 0) {
		return 1;
	}
	
	int temp = power(n, k/2);
	int ans = 1LL * temp * temp % c;
	
	if (k%2)
		ans = 1LL * ans * n % c;
	
	return ans;
}

int main(void) {
	cin >> a >> b >> c;
	
	cout << power(a, b);
	return 0;
}