kingsubin

import java.io.*;
import java.util.*;

public class boj_1629 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        long C = Long.parseLong(st.nextToken());

        System.out.println(pow(A, B, C));
    }
    
    public static long pow(long a, long b, long c) {
        if (b == 1) return a % c;
        long val = pow(a, b/2, c);
        val = val * val % c;
        if (b % 2 == 0) return val;
        return val * a % c;
    }
}

 

- 실패

 

- 재귀적을 생각하라는데 어렵다