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.
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.
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.
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\).
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.
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.
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\).
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.
Für jedes Gitterrechteck \(w \times h\) mit \(0 \lt h \le w \le N\) sei \(F(w,h)\) die Anzahl verschiedener Rechtecke, die man erhält, wenn man das Blatt entlang von Gitterlinien in zwei Teile schneidet und diese beiden Teile zu einem neuen Rechteck zusammensetzt. Rechtecke, die zum ursprünglichen kongruent sind, werden nicht gezählt, und \(w \times h\) wird mit \(h \times w\) identifiziert. Gesucht ist
$$G(N)=\sum_{1\le h\le w\le N} F(w,h).$$
Da hier \(N=10^{12}\) ist, sind weder ein Durchlauf über alle Paare \((w,h)\) noch das Testen aller Schnitte praktikabel. Die Lösung übersetzt die Geometrie deshalb in ein arithmetisches Zählproblem.
Für ein festes Rechteck \(w \ge h\) sei \(x\) die kleinere Seite eines möglichen neuen Rechtecks. Wegen Flächenerhaltung gilt \(x\mid wh\) und \(x\le\sqrt{wh}\). Ein nützliches äquivalentes Kriterium ist
$$F(w,h)=\#\Bigl\{x:\ x\mid wh,\ x\le\sqrt{wh},\ x\ne h,\ (w-x)\mid w\ \text{oder}\ (x-h)\mid x\Bigr\}.$$
Damit sieht man sofort: Das Problem ist in Wahrheit ein Teilbarkeitsproblem und keine geometrische Simulation auf Einzelquadraten.
Schreibt man die erste Teilbarkeitsbedingung als \(w=ad\) und \(x=a(d-1)\), so erhält man die Standard-Parametrisierung
$$\bigl(ad,\ b(d-1)\bigr)\longrightarrow \bigl(a(d-1),\ bd\bigr),\qquad d\ge 2,$$
und nach Vertauschen der Rollen der beiden ursprünglichen Seiten wird jede gültige Umformung durch denselben Austausch benachbarter Faktoren \(d \leftrightarrow d-1\) beschrieben.
Dies erklärt auch die Beispiele aus der Aufgabenstellung. Etwa \(9\times 4=(3\cdot 3)\times(2\cdot 2)\) mit \(d=3\) liefert \(6\times 6\); in passender Orientierung entstehen im selben Schema auch \(12\times 3\) und \(18\times 2\).
Ist die Geometrie einmal durch \((a,b,d)\) parametrisiert, wird die Gesamtsumme zu einer Floor-Summe. Für festes \(d\ge 2\) darf man wählen
$$1\le a\le \left\lfloor\frac{N}{d}\right\rfloor,\qquad 1\le b\le \left\lfloor\frac{N}{d-1}\right\rfloor,$$
also ist die rohe Anzahl der Kandidaten
$$P(N)=\sum_{d=2}^{N}\left\lfloor\frac{N}{d}\right\rfloor\left\lfloor\frac{N}{d-1}\right\rfloor.$$
Genau diese Größe berechnet der Code in sum_floor_products. Sie zählt gültige Treppenschnitt-Beschreibungen, aber noch keine verschiedenen Rechtecke: dasselbe Rechteck kann aus mehreren Teilerketten stammen, und selbstkongruente Randfälle müssen separat korrigiert werden.
Zwei klassische Summenfunktionen bereinigen diese Überzählungen:
$$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\}.$$
Die vom Solver verwendete exakte Identität lautet
$$\boxed{G(N)=P(N)-T(N)+D(N).}$$
Anschaulich zählt \(P(N)\) alle Austausche benachbarter Faktoren, \(T(N)\) entfernt die dadurch entstehenden Mehrfachzählungen aus Teilerketten der Länge drei, und \(D(N)\) fügt die paarweisen Randfälle wieder hinzu, die sonst einmal zu oft subtrahiert würden. Diese Formel stimmt mit den Kontrollwerten \(G(10)=55\), \(G(10^3)=971745\) und \(G(10^5)=9992617687\) überein.
Die Divisorsumme wird nicht termweise berechnet. Ist
$$q=\left\lfloor\frac{n}{k}\right\rfloor,$$
dann bleibt derselbe Quotient für alle \(k\) im Intervall
$$k\le j\le r,\qquad r=\left\lfloor\frac{n}{q}\right\rfloor,$$
konstant. Ein solcher Block trägt also \(q(r-k+1)\) bei, und die Schleife springt direkt zum nächsten Quotientenblock. Das ist der übliche harmonische Gruppierungstrick und reduziert die Zahl der Zustände von linear auf ungefähr \(O(\sqrt n)\).
Eine naive Dreifachzählung wäre viel zu langsam. Setze
$$L=\left\lfloor n^{1/3}\right\rfloor.$$
Jedes Tripel \((a,b,c)\) mit \(abc\le n\) besitzt mindestens eine Koordinate \(\le L\). Zählt man nach der Anzahl solcher kleinen Koordinaten, erhält man per Inklusion-Exklusion
$$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.$$
Der erste Term zählt Tripel mit mindestens einer kleinen Koordinate, der zweite entfernt die Fälle mit mindestens zwei kleinen Koordinaten, die doppelt erfasst wurden, und \(L^3\) fügt die Fälle hinzu, in denen alle drei Koordinaten klein sind.
Die Hilfsfunktion iroot3 berechnet die exakte ganzzahlige Kubikwurzel \(L=\lfloor n^{1/3}\rfloor\). divisor_summatory wertet \(D(n)\) über Quotientenblöcke aus und memoisiert wiederholte Aufrufe. sum_floor_products berechnet \(P(n)\), indem es über Intervalle springt, auf denen sowohl \(\lfloor n/i\rfloor\) als auch \(\lfloor n/(i-1)\rfloor\) konstant bleiben. triple_count implementiert die Formel für \(T(n)\), wobei sum_double_floor die doppelte Floor-Summe übernimmt. Schließlich liefert compute_G den Wert \(P(n)-T(n)+D(n)\), und erst im letzten Schritt wird modulo \(10^8\) reduziert.
Dominant ist die Doppelsumme bis \(L=\lfloor n^{1/3}\rfloor\), also beträgt die Gesamtlaufzeit ungefähr \(O(L^2)=O(n^{2/3})\). Die übrigen Divisorsummen sind dank Quotientenblöcken und Caching sublinear. Der Speicherverbrauch liegt ungefähr bei \(O(n^{1/3})\) plus Cache-Overhead. Deshalb ist \(N=10^{12}\) hier machbar, während eine direkte Enumeration aller Rechtecke aussichtslos wäre.
Her \(w \times h\) boyutlu, \(0 \lt h \le w \le N\) koşulunu sağlayan tamsayı ızgara dikdörtgeni için \(F(w,h)\), kâğıdı ızgara çizgileri boyunca iki parçaya kesip bu iki parçayı çakıştırmadan yeniden yerleştirerek elde edilebilen farklı dikdörtgenlerin sayısı olsun. Başlangıç dikdörtgeniyle eş olan durumlar sayılmaz ve \(w \times h\) ile \(h \times w\) ayrı kabul edilmez. Hesaplanmak istenen toplam
$$G(N)=\sum_{1\le h\le w\le N} F(w,h).$$
Burada \(N=10^{12}\) olduğundan, bütün \((w,h)\) çiftlerini ve bütün kesimleri tek tek denemek imkansızdır. Bu yüzden çözüm, geometrik problemi aritmetik bir sayma problemine çevirir.
Sabit bir \(w \ge h\) dikdörtgeni için, oluşabilecek yeni dikdörtgenin küçük kenarını \(x\) ile gösterelim. Alan korunduğu için \(x\mid wh\) ve \(x\le\sqrt{wh}\) olmalıdır. Kullanışlı eşdeğer ölçüt şudur:
$$F(w,h)=\#\Bigl\{x:\ x\mid wh,\ x\le\sqrt{wh},\ x\ne h,\ (w-x)\mid w\ \text{veya}\ (x-h)\mid x\Bigr\}.$$
Böylece problemin özünün, kare kare kesim simülasyonu değil bölünebilme ilişkileri olduğu görülür.
İlk bölünebilme koşulunu \(w=ad\) ve \(x=a(d-1)\) biçiminde yazarsak şu standart parametreleme elde edilir:
$$\bigl(ad,\ b(d-1)\bigr)\longrightarrow \bigl(a(d-1),\ bd\bigr),\qquad d\ge 2.$$
Başlangıçtaki iki kenarın rollerini değiştirince de aynı şema geçerlidir; yani bütün geçerli dönüşümler, komşu çarpanların \(d \leftrightarrow d-1\) biçimindeki değişimiyle açıklanır.
Bu, problemdeki örnekleri de açıklar. Örneğin \(9\times 4=(3\cdot 3)\times(2\cdot 2)\) ve \(d=3\) seçimi \(6\times 6\) üretir. Uygun yönlendirme seçildiğinde aynı çerçeve \(12\times 3\) ve \(18\times 2\) örneklerini de verir.
Geometri \((a,b,d)\) ile parametrelenince toplam, floor toplamına dönüşür. Sabit bir \(d\ge 2\) için
$$1\le a\le \left\lfloor\frac{N}{d}\right\rfloor,\qquad 1\le b\le \left\lfloor\frac{N}{d-1}\right\rfloor$$
seçilebilir. Dolayısıyla ham aday sayısı
$$P(N)=\sum_{d=2}^{N}\left\lfloor\frac{N}{d}\right\rfloor\left\lfloor\frac{N}{d-1}\right\rfloor$$
olur. Kodda sum_floor_products tam olarak bu büyüklüğü hesaplar. Fakat bu ifade henüz farklı dikdörtgenleri değil, geçerli “merdiven kesimi” tariflerini sayar. Aynı dikdörtgen birden fazla bölen zincirinden gelebilir ve başlangıçla eş olan sınır durumları ayrıca düzeltilmelidir.
Bu fazla sayımları temizlemek için iki klasik toplam fonksiyonu kullanılır:
$$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\}.$$
Çözücünün kullandığı kesin özdeşlik şudur:
$$\boxed{G(N)=P(N)-T(N)+D(N).}$$
Sezgisel olarak \(P(N)\) bütün komşu-çarpan değişimlerini sayar, \(T(N)\) üç uzunluklu bölen zincirlerinden kaynaklanan tekrarları çıkarır, \(D(N)\) ise bu çıkarma sırasında bir kez fazla eksilen ikili sınır durumlarını geri ekler. Bu kimlik, verilen kontrol değerleri \(G(10)=55\), \(G(10^3)=971745\) ve \(G(10^5)=9992617687\) ile tam uyumludur.
Bölen-toplam fonksiyonu terim terim hesaplanmaz. Eğer
$$q=\left\lfloor\frac{n}{k}\right\rfloor$$
ise aynı bölüm değeri
$$k\le j\le r,\qquad r=\left\lfloor\frac{n}{q}\right\rfloor$$
aralığındaki tüm \(j\) değerleri için sabit kalır. O halde bu blok tek seferde \(q(r-k+1)\) katkı yapar ve döngü bir sonraki blok sınırına sıçrar. Bu standart bölüm-bloklama tekniğidir ve maliyeti doğrusal olmaktan çıkarıp yaklaşık \(O(\sqrt n)\) farklı bloğa indirir.
Naif üçlü sayımı çok yavaştır. Şunu tanımlayalım:
$$L=\left\lfloor n^{1/3}\right\rfloor.$$
\(abc\le n\) sağlayan her \((a,b,c)\) üçlüsünde en az bir koordinat \(\le L\) olmak zorundadır. Küçük koordinat sayısına göre dahil etme-hariç tutma uygularsak
$$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$$
elde edilir. İlk terim en az bir küçük koordinatı olan üçlüleri sayar, ikinci terim en az iki küçük koordinatı olanları iki kez sayıldığı için düzeltir, son \(L^3\) terimi ise üç koordinatın da küçük olduğu durumları yeniden ekler.
iroot3 yardımcı fonksiyonu \(L=\lfloor n^{1/3}\rfloor\) değerini tam olarak bulur. divisor_summatory, \(D(n)\) fonksiyonunu bölüm bloklarıyla hesaplar ve tekrar eden çağrıları önbelleğe alır. sum_floor_products, hem \(\lfloor n/i\rfloor\) hem de \(\lfloor n/(i-1)\rfloor\) aynı kaldığı aralıklar boyunca sıçrayarak \(P(n)\) toplamını çıkarır. triple_count ise \(T(n)\) formülünü uygular; bunun içindeki çift floor toplamını sum_double_floor hesaplar. Son olarak compute_G, \(P(n)-T(n)+D(n)\) değerini döndürür ve sadece en sonda sonuç \(10^8\) moduna indirilir.
Baskın maliyet \(L=\lfloor n^{1/3}\rfloor\) sınırına kadar olan çift toplamdır; dolayısıyla toplam çalışma süresi yaklaşık \(O(L^2)=O(n^{2/3})\) olur. Geri kalan bölen-toplam parçaları, bölüm-bloklama ve önbellek sayesinde alt-doğrusal maliyete sahiptir. Bellek kullanımı yaklaşık \(O(n^{1/3})\) ve buna ek önbellek masrafıdır. Bu yüzden \(N=10^{12}\) bu yöntemle ulaşılabilirdir; oysa bütün dikdörtgenleri doğrudan dolaşmak tamamen pratik dışıdır.
Para cada rectángulo de enteros \(w \times h\) con \(0 \lt h \le w \le N\), sea \(F(w,h)\) el número de rectángulos distintos que pueden obtenerse al cortar la hoja por líneas de la cuadrícula en dos piezas y reordenar esas dos piezas para formar un nuevo rectángulo. No se cuentan los rectángulos congruentes al original y \(w \times h\) se identifica con \(h \times w\). Debemos calcular
$$G(N)=\sum_{1\le h\le w\le N} F(w,h).$$
Como aquí \(N=10^{12}\), ni recorrer todos los pares \((w,h)\) ni probar todos los cortes es viable. La solución convierte entonces la geometría en un problema aritmético de conteo.
Para un rectángulo fijo \(w \ge h\), sea \(x\) el lado menor de un posible nuevo rectángulo. Como el área se conserva, \(x\mid wh\) y \(x\le\sqrt{wh}\). Un criterio equivalente útil es
$$F(w,h)=\#\Bigl\{x:\ x\mid wh,\ x\le\sqrt{wh},\ x\ne h,\ (w-x)\mid w\ \text{o}\ (x-h)\mid x\Bigr\}.$$
Esto muestra que el problema es esencialmente de divisibilidad, no de simular cortes cuadrícula por cuadrícula.
Escribiendo la primera condición de divisibilidad como \(w=ad\) y \(x=a(d-1)\), obtenemos la parametrización estándar
$$\bigl(ad,\ b(d-1)\bigr)\longrightarrow \bigl(a(d-1),\ bd\bigr),\qquad d\ge 2,$$
y, tras intercambiar el papel de los dos lados originales, toda transformación válida queda descrita por el mismo intercambio de factores adyacentes \(d \leftrightarrow d-1\).
Esto también explica los ejemplos del enunciado. Por ejemplo, \(9\times 4=(3\cdot 3)\times(2\cdot 2)\) con \(d=3\) produce \(6\times 6\), y con la orientación adecuada el mismo esquema produce también \(12\times 3\) y \(18\times 2\).
Una vez parametrizada la geometría por \((a,b,d)\), la suma total se convierte en una suma con pisos. Para un \(d\ge 2\) fijo, podemos elegir
$$1\le a\le \left\lfloor\frac{N}{d}\right\rfloor,\qquad 1\le b\le \left\lfloor\frac{N}{d-1}\right\rfloor,$$
y por tanto el número bruto de construcciones candidatas es
$$P(N)=\sum_{d=2}^{N}\left\lfloor\frac{N}{d}\right\rfloor\left\lfloor\frac{N}{d-1}\right\rfloor.$$
Esta es exactamente la cantidad que el código calcula en sum_floor_products. Cuenta descripciones válidas del corte en escalera, pero todavía no rectángulos distintos: un mismo rectángulo puede proceder de más de una cadena de divisores, y además hay casos frontera congruentes consigo mismos que requieren corrección.
Dos funciones sumatorias clásicas limpian esos solapamientos:
$$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\}.$$
La identidad exacta implementada por el solver es
$$\boxed{G(N)=P(N)-T(N)+D(N).}$$
De forma intuitiva, \(P(N)\) cuenta todos los intercambios de factores adyacentes, \(T(N)\) elimina el sobreconteo producido por cadenas de divisores de longitud tres, y \(D(N)\) restaura los casos frontera a nivel de pares que quedarían sustraídos una vez de más. Esta identidad coincide con las comprobaciones dadas: \(G(10)=55\), \(G(10^3)=971745\) y \(G(10^5)=9992617687\).
La función sumatoria de divisores no se calcula término a término. Si
$$q=\left\lfloor\frac{n}{k}\right\rfloor,$$
entonces el mismo cociente permanece constante para todos los \(k\) en el intervalo
$$k\le j\le r,\qquad r=\left\lfloor\frac{n}{q}\right\rfloor.$$
Así, un bloque aporta \(q(r-k+1)\), y el bucle salta directamente al siguiente bloque de cociente. Es la técnica estándar de agrupación armónica o bloques de cociente, que reduce el coste de lineal a unas \(O(\sqrt n)\) clases distintas.
Un conteo ingenuo de ternas es demasiado lento. Definimos
$$L=\left\lfloor n^{1/3}\right\rfloor.$$
Toda terna \((a,b,c)\) con \(abc\le n\) tiene al menos una coordenada \(\le L\). Contando según cuántas coordenadas son \(\le L\), obtenemos por inclusión-exclusión
$$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.$$
El primer término cuenta las ternas con al menos una coordenada pequeña, el segundo corrige las que tienen al menos dos coordenadas pequeñas y fueron contadas dos veces, y \(L^3\) vuelve a añadir las ternas en las que las tres coordenadas son pequeñas.
La función auxiliar iroot3 calcula la raíz cúbica entera exacta \(L=\lfloor n^{1/3}\rfloor\). divisor_summatory evalúa \(D(n)\) por bloques de cociente y memoriza llamadas repetidas. sum_floor_products calcula \(P(n)\) saltando intervalos en los que tanto \(\lfloor n/i\rfloor\) como \(\lfloor n/(i-1)\rfloor\) permanecen constantes. triple_count implementa la fórmula de \(T(n)\), y sum_double_floor maneja la doble suma con pisos. Por último, compute_G devuelve \(P(n)-T(n)+D(n)\), y solo el paso final reduce el resultado módulo \(10^8\).
El coste dominante es la doble suma hasta \(L=\lfloor n^{1/3}\rfloor\), por lo que el tiempo total es aproximadamente \(O(L^2)=O(n^{2/3})\). Las demás piezas sumatorias son sublineales gracias a los bloques de cociente y la caché. La memoria es aproximadamente \(O(n^{1/3})\) más la sobrecarga de caché. Por eso \(N=10^{12}\) es tratable con este método, mientras que una enumeración directa de todos los rectángulos sería inviable.
对每个满足 \(0 \lt h \le w \le N\) 的整数网格长方形 \(w\times h\)，记 \(F(w,h)\) 为沿网格线把纸切成两块并重新拼成新长方形后，能够得到的不同长方形个数。与原长方形全等的结果不计入，且 \(w\times h\) 与 \(h\times w\) 不视为不同。要求计算
$$G(N)=\sum_{1\le h\le w\le N} F(w,h).$$
由于这里 \(N=10^{12}\)，既不可能枚举所有 \((w,h)\) 对，也不可能枚举所有切法。解法因此把几何问题转化为数论计数问题。
对固定的 \(w \ge h\)，设新长方形的较短边为 \(x\)。面积保持不变，因此 \(x\mid wh\) 且 \(x\le\sqrt{wh}\)。一个很有用的等价判据是
$$F(w,h)=\#\Bigl\{x:\ x\mid wh,\ x\le\sqrt{wh},\ x\ne h,\ (w-x)\mid w\ \text{或}\ (x-h)\mid x\Bigr\}.$$
这说明问题本质上是整除关系问题，而不是逐个小方格模拟切割。
把第一个整除条件写成 \(w=ad\) 与 \(x=a(d-1)\)，可得到标准参数化
$$\bigl(ad,\ b(d-1)\bigr)\longrightarrow \bigl(a(d-1),\ bd\bigr),\qquad d\ge 2,$$
交换原矩形两条边的角色后，所有合法重排仍然都落在同一个“相邻因子交换” \(d \leftrightarrow d-1\) 框架里。
题目中的例子也正是这样得到的。比如 \(9\times 4=(3\cdot 3)\times(2\cdot 2)\)，取 \(d=3\) 可得到 \(6\times 6\)；选取适当方向后，同一框架也会产生 \(12\times 3\) 和 \(18\times 2\)。
一旦几何对象用 \((a,b,d)\) 参数化，总和就变成 floor-sum。对固定 \(d\ge 2\)，可以选择
$$1\le a\le \left\lfloor\frac{N}{d}\right\rfloor,\qquad 1\le b\le \left\lfloor\frac{N}{d-1}\right\rfloor,$$
因此原始候选数为
$$P(N)=\sum_{d=2}^{N}\left\lfloor\frac{N}{d}\right\rfloor\left\lfloor\frac{N}{d-1}\right\rfloor.$$
代码中的 sum_floor_products 计算的正是这个量。它统计的是合法“阶梯切法”的描述数，而不是最终不同长方形的个数，因为同一个长方形可能对应多条因子链，而且与原图形全等的边界情况也需要额外修正。
为消除这些重复，程序使用两个经典求和函数：
$$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\}.$$
程序实现的精确恒等式是
$$\boxed{G(N)=P(N)-T(N)+D(N).}$$
直观地说，\(P(N)\) 先数出所有相邻因子交换，\(T(N)\) 去掉由长度为 3 的因子链造成的重复计数，而 \(D(N)\) 再把在这一过程中被多减一次的二元边界情形补回来。该恒等式与题目给出的检验值 \(G(10)=55\)、\(G(10^3)=971745\)、\(G(10^5)=9992617687\) 完全一致。
约数求和函数并不是逐项求值的。若
$$q=\left\lfloor\frac{n}{k}\right\rfloor,$$
则同样的商值会在区间
$$k\le j\le r,\qquad r=\left\lfloor\frac{n}{q}\right\rfloor$$
上保持不变。于是整个区间一次性贡献 \(q(r-k+1)\)，循环可以直接跳到下一个商值块。这就是标准的“商值分块”技巧，复杂度从线性降到大约 \(O(\sqrt n)\) 个不同块。
朴素三元计数太慢。设
$$L=\left\lfloor n^{1/3}\right\rfloor.$$
任意满足 \(abc\le n\) 的三元组 \((a,b,c)\) 至少有一个坐标不超过 \(L\)。按“不超过 \(L\) 的坐标个数”做容斥，可得
$$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.$$
第一项统计至少有一个小坐标的三元组，第二项去掉至少有两个小坐标而被重复计算的部分，最后的 \(L^3\) 把三个坐标都小的情形重新加回。
iroot3 精确计算整数立方根 \(L=\lfloor n^{1/3}\rfloor\)。divisor_summatory 用商值分块和缓存来求 \(D(n)\)。sum_floor_products 通过跳过那些同时保持 \(\lfloor n/i\rfloor\) 与 \(\lfloor n/(i-1)\rfloor\) 不变的区间来计算 \(P(n)\)。triple_count 实现 \(T(n)\) 的公式，其中 sum_double_floor 负责双重 floor 求和。最后 compute_G 返回 \(P(n)-T(n)+D(n)\)，只在最后一步再对 \(10^8\) 取模。
主导开销是上界为 \(L=\lfloor n^{1/3}\rfloor\) 的双重求和，因此总时间复杂度约为 \(O(L^2)=O(n^{2/3})\)。其余约数求和部分由于商值分块和缓存而是次线性的。空间复杂度约为 \(O(n^{1/3})\)，外加缓存开销。也正因此，\(N=10^{12}\) 在这里是可行的，而直接枚举所有长方形则完全不可行。
Для каждого целочисленного прямоугольника \(w \times h\), где \(0 \lt h \le w \le N\), обозначим через \(F(w,h)\) число различных прямоугольников, которые можно получить, если разрезать лист по линиям сетки на две части и затем без наложения переставить эти две части в новый прямоугольник. Прямоугольник, конгруэнтный исходному, не учитывается, а \(w \times h\) и \(h \times w\) считаются одним и тем же случаем. Требуется вычислить
$$G(N)=\sum_{1\le h\le w\le N} F(w,h).$$
Поскольку здесь \(N=10^{12}\), ни перебор всех пар \((w,h)\), ни перебор всех разрезов невозможны. Поэтому решение переводит геометрию в арифметическую задачу подсчета.
Для фиксированного прямоугольника \(w \ge h\) обозначим через \(x\) меньшую сторону возможного нового прямоугольника. Площадь сохраняется, значит \(x\mid wh\) и \(x\le\sqrt{wh}\). Полезный эквивалентный критерий таков:
$$F(w,h)=\#\Bigl\{x:\ x\mid wh,\ x\le\sqrt{wh},\ x\ne h,\ (w-x)\mid w\ \text{или}\ (x-h)\mid x\Bigr\}.$$
Отсюда видно, что задача по сути является задачей о делимости, а не о прямом моделировании разрезов по клеткам.
Если первую условную делимость записать как \(w=ad\) и \(x=a(d-1)\), получаем стандартную параметризацию
$$\bigl(ad,\ b(d-1)\bigr)\longrightarrow \bigl(a(d-1),\ bd\bigr),\qquad d\ge 2,$$
и после перестановки ролей двух исходных сторон любая допустимая перестройка описывается тем же обменом соседних множителей \(d \leftrightarrow d-1\).
Так объясняются и примеры из условия. Например, \(9\times 4=(3\cdot 3)\times(2\cdot 2)\) при \(d=3\) дает \(6\times 6\), а при подходящем выборе ориентации тот же механизм дает \(12\times 3\) и \(18\times 2\).
Когда геометрия параметризована тройкой \((a,b,d)\), общая сумма превращается в сумму с целыми частями. Для фиксированного \(d\ge 2\) можно выбрать
$$1\le a\le \left\lfloor\frac{N}{d}\right\rfloor,\qquad 1\le b\le \left\lfloor\frac{N}{d-1}\right\rfloor,$$
поэтому грубое число кандидатных конструкций равно
$$P(N)=\sum_{d=2}^{N}\left\lfloor\frac{N}{d}\right\rfloor\left\lfloor\frac{N}{d-1}\right\rfloor.$$
Именно эту величину вычисляет функция sum_floor_products. Она считает допустимые описания «ступенчатого» разреза, но еще не число различных прямоугольников: один и тот же прямоугольник может соответствовать нескольким цепочкам делителей, а граничные случаи, конгруэнтные исходному, нужно отдельно скорректировать.
Для устранения этих повторов используются две классические сумматорные функции:
$$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\}.$$
Точное тождество, реализованное в программе, имеет вид
$$\boxed{G(N)=P(N)-T(N)+D(N).}$$
Интуитивно \(P(N)\) считает все обмены соседних множителей, \(T(N)\) убирает возникающее переучитывание из цепочек делителей длины три, а \(D(N)\) возвращает парные граничные случаи, которые иначе были бы вычтены лишний раз. Это тождество согласуется с контрольными значениями \(G(10)=55\), \(G(10^3)=971745\) и \(G(10^5)=9992617687\).
Функция суммирования делителей считается не по одному слагаемому. Если
$$q=\left\lfloor\frac{n}{k}\right\rfloor,$$
то тот же частный сохраняется для всех \(k\) из интервала
$$k\le j\le r,\qquad r=\left\lfloor\frac{n}{q}\right\rfloor.$$
Значит, целый блок дает вклад \(q(r-k+1)\), и цикл сразу перескакивает к следующему блоку одинакового частного. Это стандартная техника группировки по частному, уменьшающая стоимость с линейной до примерно \(O(\sqrt n)\) различных блоков.
Наивный подсчет троек слишком медленный. Положим
$$L=\left\lfloor n^{1/3}\right\rfloor.$$
У любой тройки \((a,b,c)\) с \(abc\le n\) хотя бы одна координата не превосходит \(L\). Считая по числу таких малых координат, получаем по включениям-исключениям
$$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.$$
Первый член считает тройки хотя бы с одной малой координатой, второй исправляет переучет случаев хотя бы с двумя малыми координатами, а \(L^3\) добавляет обратно случаи, где малы все три координаты.
Вспомогательная функция iroot3 точно вычисляет целую кубическую корень \(L=\lfloor n^{1/3}\rfloor\). divisor_summatory вычисляет \(D(n)\) по блокам одинакового частного и кеширует повторные запросы. sum_floor_products вычисляет \(P(n)\), перепрыгивая через интервалы, на которых одновременно постоянны \(\lfloor n/i\rfloor\) и \(\lfloor n/(i-1)\rfloor\). triple_count реализует формулу для \(T(n)\), а sum_double_floor отвечает за двойную сумму с целыми частями. Наконец, compute_G возвращает \(P(n)-T(n)+D(n)\), и только в самом конце применяется модуль \(10^8\).
Главный вклад дает двойная сумма до \(L=\lfloor n^{1/3}\rfloor\), поэтому итоговое время работы составляет примерно \(O(L^2)=O(n^{2/3})\). Остальные сумматорные части сублинейны благодаря блокам одинакового частного и кешированию. Память составляет примерно \(O(n^{1/3})\) плюс накладные расходы кеша. Именно поэтому \(N=10^{12}\) здесь достижимо, тогда как прямой перебор всех прямоугольников был бы безнадежен.
لكل مستطيل شبكي بأبعاد صحيحة \(w \times h\) حيث \(0 \lt h \le w \le N\)، نرمز بـ \(F(w,h)\) إلى عدد المستطيلات المختلفة التي يمكن الحصول عليها عند قطع الورقة على خطوط الشبكة إلى قطعتين ثم إعادة ترتيب هاتين القطعتين لتكوين مستطيل جديد من دون تداخل. المستطيل المطابق للأصلي لا يُحسب، كما أن \(w \times h\) و\(h \times w\) لا يُعدّان حالتين مختلفتين. المطلوب هو حساب
$$G(N)=\sum_{1\le h\le w\le N} F(w,h).$$
ولأن \(N=10^{12}\)، فلا يمكن عمليًا تعداد جميع الأزواج \((w,h)\) ولا جميع طرق القطع. لذلك يحوّل الحل المسألة الهندسية إلى مسألة عدّ حسابية.
لنفترض مستطيلًا ثابتًا \(w \ge h\)، ولتكن \(x\) الضلع الأصغر للمستطيل الجديد المحتمل. بما أن المساحة محفوظة، فلا بد أن \(x\mid wh\) وأن \(x\le\sqrt{wh}\). ومن المعايير المكافئة المفيدة:
$$F(w,h)=\#\Bigl\{x:\ x\mid wh,\ x\le\sqrt{wh},\ x\ne h,\ (w-x)\mid w\ \text{أو}\ (x-h)\mid x\Bigr\}.$$
وهذا يوضح أن جوهر المسألة هو علاقات القسمة، لا محاكاة القطع مربعًا مربعًا.
إذا كتبنا شرط القسمة الأول على الصورة \(w=ad\) و\(x=a(d-1)\)، نحصل على البارامتريّة القياسية
$$\bigl(ad,\ b(d-1)\bigr)\longrightarrow \bigl(a(d-1),\ bd\bigr),\qquad d\ge 2,$$
وبعد تبديل دوري الضلعين الأصليين نجد أن كل إعادة ترتيب صحيحة تندرج تحت التبادل نفسه بين عاملين متجاورين \(d \leftrightarrow d-1\).
وهذا يفسر أمثلة المسألة أيضًا. فمثلًا \(9\times 4=(3\cdot 3)\times(2\cdot 2)\) مع \(d=3\) يعطي \(6\times 6\)، ومع اختيار الاتجاه المناسب ينتج الإطار نفسه كذلك \(12\times 3\) و\(18\times 2\).
بعد بارمتة البنية الهندسية بالثلاثي \((a,b,d)\)، يصبح المجموع الكلي مجموعًا من نوع floor-sum. فعند تثبيت \(d\ge 2\) يمكن اختيار
$$1\le a\le \left\lfloor\frac{N}{d}\right\rfloor,\qquad 1\le b\le \left\lfloor\frac{N}{d-1}\right\rfloor,$$
ومن ثم يكون عدد التركيبات المرشحة الخام
$$P(N)=\sum_{d=2}^{N}\left\lfloor\frac{N}{d}\right\rfloor\left\lfloor\frac{N}{d-1}\right\rfloor.$$
وهذه بالضبط هي الكمية التي تحسبها الدالة sum_floor_products في الشيفرة. لكنها تعدّ أوصاف القطع السلمي الصحيحة، لا عدد المستطيلات المختلفة بعد إزالة التكرار؛ فالمستطيل نفسه قد يظهر عبر أكثر من سلسلة قواسم، كما أن الحالات الحدية المطابقة للأصل تحتاج إلى تصحيح منفصل.
لتنظيف هذا التكرار تُستخدم دالتان تجميعيتان كلاسيكيتان:
$$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\}.$$
والمتطابقة الدقيقة التي يطبقها الحل هي
$$\boxed{G(N)=P(N)-T(N)+D(N).}$$
بصورة حدسية، يعدّ \(P(N)\) جميع تبديلات العوامل المتجاورة، ثم يزيل \(T(N)\) التكرار الناتج عن سلاسل القواسم ذات الطول ثلاثة، ثم تعيد \(D(N)\) الحالات الحدية الثنائية التي كانت ستُطرح مرة زائدة. وهذه المتطابقة تتفق تمامًا مع قيم الفحص المعطاة \(G(10)=55\) و\(G(10^3)=971745\) و\(G(10^5)=9992617687\).
لا تُحسب دالة مجموع القواسم حدًا حدًا. فإذا كان
$$q=\left\lfloor\frac{n}{k}\right\rfloor,$$
فإن القيمة نفسها تبقى ثابتة لجميع \(k\) ضمن المجال
$$k\le j\le r,\qquad r=\left\lfloor\frac{n}{q}\right\rfloor.$$
لذلك يساهم كل بلوك بمقدار \(q(r-k+1)\) دفعة واحدة، وتقفز الحلقة مباشرة إلى بلوك القسمة التالي. هذه هي حيلة تجميع خارج القسمة القياسية، وهي تخفض الكلفة من خطية إلى نحو \(O(\sqrt n)\) كتل مميزة.
العدّ الثلاثي الساذج بطيء جدًا. نعرّف
$$L=\left\lfloor n^{1/3}\right\rfloor.$$
كل ثلاثي \((a,b,c)\) يحقق \(abc\le n\) لا بد أن يملك إحداثيًا واحدًا على الأقل لا يتجاوز \(L\). وإذا عددنا الثلاثيات بحسب عدد الإحداثيات الصغيرة ثم طبقنا الاشتمال والاستبعاد نحصل على
$$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.$$
الحد الأول يعدّ الثلاثيات التي لها إحداثي صغير واحد على الأقل، والحد الثاني يصحح الحالات التي لها إحداثيان صغيران على الأقل وقد عُدّت مرتين، ثم يعيد \(L^3\) الحالات التي تكون فيها الإحداثيات الثلاثة كلها صغيرة.
تحسب الدالة المساعدة iroot3 الجذر التكعيبي الصحيح بدقة \(L=\lfloor n^{1/3}\rfloor\). وتقيّم divisor_summatory الدالة \(D(n)\) باستخدام كتل خارج القسمة مع التخزين المؤقت. أما sum_floor_products فتحسب \(P(n)\) بالقفز فوق المجالات التي يبقى فيها كل من \(\lfloor n/i\rfloor\) و\(\lfloor n/(i-1)\rfloor\) ثابتًا. وتطبق triple_count صيغة \(T(n)\)، بينما تتكفل sum_double_floor بالمجموع الثنائي ذي الدالة floor. وفي النهاية تعيد compute_G القيمة \(P(n)-T(n)+D(n)\)، ثم يؤخذ الباقي modulo \(10^8\) في الخطوة الأخيرة فقط.
الكلفة المسيطرة هي المجموع الثنائي حتى \(L=\lfloor n^{1/3}\rfloor\)، لذلك يكون الزمن الكلي تقريبًا \(O(L^2)=O(n^{2/3})\). أما بقية الحدود التجميعية فتكلفتها دون خطية بفضل تجميع خارج القسمة والتخزين المؤقت. ويبلغ استهلاك الذاكرة نحو \(O(n^{1/3})\) إضافة إلى كلفة الكاش. لهذا يمكن التعامل مع \(N=10^{12}\) بهذه الطريقة، بينما يكون التعداد المباشر لكل المستطيلات غير عملي تمامًا.