Problem 557 asks for \(S(n)\), the sum of the total areas \(T\) of all valid cutting-triangle configurations with \(T \le n\). After the geometry is reduced, every candidate can be encoded by positive integers \((a,b,c,d)\), and the condition \(b \le c\) is imposed so that mirror-image cases are not counted twice.
The total area is not approximated numerically; it is forced by an exact rational formula. That turns the task into a Diophantine search: find all integer triples \((a,b,c)\) for which the formula becomes integral, recover \(d\), and add the resulting total area \(T\).
A naive search over four positive integers would be far too slow for \(n=10000\). The successful idea is to eliminate the geometric unknowns first and then use the resulting inequalities to prune the arithmetic search very aggressively.
Let \(S(n)\) be the sum of all admissible total areas \(T\) with \(T \le n\). The key step is to replace the geometric picture by exact integer conditions.
Once the two auxiliary inner areas are solved away, the total area of a candidate configuration is determined by
$$T=\frac{a(a+b)(a+c)}{a^2-bc}.$$
So a valid cut must satisfy
$$a^2-bc\gt 0,\qquad T\in \mathbb{Z}_{\ge 1},\qquad d=T-a-b-c\in \mathbb{Z}_{\ge 1},\qquad b\le c.$$
This reduction is the heart of the solution: the geometric existence condition becomes a rational expression plus positivity and integrality constraints.
Because the four piece areas add up to the whole triangle, we have
$$T=a+b+c+d.$$
Therefore \(d\) does not need its own loop; once \(a\), \(b\), and \(c\) are known, \(d\) is determined by
$$d=T-a-b-c.$$
Substituting the formula for \(T\) gives
$$d=\frac{bc(2a+b+c)}{a^2-bc}.$$
Hence whenever \(a^2-bc\gt 0\) and \(T\) is an integer, \(d\) is automatically positive; and since \(d=T-a-b-c\), it is automatically integral as well. The implementations still test \(d\gt 0\) explicitly as a final safety check.
Several inequalities cut down the search before any divisibility test is attempted.
Since \(b\le c\) and \(bc\lt a^2\), we get \(b^2\lt a^2\), so
$$b\le a-1.$$
Also, from \(T=a+b+c+d\le n\), together with \(c\ge b\) and \(d\ge 1\), we obtain
$$a+2b+1\le n,$$
hence
$$b\le \left\lfloor\frac{n-a-1}{2}\right\rfloor.$$
There is a third bound. For fixed \(a\) and \(b\), the total area is strictly increasing as a function of \(c\) on the region \(bc\lt a^2\), because
$$\frac{dT}{dc}=\frac{a^2(a+b)^2}{(a^2-bc)^2}\gt 0.$$
So the smallest possible total for that pair occurs at \(c=b\):
$$T_{\min}=\frac{a(a+b)^2}{a^2-b^2}=\frac{a(a+b)}{a-b}.$$
Requiring \(T_{\min}\le n\) yields
$$b\le \left\lfloor\frac{a(n-a)}{a+n}\right\rfloor.$$
The implementation takes the minimum of these three upper bounds and only scans \(b\) in that reduced range.
Now fix \(a\) and \(b\). Because \(a^2-bc\gt 0\), we may rearrange \(T\le n\) without changing the direction of the inequality:
$$\frac{a(a+b)(a+c)}{a^2-bc}\le n.$$
Collecting the terms involving \(c\) gives
$$c\bigl(a(a+b)+nb\bigr)\le a^2(n-a-b),$$
so
$$c\le \left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor.$$
Two additional constraints are used simultaneously. From \(bc\lt a^2\),
$$c\le \left\lfloor\frac{a^2-1}{b}\right\rfloor.$$
From \(d\ge 1\) and \(T\le n\),
$$c\le n-a-b-1.$$
The final upper bound for \(c\) is the minimum of these three values. If that minimum is smaller than \(b\), then there is no admissible \(c\) for the current pair \((a,b)\).
For each surviving triple \((a,b,c)\), the implementations test whether the denominator divides the numerator:
$$a^2-bc \mid a(a+b)(a+c).$$
If so, then
$$T=\frac{a(a+b)(a+c)}{a^2-bc}$$
is an integer. The program keeps the candidate only if \(T\le n\), computes
$$d=T-a-b-c,$$
and confirms that \(d\gt 0\). Every valid configuration contributes its full total area \(T\) to \(S(n)\).
For this pair, the bounds on \(b\) are satisfied, so we move on to \(c\). The inequality from \(T\le n\) gives
$$c\le \left\lfloor\frac{20^2(55-20-2)}{20(20+2)+55\cdot 2}\right\rfloor=\left\lfloor\frac{13200}{550}\right\rfloor=24.$$
The bound from \(bc\lt a^2\) gives
$$c\le \left\lfloor\frac{20^2-1}{2}\right\rfloor=199,$$
and the condition \(d\ge 1\) together with \(T\le 55\) gives
$$c\le 55-20-2-1=32.$$
Therefore only \(2\le c\le 24\) must be checked. At the endpoint \(c=24\),
$$T=\frac{20\cdot 22\cdot 44}{20^2-2\cdot 24}=\frac{19360}{352}=55,$$
so
$$d=55-20-2-24=9.$$
This produces the valid quadruple \((20,2,24,9)\). Another valid quadruple with the same total area is \((22,8,11,14)\), matching the small checkpoint data used by the implementations.
The C++, Python, and Java implementations all follow the same arithmetic strategy. They loop over \(a\), derive the tight admissible range for \(b\), derive the tight admissible range for \(c\) for each remaining pair \((a,b)\), and only then perform the divisibility test that determines whether \(T\) is integral.
The C++ implementation is the main high-performance solver. For large \(n\) it partitions the outer range of \(a\) into chunks, processes those chunks on multiple threads, and sums one partial total from each worker at the end. It also checks a few small known cases before evaluating the full target input.
The Python implementation simply launches the compiled C++ solver and returns its numeric output, so it inherits the same mathematics and the same performance characteristics. The Java implementation reproduces the same bounded integer search directly with integer arithmetic. No floating-point geometry is required anywhere in the pipeline.
Define
$$B(a)=\min\left(a-1,\left\lfloor\frac{n-a-1}{2}\right\rfloor,\left\lfloor\frac{a(n-a)}{a+n}\right\rfloor\right),$$
and
$$C(a,b)=\min\left(\left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor,\left\lfloor\frac{a^2-1}{b}\right\rfloor,n-a-b-1\right).$$
Then the number of candidate triples examined by the arithmetic search is
$$\sum_{a=1}^{n-3}\sum_{b=1}^{B(a)} \max\bigl(0,\ C(a,b)-b+1\bigr).$$
This is much smaller than a naive search over all positive quadruples \((a,b,c,d)\). A coarse worst-case bound is still \(O(n^3)\) time, because after eliminating \(d\) the algorithm is essentially a three-variable integer search, but the derived inequalities remove most impossible cases before the expensive integrality test is reached.
Each surviving candidate needs only a constant amount of arithmetic: a few multiplications, one divisibility test, and a couple of comparisons. Memory usage is \(O(1)\) for the sequential search, apart from the running total. The multithreaded C++ version adds only \(O(p)\) extra storage for \(p\) worker partial sums, so the method remains extremely light on memory.
Problem 557 verlangt \(S(n)\), also die Summe aller Gesamtflächen \(T\) gültiger Schneidekonfigurationen mit \(T \le n\). Nach Eliminierung der Geometrie lässt sich jeder Kandidat durch positive ganze Zahlen \((a,b,c,d)\) beschreiben, und die Bedingung \(b \le c\) verhindert, dass spiegelbildliche Fälle doppelt gezählt werden.
Die Gesamtfläche wird nicht numerisch angenähert, sondern durch eine exakte rationale Formel festgelegt. Damit wird die Aufgabe zu einer diophantischen Suche: Finde alle ganzzahligen Tripel \((a,b,c)\), für die diese Formel ganzzahlig wird, rekonstruiere \(d\), und addiere die entstehende Gesamtfläche \(T\).
Eine naive Suche über vier positive Variablen wäre für \(n=10000\) viel zu langsam. Der entscheidende Vorteil ist, dass die Geometrie zuerst auf Arithmetik reduziert wird und diese Arithmetik dann sehr scharfe Schranken für \(b\) und \(c\) liefert.
Sei \(S(n)\) die Summe aller zulässigen Gesamtflächen \(T\) mit \(T \le n\). Der Kern der Lösung besteht darin, das geometrische Problem in exakte ganzzahlige Bedingungen zu übersetzen.
Nachdem die beiden inneren Hilfsflächen algebraisch eliminiert sind, ergibt sich für die Gesamtfläche
$$T=\frac{a(a+b)(a+c)}{a^2-bc}.$$
Eine gültige Konfiguration muss also erfüllen
$$a^2-bc\gt 0,\qquad T\in \mathbb{Z}_{\ge 1},\qquad d=T-a-b-c\in \mathbb{Z}_{\ge 1},\qquad b\le c.$$
Genau das ist die zentrale Reduktion: Die geometrische Existenzbedingung wird zu einem rationalen Ausdruck mit Positivitäts- und Ganzzahligkeitsbedingungen.
Da die vier Teilflächen zusammen die ganze Dreiecksfläche ergeben, gilt
$$T=a+b+c+d.$$
Somit braucht \(d\) keine eigene Schleife; sobald \(a\), \(b\) und \(c\) feststehen, ist
$$d=T-a-b-c$$
vollständig bestimmt. Setzt man die Formel für \(T\) ein, erhält man außerdem
$$d=\frac{bc(2a+b+c)}{a^2-bc}.$$
Damit ist klar: Immer wenn \(a^2-bc\gt 0\) und \(T\) ganzzahlig ist, ist auch \(d\) automatisch positiv; und wegen \(d=T-a-b-c\) ist \(d\) dann ebenfalls ganzzahlig. Die Implementierungen prüfen \(d\gt 0\) trotzdem noch einmal explizit nach.
Mehrere einfache Ungleichungen verkleinern den Suchraum schon vor jedem Teilbarkeitstest.
Aus \(b\le c\) und \(bc\lt a^2\) folgt \(b^2\lt a^2\), also
$$b\le a-1.$$
Außerdem erhält man aus \(T=a+b+c+d\le n\), zusammen mit \(c\ge b\) und \(d\ge 1\),
$$a+2b+1\le n,$$
also
$$b\le \left\lfloor\frac{n-a-1}{2}\right\rfloor.$$
Eine dritte Schranke entsteht aus der Monotonie in \(c\). Für feste \(a\) und \(b\) ist \(T\) auf dem Bereich \(bc\lt a^2\) streng wachsend, denn
$$\frac{dT}{dc}=\frac{a^2(a+b)^2}{(a^2-bc)^2}\gt 0.$$
Das Minimum für dieses Paar liegt also bei \(c=b\):
$$T_{\min}=\frac{a(a+b)^2}{a^2-b^2}=\frac{a(a+b)}{a-b}.$$
Aus \(T_{\min}\le n\) folgt dann
$$b\le \left\lfloor\frac{a(n-a)}{a+n}\right\rfloor.$$
Die Implementierung verwendet das Minimum dieser drei oberen Schranken als effektiven Bereich für \(b\).
Nun seien \(a\) und \(b\) fest. Weil \(a^2-bc\gt 0\) gilt, darf man \(T\le n\) ohne Richtungswechsel umformen:
$$\frac{a(a+b)(a+c)}{a^2-bc}\le n.$$
Nach Zusammenfassen der \(c\)-Terme ergibt sich
$$c\bigl(a(a+b)+nb\bigr)\le a^2(n-a-b),$$
und damit
$$c\le \left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor.$$
Gleichzeitig werden zwei weitere Bedingungen benutzt. Aus \(bc\lt a^2\) folgt
$$c\le \left\lfloor\frac{a^2-1}{b}\right\rfloor.$$
Aus \(d\ge 1\) und \(T\le n\) folgt
$$c\le n-a-b-1.$$
Die endgültige obere Grenze für \(c\) ist das Minimum dieser drei Werte. Liegt dieses Minimum unter \(b\), dann gibt es für das aktuelle Paar \((a,b)\) überhaupt keinen zulässigen Wert von \(c\).
Für jedes überlebende Tripel \((a,b,c)\) wird geprüft, ob der Nenner den Zähler teilt:
$$a^2-bc \mid a(a+b)(a+c).$$
Dann ist
$$T=\frac{a(a+b)(a+c)}{a^2-bc}$$
eine ganze Zahl. Die Implementierungen behalten den Kandidaten nur dann, wenn außerdem \(T\le n\) gilt, berechnen
$$d=T-a-b-c,$$
und prüfen nochmals \(d\gt 0\). Jede gültige Konfiguration trägt ihre volle Gesamtfläche \(T\) zu \(S(n)\) bei.
Für dieses Paar sind die Schranken für \(b\) erfüllt, also wird \(c\) betrachtet. Die Bedingung \(T\le n\) liefert
$$c\le \left\lfloor\frac{20^2(55-20-2)}{20(20+2)+55\cdot 2}\right\rfloor=\left\lfloor\frac{13200}{550}\right\rfloor=24.$$
Die Bedingung \(bc\lt a^2\) ergibt
$$c\le \left\lfloor\frac{20^2-1}{2}\right\rfloor=199,$$
und aus \(d\ge 1\) zusammen mit \(T\le 55\) folgt
$$c\le 55-20-2-1=32.$$
Somit müssen nur \(2\le c\le 24\) geprüft werden. Am Randwert \(c=24\) erhält man
$$T=\frac{20\cdot 22\cdot 44}{20^2-2\cdot 24}=\frac{19360}{352}=55,$$
also
$$d=55-20-2-24=9.$$
Damit entsteht das gültige Tupel \((20,2,24,9)\). Ein weiteres gültiges Tupel mit derselben Gesamtfläche ist \((22,8,11,14)\); genau diese kleinen Kontrollfälle erscheinen auch in den Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen alle derselben arithmetischen Strategie. Zuerst wird über \(a\) iteriert, dann wird der zulässige Bereich für \(b\) bestimmt, danach für jedes verbleibende Paar \((a,b)\) der zulässige Bereich für \(c\), und erst dann erfolgt der Teilbarkeitstest, der über die Ganzzahligkeit von \(T\) entscheidet.
Die C++-Implementierung ist der eigentliche Hochleistungslöser. Für große \(n\) teilt sie den äußeren Bereich von \(a\) in Blöcke, verarbeitet diese auf mehreren Threads und addiert am Ende die Teilsummen der einzelnen Arbeiter. Vor der vollen Auswertung des Zielwerts werden außerdem einige kleine bekannte Fälle geprüft.
Die Python-Implementierung startet lediglich den kompilierten C++-Löser und gibt dessen numerische Ausgabe zurück; mathematisch verhält sie sich also identisch. Die Java-Implementierung bildet dieselbe beschränkte Ganzzahlsuche direkt mit Integer-Arithmetik nach. Fließkomma-Geometrie wird nirgends benötigt.
Definiere
$$B(a)=\min\left(a-1,\left\lfloor\frac{n-a-1}{2}\right\rfloor,\left\lfloor\frac{a(n-a)}{a+n}\right\rfloor\right),$$
und
$$C(a,b)=\min\left(\left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor,\left\lfloor\frac{a^2-1}{b}\right\rfloor,n-a-b-1\right).$$
Dann ist die Anzahl der tatsächlich untersuchten Kandidatentripel
$$\sum_{a=1}^{n-3}\sum_{b=1}^{B(a)} \max\bigl(0,\ C(a,b)-b+1\bigr).$$
Das ist wesentlich kleiner als eine naive Suche über alle positiven Vierertupel \((a,b,c,d)\). Eine grobe Worst-Case-Schranke bleibt zwar \(O(n^3)\), weil nach der Eliminierung von \(d\) im Wesentlichen drei ganzzahlige Variablen durchsucht werden, aber die hergeleiteten Ungleichungen entfernen den größten Teil der unmöglichen Fälle schon vor dem eigentlichen Ganzzahligkeitstest.
Jeder verbleibende Kandidat benötigt nur konstant viele arithmetische Operationen: einige Multiplikationen, einen Teilbarkeitstest und wenige Vergleiche. Der Speicherverbrauch ist für die sequentielle Variante \(O(1)\), abgesehen von der laufenden Summe. Die parallele C++-Version benötigt zusätzlich nur \(O(p)\) Speicher für \(p\) Teilsummen und bleibt damit sehr speicherschonend.
Problem 557, \(T \le n\) olan tüm geçerli kesme üçgeni konfigürasyonlarının toplam alanlarını toplayan \(S(n)\) değerini ister. Geometrik yapı sadeleştirildiğinde her aday pozitif \((a,b,c,d)\) tamsayılarıyla temsil edilir ve \(b \le c\) koşulu simetrik kopyaların iki kez sayılmasını engeller.
Toplam alan sayısal yaklaşıkla bulunmaz; tam bir rasyonel formülle belirlenir. Böylece görev bir Diofant aramasına dönüşür: formülü tamsayı yapan tüm \((a,b,c)\) üçlülerini bul, \(d\)'yi geri kazan ve çıkan toplam alan \(T\) değerlerini topla.
Dört pozitif değişken üzerinde saf tarama yapmak \(n=10000\) için çok pahalıdır. Çözümün başarısı, önce geometrik bilinmeyenleri yok edip sonra elde edilen eşitsizliklerle \(b\) ve \(c\) aralığını çok sert biçimde budamasından gelir.
\(S(n)\), \(T \le n\) koşulunu sağlayan tüm geçerli toplam alanların toplamı olsun. Ana adım, geometrik kısıtları tam tamsayı koşullarına dönüştürmektir.
İki yardımcı iç alan cebirsel olarak elimine edildiğinde toplam alan
$$T=\frac{a(a+b)(a+c)}{a^2-bc}$$
şeklinde yazılır. Dolayısıyla geçerli bir kesim için
$$a^2-bc\gt 0,\qquad T\in \mathbb{Z}_{\ge 1},\qquad d=T-a-b-c\in \mathbb{Z}_{\ge 1},\qquad b\le c$$
koşulları gerekir. Çözümün merkezi tam olarak budur: geometrik varlık testi, rasyonel bir ifade ile pozitiflik ve tamsayılık koşullarına indirgenir.
Dört parçanın alanları toplam üçgen alanını verdiği için
$$T=a+b+c+d$$
olur. Bu yüzden \(d\) için ayrı bir döngü gerekmez; \(a\), \(b\) ve \(c\) belli olduğunda
$$d=T-a-b-c$$
tamamen belirlenir. \(T\) formülü yerine konursa
$$d=\frac{bc(2a+b+c)}{a^2-bc}$$
elde edilir. Böylece \(a^2-bc\gt 0\) ve \(T\) tamsayı olduğunda \(d\) otomatik olarak pozitiftir; ayrıca \(d=T-a-b-c\) olduğundan tamsayıdır da. Uygulamalar yine de son güvenlik adımı olarak \(d\gt 0\) testini açıkça yapar.
Bölünebilirlik testine geçmeden önce birkaç basit eşitsizlik arama uzayını ciddi biçimde küçültür.
\(b\le c\) ve \(bc\lt a^2\) olduğundan \(b^2\lt a^2\) elde edilir; yani
$$b\le a-1.$$
Ayrıca \(T=a+b+c+d\le n\), \(c\ge b\) ve \(d\ge 1\) birlikte
$$a+2b+1\le n$$
verir; dolayısıyla
$$b\le \left\lfloor\frac{n-a-1}{2}\right\rfloor.$$
Üçüncü sınır, \(c\)'ye göre monotonluktan gelir. Sabit \(a\) ve \(b\) için \(bc\lt a^2\) bölgesinde
$$\frac{dT}{dc}=\frac{a^2(a+b)^2}{(a^2-bc)^2}\gt 0$$
olduğu için \(T\), \(c\) arttıkça kesin olarak artar. Bu nedenle o çift için en küçük toplam alan \(c=b\) noktasında oluşur:
$$T_{\min}=\frac{a(a+b)^2}{a^2-b^2}=\frac{a(a+b)}{a-b}.$$
\(T_{\min}\le n\) şartı da
$$b\le \left\lfloor\frac{a(n-a)}{a+n}\right\rfloor$$
sınırını verir. Uygulama bu üç üst sınırın minimumunu alarak \(b\) aralığını belirler.
Şimdi \(a\) ve \(b\) sabit olsun. \(a^2-bc\gt 0\) olduğu için \(T\le n\) eşitsizliği yön değiştirmeden düzenlenebilir:
$$\frac{a(a+b)(a+c)}{a^2-bc}\le n.$$
\(c\) içeren terimler toplanınca
$$c\bigl(a(a+b)+nb\bigr)\le a^2(n-a-b)$$
elde edilir; buradan
$$c\le \left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor$$
çıkar. Aynı anda iki ek kısıt daha kullanılır. \(bc\lt a^2\) şartından
$$c\le \left\lfloor\frac{a^2-1}{b}\right\rfloor,$$
\(d\ge 1\) ve \(T\le n\) koşullarından ise
$$c\le n-a-b-1$$
gelir. Son \(c\) üst sınırı bu üç değerin minimumudur. Eğer bu minimum \(b\)'den küçükse o \((a,b)\) çifti için uygun \(c\) yoktur.
Ayakta kalan her \((a,b,c)\) üçlüsü için paydanın paydayı bölüp bölmediği sınanır:
$$a^2-bc \mid a(a+b)(a+c).$$
Bölünebiliyorsa
$$T=\frac{a(a+b)(a+c)}{a^2-bc}$$
bir tamsayıdır. Uygulama ancak \(T\le n\) ise adayı tutar, sonra
$$d=T-a-b-c$$
hesaplanır ve \(d\gt 0\) doğrulanır. Geçerli her konfigürasyon \(S(n)\)'e kendi toplam alanı \(T\) kadar katkı yapar.
Bu çift için \(b\) sınırları uygundur; şimdi \(c\)'ye geçilir. \(T\le n\) eşitsizliği
$$c\le \left\lfloor\frac{20^2(55-20-2)}{20(20+2)+55\cdot 2}\right\rfloor=\left\lfloor\frac{13200}{550}\right\rfloor=24$$
sonucunu verir. \(bc\lt a^2\) sınırı
$$c\le \left\lfloor\frac{20^2-1}{2}\right\rfloor=199,$$
\(d\ge 1\) ve \(T\le 55\) koşulları ise
$$c\le 55-20-2-1=32$$
verir. Dolayısıyla yalnızca \(2\le c\le 24\) aralığı denenir. Uç noktada \(c=24\) için
$$T=\frac{20\cdot 22\cdot 44}{20^2-2\cdot 24}=\frac{19360}{352}=55,$$
ve dolayısıyla
$$d=55-20-2-24=9$$
elde edilir. Böylece \((20,2,24,9)\) geçerli bir dörtlüdür. Aynı toplam alana sahip bir başka geçerli dörtlü de \((22,8,11,14)\) olup bu küçük örnekler uygulamalardaki denetim değerleriyle uyumludur.
C++, Python ve Java uygulamaları aynı aritmetik stratejiyi izler. Önce \(a\) üzerinde dönerler, sonra uygun \(b\) aralığını bulurlar, ardından kalan her \((a,b)\) çifti için uygun \(c\) aralığını hesaplarlar ve ancak bundan sonra \(T\)'nin tamsayı olup olmadığını belirleyen bölünebilirlik testini uygularlar.
C++ uygulaması ana yüksek performanslı çözücüdür. Büyük \(n\) değerlerinde dıştaki \(a\) aralığını parçalara böler, bu parçaları birden fazla iş parçacığında hesaplar ve en sonda kısmi toplamları birleştirir. Tam hedef girişi çalıştırmadan önce birkaç küçük bilinen örneği de doğrular.
Python uygulaması derlenmiş C++ çözücüsünü çalıştırıp sayısal sonucu geri döndürür; dolayısıyla aynı matematiği ve aynı performans profilini miras alır. Java uygulaması ise aynı sınırlı tamsayı aramasını doğrudan tamsayı aritmetiğiyle yeniden kurar. Sürecin hiçbir noktasında kayan noktalı geometriye ihtiyaç yoktur.
Şunu tanımlayalım:
$$B(a)=\min\left(a-1,\left\lfloor\frac{n-a-1}{2}\right\rfloor,\left\lfloor\frac{a(n-a)}{a+n}\right\rfloor\right),$$
ve
$$C(a,b)=\min\left(\left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor,\left\lfloor\frac{a^2-1}{b}\right\rfloor,n-a-b-1\right).$$
Böylece gerçekten incelenen aday üçlü sayısı
$$\sum_{a=1}^{n-3}\sum_{b=1}^{B(a)} \max\bigl(0,\ C(a,b)-b+1\bigr)$$
olur. Bu sayı, tüm pozitif \((a,b,c,d)\) dörtlülerini kaba kuvvetle taramaktan çok daha küçüktür. Kaba bir üst sınır yine \(O(n^3)\) zamandır; çünkü \(d\) elimine edildikten sonra algoritma esasen üç değişkenli bir tamsayı aramasıdır. Ancak çıkarılan eşitsizlikler, pahalı bölünebilirlik kontrolüne ulaşmadan önce imkansız durumların büyük bölümünü eler.
İç döngüde kalan her aday yalnızca sabit sayıda aritmetik işlem ister: birkaç çarpma, bir bölünebilirlik testi ve birkaç karşılaştırma. Sıralı sürümün bellek kullanımı, biriken toplam dışında \(O(1)\)'dir. Çok iş parçacıklı C++ sürümü yalnızca \(p\) kısmi toplam için \(O(p)\) ek bellek kullanır; yani yöntem bellekte son derece hafiftir.
El problema 557 pide \(S(n)\), la suma de las áreas totales \(T\) de todas las configuraciones válidas de corte con \(T \le n\). Una vez eliminada la parte geométrica, cada candidato puede describirse mediante enteros positivos \((a,b,c,d)\), y la condición \(b \le c\) evita contar dos veces los casos simétricos.
El área total no se aproxima numéricamente: queda fijada por una fórmula racional exacta. Por eso la tarea se convierte en una búsqueda diofántica: hallar todos los tríos \((a,b,c)\) para los que la fórmula produce un entero, reconstruir \(d\) y sumar el valor resultante de \(T\).
Un barrido ingenuo sobre cuatro variables positivas sería demasiado lento para \(n=10000\). La clave es eliminar primero los grados de libertad geométricos y usar después las desigualdades resultantes para podar con fuerza la búsqueda aritmética.
Sea \(S(n)\) la suma de todas las áreas totales admisibles \(T\) con \(T \le n\). La idea central es reemplazar la geometría por condiciones exactas sobre enteros.
Después de eliminar algebraicamente las dos áreas interiores auxiliares, el área total queda determinada por
$$T=\frac{a(a+b)(a+c)}{a^2-bc}.$$
Así, un corte válido debe satisfacer
$$a^2-bc\gt 0,\qquad T\in \mathbb{Z}_{\ge 1},\qquad d=T-a-b-c\in \mathbb{Z}_{\ge 1},\qquad b\le c.$$
Ésta es la reducción fundamental: la existencia geométrica pasa a ser una expresión racional con restricciones de positividad e integridad.
Como las cuatro piezas suman el triángulo completo, se tiene
$$T=a+b+c+d.$$
Por tanto, no hace falta iterar sobre \(d\); una vez fijados \(a\), \(b\) y \(c\), queda determinado por
$$d=T-a-b-c.$$
Sustituyendo la fórmula de \(T\) se obtiene además
$$d=\frac{bc(2a+b+c)}{a^2-bc}.$$
De aquí se deduce que, siempre que \(a^2-bc\gt 0\) y \(T\) sea entero, \(d\) es automáticamente positivo; y como \(d=T-a-b-c\), también es entero. Aun así, las implementaciones vuelven a verificar \(d\gt 0\) como comprobación final.
Varias desigualdades sencillas reducen el espacio de búsqueda antes de probar divisibilidad.
Puesto que \(b\le c\) y \(bc\lt a^2\), se tiene \(b^2\lt a^2\), luego
$$b\le a-1.$$
Además, de \(T=a+b+c+d\le n\), junto con \(c\ge b\) y \(d\ge 1\), se obtiene
$$a+2b+1\le n,$$
así que
$$b\le \left\lfloor\frac{n-a-1}{2}\right\rfloor.$$
La tercera cota viene de la monotonía en \(c\). Para \(a\) y \(b\) fijos, \(T\) crece estrictamente con \(c\) en la región \(bc\lt a^2\), porque
$$\frac{dT}{dc}=\frac{a^2(a+b)^2}{(a^2-bc)^2}\gt 0.$$
Por eso el menor valor posible para ese par aparece en \(c=b\):
$$T_{\min}=\frac{a(a+b)^2}{a^2-b^2}=\frac{a(a+b)}{a-b}.$$
La condición \(T_{\min}\le n\) produce entonces
$$b\le \left\lfloor\frac{a(n-a)}{a+n}\right\rfloor.$$
La implementación toma el mínimo de estas tres cotas superiores y sólo recorre ese intervalo reducido de valores de \(b\).
Ahora fijemos \(a\) y \(b\). Como \(a^2-bc\gt 0\), la desigualdad \(T\le n\) puede reordenarse sin cambiar de sentido:
$$\frac{a(a+b)(a+c)}{a^2-bc}\le n.$$
Reuniendo los términos que contienen \(c\) se llega a
$$c\bigl(a(a+b)+nb\bigr)\le a^2(n-a-b),$$
y por tanto
$$c\le \left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor.$$
Se usan además dos restricciones adicionales. De \(bc\lt a^2\) se obtiene
$$c\le \left\lfloor\frac{a^2-1}{b}\right\rfloor.$$
De \(d\ge 1\) junto con \(T\le n\) se obtiene
$$c\le n-a-b-1.$$
La cota final para \(c\) es el mínimo de esos tres valores. Si ese mínimo es menor que \(b\), entonces no existe ningún \(c\) admisible para el par actual \((a,b)\).
Para cada trío superviviente \((a,b,c)\), las implementaciones comprueban si el denominador divide al numerador:
$$a^2-bc \mid a(a+b)(a+c).$$
Cuando esto ocurre,
$$T=\frac{a(a+b)(a+c)}{a^2-bc}$$
es un entero. El candidato sólo se conserva si además cumple \(T\le n\); después se calcula
$$d=T-a-b-c,$$
y se confirma que \(d\gt 0\). Cada configuración válida aporta su área total completa \(T\) a la suma \(S(n)\).
Para este par, las cotas sobre \(b\) se cumplen, así que pasamos a \(c\). La desigualdad procedente de \(T\le n\) da
$$c\le \left\lfloor\frac{20^2(55-20-2)}{20(20+2)+55\cdot 2}\right\rfloor=\left\lfloor\frac{13200}{550}\right\rfloor=24.$$
La condición \(bc\lt a^2\) da
$$c\le \left\lfloor\frac{20^2-1}{2}\right\rfloor=199,$$
y la exigencia \(d\ge 1\) junto con \(T\le 55\) da
$$c\le 55-20-2-1=32.$$
Por lo tanto, sólo hay que revisar \(2\le c\le 24\). En el extremo \(c=24\),
$$T=\frac{20\cdot 22\cdot 44}{20^2-2\cdot 24}=\frac{19360}{352}=55,$$
y entonces
$$d=55-20-2-24=9.$$
Eso produce la cuádrupla válida \((20,2,24,9)\). Otra cuádrupla válida con la misma área total es \((22,8,11,14)\), lo que coincide con las verificaciones pequeñas incluidas en las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma estrategia aritmética. Recorren \(a\), calculan el intervalo admisible para \(b\), calculan el intervalo admisible para \(c\) para cada par restante \((a,b)\), y sólo después hacen la prueba de divisibilidad que decide si \(T\) es entero.
La implementación en C++ es el solucionador principal de alto rendimiento. Para valores grandes de \(n\), divide el rango exterior de \(a\) en bloques, procesa esos bloques en varios hilos y suma al final un total parcial por trabajador. También comprueba algunos casos pequeños conocidos antes de evaluar la entrada objetivo completa.
La implementación en Python se limita a lanzar el solucionador C++ compilado y devolver su salida numérica, de modo que hereda exactamente la misma matemática y el mismo perfil de rendimiento. La implementación en Java reproduce la misma búsqueda entera acotada directamente con aritmética entera. En ningún punto se necesita geometría en coma flotante.
Definamos
$$B(a)=\min\left(a-1,\left\lfloor\frac{n-a-1}{2}\right\rfloor,\left\lfloor\frac{a(n-a)}{a+n}\right\rfloor\right),$$
y
$$C(a,b)=\min\left(\left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor,\left\lfloor\frac{a^2-1}{b}\right\rfloor,n-a-b-1\right).$$
Entonces el número de tríos candidatos realmente examinados es
$$\sum_{a=1}^{n-3}\sum_{b=1}^{B(a)} \max\bigl(0,\ C(a,b)-b+1\bigr).$$
Esto es mucho menor que una búsqueda ingenua sobre todas las cuádruplas positivas \((a,b,c,d)\). Una cota grosera de peor caso sigue siendo \(O(n^3)\) en tiempo, porque tras eliminar \(d\) el algoritmo es esencialmente una búsqueda entera en tres variables; sin embargo, las desigualdades derivadas eliminan la mayoría de los casos imposibles antes de llegar a la prueba de integridad.
Cada candidato que sobrevive requiere sólo una cantidad constante de aritmética: unas pocas multiplicaciones, una prueba de divisibilidad y un par de comparaciones. El uso de memoria es \(O(1)\) en la versión secuencial, aparte del acumulador del total. La versión paralela en C++ añade sólo \(O(p)\) memoria extra para \(p\) sumas parciales, así que el método sigue siendo muy ligero en memoria.
第 557 题要求计算 \(S(n)\)：把所有总面积 \(T \le n\) 的有效切割三角形配置的总面积 \(T\) 全部相加。将几何关系消去以后，每个候选配置都可以用正整数 \((a,b,c,d)\) 表示，而条件 \(b \le c\) 用来避免把左右对称的情形重复计算。
总面积不是通过数值近似得到的，而是由一个精确的有理式强制决定。因此问题本质上变成了一个整数搜索问题：找出所有能让该公式取整数值的 \((a,b,c)\)，再据此恢复 \(d\)，最后把对应的总面积 \(T\) 加入答案。
如果直接对四个正整数做朴素枚举，那么在 \(n=10000\) 时规模太大。真正可行的做法是先把几何部分完全化为代数，再利用所得不等式对 \(b\) 和 \(c\) 做强力剪枝，这也是实现能够跑通目标输入的关键原因。
记 \(S(n)\) 为所有满足 \(T \le n\) 的合法总面积之和。求解的核心是把几何约束翻译成精确的整数条件。
把两个辅助内部面积代数消元之后，总面积满足
$$T=\frac{a(a+b)(a+c)}{a^2-bc}.$$
因此，一个有效切割至少要满足
$$a^2-bc\gt 0,\qquad T\in \mathbb{Z}_{\ge 1},\qquad d=T-a-b-c\in \mathbb{Z}_{\ge 1},\qquad b\le c.$$
这一步就是整题的关键化简：几何存在性不再需要直接处理，而是转化成一个有理表达式加上正性与整除性条件。
四块区域的面积之和就是整个三角形的面积，所以
$$T=a+b+c+d.$$
这意味着不需要再单独枚举 \(d\)。一旦 \(a\)、\(b\)、\(c\) 固定，就有
$$d=T-a-b-c.$$
把 \(T\) 的表达式代回去，还能得到
$$d=\frac{bc(2a+b+c)}{a^2-bc}.$$
因此，只要 \(a^2-bc\gt 0\) 且 \(T\) 是整数，就可以立刻知道 \(d\) 必为正数；同时因为 \(d=T-a-b-c\)，它也必然是整数。实现里仍然显式检查一次 \(d\gt 0\)，只是为了把最终筛选写得更稳妥。
在做任何整除检验之前，可以先用几个简单但非常有效的不等式把搜索范围缩小很多。
由于 \(b\le c\) 且 \(bc\lt a^2\)，于是有 \(b^2\lt a^2\)，所以
$$b\le a-1.$$
另一方面，由 \(T=a+b+c+d\le n\)、\(c\ge b\) 和 \(d\ge 1\)，可得
$$a+2b+1\le n,$$
从而
$$b\le \left\lfloor\frac{n-a-1}{2}\right\rfloor.$$
第三个上界来自 \(T\) 对 \(c\) 的单调性。固定 \(a\) 和 \(b\) 时，在 \(bc\lt a^2\) 的区域内，
$$\frac{dT}{dc}=\frac{a^2(a+b)^2}{(a^2-bc)^2}\gt 0,$$
所以 \(T\) 随 \(c\) 严格递增。于是该 \((a,b)\) 对应的最小总面积出现在最小允许值 \(c=b\) 处，即
$$T_{\min}=\frac{a(a+b)^2}{a^2-b^2}=\frac{a(a+b)}{a-b}.$$
要使这个 \((a,b)\) 还有机会产生 \(T\le n\) 的合法配置，就必须满足 \(T_{\min}\le n\)。整理后得到
$$b\le \left\lfloor\frac{a(n-a)}{a+n}\right\rfloor.$$
实现会取这三个上界的最小值，作为 \(b\) 的最终扫描范围。
现在固定 \(a\) 和 \(b\)。由于 \(a^2-bc\gt 0\)，不等式 \(T\le n\) 可以直接移项而不改变方向：
$$\frac{a(a+b)(a+c)}{a^2-bc}\le n.$$
把含 \(c\) 的项收集到一起，得到
$$c\bigl(a(a+b)+nb\bigr)\le a^2(n-a-b),$$
因此
$$c\le \left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor.$$
此外还要同时利用另外两条约束。由 \(bc\lt a^2\) 得
$$c\le \left\lfloor\frac{a^2-1}{b}\right\rfloor.$$
由 \(d\ge 1\) 以及 \(T\le n\) 得
$$c\le n-a-b-1.$$
最终的 \(c\) 上界就是这三个值的最小者。如果这个最小值已经小于 \(b\)，那么当前 \((a,b)\) 下根本不存在可行的 \(c\)。
对每一个通过上界筛选的三元组 \((a,b,c)\)，实现都会检查分母是否整除分子：
$$a^2-bc \mid a(a+b)(a+c).$$
若整除成立，则
$$T=\frac{a(a+b)(a+c)}{a^2-bc}$$
是整数。程序只保留满足 \(T\le n\) 的候选，然后计算
$$d=T-a-b-c,$$
并再次确认 \(d\gt 0\)。每个合法配置对 \(S(n)\) 的贡献不是 \(1\)，而是它自己的总面积 \(T\)。
这个 \((a,b)\) 组合通过了前面对 \(b\) 的约束，于是继续求 \(c\) 的范围。由 \(T\le n\) 得到
$$c\le \left\lfloor\frac{20^2(55-20-2)}{20(20+2)+55\cdot 2}\right\rfloor=\left\lfloor\frac{13200}{550}\right\rfloor=24.$$
由 \(bc\lt a^2\) 得到
$$c\le \left\lfloor\frac{20^2-1}{2}\right\rfloor=199,$$
而由 \(d\ge 1\) 与 \(T\le 55\) 得到
$$c\le 55-20-2-1=32.$$
因此实际上只需要检查 \(2\le c\le 24\)。在端点 \(c=24\) 时，
$$T=\frac{20\cdot 22\cdot 44}{20^2-2\cdot 24}=\frac{19360}{352}=55,$$
于是
$$d=55-20-2-24=9.$$
这就得到一个合法四元组 \((20,2,24,9)\)。同样总面积为 \(55\) 的另一组合法参数是 \((22,8,11,14)\)，这与实现中使用的小规模校验数据完全一致。
C++、Python 和 Java 三个实现遵循的是同一套算术流程。它们先枚举 \(a\)，然后根据推导出的不等式求出 \(b\) 的有效范围，再对每个剩余的 \((a,b)\) 计算 \(c\) 的有效范围，最后才做真正决定合法性的整除检验。
C++ 实现是主要的高性能求解器。对于较大的 \(n\)，它把最外层的 \(a\) 区间切成若干块，交给多个线程并行计算，并在最后把每个线程的部分和相加。它在计算目标输入之前，还会先检查几个已知的小规模结果。
Python 实现本身并不重新实现核心算法，而是调用编译后的 C++ 求解器并解析最终数值输出，因此在数学逻辑和性能特征上都与 C++ 版本一致。Java 实现则直接用整数运算重写了同样的有界枚举过程。整个流程从头到尾都不需要任何浮点几何计算。
定义
$$B(a)=\min\left(a-1,\left\lfloor\frac{n-a-1}{2}\right\rfloor,\left\lfloor\frac{a(n-a)}{a+n}\right\rfloor\right),$$
以及
$$C(a,b)=\min\left(\left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor,\left\lfloor\frac{a^2-1}{b}\right\rfloor,n-a-b-1\right).$$
那么算术搜索真正检查的候选三元组数量就是
$$\sum_{a=1}^{n-3}\sum_{b=1}^{B(a)} \max\bigl(0,\ C(a,b)-b+1\bigr).$$
这个规模远小于对所有正整数四元组 \((a,b,c,d)\) 进行朴素枚举。虽然从粗略的最坏情况来看，时间复杂度仍可写成 \(O(n^3)\)，因为消去 \(d\) 之后本质上还是三重整数搜索，但上面推导出的界限会在进入整除判定之前就排除掉绝大多数不可能的情形。
内层循环中每个幸存候选只需要常数次算术操作：几次乘法、一次整除性检查以及少量比较。顺序版本的额外空间复杂度为 \(O(1)\)，除了累计和之外几乎不占额外内存。多线程 C++ 版本也只额外保存 \(p\) 个线程的部分和，因此附加空间是 \(O(p)\)，整体仍然非常节省内存。
В задаче 557 требуется вычислить \(S(n)\), то есть сумму полных площадей \(T\) всех допустимых конфигураций разрезания, для которых \(T \le n\). После устранения геометрической части каждый кандидат описывается положительными целыми \((a,b,c,d)\), а условие \(b \le c\) нужно для того, чтобы не считать зеркально симметричные случаи дважды.
Полная площадь не подбирается численно, а задаётся точной рациональной формулой. Поэтому задача превращается в диофантов поиск: нужно найти все тройки \((a,b,c)\), для которых эта формула даёт целое значение, восстановить \(d\) и прибавить соответствующую полную площадь \(T\).
Наивный перебор четырёх положительных переменных слишком дорог уже при \(n=10000\). Рабочее решение получается только потому, что геометрия сначала сводится к арифметике, а затем эта арифметика даёт очень сильные верхние оценки для \(b\) и \(c\).
Обозначим через \(S(n)\) сумму всех допустимых полных площадей \(T\), удовлетворяющих \(T \le n\). Основная идея состоит в том, чтобы заменить геометрические условия точными целочисленными соотношениями.
После алгебраического исключения двух вспомогательных внутренних площадей полная площадь выражается так:
$$T=\frac{a(a+b)(a+c)}{a^2-bc}.$$
Следовательно, допустимая конфигурация должна удовлетворять условиям
$$a^2-bc\gt 0,\qquad T\in \mathbb{Z}_{\ge 1},\qquad d=T-a-b-c\in \mathbb{Z}_{\ge 1},\qquad b\le c.$$
Это и есть главная редукция задачи: геометрическое условие существования заменяется рациональным выражением с условиями положительности и целочисленности.
Так как площади четырёх частей дают площадь всего треугольника, имеем
$$T=a+b+c+d.$$
Значит, отдельный цикл по \(d\) не нужен: после выбора \(a\), \(b\) и \(c\)
$$d=T-a-b-c$$
определяется однозначно. Если подставить формулу для \(T\), получаем ещё и
$$d=\frac{bc(2a+b+c)}{a^2-bc}.$$
Отсюда видно, что при \(a^2-bc\gt 0\) и целочисленном \(T\) величина \(d\) автоматически положительна; а так как \(d=T-a-b-c\), она автоматически является и целым числом. Тем не менее реализации дополнительно проверяют условие \(d\gt 0\) как последний защитный фильтр.
Ещё до проверки делимости несколько простых неравенств резко уменьшают пространство поиска.
Из \(b\le c\) и \(bc\lt a^2\) следует \(b^2\lt a^2\), а значит
$$b\le a-1.$$
Кроме того, из \(T=a+b+c+d\le n\), вместе с \(c\ge b\) и \(d\ge 1\), получаем
$$a+2b+1\le n,$$
то есть
$$b\le \left\lfloor\frac{n-a-1}{2}\right\rfloor.$$
Третья оценка появляется из монотонности по \(c\). При фиксированных \(a\) и \(b\) величина \(T\) строго возрастает по \(c\) в области \(bc\lt a^2\), поскольку
$$\frac{dT}{dc}=\frac{a^2(a+b)^2}{(a^2-bc)^2}\gt 0.$$
Следовательно, минимальное возможное значение для этой пары достигается при \(c=b\):
$$T_{\min}=\frac{a(a+b)^2}{a^2-b^2}=\frac{a(a+b)}{a-b}.$$
Требование \(T_{\min}\le n\) даёт ещё одну границу:
$$b\le \left\lfloor\frac{a(n-a)}{a+n}\right\rfloor.$$
Реализация берёт минимум из этих трёх верхних оценок и перебирает только такой укороченный диапазон значений \(b\).
Теперь зафиксируем \(a\) и \(b\). Так как \(a^2-bc\gt 0\), неравенство \(T\le n\) можно преобразовать без смены знака:
$$\frac{a(a+b)(a+c)}{a^2-bc}\le n.$$
Собирая все члены с \(c\), получаем
$$c\bigl(a(a+b)+nb\bigr)\le a^2(n-a-b),$$
откуда
$$c\le \left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor.$$
Одновременно используются ещё два ограничения. Из \(bc\lt a^2\) следует
$$c\le \left\lfloor\frac{a^2-1}{b}\right\rfloor.$$
Из \(d\ge 1\) и \(T\le n\) следует
$$c\le n-a-b-1.$$
Окончательная верхняя граница для \(c\) есть минимум этих трёх величин. Если этот минимум меньше \(b\), то для текущей пары \((a,b)\) допустимых значений \(c\) не существует.
Для каждой тройки \((a,b,c)\), пережившей отсечение, проверяется делимость знаменателя на числитель:
$$a^2-bc \mid a(a+b)(a+c).$$
Если делимость выполняется, то
$$T=\frac{a(a+b)(a+c)}{a^2-bc}$$
является целым числом. Кандидат сохраняется только при условии \(T\le n\), затем вычисляется
$$d=T-a-b-c,$$
и дополнительно подтверждается, что \(d\gt 0\). Каждая допустимая конфигурация вносит в \(S(n)\) не единицу, а всю свою полную площадь \(T\).
Для этой пары ограничения на \(b\) выполняются, значит можно переходить к \(c\). Из условия \(T\le n\) получаем
$$c\le \left\lfloor\frac{20^2(55-20-2)}{20(20+2)+55\cdot 2}\right\rfloor=\left\lfloor\frac{13200}{550}\right\rfloor=24.$$
Из \(bc\lt a^2\) следует
$$c\le \left\lfloor\frac{20^2-1}{2}\right\rfloor=199,$$
а из \(d\ge 1\) вместе с \(T\le 55\) следует
$$c\le 55-20-2-1=32.$$
Значит, достаточно проверить только \(2\le c\le 24\). На граничном значении \(c=24\) имеем
$$T=\frac{20\cdot 22\cdot 44}{20^2-2\cdot 24}=\frac{19360}{352}=55,$$
поэтому
$$d=55-20-2-24=9.$$
Так получается допустимая четвёрка \((20,2,24,9)\). Ещё одна допустимая четвёрка с той же полной площадью равна \((22,8,11,14)\), и это совпадает с малыми контрольными примерами, встроенными в реализации.
Реализации на C++, Python и Java следуют одной и той же арифметической схеме. Они перебирают \(a\), затем вычисляют допустимый диапазон для \(b\), потом для каждого оставшегося \((a,b)\) вычисляют допустимый диапазон для \(c\), и только после этого выполняют проверку делимости, от которой зависит целочисленность \(T\).
Реализация на C++ является основным высокопроизводительным решателем. Для больших \(n\) она разбивает внешний диапазон по \(a\) на блоки, обрабатывает эти блоки в нескольких потоках и затем суммирует частичные результаты. Перед полным запуском на целевом значении она также проверяет несколько известных маленьких примеров.
Реализация на Python просто запускает скомпилированный C++ решатель и возвращает его числовой вывод, поэтому наследует ту же математику и те же характеристики производительности. Реализация на Java воспроизводит тот же ограниченный целочисленный перебор напрямую с помощью целочисленной арифметики. Вычисления нигде не используют плавающую геометрию.
Определим
$$B(a)=\min\left(a-1,\left\lfloor\frac{n-a-1}{2}\right\rfloor,\left\lfloor\frac{a(n-a)}{a+n}\right\rfloor\right),$$
и
$$C(a,b)=\min\left(\left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor,\left\lfloor\frac{a^2-1}{b}\right\rfloor,n-a-b-1\right).$$
Тогда число реально проверяемых троек кандидатов равно
$$\sum_{a=1}^{n-3}\sum_{b=1}^{B(a)} \max\bigl(0,\ C(a,b)-b+1\bigr).$$
Это намного меньше, чем наивный перебор всех положительных четвёрок \((a,b,c,d)\). Грубая верхняя оценка по времени всё ещё равна \(O(n^3)\), потому что после исключения \(d\) остаётся по сути трёхмерный целочисленный поиск, однако выведенные неравенства отсекают большинство невозможных случаев ещё до дорогой проверки целочисленности.
Каждый выживший кандидат требует лишь постоянного числа арифметических операций: нескольких умножений, одной проверки делимости и нескольких сравнений. Память в последовательной версии равна \(O(1)\), если не считать накопителя суммы. Многопоточная версия на C++ добавляет только \(O(p)\) памяти для \(p\) частичных сумм, так что метод остаётся очень экономным по памяти.
تطلب المسألة 557 حساب \(S(n)\)، أي مجموع المساحات الكلية \(T\) لجميع تشكيلات قطع المثلث الصالحة التي تحقق \(T \le n\). بعد حذف الجزء الهندسي من الوصف يمكن تمثيل كل مرشح بأعداد صحيحة موجبة \((a,b,c,d)\)، ويُفرض الشرط \(b \le c\) حتى لا تُحسب الحالات المتناظرة مرتين.
المساحة الكلية لا تُستخرج بتقريب عددي، بل تُفرض بصيغة كسرية دقيقة. ولهذا تتحول المسألة إلى بحث ديوفانتي: نبحث عن كل ثلاثيات \((a,b,c)\) التي تجعل الصيغة عدداً صحيحاً، ثم نستعيد \(d\)، ثم نضيف القيمة الناتجة للمساحة الكلية \(T\).
الفحص الساذج لأربع متغيرات موجبة سيكون بطيئاً جداً عندما \(n=10000\). الفكرة الفعالة هي إزالة المجاهيل الهندسية أولاً، ثم استخدام المتراجحات الناتجة لتقليم مجال البحث في \(b\) و\(c\) تقليماً قوياً قبل أي اختبار للقسمة.
لنرمز بـ \(S(n)\) إلى مجموع كل المساحات الكلية المقبولة \(T\) التي تحقق \(T \le n\). جوهر الحل هو استبدال القيود الهندسية بشروط صحيحة دقيقة.
بعد التخلص جبرياً من مساحتيْن داخليتيْن مساعدتيْن تصبح المساحة الكلية مساوية لـ
$$T=\frac{a(a+b)(a+c)}{a^2-bc}.$$
ولكي يكون القطع صالحاً يجب أن تتحقق الشروط
$$a^2-bc\gt 0,\qquad T\in \mathbb{Z}_{\ge 1},\qquad d=T-a-b-c\in \mathbb{Z}_{\ge 1},\qquad b\le c.$$
هذه هي نقطة التحويل الأساسية في الحل: شرط الوجود الهندسي يتحول إلى تعبير كسري مع شرطَي الإيجابية والصحة العددية.
بما أن مساحات الأجزاء الأربعة تساوي مساحة المثلث كاملةً، فإن
$$T=a+b+c+d.$$
لذلك لا حاجة إلى حلقة مستقلة على \(d\)؛ فمتى عُرفت القيم \(a\) و\(b\) و\(c\)، فإن
$$d=T-a-b-c$$
يصبح محدداً تماماً. وبالتعويض عن \(T\) نحصل أيضاً على
$$d=\frac{bc(2a+b+c)}{a^2-bc}.$$
ومن هنا نرى أنه متى كان \(a^2-bc\gt 0\) وكانت \(T\) عدداً صحيحاً، فإن \(d\) يكون موجباً تلقائياً؛ وبما أن \(d=T-a-b-c\)، فهو عدد صحيح أيضاً. ومع ذلك تعيد التطبيقات فحص \(d\gt 0\) صراحةً كاختبار أمان أخير.
هناك عدة متراجحات بسيطة تقلص فضاء البحث قبل الوصول إلى اختبار القسمة.
فمن \(b\le c\) و\(bc\lt a^2\) نحصل على \(b^2\lt a^2\)، وبالتالي
$$b\le a-1.$$
وكذلك من \(T=a+b+c+d\le n\) مع \(c\ge b\) و\(d\ge 1\) نستنتج
$$a+2b+1\le n,$$
ومن ثم
$$b\le \left\lfloor\frac{n-a-1}{2}\right\rfloor.$$
أما الحد الثالث فيأتي من رتابة \(T\) بالنسبة إلى \(c\). عند تثبيت \(a\) و\(b\)، تكون \(T\) متزايدة تماماً مع \(c\) داخل المجال \(bc\lt a^2\)، لأن
$$\frac{dT}{dc}=\frac{a^2(a+b)^2}{(a^2-bc)^2}\gt 0.$$
إذن أصغر مساحة كلية ممكنة لهذا الزوج تحصل عند \(c=b\):
$$T_{\min}=\frac{a(a+b)^2}{a^2-b^2}=\frac{a(a+b)}{a-b}.$$
وفرض الشرط \(T_{\min}\le n\) يعطينا
$$b\le \left\lfloor\frac{a(n-a)}{a+n}\right\rfloor.$$
تأخذ التطبيقات أصغر هذه الحدود الثلاثة لتحديد المجال الفعلي الذي تُجرى عليه حلقة \(b\).
الآن نثبت \(a\) و\(b\). بما أن \(a^2-bc\gt 0\)، فيمكن إعادة ترتيب المتراجحة \(T\le n\) من دون تغيير اتجاهها:
$$\frac{a(a+b)(a+c)}{a^2-bc}\le n.$$
وبجمع الحدود التي تحتوي على \(c\) نحصل على
$$c\bigl(a(a+b)+nb\bigr)\le a^2(n-a-b),$$
ومنها
$$c\le \left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor.$$
وهناك قيدان إضافيان يُستخدمان في الوقت نفسه. من \(bc\lt a^2\) نحصل على
$$c\le \left\lfloor\frac{a^2-1}{b}\right\rfloor.$$
ومن \(d\ge 1\) مع \(T\le n\) نحصل على
$$c\le n-a-b-1.$$
الحد الأعلى النهائي لـ \(c\) هو أصغر هذه القيم الثلاث. فإذا كان هذا الأصغر أقل من \(b\)، فلا توجد أي قيمة صالحة لـ \(c\) مع الزوج الحالي \((a,b)\).
لكل ثلاثي \((a,b,c)\) يبقى بعد التقليص، يجري اختبار ما إذا كان المقام يقسم البسط:
$$a^2-bc \mid a(a+b)(a+c).$$
إذا تحقق ذلك، فإن
$$T=\frac{a(a+b)(a+c)}{a^2-bc}$$
يكون عدداً صحيحاً. ولا يُقبل المرشح إلا إذا كان أيضاً \(T\le n\)، ثم تُحسب
$$d=T-a-b-c,$$
ويُتأكد مرة أخرى من أن \(d\gt 0\). كل تشكيل صالح يضيف إلى \(S(n)\) المساحة الكلية الكاملة \(T\)، لا مجرد وحدة واحدة.
بالنسبة إلى هذا الزوج فإن حدود \(b\) كلها متحققة، لذا ننتقل إلى \(c\). المتراجحة المستخرجة من \(T\le n\) تعطي
$$c\le \left\lfloor\frac{20^2(55-20-2)}{20(20+2)+55\cdot 2}\right\rfloor=\left\lfloor\frac{13200}{550}\right\rfloor=24.$$
أما شرط \(bc\lt a^2\) فيعطي
$$c\le \left\lfloor\frac{20^2-1}{2}\right\rfloor=199,$$
ويعطي الشرط \(d\ge 1\) مع \(T\le 55\)
$$c\le 55-20-2-1=32.$$
إذن لا يلزم فحص إلا المجال \(2\le c\le 24\). عند الطرف \(c=24\) نحصل على
$$T=\frac{20\cdot 22\cdot 44}{20^2-2\cdot 24}=\frac{19360}{352}=55,$$
ومن ثم
$$d=55-20-2-24=9.$$
وهكذا نحصل على الرباعية الصالحة \((20,2,24,9)\). وهناك رباعية صالحة أخرى لها نفس المساحة الكلية وهي \((22,8,11,14)\)، وهذا يطابق حالات التحقق الصغيرة المضمنة في التطبيقات.
تتبع تطبيقات C++ وPython وJava الإستراتيجية الحسابية نفسها. فهي تدور أولاً على \(a\)، ثم تحسب المجال المسموح لـ \(b\)، ثم تحسب المجال المسموح لـ \(c\) لكل زوج متبقٍ \((a,b)\)، وبعد ذلك فقط تجري اختبار القسمة الذي يحدد ما إذا كانت \(T\) عدداً صحيحاً.
تطبيق C++ هو الحل الرئيسي عالي الأداء. عند القيم الكبيرة لـ \(n\) يقسم المجال الخارجي الخاص بـ \(a\) إلى كتل، ويعالج هذه الكتل على عدة خيوط، ثم يجمع مجموعاً جزئياً واحداً من كل عامل في النهاية. كما أنه يفحص بعض الحالات الصغيرة المعروفة قبل تشغيل الإدخال الهدف الكامل.
أما تطبيق Python فيقوم فقط بتشغيل محلل C++ المترجم وإرجاع خرجه العددي، ولذلك يرث الرياضيات نفسها وخصائص الأداء نفسها. ويعيد تطبيق Java بناء البحث الصحيح المقيَّد نفسه مباشرةً باستخدام الحسابات الصحيحة. ولا يحتاج أي جزء من السلسلة إلى هندسة فاصلة عائمة.
لنعرّف
$$B(a)=\min\left(a-1,\left\lfloor\frac{n-a-1}{2}\right\rfloor,\left\lfloor\frac{a(n-a)}{a+n}\right\rfloor\right),$$
وكذلك
$$C(a,b)=\min\left(\left\lfloor\frac{a^2(n-a-b)}{a(a+b)+nb}\right\rfloor,\left\lfloor\frac{a^2-1}{b}\right\rfloor,n-a-b-1\right).$$
عندئذ يكون عدد الثلاثيات المرشحة التي تُفحص فعلياً هو
$$\sum_{a=1}^{n-3}\sum_{b=1}^{B(a)} \max\bigl(0,\ C(a,b)-b+1\bigr).$$
وهذا أصغر بكثير من تعداد جميع الرباعيات الموجبة \((a,b,c,d)\) بطريقة ساذجة. أما الحد الأسوأ الخشن للزمن فيبقى \(O(n^3)\)، لأنه بعد حذف \(d\) يصبح لدينا عملياً بحث صحيح على ثلاثة متغيرات، لكن المتراجحات المستنتجة تستبعد معظم الحالات المستحيلة قبل الوصول إلى اختبار الصحة العددية المكلف.
كل مرشح يبقى في الحلقة الداخلية يحتاج فقط إلى عدد ثابت من العمليات الحسابية: عدة عمليات ضرب، واختبار قسمة واحد، وبعض المقارنات. استهلاك الذاكرة في النسخة التسلسلية هو \(O(1)\) باستثناء المجمع الكلي. وتضيف النسخة متعددة الخيوط في C++ ذاكرة إضافية مقدارها \(O(p)\) فقط لتخزين المجاميع الجزئية الخاصة بـ \(p\) من العاملين، لذلك تبقى الطريقة مقتصدة جداً في الذاكرة.