[알고리즘] Java / Baekjoon / 곱셈 / 1629

[알고리즘] Java / Baekjoon / 곱셈 / 1629

문제

문제 링크

접근 방식

분할정복을 이용하여 기존 O(N) 을 O(logN)으로 줄인다

각 계산마다 C를 나누어 준다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_1629 {

	static long A,B,C;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		A = Long.parseLong(st.nextToken());
		B = Long.parseLong(st.nextToken());
		C = Long.parseLong(st.nextToken());
		
		A = A % C;
		
		System.out.println(divide(A,B));
		
	}
	
	public static long divide(long x, long y) {
//		System.out.println("x:"+x + " y:"+y);
		
		if(y==1) return A;
		
		long tmp = divide(x,y/2) % C;
		
		
		if(y % 2 == 1) return ((A*tmp) % C )*tmp % C;
		else return (tmp*tmp)%C;
		
	
	}

}