곰셈

모듈러 성질 [ (ab) mod c = ((a mod c)(b mod c)) mod c ] 을 알고있어야 한다.

Divide and Conquer 방식으로 재귀를 통해 문제를 풀 수 있다.

// 2022-03-15
// https://www.acmicpc.net/problem/1629

import java.io.*
import java.math.BigInteger

var A=0L
var C=0L
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (a,b,c) = readLine().split(' ').map{it.toInt()}
    A=a.toLong()
    C=c.toLong()
    print(re(b))
}
fun re(b:Int):Long {
    if(b==1) return (A%C)
    val tmp = re(b/2)
    return if(b%2==0) (tmp%C)*(tmp%C)%C else ((((tmp%C)*(A%C))%C)%C)*(tmp%C)%C
}