Problem 338 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 338 へ行く。
  • 1 (2011-05-15 (日) 12:51:49)

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

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

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

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

w と h の組に対し, 寸法 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 < h ≤ w ≤ N を満たす全ての w と h の組に対する 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}; で割った値を入力せよ.