The local C++ validator shows that every admissible triangle can be represented in centered form
$$P_1=(x_1,y_1),\qquad P_2=(x_2,y_2),\qquad P_3=(-x_1-x_2,-y_1-y_2),$$
so automatically
$$x_1+x_2+x_3=0,\qquad y_1+y_2+y_3=0.$$
The ellipse condition is already converted by the implementation into the Diophantine system
$$ (2x_1+x_2)y_1 + (x_1+2x_2)y_2 = 0, $$
$$ x_1^2+x_1x_2+x_2^2 - (y_1^2+y_1y_2+y_2^2) = 39. $$
We must sum the Euclidean areas of all non-degenerate integer triangles whose coordinates lie inside \([-N,N]^2\), for the real target \(N=10^9\). The brute-force search in solve_bruteforce_small is only feasible for tiny \(N\), so the fast solver rewrites the problem as a finite family of Pell-type recurrences.
Write the three \(x\)-coordinates as
$$x_1=du,\qquad x_2=dv,\qquad x_3=-d(u+v),$$
where \(d>0\) and \(\gcd(u,v)=1\). The linear constraint then becomes
$$a y_1 + b y_2 = 0,\qquad a=2u+v,\qquad b=u+2v.$$
All integer solutions of this linear equation have the form
$$y_1=\frac{b}{m}k,\qquad y_2=-\frac{a}{m}k,\qquad y_3=-y_1-y_2=\frac{u-v}{m}k,$$
where \(m=\gcd(a,b)\) and \(k\in\mathbb{Z}\). Because
$$2a-b=3u,\qquad 2b-a=3v,$$
every common divisor of \(a\) and \(b\) must divide \(3\). Since \((u,v)\) is primitive, \(m\in\{1,3\}\). The admissible primitive directions kept by the program always satisfy \(m=3\).
Define the norm
$$q_0=u^2+uv+v^2.$$
Then the \(x\)-part of the quadratic equation becomes
$$x_1^2+x_1x_2+x_2^2=d^2q_0.$$
For the \(y\)-part, using \(m=3\), \(a=2u+v\), and \(b=u+2v\), we obtain
$$y_1^2+y_1y_2+y_2^2=\frac{b^2-ab+a^2}{9}k^2.$$
Now
$$a^2-ab+b^2=3(u^2+uv+v^2)=3q_0,$$
so
$$y_1^2+y_1y_2+y_2^2=\frac{q_0}{3}k^2.$$
Substituting into the validator equation gives
$$39=q_0d^2-\frac{q_0}{3}k^2=\frac{q_0}{3}(3d^2-k^2),$$
hence
$$q_0(3d^2-k^2)=117,\qquad k^2-3d^2=-\frac{117}{q_0}.$$
This identity is the algebraic backbone of the fast method.
The previous formula shows that \(q_0\) must divide \(117\). The code then enumerates primitive pairs \((u,v)\) satisfying
$$u^2+uv+v^2=q_0,\qquad \gcd(u,v)=1,\qquad \gcd(2u+v,u+2v)=3.$$
A direct enumeration leaves exactly two norm families:
$$q_0=3 \quad\text{with 6 primitive directions},\qquad q_0=39 \quad\text{with 12 primitive directions}.$$
No admissible primitive direction exists for \(q_0=117\), so the whole search collapses to \(18\) direction templates. That is why build_directions loops only over q0 in (3, 39).
The two surviving norms lead to
$$q_0=3 \Longrightarrow k^2-3d^2=-39,\qquad q_0=39 \Longrightarrow k^2-3d^2=-3.$$
The implementations use the smallest positive seeds found by inspection:
$$ (d,k)=(4,3),(5,6)\ \text{for }-39,\qquad (d,k)=(2,3)\ \text{for }-3. $$
All larger solutions are generated by multiplication with the fundamental unit \(2+\sqrt{3}\), which yields the recurrence
$$k_{n+1}=2k_n+3d_n,\qquad d_{n+1}=k_n+2d_n.$$
For one fixed direction \((u,v)\), the coordinate bounds are
$$x_{\mathrm{scale}}=\max(|u|,|v|,|u+v|),$$
$$y_{\mathrm{scale}}=\frac{\max(|2u+v|,|u+2v|,|u-v|)}{3},$$
so the code keeps only pairs with
$$d\le \left\lfloor\frac{N}{x_{\mathrm{scale}}}\right\rfloor,\qquad k\le \left\lfloor\frac{N}{y_{\mathrm{scale}}}\right\rfloor.$$
Using the explicit coordinates, the doubled area simplifies to
$$2A=\left|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\right|=2q_0|dk|,$$
so the actual area is
$$\boxed{A=q_0|dk|}.$$
Take the primitive direction \((u,v)=(1,1)\), which belongs to the \(q_0=3\) family. With the seed \((d,k)=(4,3)\), we get
$$ (x_1,y_1)=(4,3),\qquad (x_2,y_2)=(4,-3),\qquad (x_3,y_3)=(-8,0), $$
and therefore
$$A=3\cdot 4\cdot 3=36.$$
This is one of the triangles contributing to the checkpoint value \(72\) at \(N=8\). Because different direction/sign choices can reconstruct the same triangle, the implementations sort the three vertices and use the sorted triple as a hash key. If a duplicate is seen, the code checks that the area is identical before merging.
The three solution files implement the same pipeline. build_directions enumerates the \(18\) primitive direction templates and computes their personal \((d_{\max},k_{\max})\) cutoffs. generate_pell_pairs precomputes all Pell solutions for the two negative right-hand sides up to the largest cutoff required by any direction. build_triangle_key reconstructs the three vertices, rejects out-of-range or degenerate cases, and returns the sorted vertex triple together with the closed-form area \(q_0|dk|\).
The main loop selects the correct Pell list for each direction, tries both signs of \(k\), and inserts the triangle into a hash map keyed by its sorted vertices. The C++ version adds extra validation: checkpoint values \(72\), \(252\), \(34632\), and \(3529008\) for \(N=8,10,100,1000\), plus a brute-force cross-check against solve_bruteforce_small(20). The Python and Java versions use the same fast construction without the checkpoint harness.
For this problem the number of direction templates is constant: \(18\). Each Pell sequence grows exponentially because the recurrence multiplies by \(2+\sqrt{3}\), so the number of generated \((d,k)\) pairs below the bounds is \(O(\log N)\) per family. The total running time is therefore proportional to the number of generated candidates and hash insertions, rather than to any polynomial scan over lattice coordinates. Memory usage is \(O(T)\), where \(T\) is the number of distinct triangles stored in the hash map.
solutionsCpp/Euler385.cpp, solutionsPython/Euler385.py, solutionsJava/Euler385.javaDer lokale C++-Validator zeigt, dass jedes zulässige Dreieck in zentrierter Form geschrieben werden kann als
$$P_1=(x_1,y_1),\qquad P_2=(x_2,y_2),\qquad P_3=(-x_1-x_2,-y_1-y_2),$$
womit automatisch gilt
$$x_1+x_2+x_3=0,\qquad y_1+y_2+y_3=0.$$
Die Ellipsenbedingung ist in der Implementierung bereits zu folgendem diophantischen System umgeformt:
$$ (2x_1+x_2)y_1 + (x_1+2x_2)y_2 = 0, $$
$$ x_1^2+x_1x_2+x_2^2 - (y_1^2+y_1y_2+y_2^2) = 39. $$
Gesucht ist die Summe der euklidischen Flächen aller nicht entarteten ganzzahligen Dreiecke mit Koordinaten in \([-N,N]^2\), für das eigentliche Ziel \(N=10^9\). Die brute-force-Suche in solve_bruteforce_small funktioniert nur für sehr kleine \(N\); die schnelle Lösung reduziert das Problem daher auf endlich viele Pell-artige Rekursionen.
Schreibe die drei \(x\)-Koordinaten als
$$x_1=du,\qquad x_2=dv,\qquad x_3=-d(u+v),$$
wobei \(d>0\) und \(\gcd(u,v)=1\) gilt. Dann wird die lineare Nebenbedingung zu
$$a y_1 + b y_2 = 0,\qquad a=2u+v,\qquad b=u+2v.$$
Alle ganzzahligen Lösungen haben dann die Form
$$y_1=\frac{b}{m}k,\qquad y_2=-\frac{a}{m}k,\qquad y_3=-y_1-y_2=\frac{u-v}{m}k,$$
wobei \(m=\gcd(a,b)\) und \(k\in\mathbb{Z}\). Wegen
$$2a-b=3u,\qquad 2b-a=3v$$
teilt jeder gemeinsame Teiler von \(a\) und \(b\) die Zahl \(3\). Da \((u,v)\) primitiv ist, folgt \(m\in\{1,3\}\). Die im Programm zulässigen primitiven Richtungen haben immer \(m=3\).
Definiere
$$q_0=u^2+uv+v^2.$$
Dann wird der \(x\)-Teil zu
$$x_1^2+x_1x_2+x_2^2=d^2q_0.$$
Für den \(y\)-Teil erhält man mit \(m=3\), \(a=2u+v\) und \(b=u+2v\)
$$y_1^2+y_1y_2+y_2^2=\frac{b^2-ab+a^2}{9}k^2.$$
Außerdem gilt
$$a^2-ab+b^2=3(u^2+uv+v^2)=3q_0,$$
also
$$y_1^2+y_1y_2+y_2^2=\frac{q_0}{3}k^2.$$
Damit wird die Prüfgleichung zu
$$39=q_0d^2-\frac{q_0}{3}k^2=\frac{q_0}{3}(3d^2-k^2),$$
also
$$q_0(3d^2-k^2)=117,\qquad k^2-3d^2=-\frac{117}{q_0}.$$
Genau diese Identität trägt die gesamte schnelle Methode.
Aus der vorherigen Formel folgt zunächst, dass \(q_0\) ein Teiler von \(117\) sein muss. Anschließend enumeriert der Code primitive Paare \((u,v)\) mit
$$u^2+uv+v^2=q_0,\qquad \gcd(u,v)=1,\qquad \gcd(2u+v,u+2v)=3.$$
Eine direkte Aufzählung lässt genau zwei Normfamilien übrig:
$$q_0=3 \quad\text{mit 6 primitiven Richtungen},\qquad q_0=39 \quad\text{mit 12 primitiven Richtungen}.$$
Für \(q_0=117\) existiert keine zulässige primitive Richtung, daher schrumpft der gesamte Suchraum auf genau \(18\) Richtungsschablonen. Deshalb iteriert build_directions nur über q0 in (3, 39).
Die beiden verbleibenden Normen führen zu
$$q_0=3 \Longrightarrow k^2-3d^2=-39,\qquad q_0=39 \Longrightarrow k^2-3d^2=-3.$$
Die Implementierungen verwenden die kleinsten positiven Startlösungen:
$$ (d,k)=(4,3),(5,6)\ \text{für }-39,\qquad (d,k)=(2,3)\ \text{für }-3. $$
Alle größeren Lösungen entstehen durch Multiplikation mit der Grundeinheit \(2+\sqrt{3}\); daraus folgt die Rekursion
$$k_{n+1}=2k_n+3d_n,\qquad d_{n+1}=k_n+2d_n.$$
Für eine feste Richtung \((u,v)\) sind die Schranken
$$x_{\mathrm{scale}}=\max(|u|,|v|,|u+v|),$$
$$y_{\mathrm{scale}}=\frac{\max(|2u+v|,|u+2v|,|u-v|)}{3},$$
und der Code akzeptiert nur
$$d\le \left\lfloor\frac{N}{x_{\mathrm{scale}}}\right\rfloor,\qquad k\le \left\lfloor\frac{N}{y_{\mathrm{scale}}}\right\rfloor.$$
Mit den expliziten Koordinaten vereinfacht sich die doppelte Fläche zu
$$2A=\left|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\right|=2q_0|dk|,$$
also ist die tatsächliche Fläche
$$\boxed{A=q_0|dk|}.$$
Nimm zum Beispiel die primitive Richtung \((u,v)=(1,1)\) aus der Familie \(q_0=3\). Mit der Startlösung \((d,k)=(4,3)\) erhält man
$$ (x_1,y_1)=(4,3),\qquad (x_2,y_2)=(4,-3),\qquad (x_3,y_3)=(-8,0), $$
und damit
$$A=3\cdot 4\cdot 3=36.$$
Dies ist eines der Dreiecke, die zum Kontrollwert \(72\) bei \(N=8\) beitragen. Da verschiedene Richtungs- oder Vorzeichenwahlen dasselbe Dreieck rekonstruieren können, sortieren die Implementierungen die drei Eckpunkte und benutzen das sortierte Tripel als Hash-Schlüssel. Bei einem Duplikat wird zusätzlich geprüft, dass die Fläche übereinstimmt.
Alle drei Lösungsdateien verwenden dieselbe Pipeline. build_directions erzeugt die \(18\) primitiven Richtungsschablonen und berechnet für jede Schablone ihre persönlichen Schranken \((d_{\max},k_{\max})\). generate_pell_pairs berechnet alle Pell-Lösungen für die beiden negativen rechten Seiten bis zur größten von irgendeiner Richtung benötigten Schranke. build_triangle_key setzt daraus die drei Eckpunkte zusammen, verwirft entartete oder zu große Kandidaten und liefert das sortierte Eckpunkts-Tripel zusammen mit der geschlossenen Flächenformel \(q_0|dk|\).
Die Hauptschleife wählt für jede Richtung die passende Pell-Liste, probiert beide Vorzeichen von \(k\) aus und fügt das Ergebnis in eine Hash-Map ein, die nach den sortierten Eckpunkten indiziert ist. Die C++-Version enthält zusätzlich Validierung: die Kontrollwerte \(72\), \(252\), \(34632\) und \(3529008\) für \(N=8,10,100,1000\) sowie einen brute-force-Abgleich mit solve_bruteforce_small(20). Python und Java implementieren dieselbe schnelle Konstruktion ohne dieses Prüfharness.
Für Problem 385 ist die Anzahl der Richtungsschablonen konstant: \(18\). Jede Pell-Folge wächst exponentiell, weil die Rekursion effektiv mit \(2+\sqrt{3}\) multipliziert, also gibt es pro Familie nur \(O(\log N)\) viele relevante \((d,k)\)-Paare. Die Gesamtlaufzeit ist deshalb proportional zur Zahl der tatsächlich erzeugten Kandidaten und Hash-Einfügungen statt zu einem polynomialen Gitter-Scan. Der Speicherverbrauch beträgt \(O(T)\), wobei \(T\) die Zahl der unterschiedlichen Dreiecke in der Hash-Map ist.
solutionsCpp/Euler385.cpp, solutionsPython/Euler385.py, solutionsJava/Euler385.javaYerel C++ doğrulayıcısı, her geçerli üçgenin merkezlenmiş biçimde
$$P_1=(x_1,y_1),\qquad P_2=(x_2,y_2),\qquad P_3=(-x_1-x_2,-y_1-y_2)$$
şeklinde yazılabildiğini gösterir. Böylece otomatik olarak
$$x_1+x_2+x_3=0,\qquad y_1+y_2+y_3=0$$
olur. Elips koşulu da implementasyonda şu diofant denklemlerine indirgenmiştir:
$$ (2x_1+x_2)y_1 + (x_1+2x_2)y_2 = 0, $$
$$ x_1^2+x_1x_2+x_2^2 - (y_1^2+y_1y_2+y_2^2) = 39. $$
Amacımız, koordinatları \([-N,N]^2\) içinde kalan tüm bozulmamış tamsayı üçgenlerin Öklidyen alanlarını toplamak. Gerçek hedef \(N=10^9\) olduğundan, solve_bruteforce_small içindeki kaba kuvvet yaklaşımı sadece çok küçük \(N\) için işe yarar; hızlı çözüm ise problemi sonlu sayıda Pell-tipli yinelemeye dönüştürür.
Üç \(x\)-koordinatını
$$x_1=du,\qquad x_2=dv,\qquad x_3=-d(u+v)$$
şeklinde yazalım; burada \(d>0\) ve \(\gcd(u,v)=1\). O zaman lineer kısıt
$$a y_1 + b y_2 = 0,\qquad a=2u+v,\qquad b=u+2v$$
haline gelir. Bu denklemin tüm tamsayı çözümleri
$$y_1=\frac{b}{m}k,\qquad y_2=-\frac{a}{m}k,\qquad y_3=-y_1-y_2=\frac{u-v}{m}k$$
biçimindedir; burada \(m=\gcd(a,b)\) ve \(k\in\mathbb{Z}\). Çünkü
$$2a-b=3u,\qquad 2b-a=3v,$$
\(a\) ile \(b\)'nin her ortak böleni \(3\)'ü bölmek zorundadır. \((u,v)\) ilkel olduğundan \(m\in\{1,3\}\) çıkar. Programın kabul ettiği tüm ilkel yönlerde \(m=3\) olur.
Şu normu tanımlayalım:
$$q_0=u^2+uv+v^2.$$
Böylece \(x\)-kısmı
$$x_1^2+x_1x_2+x_2^2=d^2q_0$$
olur. \(y\)-kısmı için, \(m=3\), \(a=2u+v\) ve \(b=u+2v\) kullanılırsa
$$y_1^2+y_1y_2+y_2^2=\frac{b^2-ab+a^2}{9}k^2$$
elde edilir. Ayrıca
$$a^2-ab+b^2=3(u^2+uv+v^2)=3q_0,$$
dolayısıyla
$$y_1^2+y_1y_2+y_2^2=\frac{q_0}{3}k^2.$$
Bunu doğrulayıcı denklemine koyunca
$$39=q_0d^2-\frac{q_0}{3}k^2=\frac{q_0}{3}(3d^2-k^2)$$
ve dolayısıyla
$$q_0(3d^2-k^2)=117,\qquad k^2-3d^2=-\frac{117}{q_0}$$
çıkar. Hızlı yöntemin omurgası tam olarak budur.
Bir önceki formül, \(q_0\)'ın \(117\)'yi bölmesi gerektiğini gösterir. Daha sonra kod
$$u^2+uv+v^2=q_0,\qquad \gcd(u,v)=1,\qquad \gcd(2u+v,u+2v)=3$$
koşullarını sağlayan ilkel \((u,v)\) çiftlerini tarar. Doğrudan sayım sonunda yalnızca iki norm ailesi kalır:
$$q_0=3 \quad\text{için 6 ilkel yön},\qquad q_0=39 \quad\text{için 12 ilkel yön}.$$
\(q_0=117\) için uygun ilkel yön çıkmadığından, tüm arama alanı tam olarak \(18\) yön şablonuna iner. build_directions fonksiyonunun sadece q0 in (3, 39) üzerinde dönmesinin sebebi budur.
Kalan iki norm şu denklemlere yol açar:
$$q_0=3 \Longrightarrow k^2-3d^2=-39,\qquad q_0=39 \Longrightarrow k^2-3d^2=-3.$$
Implementasyonlar en küçük pozitif tohum çözümleri kullanır:
$$ (d,k)=(4,3),(5,6)\ \text{ için }-39,\qquad (d,k)=(2,3)\ \text{ için }-3. $$
Daha büyük tüm çözümler, temel birim \(2+\sqrt{3}\) ile üretilir; bu da
$$k_{n+1}=2k_n+3d_n,\qquad d_{n+1}=k_n+2d_n$$
yinelemesini verir. Sabit bir \((u,v)\) yönü için sınırlar
$$x_{\mathrm{scale}}=\max(|u|,|v|,|u+v|),$$
$$y_{\mathrm{scale}}=\frac{\max(|2u+v|,|u+2v|,|u-v|)}{3}$$
olduğundan kod yalnızca
$$d\le \left\lfloor\frac{N}{x_{\mathrm{scale}}}\right\rfloor,\qquad k\le \left\lfloor\frac{N}{y_{\mathrm{scale}}}\right\rfloor$$
koşullarını sağlayan çiftleri tutar.
Açık koordinatlar yazıldığında iki kat alan
$$2A=\left|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\right|=2q_0|dk|$$
şeklinde sadeleşir. Yani gerçek alan
$$\boxed{A=q_0|dk|}$$
olur. Örneğin \((u,v)=(1,1)\) ilkel yönü \(q_0=3\) ailesindedir. Tohum çözüm \((d,k)=(4,3)\) seçilirse
$$ (x_1,y_1)=(4,3),\qquad (x_2,y_2)=(4,-3),\qquad (x_3,y_3)=(-8,0) $$
elde edilir ve
$$A=3\cdot 4\cdot 3=36$$
çıkar. Bu üçgen, \(N=8\) için doğrulama değerindeki \(72\)'ye katkı yapan üçgenlerden biridir. Farklı yön veya işaret seçimleri aynı üçgeni yeniden üretebildiği için implementasyonlar üç köşeyi sıralayıp bunu hash anahtarı olarak kullanır. Eğer aynı üçgen tekrar gelirse alanın da aynı olduğu ayrıca kontrol edilir.
Üç çözüm dosyasının akışı aynıdır. build_directions, \(18\) ilkel yön şablonunu çıkarır ve her biri için \((d_{\max},k_{\max})\) sınırlarını hesaplar. generate_pell_pairs, iki negatif sağ taraf için gerekli tüm Pell çözümlerini üretir. build_triangle_key ise üç köşeyi geri kurar, sınır dışı ya da bozulmuş durumları eler ve sıralanmış köşe üçlüsü ile kapalı form alanı \(q_0|dk|\) döndürür.
Ana döngü, her yön için doğru Pell listesini seçer, \(k\)'nın iki işaretini de dener ve üçgeni sıralı köşelerine göre hash tablosuna ekler. C++ sürümünde buna ek olarak doğrulama katmanı vardır: \(N=8,10,100,1000\) için \(72,252,34632,3529008\) kontrol değerleri ve solve_bruteforce_small(20) ile kaba kuvvet karşılaştırması. Python ve Java sürümleri aynı hızlı yöntemi bu kontrol çatısı olmadan uygular.
Bu problemde yön şablonu sayısı sabittir: \(18\). Her Pell dizisi, yineleme fiilen \(2+\sqrt{3}\) ile çarptığı için üstel büyür; bu nedenle sınır altında kalan \((d,k)\) sayısı aile başına \(O(\log N)\) olur. Böylece toplam süre, ızgara üzerinde polinomik tarama yapmak yerine üretilen aday ve hash ekleme sayısıyla orantılıdır. Bellek kullanımı \(O(T)\)'dir; burada \(T\), hash tablosunda tutulan farklı üçgenlerin sayısıdır.
solutionsCpp/Euler385.cpp, solutionsPython/Euler385.py, solutionsJava/Euler385.javaEl validador local en C++ muestra que todo triángulo admisible puede escribirse en forma centrada:
$$P_1=(x_1,y_1),\qquad P_2=(x_2,y_2),\qquad P_3=(-x_1-x_2,-y_1-y_2),$$
de modo que automáticamente
$$x_1+x_2+x_3=0,\qquad y_1+y_2+y_3=0.$$
La condición geométrica de la elipse ya está convertida por la implementación en el sistema diofántico
$$ (2x_1+x_2)y_1 + (x_1+2x_2)y_2 = 0, $$
$$ x_1^2+x_1x_2+x_2^2 - (y_1^2+y_1y_2+y_2^2) = 39. $$
Debemos sumar las áreas euclidianas de todos los triángulos enteros no degenerados cuyas coordenadas están dentro de \([-N,N]^2\), con el objetivo real \(N=10^9\). La búsqueda exhaustiva de solve_bruteforce_small solo sirve para \(N\) muy pequeño; la solución rápida transforma el problema en unas pocas recurrencias de tipo Pell.
Escribimos
$$x_1=du,\qquad x_2=dv,\qquad x_3=-d(u+v),$$
con \(d>0\) y \(\gcd(u,v)=1\). Entonces la restricción lineal pasa a ser
$$a y_1 + b y_2 = 0,\qquad a=2u+v,\qquad b=u+2v.$$
Todas las soluciones enteras toman la forma
$$y_1=\frac{b}{m}k,\qquad y_2=-\frac{a}{m}k,\qquad y_3=-y_1-y_2=\frac{u-v}{m}k,$$
donde \(m=\gcd(a,b)\) y \(k\in\mathbb{Z}\). Como
$$2a-b=3u,\qquad 2b-a=3v,$$
todo divisor común de \(a\) y \(b\) divide a \(3\). Como \((u,v)\) es primitivo, se obtiene \(m\in\{1,3\}\). En todas las direcciones primitivas admitidas por el programa resulta \(m=3\).
Definimos
$$q_0=u^2+uv+v^2.$$
Entonces la parte en \(x\) se convierte en
$$x_1^2+x_1x_2+x_2^2=d^2q_0.$$
Para la parte en \(y\), usando \(m=3\), \(a=2u+v\) y \(b=u+2v\), se obtiene
$$y_1^2+y_1y_2+y_2^2=\frac{b^2-ab+a^2}{9}k^2.$$
Además,
$$a^2-ab+b^2=3(u^2+uv+v^2)=3q_0,$$
y por tanto
$$y_1^2+y_1y_2+y_2^2=\frac{q_0}{3}k^2.$$
Al sustituir en la ecuación del validador aparece
$$39=q_0d^2-\frac{q_0}{3}k^2=\frac{q_0}{3}(3d^2-k^2),$$
es decir,
$$q_0(3d^2-k^2)=117,\qquad k^2-3d^2=-\frac{117}{q_0}.$$
Esta identidad es la columna vertebral algebraica del método rápido.
La fórmula anterior obliga a que \(q_0\) divida a \(117\). Después el código enumera pares primitivos \((u,v)\) con
$$u^2+uv+v^2=q_0,\qquad \gcd(u,v)=1,\qquad \gcd(2u+v,u+2v)=3.$$
La enumeración directa deja exactamente dos familias:
$$q_0=3 \quad\text{con 6 direcciones primitivas},\qquad q_0=39 \quad\text{con 12 direcciones primitivas}.$$
No existe ninguna dirección primitiva admisible para \(q_0=117\), así que todo el espacio de búsqueda se reduce a \(18\) plantillas de dirección. Por eso build_directions solo recorre q0 in (3, 39).
Las dos normas supervivientes producen
$$q_0=3 \Longrightarrow k^2-3d^2=-39,\qquad q_0=39 \Longrightarrow k^2-3d^2=-3.$$
Las implementaciones arrancan con las semillas positivas mínimas:
$$ (d,k)=(4,3),(5,6)\ \text{para }-39,\qquad (d,k)=(2,3)\ \text{para }-3. $$
Todas las soluciones mayores se generan multiplicando por la unidad fundamental \(2+\sqrt{3}\), lo que da la recurrencia
$$k_{n+1}=2k_n+3d_n,\qquad d_{n+1}=k_n+2d_n.$$
Para una dirección fija \((u,v)\), los límites geométricos son
$$x_{\mathrm{scale}}=\max(|u|,|v|,|u+v|),$$
$$y_{\mathrm{scale}}=\frac{\max(|2u+v|,|u+2v|,|u-v|)}{3},$$
y el código conserva solo los pares que cumplen
$$d\le \left\lfloor\frac{N}{x_{\mathrm{scale}}}\right\rfloor,\qquad k\le \left\lfloor\frac{N}{y_{\mathrm{scale}}}\right\rfloor.$$
Con las coordenadas explícitas, el doble del área se simplifica a
$$2A=\left|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\right|=2q_0|dk|,$$
así que el área real es
$$\boxed{A=q_0|dk|}.$$
Tomemos la dirección primitiva \((u,v)=(1,1)\), perteneciente a la familia \(q_0=3\). Con la semilla \((d,k)=(4,3)\) obtenemos
$$ (x_1,y_1)=(4,3),\qquad (x_2,y_2)=(4,-3),\qquad (x_3,y_3)=(-8,0), $$
y por tanto
$$A=3\cdot 4\cdot 3=36.$$
Este es uno de los triángulos que contribuyen al valor de control \(72\) cuando \(N=8\). Como distintas elecciones de dirección o de signo pueden reconstruir el mismo triángulo, las implementaciones ordenan los tres vértices y usan la terna ordenada como clave hash. Si aparece un duplicado, el código comprueba además que el área coincida.
Los tres archivos de solución siguen la misma tubería. build_directions enumera las \(18\) plantillas de dirección primitivas y calcula sus cotas \((d_{\max},k_{\max})\). generate_pell_pairs precalcula todas las soluciones de Pell para los dos términos independientes negativos hasta la mayor cota requerida. build_triangle_key reconstruye los tres vértices, rechaza casos degenerados o fuera del rango y devuelve la terna ordenada junto con el área cerrada \(q_0|dk|\).
El bucle principal selecciona la lista de Pell adecuada para cada dirección, prueba ambos signos de \(k\) e inserta el triángulo en una tabla hash indexada por sus vértices ordenados. La versión en C++ añade validación extra: los puntos de control \(72\), \(252\), \(34632\) y \(3529008\) para \(N=8,10,100,1000\), más una comparación exhaustiva con solve_bruteforce_small(20). Las versiones en Python y Java implementan la misma construcción rápida sin ese arnés de comprobación.
En este problema el número de plantillas de dirección es constante: \(18\). Cada sucesión de Pell crece exponencialmente porque la recurrencia equivale a multiplicar por \(2+\sqrt{3}\), de modo que el número de pares \((d,k)\) bajo la frontera es \(O(\log N)\) por familia. Por ello, el tiempo total es proporcional al número de candidatos realmente generados y a las inserciones en la tabla hash, en lugar de a un barrido polinómico sobre la rejilla. La memoria utilizada es \(O(T)\), donde \(T\) es el número de triángulos distintos almacenados.
solutionsCpp/Euler385.cpp, solutionsPython/Euler385.py, solutionsJava/Euler385.java本地 C++ 校验器表明，每个合法三角形都可以写成中心化形式
$$P_1=(x_1,y_1),\qquad P_2=(x_2,y_2),\qquad P_3=(-x_1-x_2,-y_1-y_2),$$
因此自动满足
$$x_1+x_2+x_3=0,\qquad y_1+y_2+y_3=0.$$
实现代码已经把“椭圆在三角形内”的几何条件化成了如下丢番图系统：
$$ (2x_1+x_2)y_1 + (x_1+2x_2)y_2 = 0, $$
$$ x_1^2+x_1x_2+x_2^2 - (y_1^2+y_1y_2+y_2^2) = 39. $$
目标是对所有非退化整数三角形的欧几里得面积求和，并要求所有坐标都落在 \([-N,N]^2\) 内，实际参数是 \(N=10^9\)。solve_bruteforce_small 中的暴力法只能处理很小的 \(N\)；快速解法则把问题化成有限个 Pell 型递推族。
把三个 \(x\) 坐标写成
$$x_1=du,\qquad x_2=dv,\qquad x_3=-d(u+v),$$
其中 \(d>0\)，且 \(\gcd(u,v)=1\)。此时线性约束变为
$$a y_1 + b y_2 = 0,\qquad a=2u+v,\qquad b=u+2v.$$
这个线性方程的全部整数解为
$$y_1=\frac{b}{m}k,\qquad y_2=-\frac{a}{m}k,\qquad y_3=-y_1-y_2=\frac{u-v}{m}k,$$
其中 \(m=\gcd(a,b)\)，\(k\in\mathbb{Z}\)。由于
$$2a-b=3u,\qquad 2b-a=3v,$$
\(a\) 与 \(b\) 的公因子一定整除 \(3\)。再结合 \((u,v)\) 是原始对，可知 \(m\in\{1,3\}\)。程序真正保留下来的方向全部满足 \(m=3\)。
定义二次型范数
$$q_0=u^2+uv+v^2.$$
则 \(x\) 部分化成
$$x_1^2+x_1x_2+x_2^2=d^2q_0.$$
对 \(y\) 部分，利用 \(m=3\)、\(a=2u+v\)、\(b=u+2v\)，有
$$y_1^2+y_1y_2+y_2^2=\frac{b^2-ab+a^2}{9}k^2.$$
而
$$a^2-ab+b^2=3(u^2+uv+v^2)=3q_0,$$
所以
$$y_1^2+y_1y_2+y_2^2=\frac{q_0}{3}k^2.$$
代回校验方程得到
$$39=q_0d^2-\frac{q_0}{3}k^2=\frac{q_0}{3}(3d^2-k^2),$$
也就是
$$q_0(3d^2-k^2)=117,\qquad k^2-3d^2=-\frac{117}{q_0}.$$
这正是快速算法的核心代数结构。
上式首先说明 \(q_0\) 必须整除 \(117\)。然后代码枚举满足
$$u^2+uv+v^2=q_0,\qquad \gcd(u,v)=1,\qquad \gcd(2u+v,u+2v)=3$$
的原始整数对 \((u,v)\)。直接枚举后只剩下两类：
$$q_0=3 \quad\text{对应 6 个原始方向},\qquad q_0=39 \quad\text{对应 12 个原始方向}.$$
对于 \(q_0=117\)，不存在合法的原始方向，因此整个搜索空间缩减为固定的 \(18\) 个方向模板。这就是 build_directions 只遍历 q0 in (3, 39) 的原因。
保留下来的两类范数分别给出
$$q_0=3 \Longrightarrow k^2-3d^2=-39,\qquad q_0=39 \Longrightarrow k^2-3d^2=-3.$$
实现中使用的最小正种子为
$$ (d,k)=(4,3),(5,6)\ \text{对应 }-39,\qquad (d,k)=(2,3)\ \text{对应 }-3. $$
其余所有更大的解都可由基本单位 \(2+\sqrt{3}\) 推出，对应递推
$$k_{n+1}=2k_n+3d_n,\qquad d_{n+1}=k_n+2d_n.$$
对于固定方向 \((u,v)\)，坐标边界写成
$$x_{\mathrm{scale}}=\max(|u|,|v|,|u+v|),$$
$$y_{\mathrm{scale}}=\frac{\max(|2u+v|,|u+2v|,|u-v|)}{3},$$
所以代码只保留
$$d\le \left\lfloor\frac{N}{x_{\mathrm{scale}}}\right\rfloor,\qquad k\le \left\lfloor\frac{N}{y_{\mathrm{scale}}}\right\rfloor$$
的 Pell 解对。
把显式坐标代入行列式面积公式，二倍面积会化简为
$$2A=\left|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\right|=2q_0|dk|,$$
因此真实面积就是
$$\boxed{A=q_0|dk|}.$$
例如，取 \(q_0=3\) 家族中的原始方向 \((u,v)=(1,1)\)。用种子 \((d,k)=(4,3)\) 得到
$$ (x_1,y_1)=(4,3),\qquad (x_2,y_2)=(4,-3),\qquad (x_3,y_3)=(-8,0), $$
从而
$$A=3\cdot 4\cdot 3=36.$$
这正是 \(N=8\) 时检查值 \(72\) 中的一部分贡献。由于不同的方向或 \(k\) 符号有可能重建出同一个三角形，程序会先把三个顶点排序，再用排序后的三元组作为哈希键；若发现重复，还会额外检查面积是否一致。
三份解答文件走的是同一条流水线。build_directions 枚举 \(18\) 个原始方向模板，并计算每个模板自己的 \((d_{\max},k_{\max})\) 边界。generate_pell_pairs 为两个负右端项预生成所有所需的 Pell 解。build_triangle_key 负责恢复三个顶点、剔除越界或退化情况，并返回排序后的顶点三元组和闭式面积 \(q_0|dk|\)。
主循环对每个方向选择正确的 Pell 列表，分别尝试 \(k\) 的正负号，然后把三角形插入以排序顶点为键的哈希表。C++ 版本额外包含验证层：\(N=8,10,100,1000\) 时的检查值分别是 \(72,252,34632,3529008\)，并且还会与 solve_bruteforce_small(20) 做一次暴力交叉验证。Python 与 Java 版本使用同样的快速构造，只是没有这套检查框架。
对本题来说，方向模板数量是常数 \(18\)。每条 Pell 序列都以 \(2+\sqrt{3}\) 的倍率指数增长，因此在边界以内的 \((d,k)\) 对数对每个家族只有 \(O(\log N)\)。于是总时间复杂度与实际生成的候选数量和哈希插入次数成正比，而不再是对整张整数网格做多项式级别的暴力扫描。空间复杂度为 \(O(T)\)，其中 \(T\) 是哈希表中存储的不同三角形数量。
solutionsCpp/Euler385.cpp, solutionsPython/Euler385.py, solutionsJava/Euler385.javaЛокальный C++-валидатор показывает, что любой допустимый треугольник можно записать в центрированной форме
$$P_1=(x_1,y_1),\qquad P_2=(x_2,y_2),\qquad P_3=(-x_1-x_2,-y_1-y_2),$$
и тогда автоматически выполняется
$$x_1+x_2+x_3=0,\qquad y_1+y_2+y_3=0.$$
Геометрическое условие, связанное с эллипсом, в реализации уже сведено к системе диофантовых уравнений
$$ (2x_1+x_2)y_1 + (x_1+2x_2)y_2 = 0, $$
$$ x_1^2+x_1x_2+x_2^2 - (y_1^2+y_1y_2+y_2^2) = 39. $$
Нужно просуммировать евклидовы площади всех невырожденных целочисленных треугольников с координатами внутри \([-N,N]^2\), где реальный параметр равен \(N=10^9\). Полный перебор из solve_bruteforce_small годится только для очень малых \(N\); быстрая программа заменяет его конечным набором рекуррентных семейств типа Пелля.
Запишем
$$x_1=du,\qquad x_2=dv,\qquad x_3=-d(u+v),$$
где \(d>0\), а \(\gcd(u,v)=1\). Тогда линейное условие принимает вид
$$a y_1 + b y_2 = 0,\qquad a=2u+v,\qquad b=u+2v.$$
Все целочисленные решения этого уравнения имеют форму
$$y_1=\frac{b}{m}k,\qquad y_2=-\frac{a}{m}k,\qquad y_3=-y_1-y_2=\frac{u-v}{m}k,$$
где \(m=\gcd(a,b)\) и \(k\in\mathbb{Z}\). Поскольку
$$2a-b=3u,\qquad 2b-a=3v,$$
любой общий делитель \(a\) и \(b\) обязан делить \(3\). Из примитивности \((u,v)\) следует, что \(m\in\{1,3\}\). Для всех допустимых направлений, которые реально использует программа, получается \(m=3\).
Введем норму
$$q_0=u^2+uv+v^2.$$
Тогда \(x\)-часть становится равной
$$x_1^2+x_1x_2+x_2^2=d^2q_0.$$
Для \(y\)-части, используя \(m=3\), \(a=2u+v\) и \(b=u+2v\), получаем
$$y_1^2+y_1y_2+y_2^2=\frac{b^2-ab+a^2}{9}k^2.$$
Но
$$a^2-ab+b^2=3(u^2+uv+v^2)=3q_0,$$
значит
$$y_1^2+y_1y_2+y_2^2=\frac{q_0}{3}k^2.$$
После подстановки в проверочное уравнение имеем
$$39=q_0d^2-\frac{q_0}{3}k^2=\frac{q_0}{3}(3d^2-k^2),$$
то есть
$$q_0(3d^2-k^2)=117,\qquad k^2-3d^2=-\frac{117}{q_0}.$$
Это и есть алгебраический каркас быстрого решения.
Из предыдущей формулы видно, что \(q_0\) обязан делить \(117\). Далее код перебирает примитивные пары \((u,v)\), удовлетворяющие
$$u^2+uv+v^2=q_0,\qquad \gcd(u,v)=1,\qquad \gcd(2u+v,u+2v)=3.$$
Прямой перебор оставляет ровно два семейства норм:
$$q_0=3 \quad\text{с 6 примитивными направлениями},\qquad q_0=39 \quad\text{с 12 примитивными направлениями}.$$
Для \(q_0=117\) допустимых примитивных направлений не существует, поэтому весь поиск сжимается до \(18\) шаблонов направлений. Именно поэтому build_directions итерируется только по q0 in (3, 39).
Две оставшиеся нормы приводят к уравнениям
$$q_0=3 \Longrightarrow k^2-3d^2=-39,\qquad q_0=39 \Longrightarrow k^2-3d^2=-3.$$
В реализации используются минимальные положительные семена:
$$ (d,k)=(4,3),(5,6)\ \text{для }-39,\qquad (d,k)=(2,3)\ \text{для }-3. $$
Все следующие решения порождаются умножением на фундаментальную единицу \(2+\sqrt{3}\), что дает рекуррентные формулы
$$k_{n+1}=2k_n+3d_n,\qquad d_{n+1}=k_n+2d_n.$$
Для фиксированного направления \((u,v)\) вводятся масштабы
$$x_{\mathrm{scale}}=\max(|u|,|v|,|u+v|),$$
$$y_{\mathrm{scale}}=\frac{\max(|2u+v|,|u+2v|,|u-v|)}{3},$$
после чего код оставляет только пары с условиями
$$d\le \left\lfloor\frac{N}{x_{\mathrm{scale}}}\right\rfloor,\qquad k\le \left\lfloor\frac{N}{y_{\mathrm{scale}}}\right\rfloor.$$
Если подставить явные координаты в детерминантную формулу, удвоенная площадь упрощается до
$$2A=\left|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\right|=2q_0|dk|,$$
поэтому настоящая площадь равна
$$\boxed{A=q_0|dk|}.$$
Например, возьмем примитивное направление \((u,v)=(1,1)\) из семейства \(q_0=3\). Семя \((d,k)=(4,3)\) дает
$$ (x_1,y_1)=(4,3),\qquad (x_2,y_2)=(4,-3),\qquad (x_3,y_3)=(-8,0), $$
откуда
$$A=3\cdot 4\cdot 3=36.$$
Это один из треугольников, входящих в контрольное значение \(72\) при \(N=8\). Поскольку разные выборы направления или знака могут восстановить один и тот же треугольник, реализации сортируют три вершины и используют отсортированную тройку как ключ хеша. При совпадении дополнительно проверяется совпадение площади.
Все три файла решения реализуют одну и ту же схему. build_directions перечисляет \(18\) примитивных шаблонов направлений и вычисляет их индивидуальные границы \((d_{\max},k_{\max})\). generate_pell_pairs заранее строит все нужные решения уравнений Пелля для двух отрицательных правых частей. build_triangle_key восстанавливает вершины, отбрасывает вырожденные или выходящие за пределы случаи и возвращает отсортированную тройку вершин вместе с закрытой формулой площади \(q_0|dk|\).
Главный цикл выбирает для каждого направления правильный список Pell-пар, пробует оба знака \(k\) и вставляет треугольник в хеш-таблицу, индексированную отсортированными вершинами. В C++-версии есть дополнительная проверка: контрольные значения \(72\), \(252\), \(34632\), \(3529008\) для \(N=8,10,100,1000\), а также сверка с полным перебором solve_bruteforce_small(20). Версии на Python и Java используют ту же быструю конструкцию, но без этого блока проверок.
Для этой задачи число шаблонов направлений постоянно и равно \(18\). Каждая последовательность Пелля растет экспоненциально, потому что рекурсия фактически умножает на \(2+\sqrt{3}\), значит число релевантных пар \((d,k)\) до заданной границы равно \(O(\log N)\) на семейство. Поэтому суммарное время пропорционально числу реально сгенерированных кандидатов и вставок в хеш-таблицу, а не полиномиальному перебору узлов решетки. Память равна \(O(T)\), где \(T\) — количество различных треугольников, сохраненных в хеше.
solutionsCpp/Euler385.cpp, solutionsPython/Euler385.py, solutionsJava/Euler385.javaيبين المدقق المحلي في ++C أن كل مثلث صالح يمكن كتابته في صورة متمركزة:
$$P_1=(x_1,y_1),\qquad P_2=(x_2,y_2),\qquad P_3=(-x_1-x_2,-y_1-y_2),$$
ومن ثم نحصل مباشرة على
$$x_1+x_2+x_3=0,\qquad y_1+y_2+y_3=0.$$
الشرط الهندسي المرتبط بالقطع الناقص حُوِّل داخل التنفيذ إلى النظام الديوفانتي التالي:
$$ (2x_1+x_2)y_1 + (x_1+2x_2)y_2 = 0, $$
$$ x_1^2+x_1x_2+x_2^2 - (y_1^2+y_1y_2+y_2^2) = 39. $$
المطلوب هو جمع المساحات الإقليدية لكل المثلثات الصحيحة غير المنحلة التي تقع إحداثياتها داخل \([-N,N]^2\)، وذلك للحالة الفعلية \(N=10^9\). البحث العنيف الموجود في solve_bruteforce_small لا يصلح إلا للقيم الصغيرة جدًا من \(N\)، لذلك يعيد الحل السريع صياغة المسألة على شكل عدد محدود من متتاليات شبيهة بمعادلات Pell.
نكتب
$$x_1=du,\qquad x_2=dv,\qquad x_3=-d(u+v),$$
حيث \(d>0\) و \(\gcd(u,v)=1\). عندئذ يصبح الشرط الخطي
$$a y_1 + b y_2 = 0,\qquad a=2u+v,\qquad b=u+2v.$$
وكل الحلول الصحيحة لهذا الشرط تُكتب على الصورة
$$y_1=\frac{b}{m}k,\qquad y_2=-\frac{a}{m}k,\qquad y_3=-y_1-y_2=\frac{u-v}{m}k,$$
حيث \(m=\gcd(a,b)\) و \(k\in\mathbb{Z}\). وبسبب
$$2a-b=3u,\qquad 2b-a=3v,$$
فإن أي قاسم مشترك لـ \(a\) و \(b\) يجب أن يقسم \(3\). ومع بدائية الزوج \((u,v)\) نحصل على \(m\in\{1,3\}\). جميع الاتجاهات البدائية التي يحتفظ بها البرنامج تحقق في النهاية \(m=3\).
نعرف الكمية
$$q_0=u^2+uv+v^2.$$
عندها يصبح الجزء الخاص بـ \(x\)
$$x_1^2+x_1x_2+x_2^2=d^2q_0.$$
أما الجزء الخاص بـ \(y\)، ومع استخدام \(m=3\) و \(a=2u+v\) و \(b=u+2v\)، فيعطي
$$y_1^2+y_1y_2+y_2^2=\frac{b^2-ab+a^2}{9}k^2.$$
ولدينا أيضًا
$$a^2-ab+b^2=3(u^2+uv+v^2)=3q_0,$$
ومن ثم
$$y_1^2+y_1y_2+y_2^2=\frac{q_0}{3}k^2.$$
بالتعويض في معادلة التحقق نحصل على
$$39=q_0d^2-\frac{q_0}{3}k^2=\frac{q_0}{3}(3d^2-k^2),$$
أي
$$q_0(3d^2-k^2)=117,\qquad k^2-3d^2=-\frac{117}{q_0}.$$
وهذه هي البنية الجبرية الأساسية التي يبني عليها الحل السريع.
تُظهر المعادلة السابقة أن \(q_0\) يجب أن يقسم \(117\). بعد ذلك يعدِّد الكود الأزواج البدائية \((u,v)\) التي تحقق
$$u^2+uv+v^2=q_0,\qquad \gcd(u,v)=1,\qquad \gcd(2u+v,u+2v)=3.$$
هذا التعداد يترك عائلتين فقط:
\(q_0=3\) وفيها 6 اتجاهات بدائية، و\(q_0=39\) وفيها 12 اتجاهًا بدائيًا.
لا يوجد أي اتجاه بدائي صالح عندما \(q_0=117\)، ولذلك ينهار فضاء البحث كله إلى \(18\) قالب اتجاه فقط. ولهذا يدور build_directions على q0 in (3, 39) لا غير.
العائلتان الباقيتان تعطيان
$$q_0=3 \Longrightarrow k^2-3d^2=-39,\qquad q_0=39 \Longrightarrow k^2-3d^2=-3.$$
ويستعمل التنفيذ أصغر البذور الموجبة:
\((d,k)=(4,3)\) و\((d,k)=(5,6)\) للمعادلة \(-39\)، بينما \((d,k)=(2,3)\) للمعادلة \(-3\).
كل الحلول الأكبر تُولد بضربها في الوحدة الأساسية \(2+\sqrt{3}\)، وهذا يؤدي إلى التكرار
$$k_{n+1}=2k_n+3d_n,\qquad d_{n+1}=k_n+2d_n.$$
ولكل اتجاه ثابت \((u,v)\) تُحسب الحدود من خلال
$$x_{\mathrm{scale}}=\max(|u|,|v|,|u+v|),$$
$$y_{\mathrm{scale}}=\frac{\max(|2u+v|,|u+2v|,|u-v|)}{3},$$
ومن ثم لا يحتفظ الكود إلا بالأزواج التي تحقق
$$d\le \left\lfloor\frac{N}{x_{\mathrm{scale}}}\right\rfloor,\qquad k\le \left\lfloor\frac{N}{y_{\mathrm{scale}}}\right\rfloor.$$
عند التعويض في صيغة المساحة بالمحدد نحصل على
$$2A=\left|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\right|=2q_0|dk|,$$
وبالتالي تكون المساحة الحقيقية
$$\boxed{A=q_0|dk|}.$$
على سبيل المثال، إذا أخذنا الاتجاه البدائي \((u,v)=(1,1)\) من عائلة \(q_0=3\)، ثم استعملنا البذرة \((d,k)=(4,3)\)، فإننا نحصل على
$$ (x_1,y_1)=(4,3),\qquad (x_2,y_2)=(4,-3),\qquad (x_3,y_3)=(-8,0), $$
ومن ثم
$$A=3\cdot 4\cdot 3=36.$$
وهذا أحد المثلثات الداخلة في قيمة التحقق \(72\) عند \(N=8\). وبما أن اختيارات مختلفة للاتجاه أو لإشارة \(k\) قد تعيد بناء المثلث نفسه، فإن التنفيذ يرتب الرؤوس الثلاثة ثم يستخدم الثلاثية المرتبة كمفتاح hash. وإذا ظهر مثلث مكرر فإن الكود يتحقق أيضًا من تطابق المساحة.
الملفات الثلاثة تتبع المسار نفسه. تقوم build_directions بتعداد قوالب الاتجاه البدائية الثمانية عشر وحساب الحدود الخاصة بكل قالب \((d_{\max},k_{\max})\). ثم تقوم generate_pell_pairs بإنتاج جميع حلول Pell المطلوبة للطرفين السالبين. بعد ذلك تعيد build_triangle_key بناء الرؤوس الثلاثة، وتستبعد الحالات المنحلة أو الخارجة عن الحدود، ثم تعيد الثلاثية المرتبة للرؤوس مع المساحة المغلقة \(q_0|dk|\).
في الحلقة الرئيسية يختار البرنامج قائمة Pell المناسبة لكل اتجاه، ويجرب الإشارتين الممكنتين لـ \(k\)، ثم يضيف المثلث إلى جدول hash مفهرس بالرؤوس المرتبة. إصدار ++C يضيف طبقة تحقق إضافية: القيم المرجعية \(72\)، \(252\)، \(34632\)، \(3529008\) عند \(N=8,10,100,1000\)، بالإضافة إلى مقارنة مباشرة مع solve_bruteforce_small(20). أما نسختا Python وJava فتطبقان البناء السريع نفسه من دون إطار التحقق هذا.
في هذه المسألة عدد قوالب الاتجاه ثابت ويساوي \(18\). كل متتالية Pell تنمو أسيًا لأن التكرار يعادل الضرب في \(2+\sqrt{3}\)، ولذلك فإن عدد الأزواج \((d,k)\) الواقعة تحت الحد يساوي \(O(\log N)\) لكل عائلة. وعليه فإن الزمن الكلي يتناسب مع عدد المرشحين الذين يولدهم البرنامج فعليًا وعدد عمليات الإدراج في جدول hash، بدلًا من مسح كثير حدودي لشبكة الإحداثيات. أما الذاكرة فهي \(O(T)\)، حيث \(T\) هو عدد المثلثات المختلفة المخزنة في الجدول.
solutionsCpp/Euler385.cpp, solutionsPython/Euler385.py, solutionsJava/Euler385.java