1629 - 곱셈

문제 풀이

위 문제는 일반 for문으로 풀면 O(N)의 시간이 걸리는데 B의 최대가 21억이 넘으므로 B가 최대일 때 21초가 걸린다. 하지만 문제의 시간제한은 0.5초이므로 분할정복을 이용하여 O(logN)의 시간복잡도를 이용하여 풀이를 해야한다.

정답 코드

#include <iostream>
using namespace std;

int C;

long long fun(int a, int b) {
	if (b == 1) {return a%C;}
	long long k = fun(a, b / 2)%C;
	if (b % 2 == 0) { //짝수일 때
		return k*k%C;
	}
	else { // 홀수일 때
		return (a * k%C * k)%C;
	}
}

int main() {
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	int A, B;
	cin >> A >> B >> C;
	cout<<fun(A, B)%C;
	return 0;
}

놓친 점

1. %C로 계산할 때 마다 나눠주지 못했다.
   return (a * k * k)%C -> return (a * k%C * k)%C;
2. a = 2,147,483,647(21억) b = 2 이면 int형을 벗어나므로 자료형은 long long을 써야한다.