ScalaでProject Euler（78）

Problem 48

この手の問題でBigIntを使ってはいけません。Longの範囲で解きましょう。ただ、10桁同士の掛け算を行うとLongの範囲を超える可能性があるので、少し工夫します。ここは5桁ずつに区切って計算します。

val M = 1e5.toLong
val N = M * M

def pow(n :Int, e :Int) :Long =
    if(e == 0)
        1L
    else {
        val m = pow(n, e / 2)
        val m1 = m % M
        val m2 = m / M
        val m_sq = (2 * m2 * m1 * M + m1 * m1) % N
        if(e % 2 == 1)
            m_sq * n % N
        else
            m_sq
    }

println ((1 to 1000).foldLeft(0L)((s, n) => s + pow(n, n)) % N)