Baekjoon Online Judge

algorithm practice

-問題を逐次解く

20.分割征服

4.乗算

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long A = sc.nextLong();
		long B = sc.nextLong();
		long C = sc.nextLong();
		
		System.out.println(power(A, B, C));
	}

	private static long power(long a, long b, long c) {
		
		if(b == 1) return a % c;
		
		long temp = power(a, b / 2, c);
		
		// b가 짝수일 때 
		if(b % 2 == 0) {
			return (temp * temp) % c;
		// b가 홀수일 때 
		} else {
			return (temp * temp % c) * a % c;
		}
	}
}

import sys
a, b, c = map(int, sys.stdin.readline().split())

def power(a, b, c):
    if b == 1:
        return a % c
    temp = power(a, b//2, c)
    
    if b % 2 == 0:
        return (temp * temp) % c
    else :
        return (temp * temp % c) * a % c		

print(power(a, b, c))