[BaekJoon] 1629번 - 곱셈 [Java][C++]

문제 링크

---

1. 아이디어

간단하게 $A^B \ (\mathrm{mod}\ C)$ 를 구해야 하는 문제다. B의 크기가 최대 2,147,483,647이어서 반복적으로 곱하는 방식으로는 O(N)의 시간 복잡도가 소요돼서 해결할 수 없다. O(N) 보다 빠른 알고리즘으로 해결해야 하는데 O(log N)의 시간 복잡도로 거듭제곱을 계산할 수 있는 이진 거듭제곱이라는 테크닉을 활용하면 해결할 수 있다. 모듈러 연산은 곱셈에 대한 분배가 가능하므로 연산마다 나머지만 취했다.

---

2. 코드

1. 반복문을 활용한 이진 거듭제곱 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        System.out.println(modPow(a, b, c));
    }

    static long modPow(long a, long b, long c) {
        long res = 1;

        while (b > 0) {
            if ((b & 1) > 0) res = res * a % c;
            a = a * a % c;
            b >>= 1;
        }

        return res;
    }
}

2. 반복문을 활용한 이진 거듭제곱 [C++]

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

long long modpow(long long a, long long b, long long c) {
    long long res = 1;

    while (b > 0) {
        if (b & 1) res = res * a % c;
        a = a * a % c;
        b >>= 1;
    }

    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int a, b, c;
    cin >> a >> b >> c;
    cout << modpow(a, b, c);
}

3. 재귀를 활용한 이진 거듭제곱 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        System.out.println(modPow(a, b, c));
    }

    static long modPow(long a, long b, long c) {
        if (b == 0) return 1;

        long half = modPow(a, b / 2, c);
        if (b % 2 == 1) {
            return half * half % c * a % c;
        } else {
            return half * half % c;
        }
    }
}

4. 재귀를 활용한 이진 거듭제곱 [C++]

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

long long modpow(long long a, long long b, long long c) {
    if (b == 0) return 1;

    long long half = modpow(a, b / 2, c);
    if (b % 2) {
        return half * half % c * a % c;
    } else {
        return half * half % c;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int a, b, c;
    cin >> a >> b >> c;
    cout << modpow(a, b, c);
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---