Problem 338
Cutting Rectangular Grid Paper
A rectangular sheet of grid paper with integer dimensions w × h is given. Its grid spacing is 1.
When we cut the sheet along the grid lines into two pieces and rearrange those pieces without overlap, we can make new rectangles with different dimensions.
For example, from a sheet with dimensions 9 × 4 , we can make rectangles with dimensions 18 × 2, 12 × 3 and 6 × 6 by cutting and rearranging as below:
Similarly, from a sheet with dimensions 9 × 8 , we can make rectangles with dimensions 18 × 4 and 12 × 6 .
For a pair w and h, let F(w,h) be the number of distinct rectangles that can be made from a sheet with dimensions w × h .
For example, F(2,1) = 0, F(2,2) = 1, F(9,4) = 3 and F(9,8) = 2.
Note that rectangles congruent to the initial one are not counted in F(w,h).
Note also that rectangles with dimensions w × h and dimensions h × w are not considered distinct.
For an integer N, let G(N) be the sum of F(w,h) for all pairs w and h which satisfy 0 < h ≤ w ≤ N.
We can verify that G(10) = 55, G(103) = 971745 and G(105) = 9992617687.
Find G(1012). Give your answer modulo 108.
剪长方形网格纸
我们有一张边长为整数w × h的长方形网格纸，网格的宽度为1。
如果我们沿着网格线将这张纸剪成两片，然后将它们不重叠地重排在一起，我们可以得到不同边长的新长方形。
例如，用一张边长为9 × 4的长方形网格纸，我们可以通过剪裁和重排得到边长为18 × 2、12 × 3或6 × 6的长方形，如下所示：
同样地，用一张边长为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，找出所有满足0 < h ≤ w ≤ N的数对w和h，记F(w,h)的和为G(N)。
我们可以验证G(10) = 55，G(103) = 971745，以及G(105) = 9992617687。
求G(1012)。将你的答案模108取余。