[백준] 1629 : 곱셈 JAVA 풀이

import java.io.*;
import java.util.*;
public class Main{
    static int C;
    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());
        C = Integer.parseInt(st.nextToken());
        
        System.out.println(pow(A, B));
    }
    
    static long pow(int a, int b){
        
        // b가 1인 경우 a%C를 반환
        if(b==1){
            return a % C;
        }
        
        // b가 1이 아닌 경우 분할해서 재귀
        long tmp = pow(a, b/2);
        
        // b가 홀수일 경우
        if(b%2==1){
        	/*
            	(tmp*tmp*A)%C를 반환해야 하는데
                이때 tmp*tmp*A가 long의 범위를 넘어가게 됨
                이 문제를 해결하기 위해서 모듈러 합동 공식을 사용함
            
            	(a * b) % c = (a % c * b % c) % c
                
            */
        
        
            return (tmp*tmp%C)*a%C;
        }
        
        // b가 짝수인 경우는 분할한 걸 통합한 뒤에 %C를 한 값을 반환
        return tmp*tmp%C;
    }
    
}