시작

이 문제는 그냥 일반적인 for문으로 돌린다면, 시간초과가 뜨는 문제다. 그렇다면 어떻게 시간 초과를 해결할 수 있을까 생각을 해보면, 분할 정복이라는 것을 이용하여 풀면 O(n)이 아닌 O(log2n)으로 해결이 된다는 것을 알 수 있다. 그렇담 우선 분할 정복을 어떻게 접근해야 되는지 알아보자.

접근법

우선 제곱의 성질을 알아야되는데. 2^8은 2^4 2^4로 변환할 수 있고 2^16은 2^8 2^8로 가능하다는 것을 알아야된다. 그렇다면 이 것만 아는 것이 아니라 %연산자를 또 알아야되는데, (a + b)%c는 a%c + b%c로 바꿔 사용할 수 있다. 그리고 +가 아닌 *를 보자면, (a * b) % c는 비슷하게 a%c * b%c로 변환할 수 있다는 것을 알 수 있다.
a^10을 곱셈으로 변환하면 a*a*a*a*a*...*a로 변환이 가능한데, 저 곱하는 사이사이마다 %c를 넣어줘도 문제는 쉽게 해결 된다.

알고리즘

1. 우선 b가 1이면 a % c만 해주기
2. a^2 * a^2를 해주고 %c를 해주기
3. 만약 b가 짝수가 된다면, 정답 변수에다 * a %c를 해주기.

이런식으로 간단한 알고리즘을 짤 수 있다는 것을 알 수 있는데, 바로 밑에는 코드를 적어놓았다.

코드

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<cmath>
#include<algorithm>

using namespace std;

typedef unsigned long long int ull;

ull result = 0;
ull a, b, c;

ull powL(int a, int b) {
	ull result;
	if (b == 1) {
		return a % c;
	}
	// b가 1이 될때 까지 계속 재귀
	ull ret = powL(a, b / 2);
	// a^2 * a ^2 % 2
	ret = (ret * ret) % c;
	// b가 짝수면
	if (b % 2) ret = (ret * a) % c;
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> a >> b >> c;
	result = powL(a, b);
	cout << result;

}