Project Euler Problem66できたんだけど前回同様肝心なところは理解できずでなんかダウナー気味。Haskell勉強のお題ではじめたPEなので別に数学的なところがわからなくても一向かまわないわけだけどせっかく解くのだからもう少し理解したいなぁ。と痛切に思う次第。ということで、ペル方程式というのがあるらしく、

x^2 - Dy^2 = ± 1

の最小解はDの平方根を使った漸化式で解ける*らしい*ことをまめめもさんのところで発見。前回までの問題で巡回部をひねり出すところまではなんとかできて

*Main> desc_cfrac 61
(7,[1,4,3,1,2,2,1,3,4,1,14])

いたので、これを一つのリストにまとめて漸化式を解きます。

xy :: [Integer] -> [Integer] -> Integer
xy [] xs = last xs
xy (d:ds) xs = if l == 1 then xy ds (xs ++ [d]) else xy ds (xs ++ xs')
  where
    l = length xs
    xs' = [(d*xs!!(l-1))+xs!!(l-2)]

なんか垢抜けないけど、x,yの解は求まります。求めたx,yを使って計算した結果答えが負数になるのは、巡回部の周期をkとしたとき

odd k && odd D

の時*らしい*ペル方程式の解の構成のでこれを使って

if odd k && odd D then x^2 + (D * y^2)

を解としました。んー、しかしなにがなんだかさっぱりわかりません。もう、カンニングがどうのこうのと考えるのヤメたよ。(@_@)