[Java] 백준 1629번 : 곱셈

문제

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

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1

10 11 12

예제 출력 1

4

 

소스코드

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

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static long A, B, C, result=1;
	
	public static void main(String[] args) throws IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(bf.readLine());
		A=Long.parseLong(st.nextToken());
		B=Long.parseLong(st.nextToken());
		C=Long.parseLong(st.nextToken());
		
		result=multiple(A, B);
		System.out.println(result);
	}

	public static long multiple(long a, long b) {
		if(b==1) return a%C;
		
		long mid=multiple(a, b/2);
		mid=mid*mid%C;
		if(b%2==0) return mid;
		else return mid*a%C;
	}
}

1. A, B, C 자체가  2,147,483,647 이하로 매우 큰 수가 들어갈 수 있기 때문에 계산할 때마다 매번 나머지 연산을 수행해주어야 하며, long 타입을 이용해야 합니다.

2. 실제로 B번 연산을 하게 되면 시간 초과가 발생하므로, 분할 정복을 이용하여 절반만 계산해도 결과를 얻을 수 있도록 했습니다.