[BOJ]1629. 곱셈

문제

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

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 

10 11 12

예제 출력 

4

---

풀이

거듭제곱을 빨리하는 방법은 재귀를 사용하는 것이다.

예를 들어 생각해보자

A^7 = A^6 * A

A^6 = (A^3)^2

...

즉, 아래와 같다. 

조건	pow(a,n)
n=0 일 때	1
n이 짝수 일 때	pow(a,n/2)2
n이 홀수 일 때	pow(a,n/2)2∗a

코드

package baekjoon.dq;

import java.util.Scanner;

public class B1629 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        long result = pow(a, b, c);
        System.out.println(result);
    }

    static long pow(int a, int b, int c) {
        long re = 1;
        if (b == 0)
            return 1;
        if (b == 1)
            return a % c;
        if (b % 2 == 0) {
            long tmp = pow(a, b / 2, c);
            return (tmp * tmp) % c;
        } else {
            long tmp = pow(a, b - 1, c);
            return a * tmp % c;
        }
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1629

 

풀이 참고자료 출처 : https://onsil-thegreenhouse.github.io/programming/problem/2018/03/29/problem_math_power/