ScalaでProject Euler（87）

Problem 56

これも多倍長整数の問題です。乗算は加算より簡単です。

type LongInt = List[Int]

def digits(n: Int) :LongInt = {
    def f(m :Int) :List[Int] =
        if(m == 0) Nil else m % 10 :: f(m / 10)
    f(n).reverse
}

def mul(n :LongInt, m :LongInt) :LongInt = {
    val size = n.size + m.size
    val a = new Array[Int](size)
    
    for((k, e) <- List.range(0, n.size).zip(n);
        (l, f) <- List.range(0, m.size).zip(m))
            a(k + l + 1) += e * f
    
    for(k <- size - 1 to 1 by -1) {
        a(k-1) += a(k) / 10
        a(k) %= 10
    }
    
    val b = a.toList
    if(b.head == 0)
        b.tail
    else
        b
}

def pow(n :LongInt, e :Int) :LongInt =
    if(e == 0)
        List(1)
    else {
        val m = pow(n, e / 2)
        if(e % 2 == 1)
            mul(mul(m, m), n)
        else
            mul(m, m)
    }

val N = 100
val M = 100
println ((1 to N - 1).map(digits).flatMap(
            a => (1 to M - 1).map(b => pow(a, b))).
                                            map(n => n.sum).max)