← 完整题目索引

PROJECT EULER · #0338

切割矩形网格纸

Cutting Rectangular Grid Paper

仅题目 · 待解原题 ↗

给出了一张矩形网格纸,其尺寸为整数w×h。其网格间距为 1。
当我们沿着网格线将纸张切成两块并重新排列这些块而不重叠时,我们可以制作不同尺寸的新矩形。

例如,从尺寸为 9×4 的纸张中,我们可以通过如下切割和重新排列来制作尺寸为 18×2、12×3 和 6×6 的矩形:

0338_gridpaper.gif

同样,从尺寸为 9×8 的纸张中,我们可以制作尺寸为 18×4 和 12×6 的矩形。

对于一对 w 和 h,令 F(w,h) 为可以由尺寸为 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,令 G(N) 为满足 0<h≤w≤N 的所有 w 和 h 对的 F(w,h) 之和。
我们可以验证 G(10)=55、G(103)=971745 和 G(105)=9992617687。

求G(1012)。以 108 为模给出你的答案。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。