[BOJ] 1629 곱셈

분할 정복

풀이

• A,B,C의 범위가 2,147,483,647 이하의 자연수 라서, 냅다 곱하고 나누고 하면 메모리초과 난다.
• 모듈러 성질, 지수 법칙을 이용하면 된다.
  • 모듈러 성질 : (a*b) % C = (a%c * b%c) % c
  • 지수 법칙 :a^(n+m) = a^n*a*m
• 그리고 중요한 것, B(=지수)가 홀수인지 짝수인지에 따라 다르게 return 한다.
• 또 중요한 것, long 타입으로 a,b,c를 받아야 에러가 안터진다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());
        long C = Integer.parseInt(st.nextToken());
        // (A^B)%C
        System.out.println(cur(A,B,C));
    }
    private static long cur(long a,long b,long c){
        // b가 1이 되면 a^1 이므로 return a%c
        if(b==1){
            return a%c;
        }
        long res = cur(a,b/2,c);
        if(b%2==1) return (res*res%c)*a%c;
        return res*res%c;
    }
}