[BOJ] 백준 11819번: The Shortest does not Mean the Simplest

문제

Your are given integer numbers A, B and C. Output the remainder of division AB (B-th power of A) by C .

입력

The only line of the input file contains three integers: A, B, C (1 ≤ A,B,C ≤ 1018). Numbers are separated by spaces.

 

풀이

이 문제는 반복문을 통해 해결하려고 하면 B의 범위가 10^18까지 때문에 시간초과가 나게 됩니다. 따라서 분할정복을 통해 접근해야합니다.

처음에 10^18범위인 것을 보고 long으로 잡고 해결하려고 시도했으나 중간중간 rest*rest%C*(A%C)라는 조건에서 long의 범위를 벗어나는 것이 확인되었습니다. 따라서 BigInteger를 통해 범위 조건없이 해결하였습니다. 자바가 아닌 파이썬이라면 숫자의 범위에 신경쓰지않고 바로 해결할 수 있던 문제였습니다.

코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static BigInteger A, B, C;

    private static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        A = new BigInteger(st.nextToken());
        B = new BigInteger(st.nextToken());
        C = new BigInteger(st.nextToken());
    }

    static BigInteger process(BigInteger A, BigInteger B, BigInteger C) {
        if(B.equals(BigInteger.ZERO)) return BigInteger.ONE;
        else if(B.equals(BigInteger.ONE)) return A;
        else{
            BigInteger value = process(A, B.divide(BigInteger.TWO), C);
            if(B.remainder(BigInteger.TWO).equals(BigInteger.ZERO)) return calc(value, value);
            else return calc(calc(value, value),A);
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        System.out.println(process(A.mod(C), B, C));
    }

    public static BigInteger calc(BigInteger n1, BigInteger n2){
        return n1.multiply(n2).mod(C);
    }
}

 

<출처>

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