백준 1629번 곱셈 with Kotlin

곱셈 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

45686

11870

8710

25.477%

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1 복사

10 11 12

예제 출력 1 복사

4

출처

• 문제를 만든 사람: author5

알고리즘 분류

• 수학
• 분할 정복을 이용한 거듭제곱

https://st-lab.tistory.com/237

[백준] 1629번 : 곱셈 - JAVA [자바]

 

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
 
 
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
 
fun main()=with(br){
    var (a,b,c) = readLine()!!.split(" ").map{it.toLong()}
    var ans = pow(a,b,c)
    bw.write("$ans")
    bw.flush()
    bw.close()
}
 
fun pow(base:Long,expo:Long,mod:Long): Long {
    if(expo==1L)
        return base%mod
 
    var temp = pow(base,expo/2,mod)
 
    if(expo%2==0L){
        return (temp*temp)%mod
    }
    return ((temp*temp)%mod*base)%mod
}