백준 1629: 곱셈(java)

문제

---

풀이

 

분할 정복(Divide and Conquer)으로 풀이하는 문제이다.

기본적으로 \(x^{n}=(x^{\frac{n}{2}})^2=(x^2)^{\frac{n}{2}}\)임을 이용하며, 더 자세히는 n이 홀수일 때 \(x^{n}=(x^{2})^{\frac{n}{2}}\), 짝수일 때 \(x*{n}= x\times{(x^{2})^{\frac{n-1}{2}}}\)이다. 

 

이를 바탕으로 \(x^{n}\)을 구하는 pow(x, n) 함수를 아래와 같이 작성할 수 있다.

int pow(int x, int n){
	if(n==0){	//x의 0제곱은 1
    	return 1;
    }
    else if(n%2==0){	//n이 짝수일 때
    	return pow(x*x, n/2);
    }
    else{	//n이 홀수일 때
    	return x*pow(x*x, (n-1)/2);
    }
}

 

모듈러 연산에서 

\((a\times{b})mod\;c=(a\;mod\;c\times{b\;mod\;c})\;mod\;c\) 이므로, 오버플로우 없이 A를 B번 곱한 수를 C로 나누려면 pow()를 아래와 같이 수정한다.

long pow(long base, long ex) {
	long temp;
	
	if(ex==0) {
		return 1;
	}
	else if(ex%2==0) {
		temp=pow(base*base%C, ex/2);
	}
	else {
		temp=base*(pow(base*base%C, (ex-1)/2));
	}
	return temp%C;
}

 

전체 코드

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

public class Main {
	static long C;
	
	static long pow(long base, long ex) {
		long temp;
		
		if(ex==0) {
			return 1;
		}
		else if(ex%2==0) {
			temp=pow(base*base%C, ex/2);
		}
		else {
			temp=base*(pow(base*base%C, (ex-1)/2));
		}
		return temp%C;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		long A=Long.parseLong(st.nextToken());
		long B=Long.parseLong(st.nextToken());
		C=Long.parseLong(st.nextToken());
		
		long res=pow(A, B);
		
		System.out.println(res);
	}
}