![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
#author("2024-05-16T14:45:07+00:00","","") *[[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) = 55, G(&tex{10^{3}};) = 971745, G(&tex{10^{5}};) = 9992617687 であることが確かめられる. G(10&sup{12};) を求めよ. 答えを 10&sup{8}; で割った値を入力せよ. G(&tex{10^{12}};) を求めよ. 答えを &tex{10^{8}}; で割った値を入力せよ. IP:121.80.134.87 TIME:"2024-05-16 (木) 23:45:07" REFERER:"https://odz.sakura.ne.jp/projecteuler/" USER_AGENT:"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/124.0.0.0 Safari/537.36"
