[백준] 곱셈

🔗 문제 보기 - [백준] 곱셈

📖 문제

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

✍ 입력

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

📄 출력

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

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class Main {  
    static long a, b, c;  
  
    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 b) {
        if(b == 1) {  
            return a % c;  
        }
        
        long val = pow(a, b / 2);  
  
        // 홀수일 때 모듈러 연산이 필요하다
        if(b % 2 == 1) return (val * val % c) * a % c;  

		//짝 수 일 때
        return val * val % c;  
    }  
}

🧩 코드풀이

처음에 단순히 Math.pow를 쓰면 되는 문제인가 생각하며 접근했지만 시간초과로 인해 계속 실패 했고, 이후에 찾아보니 지수법칙과 모듈러 성질을 적용하여 풀면서 분할정복 알고리즘을 이용하여 시간을 단축시키고 해결하는 문제였습니다.

1. 지수법칙
   -> $a^{n+m} = a^n * a^m$

2. 모듈러의 성질
   -> (a ${*}$ b) % c = (a % c ${*}$ b % c) % c

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