Detailed mathematical approach

Problem Summary

For each integer rectangle \(w \times h\) with \(0 \lt h \le w \le N\), let \(F(w,h)\) be the number of distinct rectangles that can be obtained by cutting the sheet along grid lines into two pieces and rearranging those two pieces into a new rectangle. Rectangles congruent to the original one are excluded, and \(w \times h\) is identified with \(h \times w\). We must compute

$G(N)=\sum_{1\le h\le w\le N} F(w,h).$

Since the problem asks for \(N=10^{12}\), neither iterating over all pairs \((w,h)\) nor testing all cuts is remotely feasible. The solution therefore converts the geometry into an arithmetic counting problem.

Mathematical Approach

Arithmetic Reformulation of One Cut

For a fixed rectangle \(w \ge h\), let \(x\) be the smaller side of a candidate new rectangle. Area is preserved, so \(x\mid wh\) and \(x\le\sqrt{wh}\). A useful equivalent criterion is

$F(w,h)=\#\Bigl\{x:\ x\mid wh,\ x\le\sqrt{wh},\ x\ne h,\ (w-x)\mid w\ \text{or}\ (x-h)\mid x\Bigr\}.$

This already shows that the problem is really about divisibility, not about simulating cuts square by square.

Writing the first divisibility condition as \(w=ad\) and \(x=a(d-1)\) gives the standard parameterization

$\bigl(ad,\ b(d-1)\bigr)\longrightarrow \bigl(a(d-1),\ bd\bigr),\qquad d\ge 2,$

and, after swapping the roles of the two original sides, every valid rearrangement is captured by the same adjacent-factor exchange \(d \leftrightarrow d-1\).

This matches the examples from the statement. For instance, \(9\times 4=(3\cdot 3)\times(2\cdot 2)\) with \(d=3\) gives \(6\times 6\), and the same framework also produces \(12\times 3\) and \(18\times 2\) after choosing the appropriate orientation.

Raw Global Counting

Once the geometry is parameterized by \((a,b,d)\), the global sum becomes a floor-sum. For a fixed \(d\ge 2\), we may choose

$1\le a\le \left\lfloor\frac{N}{d}\right\rfloor,\qquad 1\le b\le \left\lfloor\frac{N}{d-1}\right\rfloor,$

so the raw number of candidate constructions is

$P(N)=\sum_{d=2}^{N}\left\lfloor\frac{N}{d}\right\rfloor\left\lfloor\frac{N}{d-1}\right\rfloor.$

This is exactly the quantity computed by sum_floor_products in the code. It counts valid staircase descriptions, but not yet distinct rectangles: the same rectangle can arise from more than one divisor-chain description, and self-congruent boundary cases also need correction.

Pair and Triple Counting Corrections

Two classical summatory functions clean up those overlaps:

$D(n)=\sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor =\#\{(u,v)\in\mathbb N^2:\ uv\le n\},$

$T(n)=\#\{(a,b,c)\in\mathbb N^3:\ abc\le n\}.$

The exact identity implemented by the solver is

$\boxed{G(N)=P(N)-T(N)+D(N).}$

Intuitively, \(P(N)\) counts all adjacent-factor exchanges, \(T(N)\) removes the resulting overcount coming from divisor chains of length three, and \(D(N)\) restores the pair-level boundary cases that would otherwise be subtracted once too many. This identity agrees with the given checks \(G(10)=55\), \(G(10^3)=971745\), and \(G(10^5)=9992617687\).

Fast Evaluation of \(D(n)\)

The divisor summatory function is not computed term by term. If

$q=\left\lfloor\frac{n}{k}\right\rfloor,$

then the same quotient persists for all \(k\) in the interval

$k\le j\le r,\qquad r=\left\lfloor\frac{n}{q}\right\rfloor.$

Hence one block contributes \(q(r-k+1)\), and the loop jumps directly from one quotient block to the next. This is the standard harmonic-grouping or quotient-block trick, reducing the cost from linear to about \(O(\sqrt n)\) distinct blocks.

Fast Evaluation of \(T(n)\)

A naive triple count is far too slow. Let

$L=\left\lfloor n^{1/3}\right\rfloor.$

Every triple \((a,b,c)\) with \(abc\le n\) has at least one coordinate at most \(L\). Counting triples by how many coordinates are \(\le L\) gives the inclusion-exclusion identity

$T(n)=3\sum_{a=1}^{L} D\!\left(\left\lfloor\frac{n}{a}\right\rfloor\right) -3\sum_{a=1}^{L}\sum_{b=1}^{L}\left\lfloor\frac{n}{ab}\right\rfloor +L^3.$

The first term counts triples with at least one small coordinate, the second removes those with at least two small coordinates counted twice, and the final \(L^3\) adds back the triples where all three coordinates are small.

How the Code Works

The helper iroot3 computes the exact integer cube root \(L=\lfloor n^{1/3}\rfloor\). The function divisor_summatory evaluates \(D(n)\) by quotient blocks and memoizes repeated calls. The function sum_floor_products evaluates \(P(n)\) by jumping over intervals where both \(\lfloor n/i\rfloor\) and \(\lfloor n/(i-1)\rfloor\) stay constant. The function triple_count implements the formula for \(T(n)\), with sum_double_floor handling the double floor sum. Finally, compute_G returns \(P(n)-T(n)+D(n)\), and only the last step reduces modulo \(10^8\).

Complexity Analysis

The dominant cost is the double sum up to \(L=\lfloor n^{1/3}\rfloor\), so the overall running time is about \(O(L^2)=O(n^{2/3})\). The remaining divisor-summatory pieces are sublinear thanks to quotient blocks and caching. Memory usage is about \(O(n^{1/3})\) plus cache overhead. This is why \(N=10^{12}\) is practical here, whereas direct enumeration over all rectangles would be hopeless.

Further Reading

1. Problem page: https://projecteuler.net/problem=338
2. Divisor summatory function: Wikipedia
3. Dirichlet hyperbola method: Wikipedia
4. Inclusion-exclusion principle: Wikipedia