[백준] 1629번: 곱셈 -JAVA

문제 바로가기 > 1629번: 곱셈

---

 

모듈러 성질과 분할 정복을 이용해 풀 수 있다.

 

분할 정복

아래와 같이 계속해서 지수를 2로 나누어서 분할정복을 계속해서 해나간다. 

 

 

이때, 지수가 홀수일 때는 마지막에 밑을 곱해주면 된다.

 

 

 

 

그럼 예제의 A = 10, B = 11 을 위 처럼 적용해보면 이렇다.

 

위 과정에서 지수는 절반으로 나누기 때문에 각 레벨에서 나뉜 두 지수를 모두 탐색할 필요없이 한 번만 구하면 된다.

이를 코드로 옮겨보면 이렇게 짤 수 있다.

 

아래의 모듈러 공식을 이용해서 long이 오버플로우가 되지 않도록 계속해서 C의 나머지를 구해야 한다.

 

 

 

전체 코드

import java.util.Scanner;

public class _1629 {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        long a=sc.nextInt();
        long b=sc.nextInt();
        long c=sc.nextInt();
        System.out.println(pow(a,b,c));
    }
    public static long pow(long a, long b, long c){ //a^b를 c로 나눈 나머지 값
        if(b==1)
            return a%c;

        long mul=pow(a, b/2, c);

        if(b%2==1)
            return (mul*mul%c)*a%c;

        return mul*mul%c;
    }
}