[BOJ] 25517 머리 아픈 암산은 이제 그만! - P4

문제풀이

1. 10^8, 2x10^8, ..., 10^9의 10개 정도를 미리 계산해서 입력해둔다.
2. 나누기 연산은 숫자^(MOD - 2)를 곱하는 것으로 대신한다.

---

주의사항

1. 10^9의 팩토리얼 계산의 시간 복잡도를 줄이지 않으면 시간 초과를 피할 수 없다.

---

소요시간

25분

---

package 백준.Platinum.P4.p25517_머리아픈암산은이제그만

const val MOD = 1000000007
fun main() {
    val (N, M) = readln().split(" ").map(String::toInt)
    val arr = intArrayOf(
        1,
        927880474,
        933245637,
        668123525,
        429277690,
        733333339,
        724464507,
        957939114,
        203191898,
        586445753,
        698611116
    )
    var result = 1L
    for (i in 10 downTo 0) {
        if (N >= i * 100000000) {
            result = arr[i].toLong()
            break
        }
    }
    for (i in (N / 100000000 * 100000000 + 1)..N) {
        result = (result * i) % MOD
    }
    fun Int.pow(n: Int): Int {
        if (n == 0) return 1
        if (n == 1) return this
        val halfPow = pow(n / 2)
        return if (n % 2 == 1) ((this.toLong() * halfPow % MOD) * halfPow % MOD).toInt()
        else (halfPow.toLong() * halfPow % MOD).toInt()
    }

    val set = mutableSetOf<Int>()
    repeat(M) {
        val num = readln().toInt()
        if (set.add(num)) result = (result * num.pow(MOD - 2)) % MOD
    }
    println(result)
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P4/p25517_%EB%A8%B8%EB%A6%AC%EC%95%84%ED%94%88%EC%95%94%EC%82%B0%EC%9D%80%EC%9D%B4%EC%A0%9C%EA%B7%B8%EB%A7%8C/p25517_%EB%A8%B8%EB%A6%AC%EC%95%84%ED%94%88%EC%95%94%EC%82%B0%EC%9D%80%EC%9D%B4%EC%A0%9C%EA%B7%B8%EB%A7%8C.kt

---

문제링크

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