[Java+Python]1629번, 곱셈

목차

 

분할 정복 단계

 

[Java+Python]2630번, 색종이 만들기

[Java+Python]1992번, 쿼드 트리

[Java+Python]1780번, 종이의 개수

[Java+Python]11401번, 이항 계수 3

[Java+Python]2740번, 행렬 곱셈

[Java+Python]10830번, 행렬 제곱

[Java+Python]11444번, 피보나치 수 6

[Java+Python]6549번, 히스토그램에서 가장 큰 직사각형

 

문제

 

자연수 A를 B번 곱한 수를 알고 싶다. 

단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 A, B, C가 빈칸을 사이에 두고 순서대로 주어진다. 

A, B, C는 모두 2,147,483,647 이하의 자연수이다.

 

출력

 

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

 

풀이

 

int 자료형을 넘어서는 결과를 가진 큰 수의 거듭제곱을 빠르게 구하는 문제이다.

 

분할정복을 이용해 주어진 지수를 반으로 나누며 자기 자신을 재귀호출한 뒤

 

가장 작은 단위에 도착하면 결과를 합치며 답을 구하는 식으로 구현하면 된다.

 

문제를 풀고 구현하는 알고리즘은 다음과 같다.

 

1. a, b, c를 입력받는다. 각 변수는 최댓값이 2,147,483,647 이하의 자연수, 즉 int 범위의 자료형이다.
2. 재귀함수 pow()를 출력해 그 결괏값을 출력한다. 해당 함수의 작동 방식은 아래와 같다.
   
   
   1. 지수가 1이 될 때까지 거듭제곱의 지수를 반으로 나누어 문제를 분할해 자기 자신을 아래와 같이 호출한다.
      long temp = pow(a, exponent / 2, mod);
      여기서 temp는 int 범위를 넘어설 수 있기 때문에 long으로 선언해주어야 한다.
   2. 지수가 1이 된 경우 병합과정이 시작된다. 각 단계에서 지수가 짝수인 경우엔 $temp^2 (\mod c)$ 를,
      지수가 홀수인 경우엔 $((temp^2 (\mod c)) \times a) (\mod c)$ 를 계산한다.

 

Java

 

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

public class Prob1629 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		System.out.println(pow(a, b, c));
	}

	private static long pow(int a, int exponent, int mod) {

		if (exponent == 1) {
			return a % mod;
		}

		long temp = pow(a, exponent / 2, mod);

		if (exponent % 2 == 0) {
			return (temp * temp) % mod;
		} else {
			return (((temp * temp) % mod) * a) % mod;
		}
	}
}

 

Python

 

import sys

a, b, c = map(int, sys.stdin.readline().rstrip().split())


def pow(a, exponent, mod):
    if exponent == 1:
        return a % mod

    temp = pow(a, exponent // 2, mod)

    if exponent % 2 == 0:
        return (temp**2) % mod
    else:
        return (((temp**2) % mod) * a) % mod


print(pow(a, b, c))

 

Performance