[BAEKJOON 백준] 1629 곱셈 (JAVA)

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

1629번: 곱셈

 

문제

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

입력

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

출력

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

 

 

아래와 같이 pow를 새롭게 정의를 해주어 문제를 해결했습니다.

 

위의 문제의 경우, A, B, C의 수가 크기때문에 그냥 pow를 할 경우, 숫자를 초과하게 됩니다.

 

X*Y=Z 일 경우, ZmodC=(XmodC * YmodC) modC 를 활용을 해서 아래와 같이 문제를 해결했습니다.

 

 

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

public class Main {
	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());
		long C = Long.parseLong(st.nextToken());
		System.out.println(pow(A, B, C));
	}

	private static long pow(long a, long b, long c) {
		if (b == 1) {
			return a % c;
		}
		long temp = pow(a, b / 2, c);
		if (b % 2 == 1) {
			return (temp * temp % c) * a % c;
		}
		return temp * temp % c;
	}
}

 

그리고 위의 코드를 좀더 간단하게 정의가 되있는 BigInteger를 사용하게 되면 위의 코드를 간단하게 줄일 수도 있습니다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		BigInteger A = new BigInteger(st.nextToken());
		BigInteger B = new BigInteger(st.nextToken());
		BigInteger C = new BigInteger(st.nextToken());
		System.out.println(A.modPow(B, C));
	}
}