[백준 1629] 곱셈 (JAVA)

백준 1629번 문제 -  곱셈

1629번: 곱셈

---

문제 분석 

 

---

 

해결 포인트

 

• 시간 부족 문제
• 분할 정복 사용
• 지수법칙 : 2 ^ 4 = 2 ^ 2 * 2 ^ 2 

• 모듈러 성질 : 2 ^ 4 % c = ((2 ^ 2) % c * (2 ^ 2) % c 

 

참고 : https://st-lab.tistory.com/237

[백준] 1629번 : 곱셈 - 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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        long sum = pow(a, b, c) % c;

        bw.write(sum + "\n");
        bw.flush();
        bw.close();
    }

    public static long pow(int a, int b, int c) {
        if(b == 1)
            return a % c;

        long result = pow(a, b/2, c);
        if(b % 2 == 0) {
            return result * result % c;
        }
        return ((result * result) % c) * a % c;
    }
}