Cutting Rectangular Grid Paper

A rectangular sheet of grid paper with integer dimensions $w \times 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 \times 4$, we can make rectangles with dimensions $18 \times 2$, $12 \times 3$ and $6 \times 6$ by cutting and rearranging as below:

Similarly, from a sheet with dimensions $9 \times 8$, we can make rectangles with dimensions $18 \times 4$ and $12 \times 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 \times 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 \times h$ and dimensions $h \times 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 \lt h \le w \le N$.
We can verify that $G(10) = 55$, $G(10^3) = 971745$ and $G(10^5) = 9992617687$.
Find $G(10^{12})$. Give your answer modulo $10^8$.

This is a relatively advanced math problem, which makes it quite interesting.

We first need to approach the individual function F(w, h) in a strategic way.

When we have an integer pair w and h that have a common factor other than 1 or when we have w=2h, we can divide w and h into smaller parts. These can be reorganized to form other rectangles.

For example, in the 9×8 case, we could divide by the common factor 3 into three 3×8 rectangles, rearranging these to make the 18×4 rectangle, or we could divide into two parts to make the 12×6 rectangle.

For every common factor, we can form a new rectangle. So the F(9,8) = 2.

If the rectangle 9×9, we can divide into 3 parts of 3×9, forming 27×1 or 2 parts of 9×4, forming 18×2 or 3 parts of 6×4, forming 18×3 – so F(9,9) = 3

Therefore, F(w, h) equals the number of the factors of w*h except 1 – 1 (when h=w.)

Now we need to find $G(N) = ∑w∑h F(w, h)$ with the domain of w and h as 0 < h <= w <= N. F being a multiplication of numbers of factors, we can change the formula to G(N) = ∑w∑h (#F(w * h) - [w==h]). This gives that G(N)= ∑i=1^N ∑j=1^N F(i * j) - ∑i=1^N F(i * i). From this, we derive that F(i * j) = ∑k=1^N μ(k) * [(ij/k)-1] where μ(k) is the Möbius function. So we get the formula G(N)= ∑i=1^N ∑j=1^N ∑k=1^N μ(k) * [(ij/k)-1] - ∑i=1^N ∑k=1^N μ(k) * [(i^2/k)-1]. After some rearranging, we get: G(N)= ∑k=1^N μ(k) * ∑i=1^N ∑j=1^N [(ij/k)-1] - ∑k=1^N μ(k) * ∑i=1^N [(i^2/k)-1] = ∑k=1^N μ(k) * (∑i=1^N ∑j=1^N ij/k - N^2) - ∑k=1^N μ(k) * (∑i=1^N i^2/k - N) = ∑k=1^N μ(k) * (N^2 * (∑i=1^N i/k * ∑j=1^N j/k) - N^2) - ∑k=1^N μ(k) * (N * (∑i=1^N i^2/k) - N) = ∑k=1^N μ(k) * N^2 * (∑i=1^N i/k * ∑j=1^N j/k - 1) - ∑k=1^N μ(k) * N * (∑i=1^N i^2/k - 1) = N^2 * (∑k=1^N μ(k)/k * ∑i=1^N i ∑j=1^N j - N) - N * (∑k=1^N μ(k)/k * ∑i=1^N i^2 -N). . This can be simplified further, by using that ∑i=1^N i = N(N+1)/2 and ∑i=1^N i^2 = N(N+1)(2N+1)/6 Then we still calculate this in modulo 10^8 to avoid overflow. After all, we get the following algorithm: ```Python N, MOD = 10**12, 10**8 inv = [pow(i, MOD-2, MOD) for i in range(1, N+1)] s = i = res = 0 while i * i <= N: t=((N//(i+1))+1) next = min(N//(N//t), N//i) tmp = (next*(next+1)//2 - i*(i+1)//2)%MOD res=(res + tmp * s)%MOD i = next + 1 i = 1 while i <= N: res = (res + pow(i, 2, MOD) * N//i)%MOD i += 1 print((res + MOD - N) % MOD) ``` This script can calculate the answer for G(10^12) modulo 10^8.

More Answers: