object Solution {
  import java.math.BigDecimal.ROUND_HALF_UP
  import java.math.BigDecimal

  def squareRoot(i: Int, nDigits: Int): BigInt = {
    val limit = BigInt(10).pow(nDigits + 1)
    var a = 5 * BigInt(i)
    var b = BigInt(5)
    while (b < limit) {
      if (a >= b) {
        a = a - b
        b += 10
      }
      else {
        a *= 100
        b = 10 * b - 45
      }
    }
    b / 100
  }

  val ZERO = new BigDecimal("0")
  val TWO = new BigDecimal("2")
  def sqrtBigDecimal(A: BigDecimal, SCALE: Int) = {
    var x0 = ZERO
    var x1 = new BigDecimal(math.sqrt(A.intValue));
    while (!x0.equals(x1)) {
        x0 = x1
        x1 = A.divide(x0, SCALE, ROUND_HALF_UP).add(x0)
        x1 = x1.divide(TWO, SCALE, ROUND_HALF_UP);
    }
    x1
  }

  def isPerfectRoot(x: Int): Boolean = {
    val sqrt = math.sqrt(x).toInt
    sqrt * sqrt == x
  }

  def main(args: Array[String]) {
    val n = readInt
    val p = readInt
    val sum = (1 to n).filter(!isPerfectRoot(_))
      .map(x =>
        sqrtBigDecimal(new BigDecimal(x), p + 1).toString.take(p + 1)
          .foldLeft(0) { (x, y) => if (y == '.') x else x + y.asDigit }).sum
    println(sum)
  }
}

object Solution {

  def squareRoot(i: Int, nDigits: Int): BigInt = {
    val limit = BigInt(10).pow(nDigits + 1)
    var a = 5 * BigInt(i)
    var b = BigInt(5)
    while (b < limit) {
      if (a >= b) {
        a -= b
        b += 10
      }
      else {
        a *= 100
        b = (b / 10) * 100 + 5
      }
    }
    b / 100
  }

  def isPerfectRoot(x: Int): Boolean = {
    val sqrt = math.sqrt(x).toInt
    sqrt * sqrt == x
  }

  def main(args: Array[String]) {
    val n = readInt
    val p = readInt
    val sum = (1 to n).filter(!isPerfectRoot(_))
                      .map(x => squareRoot(x, p).toString.map(_.asDigit).sum).sum
    println(sum)
  }
}

--- 
+++ 
@@ -1,4 +1,6 @@
 object Solution {
+  import java.math.BigDecimal.ROUND_HALF_UP
+  import java.math.BigDecimal
 
   def squareRoot(i: Int, nDigits: Int): BigInt = {
     val limit = BigInt(10).pow(nDigits + 1)
@@ -6,15 +8,28 @@
     var b = BigInt(5)
     while (b < limit) {
       if (a >= b) {
-        a -= b
+        a = a - b
         b += 10
       }
       else {
         a *= 100
-        b = (b / 10) * 100 + 5
+        b = 10 * b - 45
       }
     }
     b / 100
+  }
+
+  val ZERO = new BigDecimal("0")
+  val TWO = new BigDecimal("2")
+  def sqrtBigDecimal(A: BigDecimal, SCALE: Int) = {
+    var x0 = ZERO
+    var x1 = new BigDecimal(math.sqrt(A.intValue));
+    while (!x0.equals(x1)) {
+        x0 = x1
+        x1 = A.divide(x0, SCALE, ROUND_HALF_UP).add(x0)
+        x1 = x1.divide(TWO, SCALE, ROUND_HALF_UP);
+    }
+    x1
   }
 
   def isPerfectRoot(x: Int): Boolean = {
@@ -26,7 +41,9 @@
     val n = readInt
     val p = readInt
     val sum = (1 to n).filter(!isPerfectRoot(_))
-                      .map(x => squareRoot(x, p).toString.map(_.asDigit).sum).sum
+      .map(x =>
+        sqrtBigDecimal(new BigDecimal(x), p + 1).toString.take(p + 1)
+          .foldLeft(0) { (x, y) => if (y == '.') x else x + y.asDigit }).sum
     println(sum)
   }
 }
Add a BigDecimal version. The first squareRoot function times out for
last two cases. The new version times out the last test case. Need
another look at the problem.
