백준 1629

문제

---

입력되는 정수가 매우 클 수 있으므로, long타입을 사용함

C로 나눈 나머지를 출력해야 하는데,

모든 계산이 끝난 후 C로 나눌 경우, 숫자가 너무 커져 오버플로우 발생할 수도 있음

따라서 정수론에서 배우는 mod 개념을 사용

---

A X B 를 C로 나눈 나머지는 A를 C로 나눈 나머지와 B를 C로 나눈 나머지의 곱과 같다.

이 성질을 이용하여 오버플로우가 발생하지않도록 곱셈 등을 할 때 큰 숫자가 되지 않게

계산 후 C로 미리 나눠주기

---

그리고 밑과 지수 모두 자연수이므로 지수는 짝수 아니면 홀수

따라서 밑을 제곱하는 것만으로도 쉽게 주어진 수를 계산할 수 있음

예를 들어, 2^4 같이 지수가 짝수일 때는 2를 3번 제곱하면 됨.

2^5와 같이 지수가 홀수일 때는 2를 3번 제곱한 뒤 2를 곱해주면 됨.

(물론, 위에서 설명했듯이 각 과정이 끝나고 C로 나눠주기)

---

Code

package test;

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

public class P1629 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		long A = Long.parseLong(st.nextToken());
		long B = Long.parseLong(st.nextToken());
		long C = Long.parseLong(st.nextToken());
		
		bw.write(String.valueOf(pow(A, B, C)));
		
		br.close();
		bw.flush();
		bw.close();
		
		
		
	}
    /*
    A : 밑, exponent : 지수, mod : 법(나누는 수)
    
    ex) 2^4을 계산할 때 (지수가 짝수일 때)
    2^4 <-- 2^2 <-- 2^1
    
    ex) 2^5을 계산할 때 (지수가 홀수일 때)
    2^5 <-- 2 * 2^4 <-- 2^2 <-- 2^1
    
    */
	private static long pow(long A, long exponent, long mod) {
		
		if(exponent == 1) {
			return A % mod;
		}
		
		long temp = pow(A, exponent / 2, mod);
		
        // 지수가 홀수
		if(exponent % 2 == 1) {
			return ((temp * temp % mod) * (A % mod)) % mod; 
		}	
        // 지수가 짝수
		return temp * temp % mod;
		
	}
}