[Baekjoon] 1629번: 곱셈

🥅 문제

https://www.acmicpc.net/problem/1629

 

🔍 설계

반복문을 사용하여 계속 a를 곱하고 c로 나누면서 갱신한다면, b가 20억 이상이므로 시간 초과가 발생한다.

 

거듭제곱의 특성 중에 x^(y+z) = x^y * x^z가 있다. 여기서는 간단하게 홀수 짝수로 구분한다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

long long a, b, c;

long long square(long long b) {
	if (b == 0) {
		return 1;
	}
	else if (b % 2 == 0) {
		long long half = square(b / 2);
		return half * half % c;
	}
	else if (b % 2 == 1) {
		return square(b - 1) * a % c;
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> a >> b >> c;

	cout << square(b) << "\n";

	return 0;
}