Problem 134

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

ユークリッドの互除法を利用。

import Number
-- given m,n. find a,b. s.t. am+bn=1
euclid m n | n > m = let (a,b) = euclid n m  in (b,a)
           | r == 1 = (1,-q)
           | otherwise = let (a,b) = euclid n r 
                         in (b,a-b*q)
    where (q,r) = divMod m n

s p1 p2 | k < 0 = (mod (p1*(-k)) p2)*10^d+p1
        | k > 0 = (mod (q1*k-1)  p2)*10^d+p1
    where (k,_)= euclid (10^d) p2
          d = length.show$p1
          q1 = 10^d - p1

main = print.sum.zipWith s (takeWhile(<10^6).drop 2$ primes) $drop 3 primes