[백준 1629] 곱셈

 

 

x제곱 하기에 수가 너무 크므로 분할하는 방법으로 접근해야 한다.

B를 2로 계속 나누어 최대한 작은 수로 만들고 매 연산마다

 

(A*B)%C = ((A%C)*(B%C))%C

 

를 이용하여 수를 더 작게 만들어준다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        
        long ans = 1;
        long mul = a % c;
        
        while(b>0) {
            if(b%2 == 1) {
                ans *= mul;
                ans %= c;
            }
            mul = ((mul % c) * (mul % c)) % c;
            b /= 2;
        }
        System.out.println(ans);
    }
}