GoogolString.scala

import java.io.{PrintWriter, File}

object GoogolString extends App {
  def log2(num: Long): Double = {
    math.log(num) / math.log(2)
  }

  def calcN(k: Long): Long = {
    log2(k).toLong + 1
  }

  def calcD(k: Long): Long = {
    val n = calcN(k)
    k - math.pow(2, n - 1).toLong
  }

  def nextK(k: Long): Long = {
    val n = calcN(k)
    val d = calcD(k)
    math.pow(2, n - 1).toLong - d
  }

  def is2N(k: Long): Boolean = {
    val mostSigBit = new java.math.BigInteger(k.toString).bitLength
    math.pow(2, mostSigBit - 1) == k
  }

  def solve(k: Long): Int = {
    if (k == 1) 0
    else if (k == 2) 0
    else if (k == 3) 1
    else if (is2N(k)) 0
    else {
      val nK = nextK(k)
      solve(nK) match {
        case 0 => 1
        case 1 => 0
      }
    }
  }

  // main
  val lines = io.Source.fromFile("A-large-practice.in").getLines()
  val out = new PrintWriter(new File("A-large-practice.out" ))

  for (i <- 1 to lines.next.toInt) {
    out.println(s"Case #${i}: ${solve(lines.next.toLong)}")
  }
  out.close
}