행렬 제곱 문제문제를 풀다가 도저히 모르겠어서 찾아보니 D&C로 거듭제곱을 빠르게 풀 수 있다는 것을 알았다. 그래서 쉬운 버전으로 풀어본 문제.
처음에 봤을때는 와닿지 않았는데, 생각해보니까 내가 직접 손으로 거듭제곱을 계산하는 방식이랑 비슷하다. 쉽게 말하면 그냥 값을 재활용하자는 것이다. 예를 들어 3^6을 계산할 때, 3*3=9->9*3=27->27*3=81->81*3=243->243*3=729처럼 계산하는 것보다 (3^3)*(3^3)으로 계산하면, (3^3)과 같이 같은 값들을 활용해 계산하는 것이 계산 횟수도 줄여준다.
구현
#include <iostream>
using namespace std;
long long solve(int A, int B, int C) {
if (B == 0) return 1;
long long N = solve(A, B / 2, C);
long long tmp = (N * N) % C;
if (B % 2 == 0) return tmp;
else return (A * tmp) % C;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int A, B, C;
cin >> A >> B >> C;
cout << solve(A, B, C) << endl;
return 0;
}