*[[Problem 338:http://projecteuler.net/problem=338]] 「長方形方眼紙の切断」 [#df29a72e]

整数の寸法 &tex{w}; × &tex{h}; をもつ長方形の方眼紙がある. 罫線の間隔は 1 である. ~
罫線に沿って方眼紙を二つに切り離し, 二つを重なりなく並び替えると, 別の寸法の長方形を新たに作ることができる.

例えば, 9 × 4 の寸法の方眼紙からは, 下のように切って並び替えると, 寸法 18 × 2, 12 × 3, 6 × 6 の長方形を作ることができる.

#ref(http://projecteuler.net/project/images/p338_gridpaper.gif,center,nolink);

同様に, 寸法 9 × 8 の方眼紙からは, 寸法 18 × 4, 12 × 6 の長方形を作ることができる.

&tex{w}; と &tex{h}; の組に対し, 寸法 &tex{w}; × &tex{h}; の方眼紙から作ることができる異なる長方形の数を F(&tex{w,h};) とする. ~
例えば, F(2,1) = 0, F(2,2) = 1, F(9,4) = 3, F(9,8) = 2 である. ~
始めの長方形と合同な長方形は F(&tex{w,h};) に数えないことに注意しよう. ~
また寸法 &tex{w}; × &tex{h}; と寸法 &tex{h}; × &tex{w}; の長方形は別とみなさないことに注意しよう.

整数 N に対し, 0 < &tex{h}; ≤ &tex{w}; ≤ &tex{N}; を満たす全ての &tex{w}; と &tex{h}; の組に対する F(&tex{w,h};) の和を G(&tex{N};) とする. ~
G(10) = 55, G(10&sup{3};) = 971745, G(10&sup{5};) = 9992617687 であることが確かめられる.

G(10&sup{12};) を求めよ. 答えを 10&sup{8}; で割った値を入力せよ.


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS