백준 1629 - 곱셈

🔐 백준 1629 - 곱셈

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

🔑 풀이

시간 제한과 수의 범위에 유의해야 한다. 자연수 A, B, C의 범위가 int형 범위 내의 숫자이지만,

A를 B번 곱하게 되면 int형보다 훨씬 수가 커지게 된다. 또한, B의 범위가 매우 클 수 있기에

A를 B번 곱하는 행위는 0.5초 내에 처리되지 않을 것이다.

이 문제를 풀기 위해서는 다음의 특성들을 떠올려야 한다.

거듭제곱 성질

x가 홀수인 경우 :    $ x^y = x^{y/2} \times x^{y/2 + 1} $
x가 짝수인 경우 :    $ x^y = x^{y/2} \times x^y $

모듈러 연산의 성질

$ (a \times b)\; mod\; m = ((a\; mod\; m) \times (b\; mod\; m))\; mod\; m $ $ (a + b)\; mod\; m = ((a\; mod\; m) + (b\; mod\; m))\; mod\; m $

응용    b가 짝수라고 가정 (b = 2k)

$ a^b \; mod\; m = a^{2k}\; mod\; m = (a^k \times a^k)\; mod\; m = (a^k \; mod\; m)^2 \; mod\; m $

위의 특성들을 사용하여 문제를 해결할 수 있다.

ll POW(ll b) {
    if (b == 1) return a % m;
    ll val = POW(b/2);
    val = val * val % m;
    if (b%2 == 0) return val;
    return val * a % m;
}

b를 절반으로 줄이면서 b가 1이 될때까지 재귀적으로 POW 함수를 호출한다.

b가 홀수일 때와 짝수일 때의 경우가 다르므로, 이 점까지 해결해주어야 한다.

예제

A = 10, B = 11, C = 12

1. POW(10, 11, 12) 호출

2. b == 1이 아니므로, POW(10, 5, 12) 호출

3. b == 1이 아니므로, POW(10, 2, 12) 호출

4. b == 1이 아니므로, POW(10, 1, 12) 호출

5. b == 1이므로, a % m 을 반환하여 10 % 12 = 10이 된다.

6. POW(10, 2, 12)로 돌아와서 (val = 10) val * val % m 계산 = 10 * 10 % 12 = 4가 된다.
   (b % 2 == 0 이므로 4 반환)

7. POW(10, 5, 12)로 돌아와서 (val = 4) val * val % m 계산 = 4 * 4 % 12 = 4가 된다.
   (b % 2 == 1 이므로 4 * a % m 계산하여 4 * 10 % 12 = 4 반환)

8. POW(10, 11, 12)로 돌아와서 (val = 4) val * val % m 계산 = 4 * 4 % 12 = 4가 된다.
   (b % 2 == 1 이므로 4 * a % m 계산하여 4 * 10 % 12 = 4 반환)

결과적으로, POW(10, 11, 12)는 4를 반환한다.

🧩 코드