« マッチ棒の並べ方パズル(解答編) | メイン | 文法ひとつで人の評価は大きく変わる »

接点と円と三角形のパズル(解答編)

 接点と円と三角形のパズルの解答編です。

 この問題では、まず、三角形 OAB の面積 S を a, b, r を使って表します。

 A の x, y 座標をそれぞれ Ax, Ay とおきます。円の接線の方程式は公式としてよく知られており(ここなど)、これが (a,b) を通過することから下記の関係がいえます。

 また、A は円上にあるため、

 がいえます。この2つを連立して解くと Ax, Ay が求められます。

 また、B の x, y 座標をそれぞれ Bx, By とすると、同様にして、

 が得られます。さらにここに三角形の面積の公式を使い、整理すると、

 となります。つまり、本問は、S が整数となるような a,b,r の組は何個かを求めることになります。

 (追記) もっとスマートな導出法をコメント欄にて教えてもらいました。△AOB と △XOY はいずれも二等辺三角形で、かつ ∠AOB=∠XOY なので相似です。その面積比は、相似比を2乗した r2:a2+b2 となります。さらに △XOY の面積は公式を使って (b2-a2)/2 となりますので、結果、上記と同じ結果が得られます。

 さて、簡単に思いつく計算方法は、すべての a,b,r の組について、分子が分母を割り切るかをチェックし、割り切るものを数え上げるというやり方です。ですが、a2+b2<108 の条件ではチェックすべき範囲が大きすぎて莫大な時間がかかってしまいます。効率よく計算するにはし工夫が必要です。

 そこで計算量の節減のため、a,b についてのみ列挙を行います。S の式をよく見ると、a,b の値を1組固定すれば、S は (分数)×r2 の形で表すことができます。したがって、この分母を約分しきるような最小の r の値が計算できれば、この r を定数倍したものをすべて条件を満たす組としてカウントすることができます。1つ1つ r の値をチェックせずに済むのです。

 そのような r を求めるにはどうすればよいでしょうか。素直に考えれば、r2 が分母を割り切ればよいので、いったん分母を素因数分解し、各素因数のべき指数を半分にして(端数切り上げ)やればOKです。ですが、素因数分解はたいへん時間のかかる処理のため、結局長い時間がかかってしまいます。

 そこでさらにいくつかの改良を施します。まず、S の形をじっと見れば分かるように、a と b が公約数をもつ場合、公約数は分母と分子で約分し合います。ですので、a と b が互いに素の場合に限って r の計算を行い、公約数をもつケースをそのときにまとめて計算するようにすれば処理が省けます。また、a,b が互いに素であれば、b2+a2 と b2-a2 の公約数は、a, b がいずれも奇数のとき 2、それ以外のとき 1 になりますので、約分の計算が簡単化できます。

 さらに、分母を約分するような r の値を、あらかじめ様々な分母の値に対して計算しておきます。値を覚えておくために1で初期化した配列を用意し、各素数の1乗、3乗、5乗、・・・のそれぞれの整数倍に対しその素数を乗じていきます。

 以上のコードをこちらに記します。コードでは、上記の改良に加え、フェルマーの 4n+1 定理(参考)により、分母の b2+a2 の部分が必ず 4n+1 の形になる点に着目し、必要な配列のサイズを4分の1にコンパクト化しています。

 実行させると、答えの 14898922 が得られます。実行時間は、マシンの種類にもよりますが、例えば僕の5年前のマシンで約30秒。出題者の工夫ではこれが限界でしたが、もしかするとさらにずっと優れた方法があるかもしれません。もし見つかればコメント欄などで教えて頂けると大変うれしいです。

 なお、本問の正解者は、順に niino さん、kozima さん、chaemon さん、xsd さんでした。Project Euler の上位の常連の方々ですね。ありがとうございます!

トラックバック

このエントリーのトラックバックURL:
http://www.riverplus.net/cgi/mt/mt-tb.cgi/3202

コメント (3)

niino:

∠AOB=∠XOY だから、余弦定理でcos∠XOY を求めて、sin∠XOYを求めて S を出しました。
これだと座標を求める必要ないのですっきりです。

niino:

あれ、⊿AOBと⊿XOYが相似だから、角度も求める必要ないですね。失礼。

riverplus:

ありがとうございます。そんなやり方がありましたか!
△AOBと△XOYの相似比が r:√(a^2+b^2)、さらに△XOYの面積が (b^2-a^2)/2 なので・・・きわめてスマートに出せますね。
まったく想定していない出し方でした。

コメントを投稿