Project Euler 66, ペル方程式

久しぶりに Project Euler を解きました。
最近あまり簡単に答えが合わなくなってきてしまったのでちょっとへこたれて Euler から遠のいていたのですが、友達がPE66を解の公式から解いたというので私も試しました。

とはいいつつもちょっと苦労したんですけどね。

任意のディオファントス方程式には一般解法は存在しないそうですが、その中でも特定の形をしたものはいくつか研究されていて、今回の問題のテーマは「ペル方程式」というもののようです。

http://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%AB%E6%96%B9%E7%A8%8B%E5%BC%8F

ただ、Wikipediaには最小解を求める方法は載っていなくて、色々検索したところ最終的に以下のページを見つけて解きました。
ちなみになぜそうなるのかは理解していませんorz
http://members.ld.infoseek.co.jp/aozora_m/suuronN/node80.html
（ちなみに、3-2 に誤植があります）

まあ、そんなわけで久しぶりに1問正答数が増えたということでｗ

最後にちょっとだけプログラミングの話に触れておくと、上記解法では有理数で表される漸化式を解くということになるのですが、Ruby には rational という超便利なモジュールがありました。
自作する必要がなくてすごく楽できました。致せり尽せりですな。