BOJ 1629 곱셈

BOJ 1629 곱셈

문제링크 : https://www.acmicpc.net/problem/1629

요약

(A^B)%C를 구하는 문제

풀이

주어지는 세 수의 최댓값이 2,147,483,647이다. 지수값이 저렇게 큰수면 곱하다가 시간초과 나버린다. 시간복잡도를 줄이기 위해서 분할정복으로 해결하여야 한다. 지수 B가 짝수인 경우에는 A^B=(A^(B/2))^2 이고 홀수인 경우엔 A^B = A*(A^((B-1)/2))^2이다. 이렇게 연산을 logB개로 줄일수 있게 되고 시간복잡도도 즉 O(logB)가 된다. 숫자가 매우 크기 때문에 long long 자료형을 사용하여 오버플로우를 방지해주었고, C로 나눠주는것도 연산할때마다 해주었다.

코드

#include<iostream>
using namespace std;
typedef long long ll;
ll A, B, C;
ll go(ll a, ll b, ll c) {
	if (b == 0) return 1;
	else if (b == 1) return a % c;
	else if (b % 2 == 0) {
		ll ans=go(a, b / 2, c);
		return (ans * ans)%c;
	}
	else {
		return (a*go(a, b - 1, c))%c;
	}
}
int main() {
	cin >> A >> B >> C;
	cout<<go(A, B, C)<<"\n";
}