[Baekjoon] 1629번: 곱셈

 

 

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

1629번: 곱셈

 

---

 

문제 해결 과정

착안

단순하게 반복적으로 같은 수를 곱하며 거듭제곱을 계산하면 지수 $E$에 대해 $O(E)$의 시간 복잡도를 소요하므로, 재귀를 활용하여 지수를 절반씩 줄여나가 $O(\log E)$의 시간 복잡도로 계산하고자 하였다.

 

한편, 나머지 연산(modulo operation)의 특성에 따라 다음과 같은 성질들이 성립함을 이용하였다. 자연수 $A, B, C$에 대하여 $A$를 $C$로 나눈 나머지를 $a \space (0 \leq a < C)$ 라고 할 때,

 

1) $A = Cq + a \space$ ($q, a$는 0 또는 자연수) 일 때,

$A^B = (Cq + a)^B$

$= {B \choose 0}(Cq)^B + {B \choose 1} (Cq)^{B-1} a + {B \choose 2} (Cq)^{B-2} a^2 + \cdots + {B \choose {B - 1}} (Cq) a^{B-1} + {B \choose B} a^B$

$= C( C^{B-1}q^B + {B \choose 1} C^{B-2}q^{B-1} a + {B \choose 2} C^{B-3}q^{B-2} a^2 + \cdots + {B \choose {B - 1}} q a^{B-1} ) + a^B$

$= C k + a^B$

이므로,

$$\therefore A^B \bmod C = a^B \bmod C$$

 

2) $B = b_1 + b_2$인 정수 $b_1, b_2$에 대해,

$A^B = A^{b_1 + b_2} = A^{b_1} A^{b_2}$

$= (Cq + a)^{b_1} (Cq + a)^{b_2}$

$= (C k_1 + a^{b_1}) (C k_2 + a^{b_2}) \space$ ($\because$ 위의 1) 에서와 같은 방법으로 전개하여 정리 가능하므로)

$= C^2 k_1 k_2 + C k_1 a^{b_2} + C k_2 a^{b_1} + a^{b_1}a^{b_2}$

$= C k_3 + a^{b_1} a^{b_2}$

 

이때 $a^{b_1} = Cq_1 + m, \space a^{b_2} = Cq_2 + n \space (0 \leq m, n < C)$ 라고 하면,

$A^B = C k_3 + (Cq_1 + m)(Cq_2 + n)$

$= C (k_3 + q_1n + q_2m) + mn$

$= C k_4 + mn$

이므로, $A^B$를 $C$로 나눈 나머지는 $mn$을 $C$로 나눈 나머지와 같다.

이때, $m = A^{b_1} \bmod C, \space n = A^{b_2} \bmod C$ 이므로,

$$\therefore A^{b_1 + b_2} \bmod C = \{ (A^{b_1} \bmod C)(A^{b_2} \bmod C) \} \bmod C$$

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

size_t ModularPow(int a, int b, int mod)
{
	if (b == 1)
		return a;

	size_t n = ModularPow(a, b / 2, mod);
	return (b % 2 ? n * n % mod * a : n * n) % mod;
}

int main()
{
	int A, B, C;
	cin >> A >> B >> C;
	cout << ModularPow(A % C, B, C) << "\n";
	return 0;
}

 

실행 결과