BOJ01629 곱셈

https://www.acmicpc.net/problem/1629 (opens new window)

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성한다.

지수 법칙

a^{n + m} = aⁿ * a^m

모듈러 성질

모듈러 연산 (opens new window)

제출 코드

// a^b
private static long pow(long a, long b) {
    if (b == 1) { // (1)
        return a % c;
    }

    long half = pow(a, b / 2); // (2)

    if (b % 2 == 0) { // (3)
        return half * half % c;
    }
    return (half * half % c) * a % c; // (4)
}

(1) 지수가 1인 경우 a^1
(2) 지수의 절반을 구한다.
(3) 지수가 짝수이면 a^4 = a^2 * a^2
(4) 지수가 홀수이면 a^5 = a^2 * a^2 * a

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ1629 {

    private static long c;

    // a^b
    private static long pow(long a, long b) {
        if (b == 1) {
            return a % c;
        }

        long half = pow(a, b / 2);

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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        long a = scanner.nextInt();
        long b = scanner.nextInt();
        c = scanner.nextInt();

        System.out.println(pow(a, b));
    }
}

References

[백준] 1629번 : 곱셈 - JAVA [자바] (opens new window)

#BOJ #수학 #분할 정복을 이용한 거듭제곱