Kotlinにおける3つ以上の数の最大公約数と最小公倍数のコードを紹介したいと思います。

理論

コード

再帰が深くなりすぎたときのことも考え、再帰ではなくスタックを用いて実装しています。

最大公約数

※AtCoder Beginner Contest (ABC) 109 C問題を解くコードになっています。

Main.kt

import java.util.*

/**
 * リストをスタックに変換する
 * @param list リスト
 * @return スタック
 */
fun listToStack(list: List<Int>): Stack<Int> {
    // スタック
    val stack = Stack<Int>()

    for (e in list) {
        stack.push(e)
    }

    return stack
}

/**
 * ユークリッドの互除法を用いて、最大公約数を導出する
 * @param list 最大公約数を求める対象となる数が格納されたリスト
 * @return 最大公約数
 */
fun gcd(list: List<Int>): Int {
    // 最大公約数を求める対象となる数が格納されたスタック
    val stack = listToStack(list)

    // ユークリッドの互除法を用いて、最大公約数を導出する
    // (最終的にスタック内に1つだけ数が残り、それが最大公約数となる)
    while (1 < stack.size) {
        // スタックから2つの数をpop
        val pops = (0 until 2).map {
            stack.pop()
        }

        // スタックからpopした2つの数のうち、小さい方の数のインデックス
        val minIndex = if (pops[1] < pops[0]) {
            1
        } else {
            0
        }

        // スタックからpopした2つの数のうち、小さい方の数をpush
        stack.push(pops[minIndex])

        // スタックからpopした2つの数の剰余
        val r = pops[(minIndex + 1) % 2] % pops[minIndex]

        // スタックからpopした2つの数に剰余があるならば、それをpush
        if (0 < r) {
            stack.push(r)
        }
    }

    // 最大公約数を返す
    return stack.pop()
}

fun main(args: Array<String>) {
    // 座標Xと座標x_iの距離が格納されるリスト
    val xx = mutableListOf<Int>()

    // 入力
    Scanner(System.`in`).use {
        val n = it.nextInt()
        val x = it.nextInt()
        for (i in 0 until n) {
            val xxI = it.nextInt()
            if (xxI < x) {
                xx.add(x - xxI)
            } else {
                xx.add(xxI - x)
            }
        }
    }

    // 正整数Dの最大値を出力
    println(gcd(xx))
}

最小公倍数

※AtCoder Beginner Contest (ABC) 109 C問題をベースにしていますが、本来であれば最大公約数 (正整数$D$) を導出すべき箇所で最小公倍数を導出するように変更を加えています。

Main.kt

import java.util.*

/**
 * リストをスタックに変換する
 * @param list リスト
 * @return スタック
 */
fun listToStack(list: List<Int>): Stack<Int> {
    // スタック
    val stack = Stack<Int>()

    for (e in list) {
        stack.push(e)
    }

    return stack
}

/**
 * ユークリッドの互除法を用いて、最大公約数を導出する
 * @param list 最大公約数を求める対象となる数が格納されたリスト
 * @return 最大公約数
 */
fun gcd(list: List<Int>): Int {
    // 最大公約数を求める対象となる数が格納されたスタック
    val stack = listToStack(list)

    // ユークリッドの互除法を用いて、最大公約数を導出する
    // (最終的にスタック内に1つだけ数が残り、それが最大公約数となる)
    while (1 < stack.size) {
        // スタックから2つの数をpop
        val pops = (0 until 2).map {
            stack.pop()
        }

        // スタックからpopした2つの数のうち、小さい方の数のインデックス
        val minIndex = if (pops[1] < pops[0]) {
            1
        } else {
            0
        }

        // スタックからpopした2つの数のうち、小さい方の数をpush
        stack.push(pops[minIndex])

        // スタックからpopした2つの数の剰余
        val r = pops[(minIndex + 1) % 2] % pops[minIndex]

        // スタックからpopした2つの数に剰余があるならば、それをpush
        if (0 < r) {
            stack.push(r)
        }
    }

    // 最大公約数を返す
    return stack.pop()
}

/**
 * 最小公倍数を導出する
 * @param list 最小公倍数を求める対象となる数が格納されたリスト
 * @return 最小公倍数
 */
fun lcm(list: List<Int>): Int {
    // 最大公約数を求める対象となる数が格納されたスタック
    val stack = listToStack(list)

    // 最小公倍数を導出する
    // (最終的にスタック内に1つだけ数が残り、それが最小公倍数となる)
    while (1 < stack.size) {
        // スタックから2つの数をpop
        val pops = (0 until 2).map {
            stack.pop()
        }

        // スタックからpopした2つの数の最小公倍数をpush
        stack.push(pops[0] * pops[1] / gcd(pops))
    }

    // 最小公倍数を返す
    return stack.pop()
}

fun main(args: Array<String>) {
    // 最小公倍数を求める対象となる数 (座標Xと座標x_iの距離) が格納されるリスト
    val xx = mutableListOf<Int>()

    // 入力
    Scanner(System.`in`).use {
        val n = it.nextInt()
        val x = it.nextInt()
        for (i in 0 until n) {
            val xxI = it.nextInt()
            if (xxI < x) {
                xx.add(x - xxI)
            } else {
                xx.add(xxI - x)
            }
        }
    }

    // 最小公倍数を出力
    // ※本来の題意からは逸脱している
    println(lcm(xx))
}