[Java] 백준 BOJ / 1629번: 곱셈

곱셈

문제

---

문제 설명

문제를 보자마자 알 수 있겠지만 일반적인 방법으로 곱해서는 절대 풀 수 없는 문제이다. 시간 제한도 0.5초 이고 숫자도 int 의 최대범위 이하의 자연수로 되어있다.

일단 우리가 구해야하는거는 ( A ^ B mod C ) 이다.

한참 생각해봤는데 기본적인 지식이 없이는 풀 수 없을 것 같아서 여러 모듈러 연산에 대해서 찾아보았다.

그러던 중 백준10430번 나머지 문제에 대해서 정리해둔 블로그를 찾았다.

여기서 봐야할 것은 아래와 같다.

( A * B ) % C = ( A % C * B % C) % C

이 식을 활용해서 이 문제를 풀 수 있다.

지수를 모두 반으로 나눠서 쪼개서 풀면 된다.

---

코드

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

public class Main_1629 {
    static long a, b, c;
    static int result;
    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(a,b));
    }

    private static long pow(Long a, Long exp) {
        if (exp == 1) {
            return a % c;
        }

        long tmp = pow(a, exp / 2);

        if (exp % 2 == 1) {
            return (tmp * tmp % c) * a % c;
        }
        return tmp * tmp % c;
    }
}

---

코드 설명

생각해야 할 점이 있었는데 모듈러 연산을 언제 해야되는지가 중요하다.

만약 아래 코드처럼 하면 틀리게 된다.

if(exp % 2 == 1) {
		return tmp * tmp * a % c;
	}

만약 이렇게 한다면 temp * temp * A 부분이 long의 최대 범위를 넘어가면서 잘못된 값으로 계산이 되기 때문에 우리는 위에서 언급했던 모듈러의 합동 공식을 알고 있어야 한다.

따라서 long의 최대 범위를 넘어가지 않게 하기 위해서 아래와 같은 코드로 대체하면 문제를 풀 수 있다.

if (exp % 2 == 1) {
         return (tmp * tmp % c) * a % c;
        }