Problem 338 「長方形方眼紙の切断」

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

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

p338_gridpaper.gif

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

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

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

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


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