この問題は整数で考えるとよいです。すなわち、2ならこれに0を198個つけた整数200…00の平方根を整数で考えます。そうするとそれはちょうど100桁になり各桁を足し合わせればよいことになります。
平方根を整数で考えるというのは例えば24なら4、25なら5というように、2乗して自分を超えない最大の整数ということです。
さて、この計算法はニュートン法とほぼ同じです。aの平方根をニュートン法で求めるというのは、
xn+1 = (xn + a / xn) / 2
x0 > 0
この数列を前項との差が十分小さくなったところで打ち切ります。
整数の場合は少し違います。まず、初項は平方根以上でなければなりません。24の平方根を求める場合、初項を24とします。漸化式は同じなので、
24 → (24 + 24/24) / 2 = 12 → (12 + 24/12) / 2 = 7 → (7 + 24/7) / 2 = 5 → (5 + 24/5) / 2 = 4 → (4 + 24/4) / 6 = 5 → …
最後、振動しますね。そこで、前項より等しいまたは大きくなったら打ち切って前項を平方根とします。上の場合、… → 7 → 5 → 4 → 5 → … なので再び5になったところで終了で、平方根は4です。
本当は次のようにすると速くなるはずです。最初は1と24をビットシフトしていって、逆転したところから上の手順を開始すると割り算が少なくて済みます。
1, 24 → 2, 12 → 4, 6 → 8, 3 → 8 → (8 + 24/8) / 2 → 5 → 4 → 5
import scala.math.sqrt def is_square(n :Int) :Boolean = { val m = sqrt(n.toDouble).toInt m * m == n } def digits(n :BigInt) :List[Int] = if(n == 0) Nil else (n % 10).toInt :: digits(n / 10) def pow(n :BigInt, e :Int) :BigInt = if(e == 0) BigInt(1) else n * pow(n, e - 1) def int_sqrt(n :BigInt) :BigInt = { def f(p :BigInt) :BigInt = { val m = (p + n / p) / 2 if(m >= p) p else f(m) } f(n) } def sum_sqrt_digits(n :Int, M :Int) :Int = digits(int_sqrt(pow(BigInt(10), (M - 1) * 2) * n)).sum val N = 100 val M = 100 println ((2 to N).filterNot(is_square).map(n => sum_sqrt_digits(n, M)).sum)
