[BOJ/백준][Gold5] 13172 : Σ (Kotlin)

https://www.acmicpc.net/problem/13172

13172번: Σ

 

 

[난이도] Gold5
[유형] 분할정복

[풀이]
지문 이해가 어려운 문제였습니다.
b^-1 이 역원이라는것을 인지한 뒤로 b^x 꼴의 수를 거듭제곱수라고 머릿속에서 생각하지 않게되어
b^x-2이 단순한 b의 x-2 제곱수라는것을 생각하지 못하였습니다.

b^-1을 직접 구하려다 실패하고 풀이를 보고 b^x-2를 구하면 되는 문제라는 것을 알게되었습니다.
x가 1000000005 제곱을 해야하기 때문에 직접 곱하면 안되고 재귀를 이용한 분할정복을 이용하였습니다.

 

 

import java.util.*
val bw = System.`out`.bufferedWriter()
val mod = 1000000007
fun gcd(pa:Long,pb:Long):Long{
    var a = pa
    var b = pb
    if(a>b) a = b.also{b=a}
    while(a>0){
        var c = b%a
        b = a
        a = c
    }
    return b
}
fun sol(n:Int,k:Long):Long{
    if(n==1) return k
    var ret = 1L
    if(n%2==1) ret=k
    var v = sol(n/2,k)
    v = (v*v)%mod
    return (ret*v)%mod
}
fun main() = with(System.`in`.bufferedReader()){
    var M = readLine().toInt()
    var ans = 0L
    repeat(M){
        val (a,b) = readLine().split(' ').map{it.toLong()}
        ans += when{
            a%b==0L -> (a/b).toLong()
            else -> {
                var g = gcd(a,b)
                var down = (a/g).toLong()
                var up = (b/g).toLong()
                down = sol(mod-2,down)
                down*up
            }
        }
        ans%=mod
    }
    println(ans)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/13172.cpp