We are looking for the perimeter \(p \le 1000\) that produces the largest number of integer right triangles. A valid solution is a triple \((a,b,c)\) with \(1 \le a \le b \lt c\), satisfying
$$a^2+b^2=c^2,\qquad a+b+c=p.$$
The C++, Python, and Java implementations all solve this by scanning the finite set of possible leg pairs, detecting when the hypotenuse is integral, counting how many times each perimeter occurs, and then returning the perimeter whose count is largest.
The central idea is that we do not need a separate search for each perimeter. Instead, we can enumerate all possible ordered pairs of legs that could appear in any triangle with perimeter at most 1000, and let each valid triangle contribute to the counter of its own perimeter.
Order the two legs so that \(a \le b\). Since \(a\) is then the smallest side and the perimeter is at most 1000, we have
$$3a \le a+b+c \le 1000,$$
so necessarily
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor.$$
Once \(a\) is fixed, the inequality \(b \le c\) gives
$$a+2b \le a+b+c \le 1000,$$
hence
$$a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor.$$
So every admissible triangle must lie in the finite lattice region
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor.$$
Those are exactly the loop bounds used by the implementations.
For a chosen pair \((a,b)\), the Pythagorean condition determines the hypotenuse completely:
$$c^2=a^2+b^2,\qquad c=\sqrt{a^2+b^2}.$$
Therefore the pair \((a,b)\) produces an integer right triangle if and only if \(a^2+b^2\) is a perfect square. This is the key mathematical test in the code. The implementations compute the integer square root of \(a^2+b^2\) and accept the candidate exactly when squaring that root recovers the original value.
If the test fails, the pair contributes nothing. If it succeeds, the triangle is forced: there is one and only one integer value of \(c\) attached to that pair.
Whenever \(c\) is integral, the perimeter is simply
$$p=a+b+c.$$
Instead of solving a separate Diophantine problem for each \(p\), we maintain a counter for every possible perimeter from 0 through 1000. Each valid triple increments the counter belonging to its own perimeter. After all candidate pairs have been tested, the answer is the perimeter whose counter is maximal.
This converts the original question into a histogram problem: scan once through the bounded search region, classify every valid triangle by its perimeter, then choose the busiest bucket.
The ordering \(a \le b\) prevents the same triangle from being counted twice as \((a,b,c)\) and \((b,a,c)\). Also, once \(a\) and \(b\) are positive, the inequality \(c \gt b\) is automatic because
$$c^2=a^2+b^2>b^2.$$
Conversely, every integer right triangle with perimeter at most 1000 satisfies the derived bounds on \(a\) and \(b\), so its ordered leg pair must appear somewhere in the scan. That proves two things at once:
no valid triangle is missed, and no valid triangle is counted twice.
The perimeter \(120\) is a useful checkpoint because it has exactly three integer right-triangle solutions. In the search region, the relevant leg pairs are
$$ (20,48),\qquad (24,45),\qquad (30,40). $$
For these pairs, the perfect-square test succeeds:
$$20^2+48^2=52^2,\qquad 24^2+45^2=51^2,\qquad 30^2+40^2=50^2.$$
Each one contributes once to the counter for
$$p=20+48+52=24+45+51=30+40+50=120.$$
No other ordered pair in the allowed region produces perimeter 120, so the count for \(p=120\) is 3. That is why the implementations use 120 as a checkpoint input.
The C++, Python, and Java implementations all follow the same structure. First they allocate an array indexed by perimeter; each entry stores how many valid right triangles have been found for that perimeter. Then they run the two nested loops over the bounded region for \((a,b)\).
For each candidate pair, the implementation forms \(a^2+b^2\), takes its integer square root, and checks whether the square-root test is exact. If it is, the code computes the corresponding perimeter \(p=a+b+c\) and increments that perimeter's counter, provided \(p\) is still within the requested bound.
After enumeration is complete, the implementation scans the counter array from left to right and keeps the perimeter with the largest count seen so far. Because the update happens only when a strictly larger count appears, ties are resolved in favor of the first perimeter reaching that maximum. The shared checkpoint verifies that when the upper bound is 120, the returned perimeter is 120.
If the perimeter bound is written as \(L\), the algorithm examines all integer pairs in
$$1 \le a \le \left\lfloor \frac{L}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{L-a}{2} \right\rfloor.$$
The number of tested pairs is therefore
$$\sum_{a=1}^{\lfloor L/3 \rfloor}\left(\left\lfloor \frac{L-a}{2} \right\rfloor-a+1\right)=O(L^2).$$
For \(L=1000\), that is about \(8.3\times 10^4\) candidate pairs, which is small. Each iteration performs constant-size arithmetic together with one integer square-root computation, and the final scan over the perimeter counters adds only \(O(L)\) time. Memory usage is \(O(L)\) because the only growing data structure is the perimeter-count array.
Gesucht ist der Umfang \(p \le 1000\), für den es die meisten ganzzahligen rechtwinkligen Dreiecke gibt. Eine gültige Lösung ist ein Tripel \((a,b,c)\) mit \(1 \le a \le b \lt c\) und
$$a^2+b^2=c^2,\qquad a+b+c=p.$$
Die C++-, Python- und Java-Implementierungen erzeugen diese Dreiecke nicht über eine Zahlentheorie-Parametrisierung, sondern durchsuchen alle zulässigen Beinpaare, prüfen, ob die Hypotenuse ganzzahlig ist, zählen die entstehenden Umfänge und wählen am Ende den Umfang mit dem größten Zähler.
Der Kern der Lösung besteht darin, das Problem in eine endliche Zählaufgabe über geordnete Beinpaare \((a,b)\) zu verwandeln. Statt jeden Umfang separat zu behandeln, wird der gesamte relevante Suchraum einmal vollständig durchlaufen.
Wir ordnen die Katheten so, dass \(a \le b\) gilt. Dann ist \(a\) die kleinste Seite, also folgt aus \(a+b+c \le 1000\)
$$3a \le a+b+c \le 1000,$$
und damit
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor.$$
Ist \(a\) fest, dann liefert \(b \le c\) die Abschätzung
$$a+2b \le a+b+c \le 1000,$$
also
$$a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor.$$
Jedes zulässige Dreieck liegt daher im endlichen Gitterbereich
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor,$$
und genau diese Grenzen verwendet der Code.
Zu einem festen Paar \((a,b)\) ist die Hypotenuse eindeutig durch die Gleichung
$$c^2=a^2+b^2,\qquad c=\sqrt{a^2+b^2}$$
gegeben. Es bleibt also nur eine Frage: Ist \(a^2+b^2\) ein Quadrat? Wenn nein, gibt es kein ganzzahliges rechtwinkliges Dreieck mit diesen Katheten. Wenn ja, ist das gesamte Tripel \((a,b,c)\) festgelegt.
Genau das testen die Implementierungen. Sie berechnen die ganzzahlige Quadratwurzel von \(a^2+b^2\) und akzeptieren das Paar genau dann, wenn das Quadrat dieser Wurzel wieder den ursprünglichen Wert ergibt.
Ist \(c\) ganzzahlig, dann gehört das Tripel zum Umfang
$$p=a+b+c.$$
Statt für jeden Umfang eine eigene diophantische Gleichung zu lösen, speichert man für jeden möglichen Umfang von 0 bis 1000 einfach die Anzahl der gefundenen Dreiecke. Jedes gültige Tripel erhöht genau einen Zähler, nämlich den seines Umfangs.
Am Ende ist die Aufgabe damit auf einen Histogramm-Schritt reduziert: Der gesuchte Umfang ist genau der Index mit der größten Häufigkeit.
Die Bedingung \(a \le b\) verhindert, dass dasselbe Dreieck zweimal als \((a,b,c)\) und \((b,a,c)\) gezählt wird. Außerdem ist \(c \gt b\) für positive rechtwinklige Dreiecke automatisch erfüllt, denn
$$c^2=a^2+b^2>b^2.$$
Umgekehrt erfüllt jedes ganzzahlige rechtwinklige Dreieck mit Umfang höchstens 1000 die hergeleiteten Schranken für \(a\) und \(b\). Sein geordnetes Kathetenpaar taucht also sicher im Suchraum auf.
Daraus folgt: Kein gültiges Dreieck wird ausgelassen, und kein gültiges Dreieck wird doppelt gezählt.
Der Umfang \(120\) ist ein nützlicher Kontrollfall, weil er genau drei Lösungen besitzt. Im Suchraum erscheinen die relevanten Kathetenpaare als
$$ (20,48),\qquad (24,45),\qquad (30,40). $$
Für diese Paare klappt der Quadrat-Test:
$$20^2+48^2=52^2,\qquad 24^2+45^2=51^2,\qquad 30^2+40^2=50^2.$$
Alle drei führen also zum selben Umfang
$$p=20+48+52=24+45+51=30+40+50=120.$$
Es gibt in der zulässigen Region kein weiteres geordnetes Paar, das ebenfalls Umfang 120 erzeugt. Deshalb ist der Zähler für 120 gleich 3, und genau darum wird 120 in den Implementierungen als Prüfwert verwendet.
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst legen sie ein Array an, das für jeden Umfang speichert, wie viele gültige rechtwinklige Dreiecke bereits gefunden wurden. Danach durchlaufen sie die zwei geschachtelten Schleifen über den hergeleiteten Bereich für \((a,b)\).
Für jedes Kandidatenpaar berechnet die Implementierung \(a^2+b^2\), zieht daraus die ganzzahlige Quadratwurzel und prüft, ob der Test exakt aufgeht. Falls ja, wird der Umfang \(p=a+b+c\) gebildet und der zugehörige Zähler erhöht, sofern \(p\) noch innerhalb der vorgegebenen Grenze liegt.
Nach der Enumeration wird das Zähler-Array von links nach rechts durchsucht. Der aktuelle beste Umfang wird nur dann ersetzt, wenn ein strikt größerer Zähler gefunden wird. Dadurch bleiben Gleichstände beim zuerst erreichten Umfang. Die gemeinsame Prüfung bestätigt, dass bei Obergrenze 120 der zurückgegebene Umfang ebenfalls 120 ist.
Schreibt man die Umfangsgrenze als \(L\), dann untersucht der Algorithmus alle ganzzahligen Paare in
$$1 \le a \le \left\lfloor \frac{L}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{L-a}{2} \right\rfloor.$$
Die Anzahl der getesteten Paare ist damit
$$\sum_{a=1}^{\lfloor L/3 \rfloor}\left(\left\lfloor \frac{L-a}{2} \right\rfloor-a+1\right)=O(L^2).$$
Für \(L=1000\) sind das ungefähr \(8{,}3\times 10^4\) Kandidatenpaare. Pro Iteration fallen nur Arithmetik fester Größe und eine ganzzahlige Quadratwurzel an; die abschließende Suche nach dem größten Zähler kostet zusätzlich \(O(L)\). Der Speicherverbrauch ist \(O(L)\), weil im Wesentlichen nur das Umfangs-Array wächst.
Aranan şey, \(p \le 1000\) koşulu altında en fazla tamsayılı dik üçgen üreten çevredir. Geçerli bir çözüm,
$$a^2+b^2=c^2,\qquad a+b+c=p$$
eşitliklerini sağlayan ve \(1 \le a \le b \lt c\) koşulunu taşıyan bir \((a,b,c)\) üçlüsüdür.
C++, Python ve Java uygulamaları aynı fikri izler: olası dik kenar çiftlerini tarar, hipotenüsün tam sayı olup olmadığını denetler, çıkan çevreleri sayar ve sonunda sayımı en büyük olan çevreyi döndürür.
Bu problemde her çevre için ayrı ayrı denklem çözmeye gerek yoktur. Bunun yerine, çevresi en fazla 1000 olan bütün aday dik üçgenlerin kapsandığı sonlu \((a,b)\) bölgesi bir kez taranır. Her geçerli üçgen kendi çevresinin sayacına bir katkı yapar.
Dik kenarları \(a \le b\) olacak şekilde sıralayalım. Böylece \(a\) en küçük kenar olur. Çevre en fazla 1000 olduğundan
$$3a \le a+b+c \le 1000,$$
ve buradan
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor$$
elde edilir. \(a\) sabitken \(b \le c\) eşitsizliği de
$$a+2b \le a+b+c \le 1000$$
verir; dolayısıyla
$$a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor.$$
Sonuç olarak her geçerli üçgen şu sonlu kafes bölgesinde yer almak zorundadır:
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor.$$
Uygulamalardaki iki iç içe döngü tam olarak bu bölgeyi dolaşır.
Bir \((a,b)\) çifti seçildiğinde hipotenüs artık tamamen belirlenmiştir:
$$c^2=a^2+b^2,\qquad c=\sqrt{a^2+b^2}.$$
Bu yüzden asıl test şudur: \(a^2+b^2\) bir tam kare mi? Değilse bu çift hiçbir tamsayılı dik üçgen üretmez. Eğer tam kareyse ilgili \(c\) değeri tektir ve üçgen doğrudan belirlenmiş olur.
Koddaki temel matematiksel değişmez tam da budur. Her aday çift için \(a^2+b^2\) hesaplanır, tam sayı karekök alınır ve karekök tekrar karesine yükseltildiğinde başlangıç değeri veriyorsa çift kabul edilir.
\(c\) tam sayı olduğunda çevre
$$p=a+b+c$$
olur. Böylece her geçerli üçgen, çevresine karşılık gelen sayaçta tam bir artış üretir. 0 ile 1000 arasındaki her çevre için bir sayaç tutmak, problemi tek bir geçişte bütün çevreleri aynı anda değerlendiren bir histogram problemine dönüştürür.
Tarama bittikten sonra yapılacak tek şey, sayacı en büyük olan çevreyi seçmektir.
\(a \le b\) koşulu, aynı üçgenin \((a,b,c)\) ve \((b,a,c)\) biçimlerinde iki kez sayılmasını engeller. Ayrıca \(a\) ve \(b\) pozitif olduğunda \(c \gt b\) zaten kendiliğinden doğrudur; çünkü
$$c^2=a^2+b^2>b^2.$$
Ters yönde bakarsak, çevresi en fazla 1000 olan her tamsayılı dik üçgen, yukarıda türetilen \(a\) ve \(b\) sınırlarını sağlamak zorundadır. O halde sıralanmış dik kenar çifti tarama sırasında mutlaka bir yerde görülür.
Demek ki yöntem hem eksiksizdir hem de çift sayım yapmaz.
\(120\) iyi bir kontrol örneğidir; çünkü tam olarak üç çözümü vardır. Tarama bölgesinde ilgili dik kenar çiftleri
$$ (20,48),\qquad (24,45),\qquad (30,40) $$
şeklindedir. Bu çiftler için tam kare testi başarılı olur:
$$20^2+48^2=52^2,\qquad 24^2+45^2=51^2,\qquad 30^2+40^2=50^2.$$
Dolayısıyla hepsi aynı çevreye katkı yapar:
$$p=20+48+52=24+45+51=30+40+50=120.$$
İzin verilen bölgede çevresi 120 olan başka sıralı bir dik kenar çifti yoktur. Bu nedenle 120'nin sayacı 3 olur ve uygulamalardaki kontrol bunun üzerine kuruludur.
C++, Python ve Java uygulamaları aynı akışı izler. Önce her çevre için kaç geçerli dik üçgen bulunduğunu saklayacak bir dizi oluşturulur. Sonra \((a,b)\) için türetilen bölge iki iç içe döngüyle dolaşılır.
Her aday çiftte \(a^2+b^2\) hesaplanır, bunun tam sayı karekökü alınır ve testin kesin olup olmadığı kontrol edilir. Eğer test başarılıysa \(p=a+b+c\) bulunur ve bu çevre üst sınırı aşmıyorsa ilgili sayaç bir artırılır.
Tarama tamamlandıktan sonra sayaç dizisi soldan sağa okunur ve o ana kadar görülen en büyük sayımı veren çevre saklanır. Güncelleme yalnızca daha büyük bir sayı görüldüğünde yapıldığı için eşitlik durumunda maksimuma ilk ulaşan çevre korunur. Ortak kontrol, üst sınır 120 iken dönen değerin de 120 olduğunu doğrular.
Üst sınır \(L\) ile gösterilirse algoritma şu bölgedeki bütün tam sayı çiftlerini inceler:
$$1 \le a \le \left\lfloor \frac{L}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{L-a}{2} \right\rfloor.$$
Bu yüzden denenen aday sayısı
$$\sum_{a=1}^{\lfloor L/3 \rfloor}\left(\left\lfloor \frac{L-a}{2} \right\rfloor-a+1\right)=O(L^2)$$
olur. \(L=1000\) için bu sayı yaklaşık \(8.3\times 10^4\) aday çifttir. Her adımda sabit boyutlu aritmetik ve bir tam sayı karekök işlemi vardır; en sonda çevre sayaçları üzerinden yapılan tarama da yalnızca \(O(L)\) zaman ekler. Bellek kullanımı \(O(L)\) düzeyindedir, çünkü büyüyen tek yapı çevre sayaç dizisidir.
Buscamos el perímetro \(p \le 1000\) que genera la mayor cantidad de triángulos rectángulos con lados enteros. Una solución válida es una terna \((a,b,c)\) con \(1 \le a \le b \lt c\) y
$$a^2+b^2=c^2,\qquad a+b+c=p.$$
Las implementaciones en C++, Python y Java resuelven esto recorriendo todos los pares posibles de catetos, comprobando si la hipotenusa resulta entera, acumulando un conteo por perímetro y, al final, eligiendo el perímetro con mayor frecuencia.
La idea principal es evitar un análisis independiente para cada perímetro. En su lugar, se recorre una sola vez toda la región finita de pares \((a,b)\) que pueden aparecer en un triángulo rectángulo con perímetro a lo sumo 1000, y cada triángulo válido aporta una unidad al contador de su propio perímetro.
Ordenamos los catetos de modo que \(a \le b\). Entonces \(a\) es el lado más pequeño, y del hecho de que \(a+b+c \le 1000\) se obtiene
$$3a \le a+b+c \le 1000,$$
por lo que necesariamente
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor.$$
Una vez fijado \(a\), la desigualdad \(b \le c\) implica
$$a+2b \le a+b+c \le 1000,$$
y por tanto
$$a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor.$$
Así, todo triángulo admisible aparece dentro de la región finita
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor,$$
que coincide exactamente con los límites de los bucles en la implementación.
Dado un par \((a,b)\), la condición pitagórica fija completamente a \(c\):
$$c^2=a^2+b^2,\qquad c=\sqrt{a^2+b^2}.$$
Por tanto, la única comprobación real es si \(a^2+b^2\) es un cuadrado perfecto. Si no lo es, el par no produce ningún triángulo rectángulo entero. Si sí lo es, el valor de \(c\) queda determinado de manera única.
Ese es el test matemático central del código. Las implementaciones calculan la raíz cuadrada entera de \(a^2+b^2\) y aceptan el candidato exactamente cuando al volver a elevarla al cuadrado se recupera el mismo número.
Cuando \(c\) es entero, el perímetro asociado es
$$p=a+b+c.$$
En vez de resolver una ecuación diofántica separada para cada \(p\), se mantiene un contador para cada perímetro entre 0 y 1000. Cada triángulo válido incrementa el contador correspondiente a su propio perímetro.
De esta forma, el problema original se convierte en un histograma: después del recorrido, la respuesta es simplemente el índice cuyo contador es máximo.
La condición \(a \le b\) evita contar el mismo triángulo dos veces como \((a,b,c)\) y \((b,a,c)\). Además, para catetos positivos se tiene automáticamente \(c \gt b\), porque
$$c^2=a^2+b^2>b^2.$$
En sentido contrario, cualquier triángulo rectángulo entero con perímetro a lo sumo 1000 satisface necesariamente las cotas deducidas para \(a\) y \(b\). Por eso, su par ordenado de catetos aparecerá forzosamente en el barrido.
Esto demuestra que la enumeración es completa y que cada solución se cuenta una sola vez.
El perímetro \(120\) es un buen caso de control porque tiene exactamente tres soluciones. En la región de búsqueda aparecen los pares de catetos
$$ (20,48),\qquad (24,45),\qquad (30,40). $$
Para ellos, la prueba de cuadrado perfecto funciona:
$$20^2+48^2=52^2,\qquad 24^2+45^2=51^2,\qquad 30^2+40^2=50^2.$$
Cada uno aporta una unidad al mismo perímetro:
$$p=20+48+52=24+45+51=30+40+50=120.$$
No existe otro par ordenado en la región permitida que produzca también perímetro 120. Por eso el contador de \(120\) vale 3 y ese valor sirve como verificación en las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma estructura. Primero reservan un arreglo indexado por perímetro; cada entrada almacena cuántos triángulos rectángulos válidos se han encontrado con ese perímetro. Luego ejecutan los dos bucles anidados sobre la región acotada de \((a,b)\).
Para cada par candidato calculan \(a^2+b^2\), obtienen su raíz cuadrada entera y comprueban si el test es exacto. Si lo es, calculan \(p=a+b+c\) e incrementan el contador correspondiente, siempre que ese perímetro siga dentro del límite pedido.
Después del barrido, el código recorre el arreglo de contadores de izquierda a derecha y conserva el perímetro con la cuenta más alta vista hasta ese momento. Como la actualización solo ocurre cuando aparece una cuenta estrictamente mayor, los empates se resuelven a favor del primer perímetro que alcanza ese máximo. La comprobación compartida confirma que, con cota 120, el resultado devuelto es 120.
Si denotamos por \(L\) la cota del perímetro, el algoritmo examina todos los pares enteros en
$$1 \le a \le \left\lfloor \frac{L}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{L-a}{2} \right\rfloor.$$
El número de candidatos probados es entonces
$$\sum_{a=1}^{\lfloor L/3 \rfloor}\left(\left\lfloor \frac{L-a}{2} \right\rfloor-a+1\right)=O(L^2).$$
Para \(L=1000\), eso equivale a aproximadamente \(8.3\times 10^4\) pares candidatos. Cada iteración usa aritmética de tamaño fijo y una raíz cuadrada entera, y el barrido final sobre los contadores añade solo \(O(L)\) tiempo. El consumo de memoria es \(O(L)\), porque la única estructura que crece con la entrada es el arreglo de conteos por perímetro.
我们要求的是在 \(p \le 1000\) 的范围内，哪个周长 \(p\) 能产生最多个整边直角三角形。一个有效解是三元组 \((a,b,c)\)，满足
$$a^2+b^2=c^2,\qquad a+b+c=p,$$
并且 \(1 \le a \le b \lt c\)。C++、Python 和 Java 实现都采用同一个思路：枚举所有可能的直角边对，判断对应斜边是否为整数，把每个有效三角形记入它所属的周长，然后选出计数最大的周长。
这个问题不需要对每一个周长单独建立一套求解过程。更直接的做法是一次性扫描所有可能出现在周长不超过 1000 的直角三角形中的边对 \((a,b)\)，让每个通过检验的三角形自动为自己的周长贡献一次计数。
把两条直角边按 \(a \le b\) 排序，则 \(a\) 是最短边。由于周长不超过 1000，有
$$3a \le a+b+c \le 1000,$$
因此必然满足
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor.$$
当 \(a\) 固定后，再利用 \(b \le c\)，得到
$$a+2b \le a+b+c \le 1000,$$
也就是
$$a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor.$$
所以所有可能的整边直角三角形都落在下面这个有限格点区域中：
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor.$$
实现中的双重循环正是按这个区域来枚举候选边对。
一旦选定 \((a,b)\)，勾股关系就把斜边 \(c\) 完全确定下来：
$$c^2=a^2+b^2,\qquad c=\sqrt{a^2+b^2}.$$
因此真正需要判断的只有一件事：\(a^2+b^2\) 是否是完全平方数。如果不是，那么这个边对不可能形成整边直角三角形；如果是，那么对应的整数斜边就唯一确定。
这正是实现中的核心数学判定。程序先计算 \(a^2+b^2\) 的整数平方根，再检查把这个平方根重新平方后是否回到原值。只有完全一致时，这个候选边对才被接受。
当 \(c\) 是整数时，该三角形的周长就是
$$p=a+b+c.$$
与其对每个 \(p\) 分别求解一个丢番图问题，不如为 0 到 1000 之间的每个周长准备一个计数槽。每找到一个有效三角形，就把它记入对应周长的计数槽中。
这样，原题就被转化成了一个直方图问题：整个搜索完成后，只要找出计数最大的那个周长即可。
条件 \(a \le b\) 消除了交换两条直角边带来的重复，因此同一个三角形不会以 \((a,b,c)\) 和 \((b,a,c)\) 两种形式被记两次。另一方面，只要 \(a\) 和 \(b\) 为正，就自动有 \(c \gt b\)，因为
$$c^2=a^2+b^2>b^2.$$
反过来看，任何周长不超过 1000 的整边直角三角形，都必须满足前面推导出的 \(a\) 与 \(b\) 的范围限制，因此它对应的有序边对一定会在枚举中出现。
这就证明了枚举既是完整的，又没有重复计数。
周长 \(120\) 是一个很好的检验点，因为它恰好有三个解。在搜索区域中，相关的直角边对是
$$ (20,48),\qquad (24,45),\qquad (30,40). $$
对这三组数据，完全平方检验都成立：
$$20^2+48^2=52^2,\qquad 24^2+45^2=51^2,\qquad 30^2+40^2=50^2.$$
于是它们都落入同一个周长桶：
$$p=20+48+52=24+45+51=30+40+50=120.$$
在允许的搜索区域里，没有其他有序边对还能产生周长 120。因此 120 的计数是 3，这也是实现用来做检查的原因。
C++、Python 和 Java 实现的结构完全一致。首先分配一个按周长索引的数组，每个位置记录该周长已经找到多少个有效直角三角形。然后按前面推导出的边界执行两层循环，枚举所有候选 \((a,b)\)。
对于每个候选边对，程序计算 \(a^2+b^2\)，取它的整数平方根，并检查这个平方根是否精确。若检验成功，就计算对应周长 \(p=a+b+c\)，只要该周长没有超过给定上界，就把相应计数加一。
枚举结束后，程序从左到右扫描周长计数数组，保留当前见过的最大计数所对应的周长。由于只有在发现严格更大的计数时才会更新答案，所以如果出现并列，保留下来的是最先达到该最大值的周长。共享的检查步骤验证了：当上界是 120 时，返回的结果确实是 120。
如果把周长上界记为 \(L\)，算法枚举的整数对位于
$$1 \le a \le \left\lfloor \frac{L}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{L-a}{2} \right\rfloor.$$
因此候选边对总数为
$$\sum_{a=1}^{\lfloor L/3 \rfloor}\left(\left\lfloor \frac{L-a}{2} \right\rfloor-a+1\right)=O(L^2).$$
当 \(L=1000\) 时，大约只需要检查 \(8.3\times 10^4\) 个候选边对。每一步只做固定规模的整数运算和一次整数平方根运算，而最后扫描周长计数数组只需再花 \(O(L)\) 时间。空间复杂度是 \(O(L)\)，因为随输入增长的主要结构只有周长计数数组。
Нужно найти такой периметр \(p \le 1000\), для которого существует максимальное число прямоугольных треугольников с целыми сторонами. Допустимое решение представляет собой тройку \((a,b,c)\), где
$$a^2+b^2=c^2,\qquad a+b+c=p,$$
и выполняется порядок \(1 \le a \le b \lt c\). Реализации на C++, Python и Java решают задачу одинаково: перебирают все допустимые пары катетов, проверяют, является ли гипотенуза целой, увеличивают счетчик соответствующего периметра и затем выбирают периметр с наибольшим числом попаданий.
Главная идея состоит в том, что не нужно отдельно исследовать каждый периметр. Гораздо удобнее один раз просканировать всю конечную область пар \((a,b)\), которые вообще могут входить в прямоугольный треугольник с периметром не больше 1000, а затем позволить каждому найденному треугольнику увеличить счетчик своего периметра.
Упорядочим катеты так, чтобы \(a \le b\). Тогда \(a\) является наименьшей стороной, и из условия \(a+b+c \le 1000\) следует
$$3a \le a+b+c \le 1000,$$
а значит,
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor.$$
Если \(a\) уже зафиксирован, то из неравенства \(b \le c\) получаем
$$a+2b \le a+b+c \le 1000,$$
то есть
$$a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor.$$
Следовательно, любой допустимый треугольник лежит внутри конечной решетчатой области
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor,$$
и именно такие границы использует программа.
Для фиксированной пары \((a,b)\) гипотенуза полностью определяется уравнением
$$c^2=a^2+b^2,\qquad c=\sqrt{a^2+b^2}.$$
Поэтому остается единственная проверка: является ли число \(a^2+b^2\) полным квадратом. Если нет, то с такими катетами целочисленного прямоугольного треугольника не существует. Если да, то соответствующее значение \(c\) определяется единственным образом.
Это и есть ключевой математический тест в реализациях. Они вычисляют целую квадратную корень величины \(a^2+b^2\) и принимают пару тогда и только тогда, когда квадрат найденного корня совпадает с исходным числом.
Если \(c\) оказался целым, то периметр равен
$$p=a+b+c.$$
Вместо того чтобы решать отдельную диофантову задачу для каждого значения \(p\), удобно завести счетчик для каждого периметра от 0 до 1000. Каждый найденный треугольник увеличивает ровно один счетчик, а именно счетчик своего периметра.
Так исходная задача превращается в задачу построения гистограммы: после завершения перебора нужно просто выбрать индекс с наибольшей частотой.
Условие \(a \le b\) устраняет двойной счет, который возник бы из-за перестановки катетов. Кроме того, для положительных катетов неравенство \(c \gt b\) автоматически верно, поскольку
$$c^2=a^2+b^2>b^2.$$
С другой стороны, любой целочисленный прямоугольный треугольник с периметром не более 1000 обязан удовлетворять выведенным ограничениям на \(a\) и \(b\). Значит, его упорядоченная пара катетов обязательно встретится при переборе.
Следовательно, ни одно допустимое решение не теряется, и ни одно решение не учитывается дважды.
Периметр \(120\) удобен как контрольный пример, потому что у него ровно три решения. В области перебора соответствующие пары катетов таковы:
$$ (20,48),\qquad (24,45),\qquad (30,40). $$
Для них проверка полного квадрата проходит успешно:
$$20^2+48^2=52^2,\qquad 24^2+45^2=51^2,\qquad 30^2+40^2=50^2.$$
Все три пары дают один и тот же периметр:
$$p=20+48+52=24+45+51=30+40+50=120.$$
Другой упорядоченной пары в допустимой области, которая тоже давала бы периметр 120, нет. Поэтому счетчик для 120 равен 3, и именно этот случай используется в качестве контрольной проверки.
Реализации на C++, Python и Java устроены одинаково. Сначала создается массив, индексируемый периметром; в нем хранится число найденных прямоугольных треугольников для каждого периметра. Затем выполняются два вложенных цикла по области допустимых пар \((a,b)\).
Для каждой пары программа вычисляет \(a^2+b^2\), берет его целый квадратный корень и проверяет, точна ли эта операция. Если проверка успешна, вычисляется периметр \(p=a+b+c\), и соответствующий счетчик увеличивается, если \(p\) не превышает заданную границу.
После завершения перебора массив счетчиков просматривается слева направо, и сохраняется периметр с наибольшим увиденным значением. Поскольку обновление ответа происходит только при строго большем счете, при равенстве побеждает первый периметр, достигший этого максимума. Общая проверка подтверждает, что при верхней границе 120 возвращается именно 120.
Если обозначить верхнюю границу периметра через \(L\), то алгоритм проверяет все целые пары в области
$$1 \le a \le \left\lfloor \frac{L}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{L-a}{2} \right\rfloor.$$
Число протестированных кандидатов равно
$$\sum_{a=1}^{\lfloor L/3 \rfloor}\left(\left\lfloor \frac{L-a}{2} \right\rfloor-a+1\right)=O(L^2).$$
При \(L=1000\) это примерно \(8.3\times 10^4\) пар катетов. Каждая итерация использует арифметику фиксированного размера и одно вычисление целого квадратного корня, а финальный проход по массиву периметров добавляет только \(O(L)\) времени. Память составляет \(O(L)\), поскольку единственная структура, растущая вместе с входом, это массив счетчиков по периметрам.
نريد إيجاد قيمة المحيط \(p \le 1000\) التي تعطي أكبر عدد من المثلثات القائمة ذات الأضلاع الصحيحة. والحل الصحيح هو ثلاثية \((a,b,c)\) تحقق
$$a^2+b^2=c^2,\qquad a+b+c=p,$$
مع الشرط \(1 \le a \le b \lt c\). وتستعمل تطبيقات C++ وPython وJava الفكرة نفسها: تعداد جميع أزواج الضلعين القائمين الممكنة، فحص ما إذا كان الوتر عددا صحيحا، زيادة عداد المحيط الموافق، ثم اختيار المحيط ذي أكبر عدد.
الفكرة الأساسية هي أنه لا حاجة إلى حل مسألة مستقلة لكل محيط على حدة. يكفي أن نمسح مرة واحدة جميع أزواج \((a,b)\) التي يمكن أن تظهر في مثلث قائم محيطه لا يتجاوز 1000، ثم نسمح لكل مثلث صالح أن يزيد عداد محيطه الخاص.
نرتب الضلعين القائمين بحيث يكون \(a \le b\). عندئذ يكون \(a\) أصغر ضلع، ومن الشرط \(a+b+c \le 1000\) نحصل على
$$3a \le a+b+c \le 1000,$$
ومن ثم
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor.$$
وبعد تثبيت \(a\)، فإن العلاقة \(b \le c\) تعطي
$$a+2b \le a+b+c \le 1000,$$
أي
$$a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor.$$
إذن كل مثلث صالح يقع داخل المنطقة الشبكية المحدودة
$$1 \le a \le \left\lfloor \frac{1000}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{1000-a}{2} \right\rfloor,$$
وهذه هي بالضبط حدود الحلقات المستخدمة في التنفيذ.
عندما نختار الزوج \((a,b)\)، يصبح الوتر محددا بصورة وحيدة من علاقة فيثاغورس:
$$c^2=a^2+b^2,\qquad c=\sqrt{a^2+b^2}.$$
لذلك يبقى اختبار واحد فقط: هل \(a^2+b^2\) مربع كامل؟ إذا لم يكن كذلك فلا يوجد مثلث قائم صحيح الأضلاع بهذه القيم. وإذا كان مربعا كاملا فإن قيمة \(c\) تصبح معروفة على الفور.
هذا هو الاختبار الرياضي المحوري في الشيفرة. فالتنفيذ يحسب الجذر التربيعي الصحيح لـ \(a^2+b^2\)، ثم يقبل الزوج فقط إذا أعاد تربيع ذلك الجذر القيمة الأصلية نفسها.
إذا كانت \(c\) عددا صحيحا فإن المحيط يساوي
$$p=a+b+c.$$
وبدل حل معادلة ديوفانتية منفصلة لكل قيمة من \(p\)، نحفظ عدادا لكل محيط من 0 إلى 1000. وكل مثلث صالح يزيد عدادا واحدا فقط، وهو عداد محيطه.
وبهذا تتحول المسألة الأصلية إلى مسألة بناء مدرج تكراري: بعد انتهاء المسح نختار ببساطة المحيط صاحب أكبر تكرار.
الشرط \(a \le b\) يمنع عد المثلث نفسه مرتين على الصورتين \((a,b,c)\) و\((b,a,c)\). كذلك فإن \(c \gt b\) متحقق تلقائيا ما دام \(a\) و\(b\) موجبين، لأن
$$c^2=a^2+b^2>b^2.$$
ومن الجهة الأخرى، فإن أي مثلث قائم صحيح الأضلاع محيطه لا يتجاوز 1000 لا بد أن يحقق القيود المستنتجة على \(a\) و\(b\). لذلك فزوج الضلعين المرتب سيظهر حتما أثناء التعداد.
إذن الطريقة كاملة ولا تحسب أي حل أكثر من مرة.
المحيط \(120\) مثال مناسب للفحص لأنه يملك ثلاثة حلول بالضبط. أزواج الضلعين القائمين المعنية داخل مجال البحث هي
$$ (20,48),\qquad (24,45),\qquad (30,40). $$
وفي كل حالة ينجح اختبار المربع الكامل:
$$20^2+48^2=52^2,\qquad 24^2+45^2=51^2,\qquad 30^2+40^2=50^2.$$
ومن ثم تساهم الحالات الثلاث كلها في المحيط نفسه:
$$p=20+48+52=24+45+51=30+40+50=120.$$
ولا يوجد زوج مرتب آخر داخل المنطقة المسموح بها ينتج أيضا المحيط 120. لذلك يكون عداد 120 مساويا لـ 3، ولهذا السبب تستعمله التطبيقات كحالة تحقق.
تتبع تطبيقات C++ وPython وJava البنية نفسها. أولا تنشئ مصفوفة مفهرسة بالمحيط، بحيث يخزن كل موضع عدد المثلثات القائمة الصحيحة التي وُجدت لذلك المحيط. ثم تنفذ حلقتين متداخلتين على المجال المحدود المشتق للأزواج \((a,b)\).
لكل زوج مرشح تحسب الشيفرة \(a^2+b^2\)، وتأخذ جذره التربيعي الصحيح، ثم تفحص ما إذا كان الاختبار دقيقا. فإذا نجح الاختبار حُسب المحيط \(p=a+b+c\)، وزيد العداد الموافق له ما دام هذا المحيط لا يتجاوز الحد المطلوب.
بعد انتهاء التعداد تمسح الشيفرة مصفوفة العدادات من اليسار إلى اليمين وتحتفظ بالمحيط الذي يملك أكبر عدد شوهد حتى تلك اللحظة. وبما أن التحديث لا يحدث إلا عند ظهور عدد أكبر على نحو صارم، فإن حالات التعادل تحسم لصالح أول محيط بلغ تلك القيمة العظمى. كما تؤكد خطوة التحقق المشتركة أن الحد الأعلى 120 يعيد فعلا القيمة 120.
إذا رمزنا إلى حد المحيط الأعلى بالرمز \(L\)، فإن الخوارزمية تختبر جميع الأزواج الصحيحة ضمن المنطقة
$$1 \le a \le \left\lfloor \frac{L}{3} \right\rfloor,\qquad a \le b \le \left\lfloor \frac{L-a}{2} \right\rfloor.$$
ومن ثم فإن عدد الأزواج المرشحة يساوي
$$\sum_{a=1}^{\lfloor L/3 \rfloor}\left(\left\lfloor \frac{L-a}{2} \right\rfloor-a+1\right)=O(L^2).$$
وعندما يكون \(L=1000\)، فهذا يعني تقريبا \(8.3\times 10^4\) زوجا مرشحا فقط. كل خطوة تستعمل حسابات ثابتة الحجم مع عملية جذر تربيعي صحيح واحدة، بينما تضيف عملية المسح النهائية على عدادات المحيط زمنا مقداره \(O(L)\) فقط. واستهلاك الذاكرة هو \(O(L)\)، لأن البنية الوحيدة التي تكبر مع الإدخال هي مصفوفة العد بحسب المحيط.