[JAVA] 백준 1629 곱셈

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

1629번: 곱셈

 

- 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램

 

 

문제 풀이 

 

분할 정복을 이용한 거듭제곱 

[백준] 1629번 : 곱셈 - JAVA [자바] (tistory.com)

 

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

분할정복을 이용한 거듭제곱 (tistory.com)

 

 

분할정복을 이용한 거듭제곱

- 임의의 수 C의 n제곱을 구할 때, C를 n번 곱하는 대신 n을 2의 거듭제곱의 합이나 절반으로 나누어 C의 제곱을 반복하여 곱하는 방법 

- 이 방법은 O(n)의 시간 복잡도를 갖는 일반적인 거듭제곱 연산보다 O(logn)의 시간 복잡도로 빠르게 계산이 가능하다.

 

- 지수가 짝수인 경우 n/2로 분할하여 곱으로 계산

ex) 11의 12 제곱은 11의 6제곱과 11의 6제곱의 곱을 통하여 구할 수 있음 

 

- 지수가 홀수인 경우 밑을 한번 더 곱해주면 됨

ex) 11의 13제곱은 13을 반으로 나누고 내림한 수인 6제곱 * 6제곱* 밑 술르 통해서 구할 수 있음

 

 

모듈러 성질 

(a*b)%c = (a%c*b%c)%c

 

정답 

 

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

public class Main {
	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());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        C = Long.parseLong(st.nextToken());
        
        bw.write(pow(A,B)%C+"");
        bw.flush();
        bw.close();
        
    }
    
    static long pow(long A, long n)
    {
        if(n==1)
        {
        	return A%C;
        }
        
        long temp = pow(A,n/2);
        
        if(n%2 == 1)
        {
        	return (temp*temp%C)*A%C;
        }
        else
        {
        	return temp*temp%C;
        }
    }
}