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 <  = (mod (p1*(-k)) p2)*10^d+p1
| k >  = (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