[백준/코틀린] 13172번: Σ

링크

13172번: Σ

풀이

M개의 주사위가 주어지고, 각 주사위의 기댓값의 합을 $10^9 + 7$로 나눈 나머지를 구하는 문제입니다.
모듈러 역원을 이용해 분수의 합을 모듈러 연산으로 처리합니다.

각 주사위의 기댓값은 $\frac{S_i}{N_i}$이고,
이 기댓값들의 합 $\sum \frac{S_i}{N_i}$을 구해야 합니다.

모듈러 연산에서 나눗셈은 직접 수행할 수 없으므로,
$\frac{a}{b} \bmod p$를 $a \cdot b^{-1} \bmod p$로 변환합니다.
여기서 $b^{-1}$은 $b$의 모듈러 역원으로, $b \cdot b^{-1} \equiv 1 \pmod{p}$를 만족하는 수입니다.

$p$가 소수일 때, 페르마 소정리에 의해 $b^{p-1} \equiv 1 \pmod{p}$이므로,
$b^{-1} \equiv b^{p-2} \pmod{p}$가 됩니다.
따라서 $b^{p-2}$를 분할 정복을 이용한 거듭제곱으로 O(log p)에 계산할 수 있습니다.

모든 주사위의 ${S_i} \times {N_i}^{-1}$를 누적 합산하면 답을 구할 수 있습니다.

코드

const val MOD = 1000000007

val powerCache = HashMap<Pair<Long, Long>, Long>()
fun power(a: Long, b: Long): Long {
    if (powerCache[a to b] != null) return powerCache.getValue(a to b)

    return when {
        b == 0L -> 1L
        b % 2 == 1L -> a * power(a, b - 1) % MOD
        else -> power(a, b / 2) * power(a, b / 2) % MOD
    }.also { powerCache[a to b] = it }
}

fun main() {
    var ans = 0L

    repeat(readln().toInt()) {
        val (n, s) = readln().split(' ').map { it.toLong() }

        ans = (ans + s * power(n, MOD - 2L)) % MOD
    }

    println(ans)
}