202 Laserbeam

Problem 202 – Project Euler

鏡の反射と聞いたら、三角形をたくさん並べてみたくなるのが、人の常。

そうすると、格子点がいくつかできるが、Cが反射してできたの点が規則的に並んでいるのが分かる。

要は、ある数と互いに素な数をある範囲で数えればいいことになるのだが…

しかし、問題ではnが1209002624と大きい。

従って、単純に互いに素なものを数えていると、計算が終らない可能性がある。

別の解法を探す必要がある。

（実際は、とりあえずナイーブなアルゴリズムを走らせてみた。

ちょっと外にでて戻ってきたら、計算が終っていた。これは内緒だ。）

簡単に分かることは、三角形を並べてみたときの、ある段での頂点Cが反射してできた点の数。

知りたいのは、ある段での頂点Cが反射してできた点のうち座標が互いに素な点の数。

この二つはメビウス関数で繋がっている。

で、あとはメビウスの反転公式を使って、式を計算していくと…

（これが、結構大変だった。）

綺麗な式がでてくる。 

import Number (factors)
import Data.List (group, nub)
phi :: Integer -> Integer
phi = product.map f.group.factors
where f (p:ps) = (p-1)*p^(length ps)
fun :: Integer -> Integer
fun n | any ((1==).(`mod` 3)) fs = 
| n `mod` 3 == 1           = 2^(length fs)
| otherwise                = -2^(length fs)
where fs = nub.factors $ n
p202 m | n `mod` 3 ==  = 
| otherwise      = div (phi n - fun n) 3
where n = (m+3) `div` 2
main :: IO ()
main = print.p202 $ 12017639147