[Kotlin] 백준 1630 : 오민식

문제 링크

1630번: 오민식

---

문제 해설

1~N의 모든 자연수로 나누어 떨어지는 수를 구해야 한다. 다시 말해 N이하의 모든 자연수의 최소 공배수를 구해야 하는데, 이는 N 이하인 소수들의 거듭제곱으로만 이루어진 곱인 소인수분해의 형태로 나타낼 수 있다.

 

예를 들어, \(N=10\)일 때 오민식을 만족하는 가장 작은 수인 2520은 \(2520=2^3\times 3^2\times 5\times 7\)로 나타낼 수 있다.

 

우선 N 이하의 모든 소수는 에라토스테네스의 체를 이용하여 구한다. 그리고 각 소수에 대하여 N 이하인 가장 큰 거듭제곱을 구해서 곱하면서 각 연산마다 987654321로 나눈 나머지를 구하면 된다.

 

추가적으로 N 이하의 소수 중 \(\sqrt{N}\)보다 큰 소수는 그 소수가 N 이하인 가장 큰 거듭제곱이기 때문에 해당 경우를 제외하면 연산 횟수를 줄일 수 있다.

Code

import kotlin.math.sqrt

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val isPrime = BooleanArray(n + 1) { true }
    isPrime[0] = false
    isPrime[1] = false
    val sqrt = sqrt(n.toDouble()).toInt()
    for (i in 2..sqrt) {
        if (isPrime[i]) {
            for (j in i * i..n step i)
                isPrime[j] = false
        }
    }
    val primes = isPrime.withIndex().filter { it.value }.map { it.index }
    var result = 1L
    for (p in primes) {
        var max = 0
        var index = 1
        if (p <= sqrt) {
            while (true) {
                val temp = p.pow(index++)
                if (temp <= n) max = temp
                else break
            }
        } else max = p
        result = (result * max) % 987654321
    }
    println(result)
}

private fun Int.pow(n: Int) = run {
    var result = 1
    repeat(n) { result *= this }
    result
}