백준 1629 곱셈 [C++]

작성일 | In |

Problem : 곱셈

유형 : 재귀

문제 해석

  • 자연수 A 를 B 제곱하고 MOD C 를 취한 결과 값을 구하여라.
  • B는 21억 까지 가능하다.
    • naive 한 구현으로는 O(21억) 이라서 시간초과가 난다.
    • O(N) 이하의 방법을 찾아야 한다.

해결 전략

  • 거듭제곱의 특징을 파악한다.
    • 2^4 은 (2^2)^2 로 표현 할 수 있다.
    • 2^8 은 (((2^2)^2)^2) 로 표현 할 수 있다.
      • 8번 해야할 작업을 3번으로 줄일 수 있다.
      • log(N) 의 수행속도로 만들 수 있다.

설계, 구현

  • b가 1인 경우에 대해서 baseCondition 을 잡는다.
  • 거듭제곱의 수(b)가 짝수 인경우, b/2 만큼의 거듭제곱을 구한뒤 다시 2제곱한다.
  • 그렇지 않은경우에는 b를 한번 더 곱해준다.
    • 2^5 = (2^2)^2 * 2

주의할 점

  • base condition 에서도 mod 연산을 취해주어야 하는걸 잊지말자

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#define ll long long\

using namespace std;

ll getPow(ll a, ll b, ll c) {
    if (b == 1) return a % c;

    ll tmp = getPow(a, b / 2, c) % c;
    ll ret = tmp * tmp % c;

    if (b % 2 == 0) {
        return ret;
    }
    else {
        return ret * a % c;
    }
}

void solve() {
    ll a, b, c;
    cin >> a >> b >> c;
    cout << getPow(a, b, c) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    solve();

    return 0;
}

피드백

  • 작은 경우에 대해서도 생각해보자.