We must count all integer-sided triangles with perimeter at most \(L\) that contain an angle of exactly \(60^\circ\), \(90^\circ\), or \(120^\circ\). The final Project Euler total is intentionally omitted; this page explains the parameterizations and counting logic used by the C++ solution.
Let
$$N(L)=N_{60}(L)+N_{90}(L)+N_{120}(L).$$
For integer-sided triangles these classes are disjoint:
\(90^\circ\) and \(120^\circ\) cannot both occur because their sum already exceeds \(180^\circ\).
\(60^\circ\) and \(120^\circ\) also cannot both occur because that would leave a third angle of \(0^\circ\).
\(60^\circ\) and \(90^\circ\) would force a \(30\)-\(60\)-\(90\) triangle, whose side ratio is \(1:\sqrt3:2\). Since \(\sqrt3\) is irrational, no positive integer scaling can make all three sides integers.
So every valid triangle belongs to exactly one of the three counters. Equilateral triangles belong only to the \(60^\circ\) family.
If side \(c\) is opposite the special angle \(\theta\), then
$$c^2=a^2+b^2-2ab\cos\theta.$$
For the three angles in the problem:
$$90^\circ:\ c^2=a^2+b^2,$$
$$60^\circ:\ c^2=a^2+b^2-ab,$$
$$120^\circ:\ c^2=a^2+b^2+ab.$$
So Project Euler 279 is really three separate integer-parameterization problems plus a scaling count.
Primitive right triangles are given by Euclid's formula:
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
with
$$m>n,\qquad \gcd(m,n)=1,\qquad m-n\text{ odd}.$$
The primitive perimeter is
$$P_{0,90}=a+b+c=2m(m+n).$$
Example: \((m,n)=(2,1)\) gives \((3,4,5)\) with perimeter \(12\). Every scaled copy \(k(3,4,5)\) is still a right triangle, so this primitive triple contributes
$$\left\lfloor\frac{L}{12}\right\rfloor$$
triangles.
For a fixed \(m\), the smallest possible perimeter occurs at \(n=1\):
$$P_{0,90}\ge 2m(m+1).$$
This is exactly the lower bound behind max_m_90() in the code.
Let \(\omega\) be a primitive cube root of unity, so
$$\omega^2+\omega+1=0.$$
The Eisenstein norm is
$$N(x+y\omega)=(x+y\omega)(x+y\omega^2)=x^2-xy+y^2.$$
This is exactly the quadratic form that appears for \(60^\circ\):
$$c^2=a^2-ab+b^2=N(a+b\omega).$$
For \(120^\circ\), write
$$a^2+ab+b^2=a^2-a(-b)+(-b)^2=N(a-b\omega).$$
So the \(60^\circ\) and \(120^\circ\) families are the Eisenstein-integer analogues of Euclid's formula for right triangles.
Square \(m-n\omega\):
$$ (m-n\omega)^2 =m^2-n^2-(2mn+n^2)\omega. $$
Its norm is
$$N(m-n\omega)^2=(m^2+mn+n^2)^2.$$
This yields the standard primitive parameterization
$$a=m^2-n^2,\qquad b=2mn+n^2,\qquad c=m^2+mn+n^2,$$
and a direct substitution confirms
$$c^2=a^2+b^2+ab.$$
Example: \((m,n)=(2,1)\) gives
$$a=3,\qquad b=5,\qquad c=7,$$
and indeed
$$7^2=3^2+5^2+3\cdot5=49.$$
The primitive perimeter is
$$P_{0,120}=a+b+c=2m^2+3mn+n^2.$$
For fixed \(m\), this is smallest at \(n=1\):
$$P_{0,120}\ge 2m^2+3m+1.$$
That is exactly the bound used by max_m_120().
There is one more subtlety: \(\gcd(m,n)=1\) does not automatically force \(\gcd(a,b,c)=1\). For example, \((m,n)=(4,1)\) gives
$$ (15,9,21)=3\cdot(5,3,7). $$
So the implementation simply tests
$$\gcd(a,b,c)=1$$
directly instead of encoding the extra mod-\(3\) restriction by hand.
First, equilateral triangles contribute immediately:
$$ (k,k,k),\qquad 3k\le L,\qquad \text{count}=\left\lfloor\frac{L}{3}\right\rfloor. $$
For non-equilateral primitive triangles, square \(m+n\omega\):
$$ (m+n\omega)^2 =(m^2-n^2)+(2mn-n^2)\omega. $$
Its norm is
$$N(m+n\omega)^2=(m^2-mn+n^2)^2.$$
So one valid branch is
$$a=m^2-n^2,\qquad b_1=2mn-n^2,\qquad c=m^2-mn+n^2,$$
with identity
$$c^2=a^2+b_1^2-ab_1.$$
Now fix
$$a=m^2-n^2,\qquad c=m^2-mn+n^2$$
and solve the \(60^\circ\) equation for the missing side \(b\):
$$b^2-ab+(a^2-c^2)=0.$$
This quadratic has one root \(b_1\), so by Vieta its second root is
$$b_2=a-b_1=(m^2-n^2)-(2mn-n^2)=m^2-2mn.$$
Therefore the code counts two non-equilateral branches:
$$b_1=2mn-n^2,\qquad b_2=m^2-2mn.$$
Example: \((m,n)=(3,1)\) gives
$$ (a,c)=(8,7),\qquad b_1=5,\qquad b_2=3. $$
So we get two valid triangles:
$$ (5,7,8),\qquad (3,7,8), $$
and in both cases
$$7^2=5^2+8^2-5\cdot8=3^2+8^2-3\cdot8=49.$$
Why restrict to \(n\le \lfloor(m-1)/2\rfloor\)? Because larger \(n\) only reproduces the same unordered triangle. If we replace \(n\) by \(m-n\), then
$$a'=m^2-(m-n)^2=2mn-n^2=b_1,$$
$$b_1'=2m(m-n)-(m-n)^2=m^2-n^2=a,$$
and
$$c'=m^2-m(m-n)+(m-n)^2=c.$$
So \((m,n)\) and \((m,m-n)\) generate the same triangle with \(a\) and \(b_1\) swapped. Example:
$$ (m,n)=(4,1)\Rightarrow(15,7,13), $$
$$ (m,n)=(4,3)\Rightarrow(7,15,13). $$
Scanning only
$$1\le n\le \left\lfloor\frac{m-1}{2}\right\rfloor$$
keeps exactly one representative of each unordered triangle. It also ensures the second root is positive:
$$b_2=m(m-2n)>0.$$
The primitive perimeters of the two branches are
$$P_{0,60A}=a+b_1+c=2m^2+mn-n^2\ge 2m^2+m-1,$$
$$P_{0,60B}=a+b_2+c=3m(m-n)\ge 3m\left\lceil\frac m2\right\rceil.$$
The code writes the second bound in integer arithmetic as
$$3m\left(\frac{m+1}{2}\right)\qquad\text{with integer division},$$
which is exactly what appears in max_m_60().
As in the \(120^\circ\) family, the code uses the direct test
$$\gcd(a,b,c)=1$$
to keep only primitive triangles.
If \((a,b,c)\) is primitive and has one of the target angles, then every multiple
$$k(a,b,c)$$
has the same angle pattern, and its perimeter is \(kP_0\). Therefore one primitive triangle contributes exactly
$$\left\lfloor\frac{L}{P_0}\right\rfloor$$
copies. This explains why every counting loop in the program adds a floor-division term.
Separate counters. The program maintains with_60, with_90, and with_120 independently.
Immediate equilateral count. with_60 starts from
$$\left\lfloor\frac{L}{3}\right\rfloor.$$
Three parameter scans. count_90_range(), count_120_range(), and count_60_non_eq_range() scan the corresponding \((m,n)\)-lattices.
Primitive filters. The right-triangle family uses the classical coprime/opposite-parity conditions; the \(60^\circ\) and \(120^\circ\) families use \(\gcd(m,n)=1\) plus a direct \(\gcd(a,b,c)=1\) test.
Hard \(m\)-bounds. The helper functions max_m_90(), max_m_120(), and max_m_60() are derived exactly from the perimeter lower bounds above.
Parallel split. Threads only divide the \(m\)-values by residue class modulo the thread count; this changes wall-clock time, not the counted set.
Brute-force validation. The program checks
$$N(100)=84,\qquad N_{60}(100)=53,\qquad N_{90}(100)=17,\qquad N_{120}(100)=14,$$
and also compares the fast method against a direct brute-force triangle scan for \(L=120,200,300\).
Each family is an \((m,n)\)-lattice scan with gcd filters, so the runtime is roughly quadratic in the relevant \(m_{\max}\). The perimeter bounds cut off large useless regions early. Memory usage is \(O(1)\) apart from a small amount of thread bookkeeping and the tiny brute-force table used by the checkpoints.
Gesucht ist die Anzahl aller Dreiecke mit ganzzahligen Seiten und Umfang \(\le L\), die einen Winkel von genau \(60^\circ\), \(90^\circ\) oder \(120^\circ\) besitzen. Die eigentliche Euler-Endzahl wird nicht angegeben; diese Seite erklärt die Parametrisierungen und die Zähllogik des C++-Programms.
Wir schreiben
$$N(L)=N_{60}(L)+N_{90}(L)+N_{120}(L).$$
Für Dreiecke mit ganzzahligen Seiten sind diese Klassen tatsächlich disjunkt:
\(90^\circ\) und \(120^\circ\) können nicht gemeinsam auftreten, weil ihre Summe schon größer als \(180^\circ\) ist.
\(60^\circ\) und \(120^\circ\) können ebenfalls nicht gemeinsam auftreten, weil dann für den dritten Winkel \(0^\circ\) übrig bliebe.
\(60^\circ\) und \(90^\circ\) würden ein \(30\)-\(60\)-\(90\)-Dreieck erzwingen. Dessen Seitenverhältnis ist \(1:\sqrt3:2\), und wegen der Irrationalität von \(\sqrt3\) gibt es davon keine ganzzahlige Version.
Jedes gültige Dreieck gehört also genau zu einem der drei Zähler. Gleichseitige Dreiecke erscheinen nur in der \(60^\circ\)-Klasse.
Ist \(c\) die dem Spezialwinkel \(\theta\) gegenüberliegende Seite, so gilt
$$c^2=a^2+b^2-2ab\cos\theta.$$
Für die drei relevanten Winkel ergibt sich:
$$90^\circ:\ c^2=a^2+b^2,$$
$$60^\circ:\ c^2=a^2+b^2-ab,$$
$$120^\circ:\ c^2=a^2+b^2+ab.$$
Damit zerfällt Problem 279 in drei Familien von ganzzahligen Lösungen plus eine Skalierungszählung.
Primitive rechtwinklige Dreiecke werden durch Euklid parametrisiert:
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
mit
$$m>n,\qquad \gcd(m,n)=1,\qquad m-n\text{ ungerade}.$$
Der primitive Umfang ist
$$P_{0,90}=a+b+c=2m(m+n).$$
Beispiel: \((m,n)=(2,1)\) liefert \((3,4,5)\) mit Umfang \(12\). Jede skalierte Kopie \(k(3,4,5)\) bleibt rechtwinklig, also trägt dieses primitive Tripel
$$\left\lfloor\frac{L}{12}\right\rfloor$$
Dreiecke bei.
Für festes \(m\) ist der kleinste mögliche Umfang bei \(n=1\):
$$P_{0,90}\ge 2m(m+1).$$
Genau diese Schranke steckt in max_m_90().
Sei \(\omega\) eine primitive dritte Einheitswurzel mit
$$\omega^2+\omega+1=0.$$
Die Eisenstein-Norm lautet
$$N(x+y\omega)=(x+y\omega)(x+y\omega^2)=x^2-xy+y^2.$$
Genau diese quadratische Form erscheint bei \(60^\circ\):
$$c^2=a^2-ab+b^2=N(a+b\omega).$$
Für \(120^\circ\) schreiben wir
$$a^2+ab+b^2=a^2-a(-b)+(-b)^2=N(a-b\omega).$$
Die \(60^\circ\)- und \(120^\circ\)-Familien sind also die Eisenstein-Analoga der Euklid-Parametrisierung für rechtwinklige Dreiecke.
Wir quadrieren \(m-n\omega\):
$$ (m-n\omega)^2 =m^2-n^2-(2mn+n^2)\omega. $$
Seine Norm ist
$$N(m-n\omega)^2=(m^2+mn+n^2)^2.$$
Daraus folgt die Standard-Parametrisierung
$$a=m^2-n^2,\qquad b=2mn+n^2,\qquad c=m^2+mn+n^2,$$
und direktes Einsetzen bestätigt
$$c^2=a^2+b^2+ab.$$
Beispiel: \((m,n)=(2,1)\) ergibt
$$a=3,\qquad b=5,\qquad c=7,$$
und damit
$$7^2=3^2+5^2+3\cdot5=49.$$
Der primitive Umfang ist
$$P_{0,120}=a+b+c=2m^2+3mn+n^2.$$
Für festes \(m\) ist dies bei \(n=1\) minimal:
$$P_{0,120}\ge 2m^2+3m+1.$$
Das ist genau die Schranke in max_m_120().
Wichtig ist noch: \(\gcd(m,n)=1\) erzwingt nicht automatisch \(\gcd(a,b,c)=1\). Beispiel:
$$ (m,n)=(4,1)\Rightarrow(15,9,21)=3\cdot(5,3,7). $$
Darum prüft die Implementierung primitiveness einfach direkt über
$$\gcd(a,b,c)=1$$
anstatt die zusätzliche Modulo-\(3\)-Bedingung theoretisch auszuprogrammieren.
Zuerst der gleichseitige Anteil:
$$ (k,k,k),\qquad 3k\le L,\qquad \text{Anzahl}=\left\lfloor\frac{L}{3}\right\rfloor. $$
Für nichtgleichseitige primitive Dreiecke quadrieren wir \(m+n\omega\):
$$ (m+n\omega)^2 =(m^2-n^2)+(2mn-n^2)\omega. $$
Die Norm ist
$$N(m+n\omega)^2=(m^2-mn+n^2)^2.$$
Damit erhält man einen ersten Zweig:
$$a=m^2-n^2,\qquad b_1=2mn-n^2,\qquad c=m^2-mn+n^2,$$
mit
$$c^2=a^2+b_1^2-ab_1.$$
Fixiert man nun
$$a=m^2-n^2,\qquad c=m^2-mn+n^2$$
und löst die \(60^\circ\)-Gleichung nach \(b\), erhält man
$$b^2-ab+(a^2-c^2)=0.$$
Eine Wurzel ist \(b_1\), also ist nach Vieta die zweite Wurzel
$$b_2=a-b_1=(m^2-n^2)-(2mn-n^2)=m^2-2mn.$$
Darum zählt der Code zwei nichtgleichseitige Zweige:
$$b_1=2mn-n^2,\qquad b_2=m^2-2mn.$$
Beispiel: \((m,n)=(3,1)\) liefert
$$ (a,c)=(8,7),\qquad b_1=5,\qquad b_2=3. $$
Also entstehen zwei gültige Dreiecke:
$$ (5,7,8),\qquad (3,7,8), $$
und in beiden Fällen gilt
$$7^2=5^2+8^2-5\cdot8=3^2+8^2-3\cdot8=49.$$
Warum die Beschränkung \(n\le \lfloor(m-1)/2\rfloor\)? Weil größere \(n\) nur dasselbe ungeordnete Dreieck erneut erzeugen. Ersetzt man \(n\) durch \(m-n\), dann gilt
$$a'=m^2-(m-n)^2=2mn-n^2=b_1,$$
$$b_1'=2m(m-n)-(m-n)^2=m^2-n^2=a,$$
und
$$c'=m^2-m(m-n)+(m-n)^2=c.$$
Also erzeugen \((m,n)\) und \((m,m-n)\) dasselbe Dreieck mit vertauschten Seiten \(a\) und \(b_1\). Beispiel:
$$ (m,n)=(4,1)\Rightarrow(15,7,13), $$
$$ (m,n)=(4,3)\Rightarrow(7,15,13). $$
Die Schleife
$$1\le n\le \left\lfloor\frac{m-1}{2}\right\rfloor$$
behält deshalb genau einen Repräsentanten je ungeordnetem Dreieck. Gleichzeitig ist dann auch die zweite Wurzel positiv:
$$b_2=m(m-2n)>0.$$
Die primitiven Umfänge der beiden Zweige sind
$$P_{0,60A}=a+b_1+c=2m^2+mn-n^2\ge 2m^2+m-1,$$
$$P_{0,60B}=a+b_2+c=3m(m-n)\ge 3m\left\lceil\frac m2\right\rceil.$$
Im Code erscheint die zweite Schranke in ganzzahliger Schreibweise als
$$3m\left(\frac{m+1}{2}\right)\qquad\text{mit ganzzahliger Division},$$
genau wie in max_m_60().
Wie bei \(120^\circ\) filtert die Implementierung primitive Dreiecke direkt über
$$\gcd(a,b,c)=1.$$
Ist \((a,b,c)\) primitiv und besitzt einen Zielwinkel, dann hat jeder Vielfache
$$k(a,b,c)$$
dieselbe Winkelstruktur und Umfang \(kP_0\). Ein primitives Dreieck trägt also immer genau
$$\left\lfloor\frac{L}{P_0}\right\rfloor$$
Kopien bei. Deshalb addiert jede Schleife im Programm einen Floor-Term.
Getrennte Zähler. Das Programm führt with_60, with_90 und with_120 separat.
Sofortiger gleichseitiger Beitrag. with_60 startet mit
$$\left\lfloor\frac{L}{3}\right\rfloor.$$
Drei Parameterscans. count_90_range(), count_120_range() und count_60_non_eq_range() durchlaufen die jeweiligen \((m,n)\)-Gitter.
Primitivitätsfilter. Die Rechtwinkelfamilie nutzt die klassischen coprime/Paritäts-Bedingungen; die \(60^\circ\)- und \(120^\circ\)-Familien benutzen \(\gcd(m,n)=1\) plus einen direkten \(\gcd(a,b,c)=1\)-Test.
Harte \(m\)-Schranken. max_m_90(), max_m_120() und max_m_60() stammen genau aus den Umfangsuntergrenzen oben.
Parallelisierung. Threads teilen nur die \(m\)-Werte nach Restklassen auf; die gezählte Menge bleibt identisch.
Brute-Force-Kontrolle. Verifiziert wird
$$N(100)=84,\qquad N_{60}(100)=53,\qquad N_{90}(100)=17,\qquad N_{120}(100)=14,$$
zusätzlich mit einem vollständigen Brute-Force-Vergleich für \(L=120,200,300\).
Jede Familie ist im Kern ein \((m,n)\)-Gitterscan mit gcd-Filtern; die Laufzeit ist also ungefähr quadratisch in der relevanten Grenze \(m_{\max}\). Die Umfangsuntergrenzen schneiden große nutzlose Bereiche früh ab. Der Speicherbedarf ist \(O(1)\), abgesehen von wenig Thread-Verwaltung und der kleinen Brute-Force-Struktur für die Checkpoints.
Çevresi \(L\)’yi aşmayan, kenarları tam sayı olan ve bir açısı tam olarak \(60^\circ\), \(90^\circ\) veya \(120^\circ\) olan tüm üçgenler sayılır. Nihai Project Euler değeri burada verilmez; amaç C++ çözümünün kullandığı parametrizasyonları ve sayım mantığını ayrıntılı biçimde açıklamaktır.
Toplamı
$$N(L)=N_{60}(L)+N_{90}(L)+N_{120}(L)$$
şeklinde ayırırız.
Tam sayı kenarlı üçgenler için bu üç sınıf gerçekten ayrıdır:
\(90^\circ\) ve \(120^\circ\) birlikte olamaz; toplamları zaten \(180^\circ\)’yi aşar.
\(60^\circ\) ve \(120^\circ\) birlikte olamaz; geriye \(0^\circ\) kalır.
\(60^\circ\) ve \(90^\circ\) birlikte olsaydı üçgen \(30\)-\(60\)-\(90\) olurdu. Bu üçgenin kenar oranı \(1:\sqrt3:2\) olduğundan, \(\sqrt3\) irrasyonel olduğu için hiçbir pozitif tamsayı katı tüm kenarları tam sayı yapamaz.
Dolayısıyla her geçerli üçgen bu üç sayaçtan tam olarak birine gider. Eşkenar üçgenler yalnızca \(60^\circ\) ailesindedir.
Özel açıya karşı gelen kenar \(c\) olsun. O zaman
$$c^2=a^2+b^2-2ab\cos\theta$$
yazılır. Problemdeki üç açı için:
$$90^\circ:\ c^2=a^2+b^2,$$
$$60^\circ:\ c^2=a^2+b^2-ab,$$
$$120^\circ:\ c^2=a^2+b^2+ab.$$
Böylece Euler 279, üç ayrı tam sayı çözüm ailesine ve sonra bunların ölçeklenerek sayılmasına indirgenir.
İlkel dik üçgenler Euclid formülüyle gelir:
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
şartlar:
$$m>n,\qquad \gcd(m,n)=1,\qquad m-n\text{ tek}.$$
İlkel çevre
$$P_{0,90}=a+b+c=2m(m+n)$$
olur. Örnek: \((m,n)=(2,1)\) için \((3,4,5)\) ve çevre \(12\) elde edilir. Bunun tüm katları yine dik üçgendir; dolayısıyla bu ilkel üçlü
$$\left\lfloor\frac{L}{12}\right\rfloor$$
adet katkı yapar.
Sabit \(m\) için en küçük çevre \(n=1\) iken oluşur:
$$P_{0,90}\ge 2m(m+1).$$
Koddaki max_m_90() tam olarak bu alt sınırı kullanır.
\(\omega\) ilkel bir üçüncü birim kök olsun:
$$\omega^2+\omega+1=0.$$
Eisenstein normu
$$N(x+y\omega)=(x+y\omega)(x+y\omega^2)=x^2-xy+y^2$$
şeklindedir. Bu tam olarak \(60^\circ\) denkleminin sol tarafıdır:
$$c^2=a^2-ab+b^2=N(a+b\omega).$$
\(120^\circ\) için de
$$a^2+ab+b^2=a^2-a(-b)+(-b)^2=N(a-b\omega)$$
yazılır. Yani \(60^\circ\) ve \(120^\circ\) aileleri, dik üçgenlerdeki Euclid formülünün Eisenstein tamsayılarındaki analogudur.
\(m-n\omega\)’nun karesini alalım:
$$ (m-n\omega)^2 =m^2-n^2-(2mn+n^2)\omega. $$
Bunun normu
$$N(m-n\omega)^2=(m^2+mn+n^2)^2$$
olur. Buradan standart parametrizasyon çıkar:
$$a=m^2-n^2,\qquad b=2mn+n^2,\qquad c=m^2+mn+n^2,$$
ve doğrudan yerine koyma ile
$$c^2=a^2+b^2+ab$$
doğrulanır.
Örnek: \((m,n)=(2,1)\) için
$$a=3,\qquad b=5,\qquad c=7,$$
ve gerçekten
$$7^2=3^2+5^2+3\cdot5=49.$$
İlkel çevre
$$P_{0,120}=a+b+c=2m^2+3mn+n^2$$
olur. Sabit \(m\) için minimum \(n=1\) noktasındadır:
$$P_{0,120}\ge 2m^2+3m+1.$$
Koddaki max_m_120() bu sınırı kullanır.
Burada önemli bir ince nokta vardır: \(\gcd(m,n)=1\) olması, \(\gcd(a,b,c)=1\) olacağını garanti etmez. Örnek:
$$ (m,n)=(4,1)\Rightarrow(15,9,21)=3\cdot(5,3,7). $$
Bu yüzden implementasyon ek mod-\(3\) koşullarını elle kodlamak yerine doğrudan
$$\gcd(a,b,c)=1$$
testi yapar.
İlk olarak eşkenar dal doğrudan gelir:
$$ (k,k,k),\qquad 3k\le L,\qquad \text{katkı}=\left\lfloor\frac{L}{3}\right\rfloor. $$
Eşkenar olmayan ilkel üçgenler için \(m+n\omega\)’nun karesini alırız:
$$ (m+n\omega)^2 =(m^2-n^2)+(2mn-n^2)\omega. $$
Norm
$$N(m+n\omega)^2=(m^2-mn+n^2)^2$$
olduğundan birinci dal
$$a=m^2-n^2,\qquad b_1=2mn-n^2,\qquad c=m^2-mn+n^2$$
şeklinde gelir ve
$$c^2=a^2+b_1^2-ab_1$$
sağlanır.
Şimdi
$$a=m^2-n^2,\qquad c=m^2-mn+n^2$$
sabitken eksik kenar \(b\) için \(60^\circ\) denklemini çözelim:
$$b^2-ab+(a^2-c^2)=0.$$
Bir kök \(b_1\) olduğuna göre Vieta ile ikinci kök
$$b_2=a-b_1=(m^2-n^2)-(2mn-n^2)=m^2-2mn$$
olur. Bu yüzden kod iki farklı eşkenar olmayan dal sayar:
$$b_1=2mn-n^2,\qquad b_2=m^2-2mn.$$
Örnek: \((m,n)=(3,1)\) için
$$ (a,c)=(8,7),\qquad b_1=5,\qquad b_2=3 $$
elde edilir. Böylece iki geçerli üçgen çıkar:
$$ (5,7,8),\qquad (3,7,8), $$
ve iki durumda da
$$7^2=5^2+8^2-5\cdot8=3^2+8^2-3\cdot8=49.$$
Neden \(n\le \lfloor(m-1)/2\rfloor\) şartı var? Çünkü daha büyük \(n\) değerleri aynı sırasız üçgeni tekrar üretir. \(n\) yerine \(m-n\) yazarsak
$$a'=m^2-(m-n)^2=2mn-n^2=b_1,$$
$$b_1'=2m(m-n)-(m-n)^2=m^2-n^2=a,$$
ve
$$c'=m^2-m(m-n)+(m-n)^2=c$$
olur. Yani \((m,n)\) ile \((m,m-n)\) aynı üçgeni sadece \(a\) ve \(b_1\)’i yer değiştirerek üretir. Örnek:
$$ (m,n)=(4,1)\Rightarrow(15,7,13), $$
$$ (m,n)=(4,3)\Rightarrow(7,15,13). $$
Bu nedenle
$$1\le n\le \left\lfloor\frac{m-1}{2}\right\rfloor$$
aralığı her sırasız üçgen için tam bir temsilci bırakır. Aynı zamanda ikinci kökün pozitif olmasını da sağlar:
$$b_2=m(m-2n)>0.$$
İki dalın ilkel çevreleri:
$$P_{0,60A}=a+b_1+c=2m^2+mn-n^2\ge 2m^2+m-1,$$
$$P_{0,60B}=a+b_2+c=3m(m-n)\ge 3m\left\lceil\frac m2\right\rceil.$$
Kod ikinci sınırı tamsayı aritmetiğiyle
$$3m\left(\frac{m+1}{2}\right)\qquad\text{(tamsayı bölmesi)}$$
olarak yazar; bu max_m_60() içinde görülür.
\(120^\circ\) ailesinde olduğu gibi burada da ilkel olma durumu doğrudan
$$\gcd(a,b,c)=1$$
testiyle uygulanır.
\((a,b,c)\) ilkel ve hedef açılardan birine sahipse, her
$$k(a,b,c)$$
çokluğu aynı açı yapısını korur ve çevresi \(kP_0\) olur. O halde bir ilkel üçgen tam olarak
$$\left\lfloor\frac{L}{P_0}\right\rfloor$$
adet kopya üretir. Programdaki tüm toplama adımları bu yüzden floor-bölme biçimindedir.
Ayrı sayaçlar. Program with_60, with_90 ve with_120 sayaçlarını ayrı tutar.
Eşkenar katkı baştan eklenir. with_60 başlangıçta
$$\left\lfloor\frac{L}{3}\right\rfloor$$
değeriyle başlar.
Üç ayrı parametre taraması. count_90_range(), count_120_range() ve count_60_non_eq_range() ilgili \((m,n)\) örgülerini dolaşır.
İlkel filtreleri. Dik üçgenler klasik aralarında asal/parite koşullarını kullanır; \(60^\circ\) ve \(120^\circ\) aileleri için \(\gcd(m,n)=1\) yanında doğrudan \(\gcd(a,b,c)=1\) kontrolü vardır.
Sert \(m\) sınırları. max_m_90(), max_m_120() ve max_m_60() yukarıdaki çevre alt sınırlarından türetilir.
Thread bölmesi. Thread’ler yalnızca \(m\) değerlerini kalıntı sınıflarına böler; sayılan kümeyi değiştirmez.
Brute-force doğrulama. Program
$$N(100)=84,\qquad N_{60}(100)=53,\qquad N_{90}(100)=17,\qquad N_{120}(100)=14$$
değerlerini kontrol eder ve ayrıca \(L=120,200,300\) için hızlı yöntemle brute-force taramayı karşılaştırır.
Her aile özünde gcd filtreli bir \((m,n)\) örgü taramasıdır; dolayısıyla çalışma süresi ilgili \(m_{\max}\) için kabaca ikinci derecedir. Çevre alt sınırları büyük ve katkısız bölgeleri erken keser. Bellek kullanımı, küçük thread bağlamları ve checkpoint brute-force yapısı dışında \(O(1)\)’dir.
Hay que contar todos los triángulos de lados enteros y perímetro \(\le L\) que tengan un ángulo exacto de \(60^\circ\), \(90^\circ\) o \(120^\circ\). El valor final de Project Euler se omite; aquí se explica con detalle la parametrización y la lógica de conteo del programa en C++.
Escribimos
$$N(L)=N_{60}(L)+N_{90}(L)+N_{120}(L).$$
Para triángulos de lados enteros, estas familias son realmente disjuntas:
\(90^\circ\) y \(120^\circ\) no pueden aparecer juntos porque ya suman más de \(180^\circ\).
\(60^\circ\) y \(120^\circ\) tampoco pueden coexistir, porque el tercer ángulo quedaría en \(0^\circ\).
\(60^\circ\) y \(90^\circ\) forzarían un triángulo \(30\)-\(60\)-\(90\), cuya razón lateral es \(1:\sqrt3:2\). Como \(\sqrt3\) es irracional, ninguna escala entera produce tres lados enteros.
Por tanto, cada triángulo válido entra en exactamente uno de los tres contadores. Los equiláteros pertenecen solo a la familia de \(60^\circ\).
Si \(c\) es el lado opuesto al ángulo especial \(\theta\), entonces
$$c^2=a^2+b^2-2ab\cos\theta.$$
Así, para los tres ángulos:
$$90^\circ:\ c^2=a^2+b^2,$$
$$60^\circ:\ c^2=a^2+b^2-ab,$$
$$120^\circ:\ c^2=a^2+b^2+ab.$$
El problema se convierte en tres familias de soluciones enteras y luego en un conteo por escalado.
Los triángulos rectángulos primitivos vienen dados por la fórmula de Euclides:
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
con
$$m>n,\qquad \gcd(m,n)=1,\qquad m-n\text{ impar}.$$
El perímetro primitivo es
$$P_{0,90}=a+b+c=2m(m+n).$$
Ejemplo: \((m,n)=(2,1)\) da \((3,4,5)\) con perímetro \(12\). Cada múltiplo \(k(3,4,5)\) sigue siendo rectángulo, así que esta terna aporta
$$\left\lfloor\frac{L}{12}\right\rfloor$$
copias.
Para \(m\) fijo, el menor perímetro posible ocurre en \(n=1\):
$$P_{0,90}\ge 2m(m+1).$$
Ésta es exactamente la cota usada por max_m_90().
Sea \(\omega\) una raíz cúbica primitiva de la unidad, con
$$\omega^2+\omega+1=0.$$
La norma de Eisenstein es
$$N(x+y\omega)=(x+y\omega)(x+y\omega^2)=x^2-xy+y^2.$$
Esta es exactamente la forma cuadrática del caso \(60^\circ\):
$$c^2=a^2-ab+b^2=N(a+b\omega).$$
Para \(120^\circ\), escribimos
$$a^2+ab+b^2=a^2-a(-b)+(-b)^2=N(a-b\omega).$$
Así, las familias de \(60^\circ\) y \(120^\circ\) son análogas a la fórmula de Euclides, pero en los enteros de Eisenstein.
Al cuadrar \(m-n\omega\) obtenemos
$$ (m-n\omega)^2 =m^2-n^2-(2mn+n^2)\omega. $$
Su norma es
$$N(m-n\omega)^2=(m^2+mn+n^2)^2.$$
De ahí sale la parametrización estándar
$$a=m^2-n^2,\qquad b=2mn+n^2,\qquad c=m^2+mn+n^2,$$
y al sustituir se comprueba
$$c^2=a^2+b^2+ab.$$
Ejemplo: \((m,n)=(2,1)\) produce
$$a=3,\qquad b=5,\qquad c=7,$$
y en efecto
$$7^2=3^2+5^2+3\cdot5=49.$$
El perímetro primitivo es
$$P_{0,120}=a+b+c=2m^2+3mn+n^2.$$
Para \(m\) fijo, el mínimo se alcanza en \(n=1\):
$$P_{0,120}\ge 2m^2+3m+1.$$
Ésta es la cota de max_m_120().
Además, \(\gcd(m,n)=1\) no garantiza automáticamente \(\gcd(a,b,c)=1\). Por ejemplo,
$$ (m,n)=(4,1)\Rightarrow(15,9,21)=3\cdot(5,3,7). $$
Por eso el código comprueba directamente
$$\gcd(a,b,c)=1$$
en vez de codificar a mano la restricción adicional módulo \(3\).
Primero, los equiláteros aportan inmediatamente
$$ (k,k,k),\qquad 3k\le L,\qquad \text{conteo}=\left\lfloor\frac{L}{3}\right\rfloor. $$
Para los no equiláteros, cuadramos \(m+n\omega\):
$$ (m+n\omega)^2 =(m^2-n^2)+(2mn-n^2)\omega. $$
La norma es
$$N(m+n\omega)^2=(m^2-mn+n^2)^2.$$
Entonces una primera rama es
$$a=m^2-n^2,\qquad b_1=2mn-n^2,\qquad c=m^2-mn+n^2,$$
con
$$c^2=a^2+b_1^2-ab_1.$$
Ahora fijamos
$$a=m^2-n^2,\qquad c=m^2-mn+n^2$$
y resolvemos la ecuación de \(60^\circ\) respecto de \(b\):
$$b^2-ab+(a^2-c^2)=0.$$
Como una raíz es \(b_1\), la otra raíz por Vieta es
$$b_2=a-b_1=(m^2-n^2)-(2mn-n^2)=m^2-2mn.$$
Por eso el programa cuenta dos ramas no equiláteras:
$$b_1=2mn-n^2,\qquad b_2=m^2-2mn.$$
Ejemplo: \((m,n)=(3,1)\) da
$$ (a,c)=(8,7),\qquad b_1=5,\qquad b_2=3. $$
Así aparecen dos triángulos válidos:
$$ (5,7,8),\qquad (3,7,8), $$
y en ambos casos
$$7^2=5^2+8^2-5\cdot8=3^2+8^2-3\cdot8=49.$$
¿Por qué restringir \(n\le \lfloor(m-1)/2\rfloor\)? Porque valores mayores de \(n\) solo reproducen el mismo triángulo no ordenado. Si sustituimos \(n\) por \(m-n\), entonces
$$a'=m^2-(m-n)^2=2mn-n^2=b_1,$$
$$b_1'=2m(m-n)-(m-n)^2=m^2-n^2=a,$$
y
$$c'=m^2-m(m-n)+(m-n)^2=c.$$
Por tanto, \((m,n)\) y \((m,m-n)\) generan el mismo triángulo con \(a\) y \(b_1\) intercambiados. Ejemplo:
$$ (m,n)=(4,1)\Rightarrow(15,7,13), $$
$$ (m,n)=(4,3)\Rightarrow(7,15,13). $$
Recorrer solo
$$1\le n\le \left\lfloor\frac{m-1}{2}\right\rfloor$$
deja exactamente un representante por cada triángulo no ordenado. Además asegura que la segunda raíz sea positiva:
$$b_2=m(m-2n)>0.$$
Los perímetros primitivos de ambas ramas son
$$P_{0,60A}=a+b_1+c=2m^2+mn-n^2\ge 2m^2+m-1,$$
$$P_{0,60B}=a+b_2+c=3m(m-n)\ge 3m\left\lceil\frac m2\right\rceil.$$
El código escribe la segunda cota en aritmética entera como
$$3m\left(\frac{m+1}{2}\right)\qquad\text{con división entera},$$
exactamente como aparece en max_m_60().
Igual que en la familia de \(120^\circ\), se usa la prueba directa
$$\gcd(a,b,c)=1$$
para conservar solo triángulos primitivos.
Si \((a,b,c)\) es primitivo y contiene uno de los ángulos buscados, todo múltiplo
$$k(a,b,c)$$
conserva el mismo patrón angular y tiene perímetro \(kP_0\). Por tanto, un triángulo primitivo aporta exactamente
$$\left\lfloor\frac{L}{P_0}\right\rfloor$$
copias. De ahí salen todos los términos de división entera del programa.
Contadores separados. El programa mantiene with_60, with_90 y with_120 por separado.
Conteo equilátero inmediato. with_60 empieza con
$$\left\lfloor\frac{L}{3}\right\rfloor.$$
Tres barridos paramétricos. count_90_range(), count_120_range() y count_60_non_eq_range() recorren las tres redes \((m,n)\).
Filtros de primitividad. La familia rectángula usa las condiciones clásicas de coprimalidad y paridad opuesta; las familias de \(60^\circ\) y \(120^\circ\) usan \(\gcd(m,n)=1\) más el chequeo directo \(\gcd(a,b,c)=1\).
Cotas duras para \(m\). max_m_90(), max_m_120() y max_m_60() salen exactamente de las cotas inferiores de perímetro obtenidas arriba.
Paralelización. Los hilos solo reparten valores de \(m\) por clases residuales; el conjunto contado no cambia.
Validación brute force. El código comprueba
$$N(100)=84,\qquad N_{60}(100)=53,\qquad N_{90}(100)=17,\qquad N_{120}(100)=14,$$
y además compara el método rápido con un barrido directo para \(L=120,200,300\).
Cada familia es esencialmente un barrido sobre la red \((m,n)\) con filtros gcd, así que el tiempo es aproximadamente cuadrático en el \(m_{\max}\) relevante. Las cotas de perímetro recortan pronto las zonas inútiles. La memoria es \(O(1)\), salvo un pequeño contexto de hilos y la estructura mínima usada por los checkpoints.
要求统计周长不超过 \(L\) 的整边三角形中，含有 \(60^\circ\)、\(90^\circ\) 或 \(120^\circ\) 角的总数。最终 Project Euler 数值答案照例省略；这里重点解释 C++ 解法所依赖的参数化与计数结构。
记
$$N(L)=N_{60}(L)+N_{90}(L)+N_{120}(L).$$
对于整边三角形，这三类确实互不重叠：
\(90^\circ\) 与 \(120^\circ\) 不可能同时出现，因为它们之和已经超过 \(180^\circ\)。
\(60^\circ\) 与 \(120^\circ\) 也不可能同时出现，因为那样第三个角只能是 \(0^\circ\)。
\(60^\circ\) 与 \(90^\circ\) 若同时出现，就得到 \(30\)-\(60\)-\(90\) 三角形，其边比为 \(1:\sqrt3:2\)。由于 \(\sqrt3\) 是无理数，不存在正整数倍使三边同时为整数。
因此每个有效三角形恰好落入一个计数器。等边三角形只属于 \(60^\circ\) 家族。
设特殊角 \(\theta\) 的对边为 \(c\)，则
$$c^2=a^2+b^2-2ab\cos\theta.$$
于是三种情况分别满足
$$90^\circ:\ c^2=a^2+b^2,$$
$$60^\circ:\ c^2=a^2+b^2-ab,$$
$$120^\circ:\ c^2=a^2+b^2+ab.$$
所以本题本质上是三套整参数化，再加上一个缩放计数。
原始勾股三元组由 Euclid 公式给出：
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
满足
$$m>n,\qquad \gcd(m,n)=1,\qquad m-n\text{ 为奇数}.$$
原始周长为
$$P_{0,90}=a+b+c=2m(m+n).$$
例如 \((m,n)=(2,1)\) 给出 \((3,4,5)\)，周长为 \(12\)。其任意倍数 \(k(3,4,5)\) 仍然是直角三角形，因此这一原始三角形贡献
$$\left\lfloor\frac{L}{12}\right\rfloor$$
个拷贝。
固定 \(m\) 时，最小周长出现在 \(n=1\)：
$$P_{0,90}\ge 2m(m+1).$$
这正是代码中 max_m_90() 的依据。
取 \(\omega\) 为原始三次单位根，使得
$$\omega^2+\omega+1=0.$$
Eisenstein 范数定义为
$$N(x+y\omega)=(x+y\omega)(x+y\omega^2)=x^2-xy+y^2.$$
这正是 \(60^\circ\) 情形中的二次型：
$$c^2=a^2-ab+b^2=N(a+b\omega).$$
而 \(120^\circ\) 可写成
$$a^2+ab+b^2=a^2-a(-b)+(-b)^2=N(a-b\omega).$$
因此 \(60^\circ\) 与 \(120^\circ\) 的参数化，可看作直角三角形 Euclid 公式在 Eisenstein 整数中的对应物。
把 \(m-n\omega\) 平方：
$$ (m-n\omega)^2 =m^2-n^2-(2mn+n^2)\omega. $$
其范数是
$$N(m-n\omega)^2=(m^2+mn+n^2)^2.$$
于是得到标准参数式
$$a=m^2-n^2,\qquad b=2mn+n^2,\qquad c=m^2+mn+n^2,$$
直接代入即可验证
$$c^2=a^2+b^2+ab.$$
例子：\((m,n)=(2,1)\) 产生
$$a=3,\qquad b=5,\qquad c=7,$$
并且
$$7^2=3^2+5^2+3\cdot5=49.$$
原始周长为
$$P_{0,120}=a+b+c=2m^2+3mn+n^2.$$
对固定 \(m\)，最小值出现在 \(n=1\)：
$$P_{0,120}\ge 2m^2+3m+1.$$
这正是 max_m_120() 使用的上界依据。
还要注意：\(\gcd(m,n)=1\) 并不自动推出 \(\gcd(a,b,c)=1\)。例如
$$ (m,n)=(4,1)\Rightarrow(15,9,21)=3\cdot(5,3,7). $$
因此程序直接检查
$$\gcd(a,b,c)=1$$
而不是手工编码额外的模 \(3\) 条件。
首先，等边三角形单独贡献
$$ (k,k,k),\qquad 3k\le L,\qquad \text{数量}=\left\lfloor\frac{L}{3}\right\rfloor. $$
对非等边原始解，平方 \(m+n\omega\)：
$$ (m+n\omega)^2 =(m^2-n^2)+(2mn-n^2)\omega. $$
其范数为
$$N(m+n\omega)^2=(m^2-mn+n^2)^2.$$
于是第一条分支是
$$a=m^2-n^2,\qquad b_1=2mn-n^2,\qquad c=m^2-mn+n^2,$$
满足
$$c^2=a^2+b_1^2-ab_1.$$
现在固定
$$a=m^2-n^2,\qquad c=m^2-mn+n^2$$
并把 \(60^\circ\) 方程视为关于 \(b\) 的二次方程：
$$b^2-ab+(a^2-c^2)=0.$$
已知其中一个根是 \(b_1\)，由 Vieta 公式可得另一个根
$$b_2=a-b_1=(m^2-n^2)-(2mn-n^2)=m^2-2mn.$$
因此代码统计两条非等边分支：
$$b_1=2mn-n^2,\qquad b_2=m^2-2mn.$$
例子：\((m,n)=(3,1)\) 给出
$$ (a,c)=(8,7),\qquad b_1=5,\qquad b_2=3. $$
于是得到两个合法三角形：
$$ (5,7,8),\qquad (3,7,8), $$
且两者都满足
$$7^2=5^2+8^2-5\cdot8=3^2+8^2-3\cdot8=49.$$
为什么限制 \(n\le \lfloor(m-1)/2\rfloor\)？ 因为更大的 \(n\) 只会重复生成同一个无序三角形。把 \(n\) 换成 \(m-n\)，就有
$$a'=m^2-(m-n)^2=2mn-n^2=b_1,$$
$$b_1'=2m(m-n)-(m-n)^2=m^2-n^2=a,$$
以及
$$c'=m^2-m(m-n)+(m-n)^2=c.$$
因此 \((m,n)\) 与 \((m,m-n)\) 生成的是同一个三角形，只是 \(a\) 与 \(b_1\) 对调。例子：
$$ (m,n)=(4,1)\Rightarrow(15,7,13), $$
$$ (m,n)=(4,3)\Rightarrow(7,15,13). $$
所以只扫描
$$1\le n\le \left\lfloor\frac{m-1}{2}\right\rfloor$$
就能为每个无序三角形保留唯一代表。同时这也保证第二个根为正：
$$b_2=m(m-2n)>0.$$
两条分支的原始周长分别为
$$P_{0,60A}=a+b_1+c=2m^2+mn-n^2\ge 2m^2+m-1,$$
$$P_{0,60B}=a+b_2+c=3m(m-n)\ge 3m\left\lceil\frac m2\right\rceil.$$
代码用整数写法表示第二个下界：
$$3m\left(\frac{m+1}{2}\right)\qquad\text{用整数除法理解},$$
这正是 max_m_60() 中的表达式。
与 \(120^\circ\) 一样，这里也用直接测试
$$\gcd(a,b,c)=1$$
筛掉非原始三角形。
如果 \((a,b,c)\) 是原始三角形并且包含目标角，那么任意倍数
$$k(a,b,c)$$
都保持相同的角结构，周长变为 \(kP_0\)。因此一个原始三角形恰好贡献
$$\left\lfloor\frac{L}{P_0}\right\rfloor$$
个拷贝。程序中的所有整除项都来自这里。
三个独立计数器。 程序分别维护 with_60、with_90、with_120。
等边项先加进去。 with_60 初值就是
$$\left\lfloor\frac{L}{3}\right\rfloor.$$
三套参数扫描。 count_90_range()、count_120_range()、count_60_non_eq_range() 分别扫描对应的 \((m,n)\) 格点。
原始性过滤。 直角家族使用经典的互素与奇偶条件；\(60^\circ\)、\(120^\circ\) 家族使用 \(\gcd(m,n)=1\) 加上直接的 \(\gcd(a,b,c)=1\) 检查。
\(m\) 的硬上界。 max_m_90()、max_m_120()、max_m_60() 都直接来自上面的周长下界。
线程划分。 线程只按模类拆分 \(m\) 的取值，改变的是运行时间，不是数学结果。
暴力校验。 代码验证
$$N(100)=84,\qquad N_{60}(100)=53,\qquad N_{90}(100)=17,\qquad N_{120}(100)=14,$$
并在 \(L=120,200,300\) 时将快速方法与 brute force 逐一比较。
每个家族本质上都是带 gcd 过滤的 \((m,n)\) 格点扫描，因此时间复杂度大致是相应 \(m_{\max}\) 的平方。周长下界能提前切掉大量无贡献区域。空间复杂度除少量线程上下文和小型暴力校验结构外基本是 \(O(1)\)。
Нужно посчитать все треугольники с целыми сторонами и периметром \(\le L\), содержащие угол \(60^\circ\), \(90^\circ\) или \(120^\circ\). Финальное число Project Euler здесь не приводится; цель страницы — подробно объяснить параметризации и схему подсчета, используемую в C++-решении.
Пишем
$$N(L)=N_{60}(L)+N_{90}(L)+N_{120}(L).$$
Для треугольников с целыми сторонами эти классы действительно не пересекаются:
\(90^\circ\) и \(120^\circ\) не могут встречаться одновременно, потому что их сумма уже больше \(180^\circ\).
\(60^\circ\) и \(120^\circ\) тоже не могут встречаться вместе, иначе третий угол был бы равен \(0^\circ\).
\(60^\circ\) и \(90^\circ\) означали бы треугольник \(30\)-\(60\)-\(90\) с отношением сторон \(1:\sqrt3:2\). Так как \(\sqrt3\) иррационально, никакое целое масштабирование не даст три целые стороны.
Значит, каждый допустимый треугольник попадает ровно в один из трех счетчиков. Равносторонние треугольники принадлежат только семейству \(60^\circ\).
Если сторона \(c\) лежит напротив особого угла \(\theta\), то
$$c^2=a^2+b^2-2ab\cos\theta.$$
Отсюда получаем:
$$90^\circ:\ c^2=a^2+b^2,$$
$$60^\circ:\ c^2=a^2+b^2-ab,$$
$$120^\circ:\ c^2=a^2+b^2+ab.$$
Итак, задача распадается на три семейства целочисленных решений и последующий учет масштабов.
Примитивные прямоугольные треугольники задаются формулой Евклида:
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
при условиях
$$m>n,\qquad \gcd(m,n)=1,\qquad m-n\text{ нечетно}.$$
Примитивный периметр равен
$$P_{0,90}=a+b+c=2m(m+n).$$
Пример: \((m,n)=(2,1)\) дает \((3,4,5)\) с периметром \(12\). Каждый масштаб \(k(3,4,5)\) остается прямоугольным, поэтому вклад этой примитивной тройки равен
$$\left\lfloor\frac{L}{12}\right\rfloor.$$
При фиксированном \(m\) наименьший периметр получается при \(n=1\):
$$P_{0,90}\ge 2m(m+1).$$
Именно эта нижняя оценка используется в max_m_90().
Пусть \(\omega\) — примитивный кубический корень из единицы, так что
$$\omega^2+\omega+1=0.$$
Норма Эйзенштейна имеет вид
$$N(x+y\omega)=(x+y\omega)(x+y\omega^2)=x^2-xy+y^2.$$
Это ровно та квадратичная форма, которая возникает для \(60^\circ\):
$$c^2=a^2-ab+b^2=N(a+b\omega).$$
Для \(120^\circ\) можно написать
$$a^2+ab+b^2=a^2-a(-b)+(-b)^2=N(a-b\omega).$$
Тем самым семейства \(60^\circ\) и \(120^\circ\) играют роль «эйлеровских» аналогов формулы Евклида в кольце целых Эйзенштейна.
Возводим в квадрат \(m-n\omega\):
$$ (m-n\omega)^2 =m^2-n^2-(2mn+n^2)\omega. $$
Его норма равна
$$N(m-n\omega)^2=(m^2+mn+n^2)^2.$$
Отсюда получаем стандартную параметризацию
$$a=m^2-n^2,\qquad b=2mn+n^2,\qquad c=m^2+mn+n^2,$$
и непосредственная подстановка дает
$$c^2=a^2+b^2+ab.$$
Пример: \((m,n)=(2,1)\) дает
$$a=3,\qquad b=5,\qquad c=7,$$
и действительно
$$7^2=3^2+5^2+3\cdot5=49.$$
Примитивный периметр равен
$$P_{0,120}=a+b+c=2m^2+3mn+n^2.$$
При фиксированном \(m\) минимум достигается при \(n=1\):
$$P_{0,120}\ge 2m^2+3m+1.$$
Это и есть оценка внутри max_m_120().
Важно, что \(\gcd(m,n)=1\) не гарантирует автоматически \(\gcd(a,b,c)=1\). Например,
$$ (m,n)=(4,1)\Rightarrow(15,9,21)=3\cdot(5,3,7). $$
Поэтому программа просто проверяет
$$\gcd(a,b,c)=1,$$
а не кодирует вручную дополнительное условие по модулю \(3\).
Сначала равносторонний вклад:
$$ (k,k,k),\qquad 3k\le L,\qquad \text{число}=\left\lfloor\frac{L}{3}\right\rfloor. $$
Для неравносторонних примитивных решений возводим в квадрат \(m+n\omega\):
$$ (m+n\omega)^2 =(m^2-n^2)+(2mn-n^2)\omega. $$
Норма равна
$$N(m+n\omega)^2=(m^2-mn+n^2)^2.$$
Первая ветвь имеет вид
$$a=m^2-n^2,\qquad b_1=2mn-n^2,\qquad c=m^2-mn+n^2,$$
причем
$$c^2=a^2+b_1^2-ab_1.$$
Теперь зафиксируем
$$a=m^2-n^2,\qquad c=m^2-mn+n^2$$
и решим уравнение для \(60^\circ\) относительно недостающей стороны \(b\):
$$b^2-ab+(a^2-c^2)=0.$$
Один корень — это \(b_1\), значит по Виету второй корень равен
$$b_2=a-b_1=(m^2-n^2)-(2mn-n^2)=m^2-2mn.$$
Именно поэтому код считает две неравносторонние ветви:
$$b_1=2mn-n^2,\qquad b_2=m^2-2mn.$$
Пример: \((m,n)=(3,1)\) дает
$$ (a,c)=(8,7),\qquad b_1=5,\qquad b_2=3. $$
Отсюда получаем два допустимых треугольника:
$$ (5,7,8),\qquad (3,7,8), $$
и в обоих случаях
$$7^2=5^2+8^2-5\cdot8=3^2+8^2-3\cdot8=49.$$
Почему ограничение \(n\le \lfloor(m-1)/2\rfloor\)? Потому что большие \(n\) лишь повторяют тот же неупорядоченный треугольник. Если заменить \(n\) на \(m-n\), то
$$a'=m^2-(m-n)^2=2mn-n^2=b_1,$$
$$b_1'=2m(m-n)-(m-n)^2=m^2-n^2=a,$$
и
$$c'=m^2-m(m-n)+(m-n)^2=c.$$
Значит, \((m,n)\) и \((m,m-n)\) порождают один и тот же треугольник, только со сменой ролей \(a\) и \(b_1\). Пример:
$$ (m,n)=(4,1)\Rightarrow(15,7,13), $$
$$ (m,n)=(4,3)\Rightarrow(7,15,13). $$
Поэтому просмотр только
$$1\le n\le \left\lfloor\frac{m-1}{2}\right\rfloor$$
оставляет ровно одного представителя для каждого неупорядоченного треугольника. Одновременно это гарантирует положительность второго корня:
$$b_2=m(m-2n)>0.$$
Примитивные периметры двух ветвей равны
$$P_{0,60A}=a+b_1+c=2m^2+mn-n^2\ge 2m^2+m-1,$$
$$P_{0,60B}=a+b_2+c=3m(m-n)\ge 3m\left\lceil\frac m2\right\rceil.$$
В коде вторая оценка записана через целочисленную арифметику как
$$3m\left(\frac{m+1}{2}\right)\qquad\text{с целым делением},$$
что и используется в max_m_60().
Как и для \(120^\circ\), примитивность фильтруется прямой проверкой
$$\gcd(a,b,c)=1.$$
Если \((a,b,c)\) примитивен и содержит один из целевых углов, то любой множитель
$$k(a,b,c)$$
сохраняет ту же угловую структуру и имеет периметр \(kP_0\). Значит, вклад одного примитивного треугольника равен
$$\left\lfloor\frac{L}{P_0}\right\rfloor.$$
Именно поэтому каждая счетная петля прибавляет целую часть от деления.
Отдельные счетчики. Программа ведет with_60, with_90 и with_120 по отдельности.
Немедленный равносторонний вклад. with_60 начинается с
$$\left\lfloor\frac{L}{3}\right\rfloor.$$
Три параметрических обхода. count_90_range(), count_120_range() и count_60_non_eq_range() проходят соответствующие решетки \((m,n)\).
Фильтры примитивности. Для прямоугольных треугольников используются классические условия взаимной простоты и разной четности; для семей \(60^\circ\) и \(120^\circ\) — \(\gcd(m,n)=1\) плюс прямой тест \(\gcd(a,b,c)=1\).
Жесткие границы по \(m\). max_m_90(), max_m_120() и max_m_60() получены напрямую из нижних оценок периметра выше.
Параллелизация. Потоки лишь делят значения \(m\) по классам вычетов; на математический ответ это не влияет.
Brute-force проверка. Код проверяет
$$N(100)=84,\qquad N_{60}(100)=53,\qquad N_{90}(100)=17,\qquad N_{120}(100)=14,$$
а затем сверяет быстрый метод с полным перебором для \(L=120,200,300\).
Каждое семейство — это по существу перебор по решетке \((m,n)\) с gcd-фильтрами, так что время работы примерно квадратично по соответствующему \(m_{\max}\). Нижние оценки на периметр заранее отсекают большие бесполезные области. Память — \(O(1)\), если не считать небольшой потоковый контекст и крошечную структуру для brute-force checkpoints.
نريد عدّ جميع المثلثات ذات الأضلاع الصحيحة والمحيط \(\le L\) والتي تحتوي زاوية تساوي تمامًا \(60^\circ\) أو \(90^\circ\) أو \(120^\circ\). لا نعرض الجواب النهائي لـ Project Euler؛ الهدف هنا هو شرح البارامتريات ومنطق العدّ الذي يستخدمه حل C++ بتفصيل أكبر.
نكتب
$$N(L)=N_{60}(L)+N_{90}(L)+N_{120}(L).$$
وبالنسبة إلى المثلثات ذات الأضلاع الصحيحة فهذه العائلات منفصلة فعلًا:
\(90^\circ\) و\(120^\circ\) لا يمكن أن يظهرا معًا لأن مجموعهما أكبر من \(180^\circ\).
\(60^\circ\) و\(120^\circ\) لا يمكن أن يجتمعا أيضًا لأن الزاوية الثالثة ستصبح \(0^\circ\).
\(60^\circ\) و\(90^\circ\) لو اجتمعا لكان المثلث من نوع \(30\)-\(60\)-\(90\)، ونسبة أضلاعه \(1:\sqrt3:2\). وبما أن \(\sqrt3\) عدد غير نسبي فلا يوجد تكبير صحيح يجعل الأضلاع الثلاثة أعدادًا صحيحة.
إذن كل مثلث صالح ينتمي إلى عدّاد واحد فقط من هذه العدّادات الثلاثة. أما المثلثات المتساوية الأضلاع فتقع فقط في عائلة \(60^\circ\).
إذا كان الضلع \(c\) يقابل الزاوية الخاصة \(\theta\)، فإن
$$c^2=a^2+b^2-2ab\cos\theta.$$
ومن ثم نحصل على
$$90^\circ:\ c^2=a^2+b^2,$$
$$60^\circ:\ c^2=a^2+b^2-ab,$$
$$120^\circ:\ c^2=a^2+b^2+ab.$$
إذًا المسألة تنقسم إلى ثلاث عائلات من الحلول الصحيحة، ثم إلى عدّ النسخ المكبّرة من كل مثلث أولي.
المثلثات القائمة الأولية تُعطى بصيغة إقليدس:
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
مع الشروط
$$m>n,\qquad \gcd(m,n)=1,\qquad m-n\text{ فردي}.$$
المحيط الأولي هو
$$P_{0,90}=a+b+c=2m(m+n).$$
مثال: \((m,n)=(2,1)\) يعطي \((3,4,5)\) ومحيطه \(12\). وكل مضاعف \(k(3,4,5)\) يبقى مثلثًا قائمًا، لذلك يساهم هذا المثلث الأولي بعدد
$$\left\lfloor\frac{L}{12}\right\rfloor$$
من النسخ.
ولقيمة \(m\) ثابتة يكون أصغر محيط ممكن عند \(n=1\):
$$P_{0,90}\ge 2m(m+1).$$
وهذا هو الحد الذي تستخدمه الدالة max_m_90().
لنأخذ \(\omega\) جذرًا تكعيبيًا بدائيًا للوحدة بحيث
$$\omega^2+\omega+1=0.$$
ومعيار أيزنشتاين هو
$$N(x+y\omega)=(x+y\omega)(x+y\omega^2)=x^2-xy+y^2.$$
وهذه بالضبط هي الصورة التربيعية التي تظهر في حالة \(60^\circ\):
$$c^2=a^2-ab+b^2=N(a+b\omega).$$
أما حالة \(120^\circ\) فنكتبها على الصورة
$$a^2+ab+b^2=a^2-a(-b)+(-b)^2=N(a-b\omega).$$
وبهذا تصبح عائلتا \(60^\circ\) و\(120^\circ\) نظيرتين لصيغة إقليدس لكن داخل أعداد أيزنشتاين.
نربّع \(m-n\omega\):
$$ (m-n\omega)^2 =m^2-n^2-(2mn+n^2)\omega. $$
ومعياره يساوي
$$N(m-n\omega)^2=(m^2+mn+n^2)^2.$$
ومن هنا نحصل على البارامتريات القياسية
$$a=m^2-n^2,\qquad b=2mn+n^2,\qquad c=m^2+mn+n^2,$$
وبالتعويض المباشر نجد
$$c^2=a^2+b^2+ab.$$
مثال: \((m,n)=(2,1)\) يعطي
$$a=3,\qquad b=5,\qquad c=7,$$
وبالفعل
$$7^2=3^2+5^2+3\cdot5=49.$$
المحيط الأولي هو
$$P_{0,120}=a+b+c=2m^2+3mn+n^2.$$
ولـ \(m\) ثابت يكون أصغره عند \(n=1\):
$$P_{0,120}\ge 2m^2+3m+1.$$
وهذا هو الحد المستخدم في max_m_120().
كما أن الشرط \(\gcd(m,n)=1\) لا يكفي وحده لضمان أولية \((a,b,c)\). فمثلًا
$$ (m,n)=(4,1)\Rightarrow(15,9,21)=3\cdot(5,3,7). $$
ولذلك يطبّق البرنامج الاختبار المباشر
$$\gcd(a,b,c)=1$$
بدل ترميز القيد الإضافي الخاص ببواقي modulo \(3\) يدويًا.
أولًا، المثلثات المتساوية الأضلاع تساهم مباشرةً:
$$ (k,k,k),\qquad 3k\le L,\qquad \text{العدد}=\left\lfloor\frac{L}{3}\right\rfloor. $$
أما للحلول الأولية غير المتساوية فنربّع \(m+n\omega\):
$$ (m+n\omega)^2 =(m^2-n^2)+(2mn-n^2)\omega. $$
ومعياره هو
$$N(m+n\omega)^2=(m^2-mn+n^2)^2.$$
ومن هنا نحصل على الفرع الأول:
$$a=m^2-n^2,\qquad b_1=2mn-n^2,\qquad c=m^2-mn+n^2,$$
بحيث
$$c^2=a^2+b_1^2-ab_1.$$
الآن نثبّت
$$a=m^2-n^2,\qquad c=m^2-mn+n^2$$
ونحل معادلة \(60^\circ\) بالنسبة إلى الضلع المجهول \(b\):
$$b^2-ab+(a^2-c^2)=0.$$
وبما أن أحد الجذرين هو \(b_1\)، فإن الجذر الثاني حسب فييتا هو
$$b_2=a-b_1=(m^2-n^2)-(2mn-n^2)=m^2-2mn.$$
ولهذا يعدّ الكود شعبتين غير متساويتين:
$$b_1=2mn-n^2,\qquad b_2=m^2-2mn.$$
مثال: \((m,n)=(3,1)\) يعطي
$$ (a,c)=(8,7),\qquad b_1=5,\qquad b_2=3. $$
ومن ثم نحصل على مثلثين صالحين:
$$ (5,7,8),\qquad (3,7,8), $$
وفي الحالتين
$$7^2=5^2+8^2-5\cdot8=3^2+8^2-3\cdot8=49.$$
لماذا نقيّد \(n\le \lfloor(m-1)/2\rfloor\)؟ لأن القيم الأكبر من \(n\) تعيد إنتاج المثلث غير المرتب نفسه فقط. إذا استبدلنا \(n\) بـ \(m-n\) نحصل على
$$a'=m^2-(m-n)^2=2mn-n^2=b_1,$$
$$b_1'=2m(m-n)-(m-n)^2=m^2-n^2=a,$$
وكذلك
$$c'=m^2-m(m-n)+(m-n)^2=c.$$
إذن الزوجان \((m,n)\) و\((m,m-n)\) يولدان المثلث نفسه بعد تبديل \(a\) و\(b_1\). مثال:
$$ (m,n)=(4,1)\Rightarrow(15,7,13), $$
$$ (m,n)=(4,3)\Rightarrow(7,15,13). $$
وبالتالي فإن المسح ضمن المجال
$$1\le n\le \left\lfloor\frac{m-1}{2}\right\rfloor$$
يترك ممثلًا واحدًا فقط لكل مثلث غير مرتب. كما يضمن أيضًا أن يكون الجذر الثاني موجبًا:
$$b_2=m(m-2n)>0.$$
محيطا الشعبتين الأوليين هما
$$P_{0,60A}=a+b_1+c=2m^2+mn-n^2\ge 2m^2+m-1,$$
$$P_{0,60B}=a+b_2+c=3m(m-n)\ge 3m\left\lceil\frac m2\right\rceil.$$
ويكتب الكود الحد الثاني بصياغة حساب صحيح على الصورة
$$3m\left(\frac{m+1}{2}\right)\qquad\text{مع فهمه كقسمة صحيحة},$$
وهو ما يظهر داخل max_m_60().
وكما في عائلة \(120^\circ\)، يتم الاحتفاظ بالمثلثات الأولية فقط عبر الاختبار المباشر
$$\gcd(a,b,c)=1.$$
إذا كان \((a,b,c)\) مثلثًا أوليًا ويحمل إحدى الزوايا المطلوبة، فإن كل مضاعف
$$k(a,b,c)$$
يحافظ على البنية الزاوية نفسها ويملك محيطًا يساوي \(kP_0\). لذلك يساهم كل مثلث أولي بعدد
$$\left\lfloor\frac{L}{P_0}\right\rfloor$$
من النسخ. ومن هنا تأتي جميع حدود القسمة الصحيحة في البرنامج.
عدّادات منفصلة. يحتفظ البرنامج بـ with_60 وwith_90 وwith_120 بشكل مستقل.
إضافة المتساوي الأضلاع مباشرة. يبدأ with_60 بالقيمة
$$\left\lfloor\frac{L}{3}\right\rfloor.$$
ثلاث عمليات مسح بارامتري. تقوم الدوال count_90_range() وcount_120_range() وcount_60_non_eq_range() بمسح شبكات \((m,n)\) المناسبة.
مرشحات الأولية. عائلة الزاوية القائمة تستخدم الشروط الكلاسيكية للتباين في الفردية/الزوجية مع coprime؛ أما عائلتا \(60^\circ\) و\(120^\circ\) فتستخدمان \(\gcd(m,n)=1\) مع فحص مباشر لـ \(\gcd(a,b,c)=1\).
حدود صلبة لـ \(m\). الدوال max_m_90() وmax_m_120() وmax_m_60() مشتقة مباشرة من حدود المحيط الدنيا التي شرحناها.
التوازي. الخيوط تقسّم قيم \(m\) فقط حسب البواقي؛ هذا يغيّر زمن التنفيذ لا المجموعة المعدودة.
التحقق brute force. من أهم نقاط التحقق في البرنامج:
$$N(100)=84,\qquad N_{60}(100)=53,\qquad N_{90}(100)=17,\qquad N_{120}(100)=14,$$
ثم تُقارن الطريقة السريعة بالمسح المباشر عند \(L=120,200,300\).
كل عائلة هي في الأساس مسح على شبكة \((m,n)\) مع مرشحات gcd، ولذلك يكون الزمن تقريبًا تربيعيًا في \(m_{\max}\) المناسب. حدود المحيط تقصّ مناطق واسعة بلا مساهمة مبكرًا. الذاكرة هي \(O(1)\) تقريبًا، باستثناء سياق صغير للخيوط وبنية brute-force الصغيرة المستخدمة في نقاط التحقق.