Problem 159

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

mdrs(n) = max_{m*d=n}(mdrs(m) + mdrs(d))

まぁ、成り立つでしょ。

import Control.Monad
import Data.Array.IO
lim = 10^6
main = do
drs <- newListArray (2,lim-1).tail.cycle$[1..9] :: IO (IOUArray Int Int)
let update n dn = forM_ [2..div (lim-1) n] $ m -> do
dm <- readArray drs m
dmn <- readArray drs (n*m)
writeArray drs (n*m) $ max dmn (dn+dm)
forM_ [2..div lim 2] $ n ->
readArray drs n >>= update n
getElems drs>>=print.sum.map toInteger

IOUArrayは偉大だ。IOArrayよりも10倍ぐらい速かった。