Project Eulerをhaskellで練習していく日記: Problem 33

#問題
分母分子共に２桁の分数を約分する場合、例えば
89/92=8/2
のように分母分子に共通する数(9)を消してしまうと、算数問題としては間違いである。

しかし、分母分子共に２桁かつ分子＜分母となる分数のうち、４つだけこのような間違った約分をしてもたまたま正解になるパターンがある。

それら４つの分数の積を求め、その分母（最も約分された時の分母）の値を求めよ。
#回答
上下に同じ数が現れるパターンを以下の４パターンに分けると、

1. 21/81 のように１の位が同じ場合
2. 21/23 のように１０の位が同じ場合
3. 21/92 のように分子の１０の位と分母の１の位が同じ場合
4. 89/92 のように分子の１の位と分母の１０の位が同じ場合
   の４通りがある。
   しかし、このうち、1〜3のパターンは数学的に起こりえないことが証明できるので、4の場合に限って計算する。
   （この証明は以下のプログラムのコメントにて。）

import Data.Ratio

-- パターン１があり得ないことの証明
-- (10a+b)/(10c+b)=a/c<1
-- このときa<cであるが、
-- c(10a+b)=a(10c+b)
-- 10ac+bc=10ac+ab
-- bc=ab
-- c=a
-- これはa<cに矛盾する

-- パターン２があり得ないことの証明
-- (10a+b)/(10a+c)=b/c<1
-- このときb<cであるが、
-- 10ac+bc = 10ab+bc
-- ac=ab
-- c=b
-- c=b これはb<cに矛盾する

-- パターン３があり得ないことの証明
-- (10a+b)/(10c+a) = b/c < 1
-- 10ac+bc=10bc+ab
-- 10(ac-bc)+bc-ab=0
-- 10(a-b)c+b(c-a)=0
-- b(c-a)=10(b-a)c>0
-- よって、 b>a
-- したがって、a<=b-1, また、もともとb<cなので、b<=c-1
-- 0=10ac+bc-10bc-ab<=10(b-1)c+bc-10bc-ab=-10c+bc-ab<=-10c+(c-1)c-ab=c^2-11c-ab
-- cの二次式の判別式を考えると、D=(-11)^2-4(-ab)=11^2+4ab<=0
-- となるが、a,b>0なので、D<=0となることはあり得ない。

-- 以上により、(10a+b)/(10b+c)=a/c<1 となるパターンのみから発見すれば良い。

kouho = [a%c| b<-[1..9], c<-[1..9], a<-[1..min (b-1) (c-1)], 
              b/=c, 
              (10*a+b) % (10*b+c) == a % c]

main = do
     print $ product kouho

#感想
Haskellの分数機能はすばらしい！！！