곱셈

시간 제한	      메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB       	52968	13956	10237	25.684%

문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1
10 11 12

예제 출력 1
4

---

먼저, python 으로 풀지 않는 이상 코드 내에서 변수들의 크기가 자료형의 범위를 훨씬 뛰어넘을 수 있다는 것을 주의해야한다. (int overflow 주의)
또한, 시간 제한이 0.5초로 주어졌는데 만약 거듭제곱을 for 문으로 계산해준다고 가정해보면 B가 가질 수 있는 값은 2,147,483,647이 최대이다. 대충 생각해보면 2,147,483,647 회만큼의 연산이 발생할 수 있고 이는 요구되는 시간 제한에 전혀 미치지 못한다.
~> 함수 재귀를 이용하는 분할정복(divide and conquer) 알고리즘을 이용하면 O(log N)의 시간 복잡도로 해결할 수 있다.

---

구현

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll pow(ll a, ll b, ll c)
{
	if (b == 1) return a%c;
	ll var = pow(a, b / 2, c);
	var = var * var % c;
	if (b % 2 == 0)return var;
	else return var*a% c;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	ll a, b, c;
	cin >> a >> b >> c;
	cout << pow(a, b, c) << endl;
	
	return 0;

}