gNumber.scala

import java.io.{PrintStream, File}

import scala.annotation.tailrec
import scala.io.Source

object gNumber {

  def powerAndRemain(n: Long, d: Long): (Long, Long) = {
    @tailrec
    def powerAndRemainInner(acc: Long, remain: Long): (Long, Long) = {
      if ((remain % d) == 0) powerAndRemainInner(acc + 1, remain / d)
      else (acc, remain)
    }
    powerAndRemainInner(0, n)
  }

  def primeNumberDecompose(n : Long) : List[(Long, Long)] = {
    @tailrec
    def primeNumberDecompositeInner(d: Long, remain: Long, acc: List[(Long, Long)]): List[(Long, Long)] = {
      if (d > n || remain == 1) acc
      else {
        val (pow, newRemain) = powerAndRemain(remain, d)
        if (pow == 0) primeNumberDecompositeInner(d + 1, remain, acc)
        else primeNumberDecompositeInner(d + 1, newRemain, acc ++ List((d, pow)))
      }
    }

    primeNumberDecompositeInner(2, n, List())
  }

  def isPrime(pList : List[(Long, Long)]) : Boolean = {
    pList.length == 1 && pList.head._2 == 1
  }

  def sumDigit(n: Long): Long = {
    @tailrec
    def sumDigitInner(remain: Long, acc: Long): Long = {
      if (remain < 10) acc + remain
      else sumDigitInner(remain / 10, acc + (remain % 10))
    }
    sumDigitInner(n, 0)
  }

  def isGNumber(n : Long) = {
    if (sumDigit(n) == 1) true
    else isPrime(primeNumberDecompose(sumDigit(n)))
  }

  def canWin(n : Long) : Boolean = {
    if( isGNumber(n) ) return false
    else {
      val nextNum = primeNumberDecompose(n).map{pair=>
        n / Math.pow(pair._1, pair._2).toInt
      }
      if( nextNum.map{ num =>
        isGNumber(num)
      }.exists(_ == true) ) return true
      else {
        if(nextNum.map(canWin).exists(_ == false)) return true
        else return false
      }
    }
  }

  def process(iter: Iterator[String])(pr: String => Unit) {
    for (i <- 1 to iter.next().toInt) yield {
      pr(s"Case #$i: ${if(canWin(iter.next().toLong))"Laurence" else "Seymour"}")
    }
  }

  def main(args: Array[String]) {
    val in = Source.fromFile(new File("large.in"))
    val out = new PrintStream(new File("large.out"))
    try {
      process(in.getLines) { s: String => out.println(s) }
    } finally {
      out.flush; out.close
    }
  }
}