1629번. 곱셈

 

아이디어

시간 제한이 0.5 초이고 B 는 최대 2,147,483,647 이기 때문에 직접 모든 반복 연산을 수행하는 것은 시간 초과가 나게 된다.

 

지수법칙과 모듈러 연산을 이용해서 시간 초과는 물론 타입에 따른 오버플로우를 방지하는 방법을 사용하면 문제를 해결할 수 있다.

 

지수법칙에 의하면 a ^ b  = a ^ (b / 2) * a ^ (b / 2) 이고 모듈러 연산에 의하면 (A * B) % C = ((A % C) * (B % C)) % C 이므로 이를 통해 굳이 b번 반복 연산을 수행하지 않아도 원하는 값을 얻을 수 있게 되는 것이다.

 

 

풀이코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        System.out.println(calculator(A, B, C));
    }

    public static long calculator(int a, int b, int c) {
        if (b == 0) return 1;

        long half = calculator(a, b / 2, c);
        long result = ((half % c) * (half % c)) % c;

        return b % 2 == 0 ? result : ((result % c) * (a % c)) % c;
    }
}