[Java] 백준 1629 : 곱셈

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

1629번: 곱셈

---

 

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 가장 대표적인 예는 병합정렬(Merge Sort)이다.

import java.util.*;
public class Main {

	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)%C);
		
	}// main()
	
	static long pow(long A, long B,long C) {
		if(B==0) {
			return 1;
		}else if(B==1) {
			return A;
		} else if (B % 2 == 0) { //짝수 지수
            long n = pow(A, B / 2, C) % C;
            return (n * n) % C;
        } else { //홀수 지수
            long n = pow(A, B / 2, C) %C;
            return (((n * n) % C) * A) % C;
        }
	}//pow()
	
}// class Main