Baekjoon1629: 곱셈

곱셈

0.5 초 (추가 시간 없음)

128 MB

51498

13513

9899

25.586%

문제

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

입력

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

출력

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

풀이

제한 시간은 0.5초이며 A와 B와 C의 범위는 정수형의 범위이다.

 

모듈러 연산을 사용한 방법?

A = 10, B = 11, C = 12 라고 가정하면 다음처럼 분할해 모듈러 연산을 활용할 수 있다.

10의 11승 = (10의 5승)x(10의 5승)x10

(10의 5승)x(10의 5승)x10 = {(10의 2승)x(10의 2승)x10} x{(10의 2승)x(10의 2승)x10}x10

문제점

A = 2,147,483,646, B = 2,147,483,646, C = 2,147,483,647 일 때 문제가 발생한다

정수형의 범위를 넘어갈 수 있으므로 연산마다 C로 계속 나눠줘야한다

import java.util.*;
public class Main {
	static long C;
	static long modular(long A, long B) {
		if(B==1) return A%C;
		long half = modular(A,B/2)%C;
		if(B%2==0) {
			return half*half%C;
		} else {
			return (((half*half)%C)*A)%C;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		long A = sc.nextLong();
		long B = sc.nextLong();
		C= sc.nextLong();
		System.out.println(modular(A,B));
}}