[Python / Java] 백준 1629번 - 곱셈

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

1629번: 곱셈

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 수학
 - 분할 정복을 이용한 거듭제곱

문제

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

입력

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

출력

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

 

---

 

단순한 문제이다.

 

A**B%C

를 구하는 문제다.

 

하지만 이걸 그대로 제출하면 시간초과가 발생한다.

 

2,147,483,647 까지의 자연수가 올 수 있으며 이는 보통 INT의 최대한계점이다.

 

https://hbj0209.tistory.com/43

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

 

https://st-lab.tistory.com/237

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

거듭제곱을 분할정복 하는 걸 처음 알았다.

 

우선 제곱의 성질과

나머지의 성질을 보자.

 

 

위의 식을 이용하면 분할 정복된 거듭제곱을 사용할 수 있다.

 

예시에 나온 10 11 12를 예로 들면

 

A = 10, B = 11, C = 12

X = A**B
X = 10**11
X = (10 * 5) * (10 * 5) * 10
X = (10 * 2) * (10 * 2) * 10 * (10 * 2) * (10 * 2) * 10 * 10
X = 10 * 10 * ... * 10

뭐 알고 보면 단순하지만 위와 같이 나타낼 수 있다.

 

저기에서 나머지의 성질을 사용하면

 

A = 10, B = 11, C = 12

X = (A**B)%C
X = (10**11)%12
X = (10 * 5)%12 * (10 * 5)%12 * 10%12
X = (10 * 2)%12 * (10 * 2)%12 * 10 %12* (10 * 2)%12 * (10 * 2)%12 * 10%12 * 10%12
X = 10%12 * 10%12 * ... * 10%12

이제 이를 코드로 작성하면 끝이다.

 

 

Python

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

def foo(b):
    if b == 1:
        return a % c
    else:
        x = foo(b//2)
        if b % 2 == 0:
            return x*x%c
        else:
            return x*x*a%c
    
print(foo(b))

 

Java

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

public class Main {
	static long a;
	static long b;
	static long 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());
		
		System.out.println(pow(b));
	}
	private static long pow(long b2) {
		if(b2 == 1) {
			return a%c;
		}
		else {
			long x = pow(b2/2);
			if( b2 % 2 == 0) {
				return x * x % c;
			} else {
				return (x * x % c) * a % c;
			}
		}
	}
}

Java의 경우엔

 

Int 타입에 수를 다 담을 수 없기 때문에 long으로 선언해 준다.