Problem 251

251 Cardano Triplets

Problem 251 – Project Euler

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

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

式を整理してやると,a, b, cについての3次式になる.

さらに,cについて,解くと結構きれいな形になる.c = (a の3次式)/(定数×b^2).

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

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

これをやるには,探索範囲が広すぎる.

ふるいを使っても,無謀である(と思う,メモリを非常に使うし,計算量も多そう).

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

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

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

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

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

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

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

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

More Reading
Newer// 計算幾何