251 Cardano Triplets

Problem 251 – Project Euler

ある条件を満たす，三つ組の整数を探すもんだい．

条件に三乗根があり，しかも，その中に二乗根まであるので，見た瞬間は，ぎょっとしますが…

式を整理してやると，a, b, cについての３次式になる．

さらに，cについて，解くと結構きれいな形になる．c = （a の３次式)/（定数×b^2)．

なので，整数という条件を利用するため，素因数分解とか使えば良い．

と，思っていた時期が僕にもありました．

これをやるには，探索範囲が広すぎる．

ふるいを使っても，無謀である（と思う，メモリを非常に使うし，計算量も多そう）．

というわけで，似たピタゴラス数の列挙などの解法をヒントに，

問題をいったん，整数から有理数へとおとし，考えた．

f(整数変数) = 整数変数 -> g(有理変数) = 1

それで，得られた有理数解から元の問題の整数解を構成する手順を考えた．

結果，そんなに速くはないが，シンプルなコードになったので良しとした．

C++ のコード（パスは問題の答え,a+b+c<= 10^8）

http://firestorage.jp/download/2ef4d37bd7b3d2d26a312d5e26b0741b4232ed0f

計算量的に厳しそうだったので，Haskellではなく，始めからC++で書いた．