[Java] 백준 1629번 곱셈 - 분할정복법

분할정복법

신기하다.

 

Integer의 max value로 세번만 곱해져도 long범위 넘어갈수도 있으니

long의 범위를 넘기지 않기 위해 수시로 모듈러연산을 해주어야한다!

 

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

좋은 설명 감사합니다

[백준] 1629번 : 곱셈 - JAVA [자바]

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

public class s1_1629 {
    static long a;
    static long c;
    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());

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

        long ans = daq(b);

        bw.write(String.valueOf(ans));

        bw.flush();
        bw.close();
    }

    //daq(k) = Math.pow(a, k) mod c 를 분할정복하는 코드
    public static long daq(long k){
        if (k == 1){
            return (a % c);
        }
        else{
            long temp = daq(k / 2);
            if ((k & 1) == 0){
                return temp * temp % c;
            }
            else{
                return ((temp * temp % c) * (a % c)) % c;
            }
        }
    }
}