For an integer wire length \(L\), we ask whether it can be bent into a right triangle with integer side lengths \((a,b,c)\). The goal is to count how many perimeters \(L \le 1{,}500{,}000\) admit exactly one such triangle.
The difficulty is that the same perimeter may come from several different Pythagorean triples. So the real task is not merely to generate right triangles, but to count how many distinct integer right triangles correspond to each perimeter.
The solution is built around Euclid's parametrization of primitive Pythagorean triples. Once primitive triples are generated, every non-primitive triple appears as an integer multiple of one of them, so the whole problem becomes a perimeter-counting sieve.
Every primitive integer right triangle can be written in the form
$$a = m^2 - n^2,\qquad b = 2mn,\qquad c = m^2 + n^2,$$
with integers \(m > n > 0\), \(\gcd(m,n)=1\), and \(m-n\) odd. The coprimality condition removes a common scale factor, and the parity condition prevents all three sides from being even. Conversely, each such pair \((m,n)\) produces one primitive Pythagorean triple.
Adding the three sides gives the primitive perimeter
$$p_0 = a+b+c = (m^2-n^2)+2mn+(m^2+n^2)=2m(m+n).$$
This already explains two important facts used by the implementations. First, every right-triangle perimeter counted by the program is even. Second, for a fixed \(m\), the smallest possible primitive perimeter occurs at \(n=1\), namely \(2m(m+1)\). Therefore, once \(2m(m+1) > N\), no larger \(m\) can contribute any perimeter up to the limit.
Every non-primitive Pythagorean triple is uniquely of the form \(k(a,b,c)\), where \((a,b,c)\) is primitive and \(k \ge 1\). Its perimeter is then \(kp_0\). So from each primitive perimeter \(p_0\), all valid perimeters generated by that family are exactly
$$p_0,\ 2p_0,\ 3p_0,\ \dots \le N.$$
This gives the key invariant of the algorithm: if we increment a counter for every multiple of every primitive perimeter, then after all primitive generators have been processed, the counter at index \(L\) is exactly the number of distinct integer right triangles with perimeter \(L\).
The problem statement mentions \(L=120\), and Euclid's formula explains the three representations cleanly. Three primitive generators already suffice:
\(m=2,n=1\) gives \((3,4,5)\) with \(p_0=12\),
\(m=3,n=2\) gives \((5,12,13)\) with \(p_0=30\),
\(m=4,n=1\) gives \((15,8,17)\) with \(p_0=40\).
Since \(120 = 10 \cdot 12 = 4 \cdot 30 = 3 \cdot 40\), the perimeter \(120\) is produced by
$$ (30,40,50),\qquad (20,48,52),\qquad (24,45,51). $$
So \(120\) is not singular. By contrast, \(L=12\) comes only from \((3,4,5)\), so it is singular. The final answer is therefore the number of perimeters whose counter value is exactly \(1\).
The C++, Python, and Java implementations iterate over \(m \ge 2\) while \(2m(m+1) \le N\). For each \(m\), they test all \(1 \le n < m\), reject pairs with even \(m-n\), and reject pairs with \(\gcd(m,n)\ne 1\). The surviving pairs are precisely the primitive generators required by Euclid's formula.
For each accepted pair, the implementation computes the primitive perimeter \(p_0 = 2m(m+n)\). It then walks through the arithmetic progression \(p_0, 2p_0, 3p_0, \dots\) up to the limit and increments a perimeter-frequency array at each step. This is the entire counting mechanism: every valid triangle contributes exactly one increment to its own perimeter.
After all primitive generators have been processed, the implementation scans the array and counts how many entries are equal to \(1\). That is exactly the number of singular wire lengths. The C++ and Python implementations also verify the smaller checkpoint \(N=150\), for which the correct count is \(16\), before evaluating the main limit; the Java implementation applies the same algorithm directly to \(1{,}500{,}000\).
The parameter search itself is bounded by \(m \le \sqrt{N/2}\), so enumerating candidate pairs \((m,n)\) costs \(O(N)\) in the worst case. The larger part of the work is updating all multiples of each primitive perimeter.
If the primitive perimeters are \(p_0\), then the number of counter updates is
$$\sum_{p_0}\left\lfloor\frac{N}{p_0}\right\rfloor.$$
This behaves like a harmonic sum over the generated primitive perimeters and is comfortably near \(O(N \log N)\) for this problem size. Memory usage is \(O(N)\) because the implementation stores one counter per perimeter up to \(1{,}500{,}000\).
Für eine Drahtlänge \(L\) soll entschieden werden, ob sich daraus ein rechtwinkliges Dreieck mit ganzzahligen Seiten \((a,b,c)\) formen lässt. Gesucht ist die Anzahl der Umfänge \(L \le 1{,}500{,}000\), für die das auf genau eine Weise möglich ist.
Die Schwierigkeit liegt darin, dass derselbe Umfang zu mehreren verschiedenen pythagoreischen Tripeln gehören kann. Deshalb muss man nicht nur Dreiecke erzeugen, sondern für jeden Umfang exakt mitzählen, wie viele verschiedene ganzzahlige rechtwinklige Dreiecke es dazu gibt.
Die Lösung basiert auf Euklids Parametrisierung primitiver pythagoreischer Tripel. Sobald alle primitiven Tripel erzeugt sind, entstehen alle nicht-primitiven Tripel als ganzzahlige Vielfache davon. Damit wird das Problem zu einem Sieb über Umfänge.
Jedes primitive ganzzahlige rechtwinklige Dreieck hat die Form
$$a = m^2 - n^2,\qquad b = 2mn,\qquad c = m^2 + n^2,$$
wobei \(m > n > 0\), \(\gcd(m,n)=1\) und \(m-n\) ungerade ist. Die Teilerfremdheit entfernt einen gemeinsamen Faktor, und die entgegengesetzte Parität verhindert, dass alle drei Seiten gerade sind. Umgekehrt liefert jedes solche Paar \((m,n)\) genau ein primitives pythagoreisches Tripel.
Der primitive Umfang ist
$$p_0 = a+b+c = (m^2-n^2)+2mn+(m^2+n^2)=2m(m+n).$$
Daraus folgen sofort zwei für den Code wichtige Beobachtungen. Erstens ist jeder mögliche Umfang eines ganzzahligen rechtwinkligen Dreiecks gerade. Zweitens ist für festes \(m\) der kleinste primitive Umfang bei \(n=1\) gleich \(2m(m+1)\). Sobald also \(2m(m+1) > N\) gilt, kann kein größeres \(m\) mehr einen Umfang bis zur Grenze liefern.
Jedes nicht-primitive pythagoreische Tripel lässt sich eindeutig als \(k(a,b,c)\) schreiben, wobei \((a,b,c)\) primitiv und \(k \ge 1\) ist. Sein Umfang ist dann \(kp_0\). Für jedes primitive \(p_0\) sind die dazugehörigen gültigen Umfänge also genau
$$p_0,\ 2p_0,\ 3p_0,\ \dots \le N.$$
Das ist die zentrale Invariante des Algorithmus: Erhöht man für jedes primitive \(p_0\) die Zähler aller seiner Vielfachen, dann steht nach Abschluss aller Durchläufe an Position \(L\) genau die Anzahl der verschiedenen ganzzahligen rechtwinkligen Dreiecke mit Umfang \(L\).
Die Angabe \(L=120\) aus der Problemstellung lässt sich mit der Parametrisierung direkt erklären. Schon drei primitive Erzeuger reichen:
\(m=2,n=1\) liefert \((3,4,5)\) mit \(p_0=12\),
\(m=3,n=2\) liefert \((5,12,13)\) mit \(p_0=30\),
\(m=4,n=1\) liefert \((15,8,17)\) mit \(p_0=40\).
Weil \(120 = 10 \cdot 12 = 4 \cdot 30 = 3 \cdot 40\), entsteht der Umfang \(120\) durch
$$ (30,40,50),\qquad (20,48,52),\qquad (24,45,51). $$
Also ist \(120\) nicht singulär. Dagegen kommt \(L=12\) nur von \((3,4,5)\) und ist damit singulär. Gesucht ist somit die Anzahl aller Umfänge mit Zählerwert \(1\).
Die Implementierungen in C++, Python und Java iterieren über \(m \ge 2\), solange \(2m(m+1) \le N\) gilt. Für jedes \(m\) werden alle \(1 \le n < m\) geprüft; Paare mit geradem \(m-n\) oder mit \(\gcd(m,n)\ne 1\) werden verworfen. Genau die übrigen Paare sind die primitiven Erzeuger aus Euklids Formel.
Für jedes akzeptierte Paar wird der primitive Umfang \(p_0 = 2m(m+n)\) berechnet. Danach läuft die Implementierung über die arithmetische Folge \(p_0, 2p_0, 3p_0, \dots\) bis zur Grenze und erhöht für jeden dieser Werte einen Zähler im Umfangsarray. Das funktioniert wie ein Sieb: Jede weitere darstellbare Dreiecksform erhöht die Häufigkeit ihres Umfangs um eins.
Nach der Vorverarbeitung wird das Array einmal vollständig durchsucht, und alle Einträge mit Wert \(1\) werden gezählt. Genau das ist die Anzahl der singulären Drahtlängen. Die C++- und Python-Implementierungen prüfen zusätzlich den kleineren Testfall \(N=150\), für den das korrekte Ergebnis \(16\) ist; die Java-Implementierung wendet dieselbe Methode direkt auf \(1{,}500{,}000\) an.
Die Suche im Parameterraum ist durch \(m \le \sqrt{N/2}\) beschränkt. Das reine Durchlaufen der Kandidatenpaare \((m,n)\) kostet damit im Worst Case \(O(N)\). Der größere Aufwand entsteht durch das Markieren aller Vielfachen eines primitiven Umfangs.
Ist \(p_0\) ein primitiver Umfang, dann beträgt die Gesamtzahl der Array-Aktualisierungen
$$\sum_{p_0}\left\lfloor\frac{N}{p_0}\right\rfloor.$$
Diese Summe verhält sich wie eine harmonische Summe über die erzeugten primitiven Umfänge und liegt für diese Problemgröße bequem in der Nähe von \(O(N \log N)\). Der Speicherbedarf ist \(O(N)\), da bis zur Grenze genau ein Zähler pro Umfang gespeichert wird.
\(L\) uzunluğunda bir telin, kenarları tamsayı olan bir dik üçgen oluşturacak şekilde bükülüp bükülemeyeceğini inceliyoruz. Amaç, \(L \le 1{,}500{,}000\) için tam olarak bir farklı çözüm veren çevrelerin sayısını bulmaktır.
Zorluk şuradadır: aynı çevre birden fazla Pisagor üçlüsünden gelebilir. Bu yüzden yalnızca dik üçgen üretmek yetmez; her çevrenin kaç farklı tamsayı dik üçgene karşılık geldiğini de doğru biçimde saymak gerekir.
Çözüm, ilkel Pisagor üçlüleri için Öklid parametreleştirmesine dayanır. İlkel üçlüler üretildikten sonra, ilkel olmayan bütün üçlüler bunların tamsayı katları olarak ortaya çıkar. Böylece problem, çevreler üzerinde çalışan bir sayma eleğine dönüşür.
Her ilkel tamsayı dik üçgen şu biçimde yazılabilir:
$$a = m^2 - n^2,\qquad b = 2mn,\qquad c = m^2 + n^2,$$
burada \(m > n > 0\), \(\gcd(m,n)=1\) ve \(m-n\) tektir. Aralarında asal olma koşulu ortak bir ölçeği kaldırır; zıt parity koşulu ise üç kenarın birden çift olmasını engeller. Tersine, bu şartları sağlayan her \((m,n)\) çifti tam bir ilkel Pisagor üçlüsü üretir.
İlkel çevre
$$p_0 = a+b+c = (m^2-n^2)+2mn+(m^2+n^2)=2m(m+n)$$
olur. Buradan kodda kullanılan iki önemli sonuç çıkar. Birincisi, tamsayı dik üçgenlerin bütün çevreleri çifttir. İkincisi, sabit bir \(m\) için mümkün olan en küçük ilkel çevre \(n=1\) iken \(2m(m+1)\) değeridir. Dolayısıyla \(2m(m+1) > N\) olduğunda daha büyük hiçbir \(m\), sınıra kadar yeni bir çevre üretemez.
İlkel olmayan her Pisagor üçlüsü, tek biçimde \(k(a,b,c)\) şeklinde yazılır; burada \((a,b,c)\) ilkel ve \(k \ge 1\) olur. Çevresi de \(kp_0\) olur. Bu yüzden her ilkel \(p_0\) için o aileden gelen bütün geçerli çevreler tam olarak
$$p_0,\ 2p_0,\ 3p_0,\ \dots \le N$$
değerleridir. Algoritmanın temel değişmezi budur: her ilkel çevrenin bütün katlarında sayaç bir artırılırsa, işlem bittikten sonra \(L\) indisindeki değer tam olarak çevresi \(L\) olan farklı tamsayı dik üçgenlerin sayısını verir.
Soruda vurgulanan \(L=120\) değeri parametreleştirme ile hemen açıklanır. Üç ilkel üretici yeterlidir:
\(m=2,n=1\) için \((3,4,5)\) ve \(p_0=12\),
\(m=3,n=2\) için \((5,12,13)\) ve \(p_0=30\),
\(m=4,n=1\) için \((15,8,17)\) ve \(p_0=40\).
\(120 = 10 \cdot 12 = 4 \cdot 30 = 3 \cdot 40\) olduğu için \(120\) çevresi şu üçgenden gelir:
$$ (30,40,50),\qquad (20,48,52),\qquad (24,45,51). $$
Bu nedenle \(120\) tekil değildir. Buna karşılık \(L=12\) yalnızca \((3,4,5)\) üçlüsünden gelir ve tekildir. Sonuçta aradığımız şey, sayacı tam olarak \(1\) olan çevrelerin sayısıdır.
C++, Python ve Java uygulamaları \(m \ge 2\) için \(2m(m+1) \le N\) olduğu sürece döner. Her \(m\) için \(1 \le n < m\) aralığı incelenir; \(m-n\) çiftse veya \(\gcd(m,n)\ne 1\) ise çift elenir. Geriye kalan çiftler, Öklid formülündeki ilkel üreticilerdir.
Her kabul edilen çift için ilkel çevre \(p_0 = 2m(m+n)\) hesaplanır. Sonra uygulama \(p_0, 2p_0, 3p_0, \dots\) aritmetik dizisini sınır aşılana kadar dolaşır ve her adımda bir çevre-frekans dizisini artırır. Sayım mekanizmasının tamamı budur: geçerli her üçgen kendi çevresine tam bir katkı yapar.
Bütün ilkel üreticiler işlendiğinde dizi baştan sona taranır ve değeri \(1\) olan girişler sayılır. Bu, tekil tel uzunluklarının sayısıdır. C++ ve Python uygulamaları ana sınıra geçmeden önce \(N=150\) için doğru sonucun \(16\) olduğunu da doğrular; Java uygulaması ise aynı yöntemi doğrudan \(1{,}500{,}000\) için uygular.
Parametre uzayındaki tarama \(m \le \sqrt{N/2}\) ile sınırlıdır; dolayısıyla aday \((m,n)\) çiftlerini dolaşmanın en kötü durum maliyeti \(O(N)\) olur. Asıl ek yük, her ilkel çevrenin tüm katlarının işaretlenmesidir.
İlkel çevreler \(p_0\) ile gösterilirse toplam sayaç güncellemesi sayısı
$$\sum_{p_0}\left\lfloor\frac{N}{p_0}\right\rfloor$$
şeklindedir. Bu toplam, üretilen ilkel çevreler üzerinde harmonik tipte davranır ve bu problem boyutunda rahatça \(O(N \log N)\) mertebesindedir. Bellek kullanımı \(O(N)\)'dir; çünkü üst sınıra kadar her çevre için bir sayaç tutulur.
Dada una longitud de alambre \(L\), queremos saber si puede doblarse para formar un triángulo rectángulo con lados enteros \((a,b,c)\). El objetivo es contar cuántos perímetros \(L \le 1{,}500{,}000\) admiten exactamente una solución.
La dificultad es que un mismo perímetro puede corresponder a varias ternas pitagóricas distintas. Por eso no basta con generar triángulos rectángulos enteros: también hay que contar cuántas representaciones tiene cada perímetro.
La solución se apoya en la parametrización de Euclides para las ternas pitagóricas primitivas. Una vez generadas las ternas primitivas, todas las no primitivas aparecen como múltiplos enteros de alguna de ellas. Así, el problema se transforma en un cribado de perímetros.
Toda terna pitagórica primitiva puede escribirse como
$$a = m^2 - n^2,\qquad b = 2mn,\qquad c = m^2 + n^2,$$
con enteros \(m > n > 0\), \(\gcd(m,n)=1\) y \(m-n\) impar. La condición de coprimalidad elimina un factor común, y la condición de paridad impide que las tres longitudes sean pares a la vez. A la inversa, cada par \((m,n)\) que cumple esas condiciones produce una única terna primitiva.
El perímetro primitivo es
$$p_0 = a+b+c = (m^2-n^2)+2mn+(m^2+n^2)=2m(m+n).$$
De aquí salen dos hechos importantes para el algoritmo. Primero, todo perímetro de un triángulo rectángulo entero es par. Segundo, para un \(m\) fijo, el menor perímetro primitivo aparece cuando \(n=1\), y vale \(2m(m+1)\). Por tanto, en cuanto \(2m(m+1) > N\), ningún valor mayor de \(m\) puede contribuir un perímetro válido.
Toda terna pitagórica no primitiva se escribe de manera única como \(k(a,b,c)\), donde \((a,b,c)\) es primitiva y \(k \ge 1\). Su perímetro es entonces \(kp_0\). Por ello, para cada perímetro primitivo \(p_0\), los perímetros válidos que pertenecen a esa familia son exactamente
$$p_0,\ 2p_0,\ 3p_0,\ \dots \le N.$$
Ésa es la invariante central del método: si incrementamos un contador en todos los múltiplos de cada perímetro primitivo, al final el valor almacenado en \(L\) coincide exactamente con el número de triángulos rectángulos enteros distintos de perímetro \(L\).
El caso \(L=120\) mencionado en el enunciado se explica de inmediato con la parametrización. Bastan tres generadores primitivos:
\(m=2,n=1\) produce \((3,4,5)\) con \(p_0=12\),
\(m=3,n=2\) produce \((5,12,13)\) con \(p_0=30\),
\(m=4,n=1\) produce \((15,8,17)\) con \(p_0=40\).
Como \(120 = 10 \cdot 12 = 4 \cdot 30 = 3 \cdot 40\), el perímetro \(120\) aparece en
$$ (30,40,50),\qquad (20,48,52),\qquad (24,45,51). $$
Así que \(120\) no es singular. En cambio, \(L=12\) sólo aparece a partir de \((3,4,5)\), y por eso sí es singular. La respuesta final es el número de perímetros cuyo contador vale exactamente \(1\).
Las implementaciones en C++, Python y Java recorren \(m \ge 2\) mientras \(2m(m+1) \le N\). Para cada \(m\), prueban todos los \(n\) con \(1 \le n < m\), descartan los pares con \(m-n\) par y descartan los pares con \(\gcd(m,n)\ne 1\). Los pares que sobreviven son exactamente los generadores primitivos de la fórmula de Euclides.
Para cada par aceptado, la implementación calcula el perímetro primitivo \(p_0 = 2m(m+n)\). Después recorre la progresión aritmética \(p_0, 2p_0, 3p_0, \dots\) hasta el límite y aumenta un arreglo de frecuencias en cada uno de esos perímetros. Ese arreglo actúa como un cribado: cada nueva realización válida de un triángulo incrementa en uno el contador de su perímetro.
Una vez procesados todos los generadores primitivos, el programa recorre el arreglo y cuenta cuántas entradas son iguales a \(1\). Eso da exactamente el número de perímetros singulares. Las versiones en C++ y Python también verifican el caso pequeño \(N=150\), donde la respuesta correcta es \(16\), antes de evaluar el límite principal; la versión en Java aplica el mismo algoritmo directamente a \(1{,}500{,}000\).
La búsqueda en el espacio de parámetros está acotada por \(m \le \sqrt{N/2}\), así que recorrer los pares candidatos \((m,n)\) cuesta \(O(N)\) en el peor caso. El trabajo adicional importante está en marcar todos los múltiplos de cada perímetro primitivo.
Si denotamos por \(p_0\) los perímetros primitivos, el número total de actualizaciones del arreglo es
$$\sum_{p_0}\left\lfloor\frac{N}{p_0}\right\rfloor.$$
Esta suma se comporta como una suma armónica sobre los perímetros primitivos generados y queda cómodamente cerca de \(O(N \log N)\) para este tamaño de entrada. El uso de memoria es \(O(N)\), porque se guarda un contador por perímetro hasta \(1{,}500{,}000\).
给定一段长度为 \(L\) 的铁丝，问它是否能被弯成一个边长全为整数的直角三角形 \((a,b,c)\)。题目要求统计满足 \(L \le 1{,}500{,}000\) 且恰好只有一种构造方式的周长个数。
难点在于，同一个周长可能对应多个不同的勾股三元组。因此，真正要做的不是简单枚举直角三角形，而是对每个周长精确统计它能由多少个不同的整数直角三角形得到。
整个解法建立在欧几里得对本原勾股三元组的参数化之上。一旦本原三元组被完整生成，所有非本原三元组都只是它们的整数倍，于是问题就变成了对周长做一次计数筛。
每一个本原整数直角三角形都可以写成
$$a = m^2 - n^2,\qquad b = 2mn,\qquad c = m^2 + n^2,$$
其中 \(m > n > 0\)，\(\gcd(m,n)=1\)，并且 \(m-n\) 为奇数。互素条件去掉公共缩放因子，奇偶性条件保证三条边不会同时为偶数。反过来，任何满足这些条件的 \((m,n)\) 都会生成唯一一个本原勾股三元组。
把三条边相加，可得本原周长
$$p_0 = a+b+c = (m^2-n^2)+2mn+(m^2+n^2)=2m(m+n).$$
这个公式立刻带来两个实现层面非常重要的结论。第一，所有整数直角三角形的周长都一定是偶数。第二，在固定 \(m\) 的情况下，最小的本原周长出现在 \(n=1\) 时，等于 \(2m(m+1)\)。所以一旦 \(2m(m+1) > N\)，更大的 \(m\) 就不可能再产生不超过上界的周长。
任意一个非本原勾股三元组都能唯一地写成 \(k(a,b,c)\)，其中 \((a,b,c)\) 是本原三元组，且 \(k \ge 1\)。它的周长因此就是 \(kp_0\)。于是，对每个本原周长 \(p_0\)，这一家族所能贡献的全部合法周长恰好是
$$p_0,\ 2p_0,\ 3p_0,\ \dots \le N.$$
这正是算法的核心不变量：如果对每个本原周长的所有倍数都把计数器加一，那么全部处理结束后，数组在位置 \(L\) 处的值就等于周长为 \(L\) 的不同整数直角三角形个数。
题目中专门提到 \(L=120\)，而参数化可以直接解释它为什么不会被计入答案。下面三个本原生成器已经足够：
\(m=2,n=1\) 生成 \((3,4,5)\)，其本原周长为 \(12\)；
\(m=3,n=2\) 生成 \((5,12,13)\)，其本原周长为 \(30\)；
\(m=4,n=1\) 生成 \((15,8,17)\)，其本原周长为 \(40\)。
因为 \(120 = 10 \cdot 12 = 4 \cdot 30 = 3 \cdot 40\)，所以周长 \(120\) 对应下列三个三角形：
$$ (30,40,50),\qquad (20,48,52),\qquad (24,45,51). $$
因此 \(120\) 不是“恰好一种”的周长。相反，\(L=12\) 只能由 \((3,4,5)\) 这一组得到，所以它是唯一周长。最终答案就是所有计数值恰好等于 \(1\) 的周长个数。
C++、Python 和 Java 实现都从 \(m \ge 2\) 开始，只要 \(2m(m+1) \le N\) 就继续。对每个 \(m\)，程序检查所有满足 \(1 \le n < m\) 的候选值，去掉 \(m-n\) 为偶数的情况，再去掉 \(\gcd(m,n)\ne 1\) 的情况。留下来的恰好就是欧几里得公式需要的本原生成参数。
对于每个通过筛选的参数对，程序先算出本原周长 \(p_0 = 2m(m+n)\)。然后沿着等差序列 \(p_0, 2p_0, 3p_0, \dots\) 一直走到上界，并在周长计数数组中把这些位置各加一。这个过程就像筛法：每发现一种新的整数直角三角形，就把对应周长的出现次数增加一次。
当所有本原生成器都处理完后，程序线性扫描整个数组，统计其中值恰好为 \(1\) 的项数。这就是唯一周长的总数。C++ 和 Python 实现还会先验证较小的检查点 \(N=150\)，此时正确答案是 \(16\)；Java 实现则把同样的算法直接用于 \(1{,}500{,}000\) 这一主上界。
参数搜索由 \(m \le \sqrt{N/2}\) 限定，因此单纯枚举候选 \((m,n)\) 对的最坏代价是 \(O(N)\)。更主要的额外开销来自对每个本原周长的全部倍数进行更新。
若把本原周长记作 \(p_0\)，那么总更新次数为
$$\sum_{p_0}\left\lfloor\frac{N}{p_0}\right\rfloor.$$
这可以看作对生成出来的本原周长做一类调和级数求和；在本题规模下，它稳定地落在接近 \(O(N \log N)\) 的量级。空间复杂度为 \(O(N)\)，因为程序为从 \(0\) 到 \(1{,}500{,}000\) 的每个周长维护了一个计数器。
Для длины проволоки \(L\) нужно выяснить, можно ли согнуть ее в прямоугольный треугольник с целыми сторонами \((a,b,c)\). Требуется посчитать, для скольких периметров \(L \le 1{,}500{,}000\) существует ровно одно такое представление.
Главная трудность в том, что один и тот же периметр может соответствовать нескольким различным пифагоровым тройкам. Поэтому нужно не просто генерировать прямоугольные треугольники, а точно подсчитать число представлений каждого периметра.
Решение основано на параметризации Евклида для примитивных пифагоровых троек. После генерации всех примитивных троек все остальные получаются как их целые кратные. Тем самым задача превращается в подсчет по периметрам с помощью своеобразного решета.
Любая примитивная целочисленная прямоугольная тройка имеет вид
$$a = m^2 - n^2,\qquad b = 2mn,\qquad c = m^2 + n^2,$$
где \(m > n > 0\), \(\gcd(m,n)=1\), а \(m-n\) нечетно. Условие взаимной простоты убирает общий множитель, а условие на четность не позволяет всем трем сторонам быть четными одновременно. И наоборот, любое такое \((m,n)\) порождает ровно одну примитивную пифагорову тройку.
Для примитивной тройки периметр равен
$$p_0 = a+b+c = (m^2-n^2)+2mn+(m^2+n^2)=2m(m+n).$$
Отсюда сразу следуют два факта, которыми пользуется реализация. Во-первых, любой периметр целочисленного прямоугольного треугольника обязан быть четным. Во-вторых, при фиксированном \(m\) минимальный примитивный периметр достигается при \(n=1\) и равен \(2m(m+1)\). Поэтому как только \(2m(m+1) > N\), никакое большее \(m\) уже не даст периметр в пределах лимита.
Любая непримитивная пифагорова тройка единственным образом записывается как \(k(a,b,c)\), где \((a,b,c)\) примитивна, а \(k \ge 1\). Ее периметр тогда равен \(kp_0\). Значит, для каждого примитивного \(p_0\) все допустимые периметры этой семьи имеют вид
$$p_0,\ 2p_0,\ 3p_0,\ \dots \le N.$$
В этом и состоит основной инвариант алгоритма: если для каждого примитивного периметра увеличивать счетчик у всех его кратных, то после завершения всех проходов значение в позиции \(L\) будет в точности равно числу различных целочисленных прямоугольных треугольников периметра \(L\).
Периметр \(120\), упомянутый в условии, удобно объясняется прямо через параметризацию. Достаточно трех примитивных генераторов:
\(m=2,n=1\) дает \((3,4,5)\) с \(p_0=12\),
\(m=3,n=2\) дает \((5,12,13)\) с \(p_0=30\),
\(m=4,n=1\) дает \((15,8,17)\) с \(p_0=40\).
Поскольку \(120 = 10 \cdot 12 = 4 \cdot 30 = 3 \cdot 40\), этот периметр возникает у треугольников
$$ (30,40,50),\qquad (20,48,52),\qquad (24,45,51). $$
Следовательно, \(120\) не является особым. Напротив, \(L=12\) получается только из \((3,4,5)\), поэтому он дает ровно одно представление. В итоге нужно подсчитать количество периметров со значением счетчика, равным \(1\).
Реализации на C++, Python и Java перебирают \(m \ge 2\), пока выполняется \(2m(m+1) \le N\). Для каждого \(m\) рассматриваются все \(n\) из диапазона \(1 \le n < m\); пары с четным \(m-n\) отбрасываются, пары с \(\gcd(m,n)\ne 1\) тоже отбрасываются. Оставшиеся пары и есть именно те примитивные генераторы, которые нужны по формуле Евклида.
Для каждой принятой пары вычисляется примитивный периметр \(p_0 = 2m(m+n)\). Затем реализация проходит по арифметической прогрессии \(p_0, 2p_0, 3p_0, \dots\) до верхней границы и увеличивает частотный счетчик в каждом таком периметре. Это и есть вся схема подсчета: каждый допустимый треугольник ровно один раз добавляет единицу своему периметру.
После обработки всех примитивных генераторов массив просматривается целиком, и подсчитываются все ячейки со значением \(1\). Это и есть число особых длин проволоки. Версии на C++ и Python дополнительно проверяют контрольный пример \(N=150\), где правильный ответ равен \(16\), а версия на Java применяет тот же алгоритм сразу к пределу \(1{,}500{,}000\).
Пространство параметров ограничено условием \(m \le \sqrt{N/2}\), поэтому сам перебор кандидатных пар \((m,n)\) имеет стоимость \(O(N)\) в худшем случае. Более заметная часть времени уходит на обновление всех кратных каждого примитивного периметра.
Если обозначить примитивные периметры через \(p_0\), то общее число обновлений массива равно
$$\sum_{p_0}\left\lfloor\frac{N}{p_0}\right\rfloor.$$
Эта сумма ведет себя как гармонический ряд по порожденным примитивным периметрам и для данного ограничения уверенно лежит рядом с \(O(N \log N)\). Память составляет \(O(N)\), поскольку хранится по одному счетчику на каждый периметр вплоть до \(1{,}500{,}000\).
لدينا سلك طوله \(L\)، ونريد أن نعرف هل يمكن ثنيه ليكوّن مثلثًا قائم الزاوية بأضلاع صحيحة \((a,b,c)\). المطلوب هو عدّ قيم \(L \le 1{,}500{,}000\) التي تسمح بطريقة واحدة فقط لبناء مثل هذا المثلث.
الصعوبة أن المحيط نفسه قد ينتج من أكثر من ثلاثية فيثاغورية واحدة. لذلك فالمسألة ليست مجرد توليد مثلثات قائمة صحيحة، بل عدّ عدد التمثيلات المختلفة لكل محيط بدقة.
الحل يعتمد على صيغة إقليدس لتوليد الثلاثيات الفيثاغورية البدائية. وبعد توليد الثلاثيات البدائية، فإن كل ثلاثية غير بدائية تظهر فقط كمضاعف صحيح لإحدى هذه الثلاثيات. عندئذ تتحول المسألة إلى عملية غربلة على المحيطات.
كل مثلث قائم صحيح بدائي يمكن كتابته على الصورة
$$a = m^2 - n^2,\qquad b = 2mn,\qquad c = m^2 + n^2,$$
حيث \(m > n > 0\)، و\(\gcd(m,n)=1\)، و\(m-n\) عدد فردي. شرط التباين النسبي يزيل أي عامل مشترك، وشرط الفردية يمنع أن تكون الأضلاع الثلاثة كلها زوجية. وبالعكس، كل زوج \((m,n)\) يحقق هذه الشروط يولد ثلاثية فيثاغورية بدائية واحدة بالضبط.
محيط الثلاثية البدائية يساوي
$$p_0 = a+b+c = (m^2-n^2)+2mn+(m^2+n^2)=2m(m+n).$$
ومن هذه الصيغة تظهر حقيقتان مهمتان جدًا للتنفيذ. الأولى أن كل محيط لمثلث قائم صحيح لا بد أن يكون زوجيًا. والثانية أن أصغر محيط بدائي لقيمة ثابتة من \(m\) يظهر عند \(n=1\)، ويساوي \(2m(m+1)\). لذلك ما إن يصبح \(2m(m+1) > N\)، فلن يتمكن أي \(m\) أكبر من إنتاج محيط لا يتجاوز الحد.
كل ثلاثية فيثاغورية غير بدائية تُكتب بشكل وحيد على الصورة \(k(a,b,c)\)، حيث \((a,b,c)\) ثلاثية بدائية و\(k \ge 1\). وعندئذ يكون محيطها \(kp_0\). إذن فلكل محيط بدائي \(p_0\)، تكون جميع المحيطات الصحيحة التابعة له هي
$$p_0,\ 2p_0,\ 3p_0,\ \dots \le N.$$
وهذا هو الثابت الأساسي في الخوارزمية: إذا زدنا عدادًا واحدًا عند كل مضاعف لكل محيط بدائي، فإن القيمة الموجودة في الموضع \(L\) بعد انتهاء جميع المعالجات ستكون مساوية تمامًا لعدد المثلثات القائمة الصحيحة المختلفة ذات المحيط \(L\).
القيمة \(L=120\) المذكورة في نص المسألة تتضح مباشرة من خلال هذه الصيغة. ثلاثة مولدات بدائية تكفي:
\(m=2,n=1\) تعطي \((3,4,5)\) ومحيطها البدائي \(12\)،
\(m=3,n=2\) تعطي \((5,12,13)\) ومحيطها البدائي \(30\)،
\(m=4,n=1\) تعطي \((15,8,17)\) ومحيطها البدائي \(40\).
وبما أن \(120 = 10 \cdot 12 = 4 \cdot 30 = 3 \cdot 40\)، فإن المحيط \(120\) يظهر في المثلثات
$$ (30,40,50),\qquad (20,48,52),\qquad (24,45,51). $$
إذًا \(120\) ليس محيطًا منفردًا. أما \(L=12\) فلا ينتج إلا من \((3,4,5)\)، ولذلك فهو محيط منفرد. والنتيجة النهائية هي عدد المحيطات التي يكون عدادها مساويًا تمامًا لـ \(1\).
تقوم تطبيقات C++ وPython وJava بالمرور على قيم \(m \ge 2\) ما دام الشرط \(2m(m+1) \le N\) محققًا. ولكل \(m\)، يتم فحص جميع قيم \(n\) بحيث \(1 \le n < m\)، ثم تُستبعد الأزواج التي يكون فيها \(m-n\) زوجيًا أو التي تحقق \(\gcd(m,n)\ne 1\). الأزواج الباقية هي بالضبط المولدات البدائية المطلوبة في صيغة إقليدس.
لكل زوج مقبول، يحسب التنفيذ المحيط البدائي \(p_0 = 2m(m+n)\). بعد ذلك يسير عبر المتتالية الحسابية \(p_0, 2p_0, 3p_0, \dots\) حتى يصل إلى الحد الأعلى، ويزيد مصفوفة تكرار المحيطات عند كل خطوة. هذه هي آلية العد كلها: كل مثلث صحيح صالح يضيف زيادة واحدة إلى محيطه الخاص.
بعد معالجة جميع المولدات البدائية، يُفحص المصفوفة كاملة ويُعدّ عدد الخانات التي تساوي \(1\). وهذا يساوي عدد أطوال الأسلاك المنفردة. كما أن تطبيقي C++ وPython يتحققان أولًا من الحالة الصغيرة \(N=150\)، حيث يكون الجواب الصحيح \(16\)، قبل الانتقال إلى الحد الرئيسي؛ أما تطبيق Java فيطبق الخوارزمية نفسها مباشرة على \(1{,}500{,}000\).
فضاء البحث في المعلمات محدود بالشرط \(m \le \sqrt{N/2}\)، ولذلك فإن مجرد تعداد الأزواج المرشحة \((m,n)\) يكلف \(O(N)\) في أسوأ الأحوال. أما العبء الأكبر فيأتي من تحديث جميع مضاعفات كل محيط بدائي.
إذا رمزنا إلى المحيطات البدائية بـ \(p_0\)، فإن العدد الكلي لتحديثات المصفوفة هو
$$\sum_{p_0}\left\lfloor\frac{N}{p_0}\right\rfloor.$$
ويتصرف هذا المجموع مثل مجموع توافقي على المحيطات البدائية المولدة، ولذلك يبقى عمليًا قريبًا من \(O(N \log N)\) عند هذا الحجم من الإدخال. أما الذاكرة فهي \(O(N)\)، لأن التنفيذ يحتفظ بعداد واحد لكل محيط حتى \(1{,}500{,}000\).