Baekjoon 1629 곱셈 JAVA

1629번: 곱셈

문제

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

입력

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

출력

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

풀이

입력되는 값은 Integer의 최대값이다. 한번의 연산에서라도 Int의 범위를 넘으면 안되기에 long을 이용하여 중간에 연산되는 값을 연산후(int의 범위를 넘을수도 있음), c로 나눈 나머지를 이용하였다(int의 범위 안에 들어옴).

코드

import java.util.Scanner;

public class Main {
	static long f(long a, long b,long c) {
		if(b==1)
			return a;
		else {
			long x=f(a,b/2,c);
			if(b%2==0)
				return ((x*x)%c)%c;
			else
				return ((x*x)%c*a)%c;
		}
	}
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		long a=sc.nextLong(), b=sc.nextLong(), c=sc.nextLong();
		System.out.println(f(a,b,c)%c);
	}
}