[BOJ/JAVA] 백준 1629 : 곱셈 (자바)

문제 정보

  문제명   - 곱셈
  난이도   - 실버 I
문제 번호 - 1629번

---

문제 링크

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

1629번: 곱셈

---

문제

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

---

입력

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

---

출력

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

---

예제 입력/출력

예제 입력	예제 출력
10 11 12	4

---

알고리즘 분류

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

---

소스코드

package Lv2_Silver;

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

/**
 * @author HanHoon
 * @category 수학, 분할정복을 이용한 거듭제곱
 * https://www.acmicpc.net/problem/1629
 */
public class BOJ_S1_1629_곱셈 {
    public static long pow(long A, long B, long C){
        if(B == 1)
            return A%C;

        // B번 거듭제곱하지 않고 절반씩 계산해서 분할정복한다.
        long tmp = pow(A, B/2, C);

        long result = tmp*tmp%C;

        if(B%2 == 0)
            return result;

        return result*A%C;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder str = new StringBuilder();

        // A, B, C
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        long C = Long.parseLong(st.nextToken());

        str.append(pow(A,B,C));

        System.out.print(str);
        br.close();
    }
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---