yu/logs/*

技術メモ　など

AtCoder ABC144 C 解法メモ （Kotlinで）約数列挙したい

AtCoder Kotlin

前に解いたような気がするけど忘れてしまってたのでメモ

解いていた問題

atcoder.jp

解法メモ

  • 面積が記載されるので、i * j = n となるi, jの組み合わせはnの約数のいずれか
  • 約数を列挙し、i+jが最小になる組み合わせを探す
    • n <= 1012なので√nまで探索する約数列挙だと実行時間制限に間に合う

実装メモ

    // ref: https://qiita.com/drken/items/a14e9af0ca2d857dad23#3-%E7%B4%84%E6%95%B0%E5%88%97%E6%8C%99
    fun getDivisors(n: Long): MutableList<Long> {
        val res = mutableListOf<Long>()

        var i = 1L
        while (i * i <= n) {
            if (n % i == 0L) {
                res.add(i)
                if (n / i != i) res.add(n / i)
            }
            i++
        }
        res.sort()
        return res
    }

提出した回答