import scala.annotation.tailrec object Problem280 { def proc(z: List[BigDecimal]) = { @tailrec def calcLastTheta(child: BigDecimal, parent: BigDecimal, z: List[BigDecimal]): (BigDecimal, BigDecimal) = { z match { case (head :: Nil) => (child, parent) case (head :: next :: tail) => { val c = child * head val p = parent * next // 毎回約分することで桁あふれを起こさない val g = gcd(c, p) val rc = c / g val rp = p / g calcLastTheta(rc, rp, z.tail) } case _ => throw new IllegalStateException("2 <= N <= 50なので起こり得ない") } } // θjを求める val (child, parent) = calcLastTheta(1, 1, z) // gcdで最大公約数求めて約分する val g = gcd(child, parent) val reductionChild = child / g val reductionParent = parent / g // 1/(child/parent) なので parent/child を表示 reductionParent + "/" + reductionChild } @tailrec def gcd(m: BigDecimal, n: BigDecimal): BigDecimal = { if (n == 0) { m } else { gcd(n, m % n) } } // N // z1 z2 ... zN def main(args: Array[String]) { val N = scala.io.StdIn.readInt() val z = scala.io.StdIn.readLine().split(" ").map(x => BigDecimal(x)).toList val result = proc(z) println(result) // test } def test = { assert(proc(List(20, 40)) == "2/1") assert(proc(List(10, 10, 10)) == "1/1") assert(proc(List(20, 60)) == "3/1") } }