Project Euler 48

http://projecteuler.net/index.php?section=problems&id=48

多倍長整数を使うと簡単すぎるので、64ビット整数を使って、5桁で区切って掛け算を行いました。

let N = 1000
let L = 100000L
let M = L * L

let rec pow (n : int) e =
    if e = 0 then
        1L
    else
        let m = pow n (e / 2)
        let m1 = m % L
        let m2 = m / L
        let m' = (m1 * m1 + 2L * m1 * m2 * L) % M
        if e % 2 = 1 then m' * (int64 n) % M else m'

printfn "%d" ((List.sum [ for n in 1..N -> pow n n ]) % M)