[백준] 1629번 Silver 1 곱셈, Java 코드

solved.ac의 Class 4 문제 중 곱셈 문제이다.

자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 문제이다.

 

여기서 생각을 해야 하는 것은 그냥 (A^B)% C를 구했다가는 시간 초과가 발생한다는 점이다.

그렇다면 어떻게 구해야 하는가?

 

모듈러 산술 연산의 특징
(a * b) % c = (a % c * b % c) % c을 이용해 구해볼 것이다.

 

예를 들어 A^6인 경우,

A^6 = A^3 * A^3으로 나누고,

A^3 = A ^1 *  A^1  *  A로 또 나누어 구한다.

즉, 재귀의 방식으로 구할 것이다.

 

문제를 풀 때, 참고했던 블로그는 아래와 같다.

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

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

 

 

해결했던 코드는 다음과 같다.

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

public class Main {
	
	public static long c;

	public static void main(String[] args) throws IOException {
		BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
		String ip[] = buf.readLine().split(" ");
		long a = Long.parseLong(ip[0]);
		long b = Long.parseLong(ip[1]);
		c = Long.parseLong(ip[2]);
		
		System.out.println(pow(a, b));
	}
	
	public static long pow(long num, long exp) {
		
		//지수가 1일 경우에는 그냥 c의 나머지 연산을 하면 됨.
		if (exp == 1) { return num % c; }
		
		// 지수의 절반에 해당되는 값을 이용해 num^(exp/2)를 구한다.
		long temp = pow(num, exp/2);
		
		// 홀수인 경우에는 추가로 tmp 값을 한번 더 곱해줘야 한다.
		// num^7 = num^3 * num^3 * num이기 때문이다.
		
		/**
		 * 모듈러 산술 연산의 특징
		(a * b) % c = (a % c * b % c) % c 이므로,
		(temp*temp*num)%c = ((temp * (temp*1) % c) * (num % c)) % c
	     = (((temp * temp % c) % c) * (num % c)) % c
	     = ((temp * temp % c) * num) % c
		**/
		
		if (exp % 2 == 1) {
			return (temp*temp % c) * num % c;
		}
		
		return temp * temp % c;
	}
}