The problem asks for the number of Pythagorean triples \((a,b,c)\) with perimeter \(a+b+c<10^8\) that can form the classic “square hole” arrangement: four congruent right triangles are placed inside a \(c\times c\) square, leaving a central square of side \(|a-b|\). The arrangement becomes a genuine tiling only when that inner square side divides the outer side, so the arithmetic condition is
$$|a-b|\mid c.$$
Rather than scan every non-primitive triple separately, the efficient strategy is to enumerate primitive triples first and then count all allowed multiples.
The implementations are based on Euclid's parametrization of primitive Pythagorean triples, but the divisibility test hides a stronger structure. Once that structure is exposed, the code becomes easy to justify.
For a right triangle with legs \(a,b\) and hypotenuse \(c\), four copies fit inside a square of side \(c\). The central gap is itself a square, and a short geometric inspection shows that its side length is exactly
$$d=|a-b|.$$
If the large square is to be tiled by smaller copies of that inner square pattern, the side length of the hole must divide the side length of the outer square. So the entire problem reduces to checking whether
$$d\mid c.$$
This is the only arithmetic test used by the implementations.
Every primitive Pythagorean triple can be written uniquely as
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
with integers \(m>n\ge 1\), \(\gcd(m,n)=1\), and \(m-n\) odd. Its perimeter is
$$P=a+b+c=2m(m+n).$$
This gives the search space used in the code: loop over admissible pairs \((m,n)\), build the primitive triple, and test the tiling condition.
Let \(d=|a-b|\) for a primitive triple. If the tiling condition holds, then \(d\mid c\). Since \(d\mid(a-b)\) as well, we also have
$$d\mid c^2-(a-b)^2.$$
Using \(c^2=a^2+b^2\), this becomes
$$c^2-(a-b)^2=a^2+b^2-(a^2-2ab+b^2)=2ab,$$
so \(d\mid 2ab\).
Now use the primitive-triple facts. We have \(\gcd(a,b)=1\), one leg is even, the other is odd, and therefore \(d=|a-b|\) is odd. Also
$$\gcd(d,a)=\gcd(a-b,a)=\gcd(a,b)=1,\qquad \gcd(d,b)=1.$$
Thus \(d\) is coprime to \(2\), to \(a\), and to \(b\), yet it divides \(2ab\). The only possibility is
$$d=1.$$
Conversely, \(d=1\) obviously implies \(d\mid c\). So for primitive triples the condition is equivalent to saying that the two legs are consecutive integers.
Substituting Euclid's formula into \(|a-b|=1\) gives
$$|m^2-n^2-2mn|=1,$$
or, after setting \(x=m-n\) and \(y=n\),
$$|x^2-2y^2|=1.$$
This is the Pell equation \(x^2-2y^2=\pm1\). Therefore the primitive tiling triples form a Pell family, equivalently an “almost isosceles” family with consecutive legs. One convenient recurrence for the Euclid parameters is
$$m_{k+1}=2m_k+n_k,\qquad n_{k+1}=m_k,$$
starting from \((m_1,n_1)=(2,1)\). It produces
$$ (3,4,5),\ (20,21,29),\ (119,120,169),\ (696,697,985),\dots $$
The implementations do not generate this recurrence explicitly, but the divisibility test they apply is exactly selecting this same family from the full Euclid search.
If \((a,b,c)\) is a qualifying primitive triple, then every multiple
$$\bigl(ka,kb,kc\bigr)$$
also qualifies, because
$$|ka-kb|=k|a-b|$$
and divisibility is preserved. If the primitive perimeter is \(P\), then the allowed values of \(k\) satisfy
$$kP<10^8,$$
so the number of counted multiples is
$$\left\lfloor\frac{10^8-1}{P}\right\rfloor.$$
This explains the accumulation formula used in all three implementations.
For perimeter \(P<100\), the primitive tiling triples are exactly
$$ (3,4,5)\ (P=12),\qquad (20,21,29)\ (P=70). $$
All qualifying triples below 100 come from their multiples:
$$\left\lfloor\frac{99}{12}\right\rfloor=8,\qquad \left\lfloor\frac{99}{70}\right\rfloor=1.$$
Therefore the total count is
$$8+1=9,$$
which is exactly the checkpoint used by the C++ implementation.
The C++, Python, and Java implementations loop over Euclid parameters \(m>n\). The outer loop stops as soon as the smallest perimeter for that \(m\), namely \(2m(m+1)\), reaches the limit. Inside, the code keeps only coprime pairs of opposite parity, which are precisely the primitive generators.
For each admissible pair \((m,n)\), the implementation constructs \(a\), \(b\), \(c\), and the leg difference \(d=|a-b|\). It then checks the single condition \(c\bmod d=0\). That condition is mathematically equivalent to selecting the consecutive-leg Pell family, but the code keeps the test in this direct arithmetic form.
Once a primitive triple passes the divisibility test, its perimeter \(P\) is known. Every scaled copy with \(kP<10^8\) is counted, so the contribution added to the answer is \(\left\lfloor(10^8-1)/P\right\rfloor\). The three implementations differ only in language syntax; their control flow and counting logic are the same.
Let \(L=10^8\). Since the outer loop stops when \(2m(m+1)\ge L\), we have \(m=O(\sqrt{L})\). For each \(m\), the inner loop scans \(n=1,2,\dots,m-1\), so the total number of candidate Euclid pairs is \(O(L)\).
Each candidate requires a gcd computation and a constant amount of integer arithmetic, giving \(O(L\log L)\) time in a strict arithmetic model, or effectively linear time in the number of tested pairs on fixed-size machine integers. Memory usage is \(O(1)\), because the implementation stores only a handful of integers and the running total.
Gesucht ist die Anzahl der pythagoreischen Tripel \((a,b,c)\) mit Umfang \(a+b+c<10^8\), die die klassische Anordnung mit quadratischer Lücke zulassen: Vier kongruente rechtwinklige Dreiecke liegen in einem \(c\times c\)-Quadrat und lassen in der Mitte ein Quadrat der Seitenlänge \(|a-b|\) frei. Damit diese Figur wirklich ein Kachelmuster liefert, muss die Seitenlänge des inneren Quadrats die Seitenlänge des äußeren Quadrats teilen, also gilt genau dann
$$|a-b|\mid c.$$
Effizient zählt man daher zunächst primitive Tripel und addiert anschließend alle zulässigen Vielfachen.
Die Implementierungen arbeiten mit der euklidischen Parametrisierung primitiver pythagoreischer Tripel. Hinter der einfachen Teilbarkeitsprüfung steckt jedoch eine stärkere Struktur, und genau diese erklärt, warum der Code korrekt ist.
Für ein rechtwinkliges Dreieck mit Katheten \(a,b\) und Hypotenuse \(c\) passen vier Kopien in ein Quadrat der Seitenlänge \(c\). Die zentrale Lücke ist wieder ein Quadrat, dessen Seitenlänge durch eine kurze geometrische Betrachtung als
$$d=|a-b|$$
erscheint. Damit das große Quadrat durch Wiederholung dieser Struktur lückenlos gekachelt werden kann, muss \(d\) ein Teiler von \(c\) sein. Das gesamte Problem reduziert sich also auf die Bedingung
$$d\mid c.$$
Genau diese arithmetische Invariante wird im Code geprüft.
Jedes primitive pythagoreische Tripel besitzt die eindeutige Darstellung
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
mit ganzen Zahlen \(m>n\ge 1\), \(\gcd(m,n)=1\) und ungeradem \(m-n\). Der Umfang lautet
$$P=a+b+c=2m(m+n).$$
Damit ist der Suchraum der Implementierungen festgelegt: Alle zulässigen Parameterpaare \((m,n)\) werden durchlaufen, daraus das primitive Tripel konstruiert und anschließend die Kachelbedingung getestet.
Sei \(d=|a-b|\) für ein primitives Tripel. Gilt die Kachelbedingung, dann ist \(d\mid c\). Weil zugleich \(d\mid(a-b)\), folgt auch
$$d\mid c^2-(a-b)^2.$$
Mit \(c^2=a^2+b^2\) wird daraus
$$c^2-(a-b)^2=a^2+b^2-(a^2-2ab+b^2)=2ab,$$
also \(d\mid 2ab\).
Nun kommt die Primitivität ins Spiel: \(\gcd(a,b)=1\), eine Kathete ist gerade und die andere ungerade, also ist \(d=|a-b|\) ungerade. Außerdem gilt
$$\gcd(d,a)=\gcd(a-b,a)=\gcd(a,b)=1,\qquad \gcd(d,b)=1.$$
Damit ist \(d\) teilerfremd zu \(2\), zu \(a\) und zu \(b\), teilt aber \(2ab\). Das ist nur möglich für
$$d=1.$$
Umgekehrt impliziert \(d=1\) natürlich sofort \(d\mid c\). Primitive Kacheltripel sind also genau die primitiven pythagoreischen Tripel mit aufeinanderfolgenden Katheten.
Setzt man die euklidische Formel in \(|a-b|=1\) ein, so erhält man
$$|m^2-n^2-2mn|=1.$$
Mit \(x=m-n\) und \(y=n\) wird das zu
$$|x^2-2y^2|=1,$$
also zur Pell-Gleichung \(x^2-2y^2=\pm1\). Die primitiven Kacheltripel bilden daher eine Pell-Familie beziehungsweise eine Familie fast gleichschenkliger rechtwinkliger Dreiecke mit Kathetendifferenz 1. Eine praktische Rekursion für die euklidischen Parameter lautet
$$m_{k+1}=2m_k+n_k,\qquad n_{k+1}=m_k,$$
mit Startwert \((m_1,n_1)=(2,1)\). Daraus entstehen die Tripel
$$ (3,4,5),\ (20,21,29),\ (119,120,169),\ (696,697,985),\dots $$
Die Implementierungen erzeugen diese Folge nicht direkt, sondern filtern sie durch die Bedingung \(c\bmod |a-b|=0\) aus der vollständigen euklidischen Suche heraus.
Ist \((a,b,c)\) ein primitives Kacheltripel, dann ist auch jedes Vielfache
$$\bigl(ka,kb,kc\bigr)$$
wieder zulässig, denn es gilt
$$|ka-kb|=k|a-b|$$
und die Teilbarkeit bleibt erhalten. Hat das primitive Tripel den Umfang \(P\), dann müssen die zulässigen Faktoren \(k\) die strenge Schranke
$$kP<10^8$$
erfüllen. Daher liefert dieses primitive Tripel genau
$$\left\lfloor\frac{10^8-1}{P}\right\rfloor$$
gültige Beiträge. Genau diese Summanden akkumuliert der Code.
Für die Schranke \(P<100\) gibt es genau zwei primitive Kacheltripel:
$$ (3,4,5)\ (P=12),\qquad (20,21,29)\ (P=70). $$
Ihre gültigen Vielfachen unter 100 sind
$$\left\lfloor\frac{99}{12}\right\rfloor=8,\qquad \left\lfloor\frac{99}{70}\right\rfloor=1.$$
Somit ergibt sich insgesamt
$$8+1=9,$$
und genau dieses Ergebnis wird auch als Kontrollwert in der C++-Implementierung verwendet.
Die Implementierungen in C++, Python und Java iterieren über die euklidischen Parameter \(m>n\). Die äußere Schleife endet, sobald der kleinste zugehörige Umfang \(2m(m+1)\) die Grenze erreicht. Im Inneren bleiben nur teilerfremde Paare unterschiedlicher Parität übrig, denn genau sie erzeugen primitive Tripel.
Für jedes zulässige Paar \((m,n)\) werden \(a\), \(b\), \(c\) und die Kathetendifferenz \(d=|a-b|\) berechnet. Danach prüft die Implementierung nur noch \(c\bmod d=0\). Mathematisch ist das äquivalent zur Auswahl der Pell-Familie mit aufeinanderfolgenden Katheten, im Programm bleibt die Bedingung aber bewusst als direkter Teilbarkeitstest formuliert.
Besteht ein primitives Tripel den Test, ist sein Umfang \(P\) bekannt. Dann werden automatisch alle ähnlichen Tripel mit \(kP<10^8\) mitgezählt, also ein Beitrag von \(\left\lfloor(10^8-1)/P\right\rfloor\). Die drei Sprachversionen unterscheiden sich nur syntaktisch; der Zählablauf ist identisch.
Setze \(L=10^8\). Da die äußere Schleife bei \(2m(m+1)\ge L\) stoppt, ist \(m=O(\sqrt{L})\). Für jedes \(m\) läuft die innere Schleife über \(n=1,2,\dots,m-1\), also werden insgesamt \(O(L)\) Kandidatenpaare \((m,n)\) betrachtet.
Jedes Kandidatenpaar benötigt eine ggT-Berechnung und konstant viel Ganzzahlarithmetik. Damit ergibt sich in einem strengen arithmetischen Modell \(O(L\log L)\) Laufzeit, beziehungsweise praktisch lineare Zeit in der Anzahl der getesteten Paare bei Maschinenarithmetik fester Breite. Der Speicherbedarf ist \(O(1)\), weil nur einige wenige Ganzzahlen und die laufende Summe gehalten werden.
İstenen şey, çevresi \(a+b+c<10^8\) olan Pisagor üçlüleri \((a,b,c)\) arasında klasik “ortası kare boşluklu” düzeni oluşturabilenlerin sayısıdır. Dört eş dik üçgen bir \(c\times c\) karesinin içine yerleştirildiğinde ortada kenarı \(|a-b|\) olan bir kare boşluk kalır. Bu şeklin gerçekten döşeme vermesi için içteki karenin kenarı dıştaki karenin kenarını bölmelidir; yani aranan koşul tam olarak
$$|a-b|\mid c.$$
Bu yüzden verimli yaklaşım, önce ilkel üçlüleri üretmek, sonra da bunların izin verilen tüm katlarını toplamak olur.
Uygulamalar ilkel Pisagor üçlüleri için Öklid parametrelemesini kullanıyor. Fakat basit görünen bölünebilirlik testinin arkasında daha güçlü bir yapı var; bunu açığa çıkarınca kodun mantığı tamamen netleşiyor.
Kenarları \(a,b\), hipotenüsü \(c\) olan bir dik üçgenin dört kopyası, kenarı \(c\) olan bir karenin içine yerleşir. Ortada kalan boşluk yine bir karedir ve kısa bir geometrik inceleme bunun kenarının
$$d=|a-b|$$
olduğunu gösterir. Büyük karenin bu düzen tekrar edilerek tamamen döşenebilmesi için \(d\) sayısının \(c\)'yi bölmesi gerekir. Dolayısıyla bütün problem şu tek aritmetik koşula iner:
$$d\mid c.$$
Uygulamaların test ettiği tek invariant da budur.
Her ilkel Pisagor üçlüsü tek biçimde
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
şeklinde yazılır; burada \(m>n\ge 1\), \(\gcd(m,n)=1\) ve \(m-n\) tektir. Çevre ise
$$P=a+b+c=2m(m+n)$$
olur. Kodun taradığı durum uzayı tam olarak budur: uygun \((m,n)\) çiftlerini dolaş, ilkel üçlüyü kur ve döşeme koşulunu test et.
İlkel bir üçlü için \(d=|a-b|\) olsun. Döşeme koşulu sağlanıyorsa \(d\mid c\) olur. Zaten \(d\mid(a-b)\) da olduğundan
$$d\mid c^2-(a-b)^2$$
elde edilir. \(c^2=a^2+b^2\) kimliğini kullanırsak
$$c^2-(a-b)^2=a^2+b^2-(a^2-2ab+b^2)=2ab,$$
yani \(d\mid 2ab\).
Şimdi ilkellik devreye girer. \(\gcd(a,b)=1\)'dir; ayrıca katetlerden biri çift, diğeri tektir, dolayısıyla \(d=|a-b|\) tektir. Bir de
$$\gcd(d,a)=\gcd(a-b,a)=\gcd(a,b)=1,\qquad \gcd(d,b)=1$$
vardır. Demek ki \(d\), \(2\), \(a\) ve \(b\) ile aralarında asaldır; ama aynı zamanda \(2ab\)'yi bölmektedir. Bunun tek yolu
$$d=1$$
olmasıdır. Tersi de açıktır: \(d=1\) ise elbette \(d\mid c\). Sonuç olarak ilkel döşeme üçlüleri, katetleri ardışık tamsayı olan ilkel Pisagor üçlüleridir.
\(|a-b|=1\) koşulunda Öklid formülünü yerine koyarsak
$$|m^2-n^2-2mn|=1$$
çıkar. \(x=m-n\) ve \(y=n\) dersek bu
$$|x^2-2y^2|=1$$
biçimine gelir; yani \(x^2-2y^2=\pm1\) Pell denklemi ortaya çıkar. Bu nedenle ilkel döşeme üçlüleri, katet farkı 1 olan bir Pell ailesi oluşturur. Öklid parametreleri için uygun bir yineleme
$$m_{k+1}=2m_k+n_k,\qquad n_{k+1}=m_k,$$
başlangıç değeri \((m_1,n_1)=(2,1)\) olacak şekilde yazılabilir. Böylece
$$ (3,4,5),\ (20,21,29),\ (119,120,169),\ (696,697,985),\dots $$
dizisi elde edilir. Uygulamalar bu yinelemeyi doğrudan kullanmıyor; onun yerine tüm Öklid aramasını yapıp aynı aileyi \(c\bmod |a-b|=0\) testiyle seçiyor.
\((a,b,c)\) ilkel ve uygun bir üçlü ise her
$$\bigl(ka,kb,kc\bigr)$$
çarpanı da uygundur; çünkü
$$|ka-kb|=k|a-b|$$
ve bölünebilme korunur. İlkel üçlünün çevresi \(P\) ise izin verilen \(k\) değerleri
$$kP<10^8$$
eşitsizliğini sağlamalıdır. Dolayısıyla bu ilkel üçlünün katkısı
$$\left\lfloor\frac{10^8-1}{P}\right\rfloor$$
olur. Üç uygulamanın topladığı miktar tam olarak budur.
\(P<100\) sınırında uygun ilkel üçlüler yalnızca şunlardır:
$$ (3,4,5)\ (P=12),\qquad (20,21,29)\ (P=70). $$
Bunların 100'den küçük tüm uygun katları
$$\left\lfloor\frac{99}{12}\right\rfloor=8,\qquad \left\lfloor\frac{99}{70}\right\rfloor=1$$
adet verir. Toplam
$$8+1=9$$
olur; bu da C++ uygulamasındaki kontrol sonucuyla aynıdır.
C++, Python ve Java uygulamaları \(m>n\) olacak biçimde Öklid parametrelerini dolaşır. Dış döngü, bu \(m\) için mümkün olan en küçük çevre \(2m(m+1)\) sınıra ulaştığında biter. İçeride yalnızca aralarında asal ve farklı parity'ye sahip çiftler tutulur; çünkü bunlar tam olarak ilkel üreticilerdir.
Her uygun \((m,n)\) çifti için \(a\), \(b\), \(c\) ve \(d=|a-b|\) hesaplanır. Sonra yalnızca \(c\bmod d=0\) testi yapılır. Matematiksel olarak bu test, Pell ailesindeki ardışık katetli çözümleri seçmeye denktir; fakat kod bunu doğrudan bu aritmetik biçimde bırakır.
İlkel bir üçlü testi geçince çevresi \(P\) bilinir. Artık \(kP<10^8\) sağlayan tüm benzer üçlüler sayılır; yani sonuca \(\left\lfloor(10^8-1)/P\right\rfloor\) eklenir. Üç dildeki uygulamalar sözdizimi dışında aynı akışı izler.
\(L=10^8\) olsun. Dış döngü \(2m(m+1)\ge L\) olduğunda durduğu için \(m=O(\sqrt{L})\) olur. Her \(m\) için iç döngü \(n=1,2,\dots,m-1\) üzerinden ilerlediğinden, toplam aday \((m,n)\) sayısı \(O(L)\)'dir.
Her aday için bir EBOB hesabı ve sabit sayıda tamsayı işlemi gerekir. Bu yüzden katı aritmetik modelde süre \(O(L\log L)\), sabit genişlikli makine tamsayılarında ise test edilen çift sayısına göre pratikte doğrusal zamandır. Bellek kullanımı \(O(1)\)'dir; çünkü yalnızca birkaç tamsayı ve çalışan toplam tutulur.
La tarea es contar los triples pitagóricos \((a,b,c)\) con perímetro \(a+b+c<10^8\) que admiten la configuración clásica con un hueco cuadrado en el centro. Al colocar cuatro triángulos rectángulos congruentes dentro de un cuadrado de lado \(c\), queda un cuadrado interior de lado \(|a-b|\). Para que esa figura dé lugar a un mosaico auténtico, la longitud del lado interior debe dividir la del cuadrado exterior; por tanto, la condición aritmética es
$$|a-b|\mid c.$$
La forma eficiente de contar es generar primero los triples primitivos y después sumar todos sus múltiplos válidos.
Las implementaciones usan la parametrización de Euclides para los triples pitagóricos primitivos. Sin embargo, la simple prueba de divisibilidad esconde una estructura más rígida, y esa estructura es la que explica toda la solución.
Si un triángulo rectángulo tiene catetos \(a,b\) e hipotenusa \(c\), cuatro copias caben dentro de un cuadrado de lado \(c\). El hueco central vuelve a ser un cuadrado, y un análisis geométrico directo muestra que su lado vale
$$d=|a-b|.$$
Para que el cuadrado grande pueda teselarse repitiendo ese patrón, \(d\) debe dividir a \(c\). Así, todo el problema se reduce a verificar
$$d\mid c.$$
Ésa es exactamente la prueba aritmética que aplican los programas.
Todo triple pitagórico primitivo puede escribirse de manera única como
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
con \(m>n\ge 1\), \(\gcd(m,n)=1\) y \(m-n\) impar. Su perímetro es
$$P=a+b+c=2m(m+n).$$
Esto fija el espacio de búsqueda real del código: recorrer pares \((m,n)\), construir el triple primitivo correspondiente y comprobar si satisface la condición de mosaico.
Sea \(d=|a-b|\) en un triple primitivo. Si se cumple la condición de mosaico, entonces \(d\mid c\). Como además \(d\mid(a-b)\), también se tiene
$$d\mid c^2-(a-b)^2.$$
Usando \(c^2=a^2+b^2\), obtenemos
$$c^2-(a-b)^2=a^2+b^2-(a^2-2ab+b^2)=2ab,$$
de modo que \(d\mid 2ab\).
Ahora interviene la primitividad. Como \(\gcd(a,b)=1\), un cateto es par y el otro impar, luego \(d=|a-b|\) es impar. Además,
$$\gcd(d,a)=\gcd(a-b,a)=\gcd(a,b)=1,\qquad \gcd(d,b)=1.$$
Así, \(d\) es coprimo con \(2\), con \(a\) y con \(b\), pero divide a \(2ab\). La única posibilidad es
$$d=1.$$
La implicación recíproca es inmediata: si \(d=1\), entonces \(d\mid c\) automáticamente. Por tanto, los triples primitivos válidos son exactamente los triples pitagóricos primitivos cuyos catetos son consecutivos.
Al sustituir la fórmula de Euclides en \(|a-b|=1\), aparece
$$|m^2-n^2-2mn|=1.$$
Si definimos \(x=m-n\) e \(y=n\), queda
$$|x^2-2y^2|=1,$$
es decir, la ecuación de Pell \(x^2-2y^2=\pm1\). En consecuencia, los triples primitivos que teselan forman una familia de Pell, o si se prefiere, la familia “casi isósceles” de triángulos rectángulos con diferencia 1 entre los catetos. Una recurrencia cómoda para los parámetros de Euclides es
$$m_{k+1}=2m_k+n_k,\qquad n_{k+1}=m_k,$$
con arranque en \((m_1,n_1)=(2,1)\). Esto genera
$$ (3,4,5),\ (20,21,29),\ (119,120,169),\ (696,697,985),\dots $$
Las implementaciones no usan esa recurrencia de forma explícita; la misma familia aparece al filtrar la búsqueda completa de Euclides mediante la condición \(c\bmod |a-b|=0\).
Si \((a,b,c)\) es un triple primitivo válido, entonces cualquier múltiplo
$$\bigl(ka,kb,kc\bigr)$$
también es válido, porque
$$|ka-kb|=k|a-b|$$
y la divisibilidad se conserva. Si el perímetro primitivo es \(P\), los factores permitidos \(k\) son los que cumplen
$$kP<10^8,$$
de modo que el número de contribuciones es
$$\left\lfloor\frac{10^8-1}{P}\right\rfloor.$$
Ésa es precisamente la cantidad que se suma en las tres implementaciones.
Cuando el límite es \(P<100\), los únicos triples primitivos válidos son
$$ (3,4,5)\ (P=12),\qquad (20,21,29)\ (P=70). $$
Sus múltiplos permitidos por debajo de 100 son
$$\left\lfloor\frac{99}{12}\right\rfloor=8,\qquad \left\lfloor\frac{99}{70}\right\rfloor=1.$$
Por lo tanto, el total es
$$8+1=9,$$
que coincide exactamente con la comprobación pequeña usada por la implementación en C++.
Las implementaciones en C++, Python y Java recorren parámetros de Euclides con \(m>n\). El bucle exterior termina cuando el perímetro mínimo asociado a ese \(m\), es decir \(2m(m+1)\), alcanza el límite. En el bucle interior sólo se conservan los pares coprimos de distinta paridad, que son exactamente los generadores primitivos.
Para cada par admisible \((m,n)\), la implementación calcula \(a\), \(b\), \(c\) y \(d=|a-b|\). Después aplica una única prueba: \(c\bmod d=0\). Matemáticamente esa prueba equivale a seleccionar la familia de Pell con catetos consecutivos, pero el programa la deja en esta forma aritmética directa.
Una vez que un triple primitivo supera la prueba, ya se conoce su perímetro \(P\). Entonces se cuentan todos los triángulos semejantes con \(kP<10^8\), es decir, se añade \(\left\lfloor(10^8-1)/P\right\rfloor\) al total. Las tres versiones cambian sólo en la sintaxis del lenguaje.
Sea \(L=10^8\). Como el bucle exterior se detiene cuando \(2m(m+1)\ge L\), el valor máximo de \(m\) es \(O(\sqrt{L})\). Para cada \(m\), el bucle interior recorre \(n=1,2,\dots,m-1\), así que el número total de pares candidatos \((m,n)\) es \(O(L)\).
Cada candidato requiere un cálculo de mcd y una cantidad constante de aritmética entera. Por ello, en un modelo aritmético estricto el tiempo es \(O(L\log L)\), mientras que con enteros de máquina de tamaño fijo el comportamiento práctico es esencialmente lineal en el número de pares probados. La memoria es \(O(1)\), ya que sólo se mantienen unos pocos enteros y el acumulador final.
题目要求统计所有周长满足 \(a+b+c<10^8\) 的毕达哥拉斯三元组 \((a,b,c)\)，其中四个全等直角三角形能够围成经典的“中间留一个正方形孔”的图形。把四个三角形放进边长为 \(c\) 的大正方形后，中央留下的小正方形边长正好是 \(|a-b|\)。如果这个结构能够继续用于整齐铺砌，那么内孔的边长必须整除外部正方形的边长，因此核心算术条件就是
$$|a-b|\mid c.$$
高效做法不是直接枚举所有非本原三元组，而是先枚举本原三元组，再把所有允许的倍数一次性计入。
实现代码直接建立在 Euclid 参数化之上，但那个看似简单的整除判断实际上蕴含了一条非常强的结构性结论。把这条结论说明白之后，整个算法就顺理成章了。
设直角三角形的两条直角边为 \(a,b\)，斜边为 \(c\)。四个这样的三角形可以拼进一个边长为 \(c\) 的正方形。中间剩下的空白仍然是一个正方形，直接从图形关系就能看出它的边长是
$$d=|a-b|.$$
如果想让这个“外方内孔”的结构继续重复成真正的平铺，那么内孔边长 \(d\) 必须整除外部大正方形边长 \(c\)。于是整道题就被压缩成一个单独的判断：
$$d\mid c.$$
三份实现中真正执行的筛选条件只有这一条。
每个本原毕达哥拉斯三元组都能唯一写成
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
其中 \(m>n\ge 1\)、\(\gcd(m,n)=1\)，并且 \(m-n\) 为奇数。对应的周长为
$$P=a+b+c=2m(m+n).$$
这正是代码扫描的状态空间：枚举满足条件的 \((m,n)\)，构造出本原三元组，然后检查是否通过平铺测试。
设某个本原三元组的 \(d=|a-b|\)。如果它满足题目条件，那么 \(d\mid c\)。由于本来就有 \(d\mid(a-b)\)，所以还得到
$$d\mid c^2-(a-b)^2.$$
再利用 \(c^2=a^2+b^2\)，可得
$$c^2-(a-b)^2=a^2+b^2-(a^2-2ab+b^2)=2ab,$$
因此 \(d\mid 2ab\)。
接下来用到本原三元组的基本性质：\(\gcd(a,b)=1\)，两条直角边一奇一偶，所以 \(d=|a-b|\) 一定是奇数。另外还有
$$\gcd(d,a)=\gcd(a-b,a)=\gcd(a,b)=1,\qquad \gcd(d,b)=1.$$
也就是说，\(d\) 与 \(2\)、\(a\)、\(b\) 都互素，却又整除 \(2ab\)。这只能发生在
$$d=1$$
的情况下。反过来，如果 \(d=1\)，那么 \(d\mid c\) 当然自动成立。于是对本原三元组来说，题目条件等价于两条直角边恰好是相邻整数。
把 \(|a-b|=1\) 代入 Euclid 公式，得到
$$|m^2-n^2-2mn|=1.$$
令 \(x=m-n\)、\(y=n\)，就变成
$$|x^2-2y^2|=1,$$
也就是 Pell 方程 \(x^2-2y^2=\pm1\)。因此，本原可平铺三元组构成一条 Pell 族，也可以看成“几乎等腰”的直角三角形族：两条直角边只差 1。对 Euclid 参数，一个方便的递推写法是
$$m_{k+1}=2m_k+n_k,\qquad n_{k+1}=m_k,$$
初值为 \((m_1,n_1)=(2,1)\)。它依次生成
$$ (3,4,5),\ (20,21,29),\ (119,120,169),\ (696,697,985),\dots $$
实现代码并没有直接按这个递推式生成解，而是遍历全部 Euclid 生成元，再用 \(c\bmod |a-b|=0\) 这一条件把同一条 Pell 族筛选出来。
如果 \((a,b,c)\) 是一个合格的本原三元组，那么任意倍数
$$\bigl(ka,kb,kc\bigr)$$
也同样合格，因为
$$|ka-kb|=k|a-b|$$
并且整除关系会被整体缩放保留下来。若该本原三元组的周长是 \(P\)，允许的倍数 \(k\) 必须满足
$$kP<10^8.$$
因此，这一个本原三元组对答案的贡献就是
$$\left\lfloor\frac{10^8-1}{P}\right\rfloor.$$
三份实现累加的正是这个数量。
当周长限制变成 \(P<100\) 时，满足条件的本原三元组只有两个：
$$ (3,4,5)\ (P=12),\qquad (20,21,29)\ (P=70). $$
它们在 100 以内可以产生的所有倍数个数分别是
$$\left\lfloor\frac{99}{12}\right\rfloor=8,\qquad \left\lfloor\frac{99}{70}\right\rfloor=1.$$
所以总数为
$$8+1=9.$$
这正好对应 C++ 实现里使用的小范围校验值。
C++、Python 和 Java 的实现都按照 \(m>n\) 枚举 Euclid 参数。外层循环一旦发现当前 \(m\) 的最小可能周长 \(2m(m+1)\) 已经达到上界，就停止继续增大 \(m\)。内层只保留互素且奇偶性不同的 \((m,n)\)，因为它们恰好对应本原三元组。
对于每个保留下来的 \((m,n)\)，实现都会计算 \(a\)、\(b\)、\(c\) 以及差值 \(d=|a-b|\)，然后检查唯一的条件 \(c\bmod d=0\)。从数学上讲，这一步等价于筛出那条“直角边相差 1”的 Pell 家族；但在程序里，它保持为最直接的算术测试。
一旦某个本原三元组通过筛选，它的周长 \(P\) 就已知了。所有满足 \(kP<10^8\) 的相似三元组都要计数，因此该三元组贡献 \(\left\lfloor(10^8-1)/P\right\rfloor\)。三种语言的实现除了语法外没有本质差别，控制流程完全一致。
记上界为 \(L=10^8\)。因为外层循环在 \(2m(m+1)\ge L\) 时停止，所以最大的 \(m\) 只有 \(O(\sqrt{L})\) 级别。对每个 \(m\)，内层循环考察 \(n=1,2,\dots,m-1\)，因此总的候选参数对 \((m,n)\) 数量是 \(O(L)\)。
每个候选只需要一次 gcd 计算和常数次整数运算。在严格的算术模型下，时间复杂度可写作 \(O(L\log L)\)；如果把机器整数运算视为常数时间，那么它在实践中几乎就是对候选对数目的线性扫描。空间复杂度是 \(O(1)\)，因为程序只维护少量整数和最终累加器。
Нужно посчитать все тройки Пифагора \((a,b,c)\) с периметром \(a+b+c<10^8\), для которых возможна классическая конфигурация с квадратным отверстием в центре. Если поместить четыре одинаковых прямоугольных треугольника в квадрат со стороной \(c\), то посередине останется квадрат со стороной \(|a-b|\). Чтобы такая конструкция действительно порождала замощение, сторона внутреннего квадрата должна делить сторону внешнего. Значит, ключевое арифметическое условие имеет вид
$$|a-b|\mid c.$$
Эффективное решение поэтому сначала перечисляет примитивные тройки, а затем прибавляет все допустимые кратные.
Реализации используют параметризацию Евклида для примитивных троек Пифагора. Но за простой проверкой делимости скрывается более жесткая структура, и именно она объясняет весь алгоритм.
Пусть у прямоугольного треугольника катеты равны \(a,b\), а гипотенуза равна \(c\). Четыре такие копии заполняют квадрат со стороной \(c\). Центральная пустота снова является квадратом, и из геометрии сразу видно, что его сторона равна
$$d=|a-b|.$$
Чтобы большой квадрат можно было полностью замостить повторением такого рисунка, необходимо, чтобы \(d\) делило \(c\). Следовательно, вся задача сводится к условию
$$d\mid c.$$
Именно это условие и проверяют программы.
Любая примитивная тройка Пифагора единственным образом записывается как
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
где \(m>n\ge 1\), \(\gcd(m,n)=1\), а \(m-n\) нечетно. Периметр равен
$$P=a+b+c=2m(m+n).$$
Это и есть реальное пространство перебора: код проходит по подходящим парам \((m,n)\), строит примитивную тройку и проверяет, проходит ли она тест замощения.
Пусть \(d=|a-b|\) для примитивной тройки. Если выполняется условие задачи, то \(d\mid c\). Поскольку одновременно \(d\mid(a-b)\), отсюда следует и
$$d\mid c^2-(a-b)^2.$$
С учетом \(c^2=a^2+b^2\) получаем
$$c^2-(a-b)^2=a^2+b^2-(a^2-2ab+b^2)=2ab,$$
то есть \(d\mid 2ab\).
Теперь используется примитивность: \(\gcd(a,b)=1\), один катет четный, другой нечетный, значит \(d=|a-b|\) нечетно. Кроме того,
$$\gcd(d,a)=\gcd(a-b,a)=\gcd(a,b)=1,\qquad \gcd(d,b)=1.$$
Итак, \(d\) взаимно просто с \(2\), с \(a\) и с \(b\), но при этом делит \(2ab\). Это возможно только при
$$d=1.$$
Обратное направление очевидно: если \(d=1\), то \(d\mid c\) выполняется автоматически. Следовательно, примитивные подходящие тройки - это в точности примитивные тройки Пифагора с соседними катетами.
Подстановка формулы Евклида в условие \(|a-b|=1\) дает
$$|m^2-n^2-2mn|=1.$$
Если ввести \(x=m-n\) и \(y=n\), получится
$$|x^2-2y^2|=1,$$
то есть уравнение Пелля \(x^2-2y^2=\pm1\). Значит, примитивные замощающие тройки образуют Pell-семейство, или, что то же самое, семейство почти равнобедренных прямоугольных треугольников, у которых катеты отличаются на 1. Удобная рекуррентная формула для параметров Евклида такова:
$$m_{k+1}=2m_k+n_k,\qquad n_{k+1}=m_k,$$
при старте \((m_1,n_1)=(2,1)\). Она порождает последовательность
$$ (3,4,5),\ (20,21,29),\ (119,120,169),\ (696,697,985),\dots $$
Сами реализации не строят решения по этой рекурсии, а получают то же семейство, отфильтровывая полный перебор по Евклиду условием \(c\bmod |a-b|=0\).
Если \((a,b,c)\) - подходящая примитивная тройка, то любое кратное
$$\bigl(ka,kb,kc\bigr)$$
тоже подходит, поскольку
$$|ka-kb|=k|a-b|$$
и делимость сохраняется при масштабировании. Если примитивный периметр равен \(P\), допустимые значения \(k\) определяются строгим неравенством
$$kP<10^8.$$
Следовательно, вклад этой одной примитивной тройки равен
$$\left\lfloor\frac{10^8-1}{P}\right\rfloor.$$
Именно это число прибавляют все три реализации.
Если взять границу \(P<100\), то примитивных подходящих троек всего две:
$$ (3,4,5)\ (P=12),\qquad (20,21,29)\ (P=70). $$
Количество их кратных ниже 100 равно
$$\left\lfloor\frac{99}{12}\right\rfloor=8,\qquad \left\lfloor\frac{99}{70}\right\rfloor=1.$$
Значит, итоговый счет равен
$$8+1=9,$$
и именно это маленькое значение используется как проверка в реализации на C++.
Реализации на C++, Python и Java перебирают параметры Евклида с \(m>n\). Внешний цикл останавливается, когда минимальный возможный периметр для данного \(m\), а именно \(2m(m+1)\), достигает границы. Во внутреннем цикле сохраняются только взаимно простые пары разной четности, поскольку именно они порождают примитивные тройки.
Для каждой допустимой пары \((m,n)\) вычисляются \(a\), \(b\), \(c\) и \(d=|a-b|\). После этого выполняется единственная проверка \(c\bmod d=0\). Математически эта проверка эквивалентна выделению Pell-семейства с соседними катетами, но в коде она оставлена в самом прямом арифметическом виде.
Если примитивная тройка прошла тест, ее периметр \(P\) уже известен. Тогда автоматически учитываются все подобные тройки с \(kP<10^8\), то есть в ответ добавляется \(\left\lfloor(10^8-1)/P\right\rfloor\). Во всех трех языках схема одна и та же, различается только синтаксис.
Пусть \(L=10^8\). Поскольку внешний цикл заканчивается при \(2m(m+1)\ge L\), максимальное \(m\) имеет порядок \(O(\sqrt{L})\). Для каждого \(m\) внутренний цикл перебирает \(n=1,2,\dots,m-1\), поэтому общее число кандидатных пар \((m,n)\) равно \(O(L)\).
На каждую пару приходится одно вычисление gcd и постоянное число операций с целыми. Поэтому в строгой арифметической модели время работы равно \(O(L\log L)\), а на машинных целых фиксированной ширины поведение практически линейно по числу проверяемых пар. Память \(O(1)\), потому что хранятся лишь несколько целых чисел и накопленная сумма.
المطلوب هو عد جميع ثلاثيات فيثاغورس \((a,b,c)\) التي تحقق \(a+b+c<10^8\) ويمكنها تكوين الشكل المعروف ذي الفتحة المربعة في الوسط. عند وضع أربع نسخ متطابقة من المثلث القائم داخل مربع ضلعه \(c\)، يتبقى في المنتصف مربع طول ضلعه \(|a-b|\). ولكي يتحول هذا الشكل إلى تبليط حقيقي، يجب أن يقسم طول ضلع المربع الداخلي طول ضلع المربع الخارجي، أي أن الشرط الحاسم هو
$$|a-b|\mid c.$$
لذلك فالطريقة الفعالة هي توليد الثلاثيات البدائية أولًا، ثم احتساب كل المضاعفات المسموح بها دفعة واحدة.
تعتمد التطبيقات على صيغة إقليدس لتوليد ثلاثيات فيثاغورس البدائية، لكن اختبار القسمة البسيط في الشفرة يخفي بنية أقوى بكثير. وعندما تظهر هذه البنية يصبح تفسير الحل كاملًا وواضحًا.
إذا كان للمثلث القائم ضلعان \(a,b\) ووتر \(c\)، فإن أربع نسخ منه تملأ مربعًا ضلعه \(c\). أما الفراغ الأوسط فهو أيضًا مربع، ومن الشكل الهندسي نفسه يتبين أن طول ضلعه هو
$$d=|a-b|.$$
ولكي يمكن تبليط المربع الكبير بتكرار هذا النمط، يجب أن يكون \(d\) قاسمًا لـ \(c\). وهكذا تختزل المسألة كلها إلى التحقق من
$$d\mid c.$$
وهذا بالضبط هو الاختبار الحسابي الوحيد الذي تنفذه التطبيقات.
كل ثلاثية فيثاغورس بدائية تكتب بصورة وحيدة على الشكل
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
حيث \(m>n\ge 1\)، و\(\gcd(m,n)=1\)، و\(m-n\) عدد فردي. أما المحيط فهو
$$P=a+b+c=2m(m+n).$$
وهذا يحدد فضاء البحث الفعلي في الشفرة: المرور على الأزواج \((m,n)\) المسموح بها، وبناء الثلاثية البدائية، ثم اختبار شرط التبليط.
لتكن \(d=|a-b|\) لثلاثية بدائية. إذا تحقق شرط التبليط فلدينا \(d\mid c\). وبما أن \(d\mid(a-b)\) أصلًا، فإننا نحصل أيضًا على
$$d\mid c^2-(a-b)^2.$$
وباستخدام \(c^2=a^2+b^2\) يصبح هذا
$$c^2-(a-b)^2=a^2+b^2-(a^2-2ab+b^2)=2ab,$$
أي إن \(d\mid 2ab\).
الآن نستخدم خاصية البدائية. بما أن \(\gcd(a,b)=1\)، فأحد الضلعين زوجي والآخر فردي، ولذلك يكون \(d=|a-b|\) فرديًا. وكذلك
$$\gcd(d,a)=\gcd(a-b,a)=\gcd(a,b)=1,\qquad \gcd(d,b)=1.$$
إذن \(d\) أولي مع \(2\)، ومع \(a\)، ومع \(b\)، ومع ذلك يقسم \(2ab\). الاحتمال الوحيد هو
$$d=1.$$
والعكس واضح فورًا: إذا كان \(d=1\) فالقسمة على \(c\) تتحقق تلقائيًا. لذلك فإن الثلاثيات البدائية الصالحة هنا هي بالضبط ثلاثيات فيثاغورس البدائية التي يختلف ضلعَاها القائمان فيها بمقدار 1.
عند التعويض بصيغة إقليدس في الشرط \(|a-b|=1\) نحصل على
$$|m^2-n^2-2mn|=1.$$
ولو وضعنا \(x=m-n\) و\(y=n\) يصبح الشرط
$$|x^2-2y^2|=1,$$
أي معادلة بيل \(x^2-2y^2=\pm1\). وهذا يعني أن الثلاثيات البدائية القابلة للتبليط تشكل عائلة من حلول بيل، أو إن شئت عائلة مثلثات قائمة “شبه متساوية الساقين” لأن الفرق بين الضلعين القائمين يساوي 1. ومن التراجعات المناسبة لمعاملات إقليدس
$$m_{k+1}=2m_k+n_k,\qquad n_{k+1}=m_k,$$
مع البداية \((m_1,n_1)=(2,1)\). وهذا يولد
$$ (3,4,5),\ (20,21,29),\ (119,120,169),\ (696,697,985),\dots $$
لا تستخدم التطبيقات هذه العلاقة التراجعية صراحة، لكنها تصل إلى العائلة نفسها عبر المرور على جميع مولدات إقليدس ثم إبقاء الحالات التي تحقق \(c\bmod |a-b|=0\).
إذا كانت \((a,b,c)\) ثلاثية بدائية صالحة، فإن كل مضاعف
$$\bigl(ka,kb,kc\bigr)$$
يبقى صالحًا أيضًا، لأن
$$|ka-kb|=k|a-b|$$
والقابلية للقسمة تبقى محفوظة بعد التكبير. إذا كان محيط الثلاثية البدائية هو \(P\)، فإن قيم \(k\) المسموح بها هي التي تحقق
$$kP<10^8.$$
ولذلك فإن مساهمة هذه الثلاثية الواحدة في الجواب هي
$$\left\lfloor\frac{10^8-1}{P}\right\rfloor.$$
وهذه هي الكمية التي تجمعها التطبيقات الثلاثة حرفيًا.
عندما يكون الشرط \(P<100\)، فإن الثلاثيات البدائية الصالحة الوحيدة هي
$$ (3,4,5)\ (P=12),\qquad (20,21,29)\ (P=70). $$
عدد مضاعفات كل منهما تحت 100 هو
$$\left\lfloor\frac{99}{12}\right\rfloor=8,\qquad \left\lfloor\frac{99}{70}\right\rfloor=1.$$
إذًا المجموع النهائي يساوي
$$8+1=9,$$
وهو تمامًا مقدار نقطة التحقق الصغيرة المستخدمة في تنفيذ C++.
تقوم تطبيقات C++ وPython وJava بالمرور على معاملات إقليدس بحيث \(m>n\). تتوقف الحلقة الخارجية عندما يصل أصغر محيط ممكن لذلك \(m\)، وهو \(2m(m+1)\)، إلى الحد المطلوب. وفي الداخل لا تُقبل إلا الأزواج المتباينة في الفردية والأولية فيما بينها، لأنها هي التي تولد الثلاثيات البدائية فقط.
لكل زوج مسموح \((m,n)\)، تحسب الشفرة \(a\) و\(b\) و\(c\) و\(d=|a-b|\)، ثم تفحص الشرط الوحيد \(c\bmod d=0\). من الناحية الرياضية هذا مكافئ لاختيار عائلة بيل ذات الضلعين المتتاليين، لكن التنفيذ يبقيه في صورة اختبار حسابي مباشر.
بمجرد أن تنجح ثلاثية بدائية في الاختبار، يصبح محيطها \(P\) معلومًا. بعد ذلك تُحسب كل النسخ المشابهة التي تحقق \(kP<10^8\)، أي تضاف الكمية \(\left\lfloor(10^8-1)/P\right\rfloor\) إلى الجواب. تختلف النسخ الثلاث في الصياغة اللغوية فقط، أما منطق العد نفسه فهو واحد.
لنرمز للحد بـ \(L=10^8\). بما أن الحلقة الخارجية تتوقف عند \(2m(m+1)\ge L\)، فإن أكبر قيمة لـ \(m\) هي من الرتبة \(O(\sqrt{L})\). ولكل \(m\)، تمر الحلقة الداخلية على \(n=1,2,\dots,m-1\)، ولذلك فإن عدد الأزواج المرشحة \((m,n)\) هو \(O(L)\).
كل زوج يحتاج إلى حساب gcd واحد وإلى عدد ثابت من عمليات الأعداد الصحيحة. ومن ثم يكون الزمن \(O(L\log L)\) في نموذج حسابي صارم، بينما يكون السلوك العملي شبه خطي في عدد الأزواج المختبرة عند اعتبار أعداد الآلة ثابتة الكلفة. أما الذاكرة فهي \(O(1)\)، لأن التنفيذ يحتفظ بعدد قليل فقط من القيم الصحيحة والمجموع الجاري.