Let \(T\) be the Torricelli point of a triangle \(ABC\), and write \(p=TA\), \(q=TB\), \(r=TC\). The problem asks for the sum of all distinct values of \(p+q+r\) with \(p+q+r \le 120{,}000\), under the condition that \(p\), \(q\), and \(r\) are integers and that the three side lengths of the triangle are integers as well.
The decisive fact is that the three angles at \(T\) are all \(120^\circ\). That turns the geometry into an arithmetic question about when expressions of the form \(x^2+xy+y^2\) are perfect squares. The implementations exploit that arithmetic structure directly and never need to reconstruct coordinates.
Write the triangle sides as \(a=BC\), \(b=CA\), and \(c=AB\). Since the angles \(\angle ATB\), \(\angle BTC\), and \(\angle CTA\) are each \(120^\circ\), every side length is determined by a cosine-law identity.
Applying the law of cosines with \(\cos 120^\circ=-\tfrac12\) gives
$$a^2=q^2+qr+r^2,\qquad b^2=r^2+rp+p^2,\qquad c^2=p^2+pq+q^2.$$
So a triple \((p,q,r)\) is admissible exactly when all three quadratic forms
$$p^2+pq+q^2,\qquad q^2+qr+r^2,\qquad r^2+rp+p^2$$
are perfect squares. Once this happens, the corresponding triangle sides are integers, and the point with three \(120^\circ\) rays is precisely the Torricelli configuration described in the problem.
Call two positive integers \(x\) and \(y\) compatible if
$$x^2+xy+y^2=z^2$$
for some integer \(z\). Geometrically, \(x\) and \(y\) can then appear as two Torricelli distances meeting at \(120^\circ\), and \(z\) is the opposite triangle side. The full problem is therefore not about arbitrary triples first; it is about finding three distances that are pairwise compatible.
That observation turns the search into a graph problem. Take the integers \(1,2,\dots,N\) with \(N=120{,}000\) as vertices, and join \(x\) and \(y\) by an edge whenever they are compatible. Then every valid \((p,q,r)\) is exactly a 3-clique in this graph, because all three pairwise square conditions must hold simultaneously.
The optimized implementations do not test every pair \((x,y)\) from scratch. They use the standard parametrization of primitive solutions of
$$x^2+xy+y^2=z^2,$$
namely, up to swapping \(x\) and \(y\),
$$x_0=m^2-n^2,\qquad y_0=n(2m+n),\qquad z_0=m^2+mn+n^2,$$
with
$$m>n>0,\qquad \gcd(m,n)=1,\qquad m-n\not\equiv 0 \pmod 3.$$
Every non-primitive compatible pair is then just a multiple \((kx_0,ky_0)\). This is why the fast versions loop over \((m,n)\), generate primitive seeds, and then scale them by \(k\) until the limit is reached. The side length \(z\) never needs to be stored, because the existence of an edge is all that matters later.
Suppose \(p<q<r\). In graph language, \((p,q,r)\) is valid exactly when \(q\) and \(r\) are both neighbors of \(p\), and \(r\) is also a neighbor of \(q\). So after building sorted adjacency lists, one can fix \(p\), choose \(q>p\) among the neighbors of \(p\), and then look for common neighbors of \(p\) and \(q\) that are larger than \(q\). Intersecting the two sorted tails finds precisely those \(r\).
This ordered search has two important invariants. First, \(p<q<r\) prevents the same triple from being generated in six different permutations. Second, the problem asks for distinct sums \(p+q+r\), not distinct triples, so the final sums are inserted into a set before being added together. Two different triples may contribute the same perimeter, and that perimeter must be counted once.
A concrete solution is
$$ (p,q,r)=(195,264,325). $$
Indeed,
$$195^2+195\cdot264+264^2=399^2,$$
$$195^2+195\cdot325+325^2=455^2,$$
$$264^2+264\cdot325+325^2=511^2.$$
So the three sides of the triangle are \(399\), \(455\), and \(511\), all integral, and the corresponding Torricelli-distance sum is
$$195+264+325=784.$$
This is the small example used by the implementations as a sanity check before attacking the full limit.
The C++, Python, and Java implementations all work with the same graph of compatible distance pairs. The optimized C++ and Python versions build that graph from the parametrization above, adding each generated pair to both adjacency lists because compatibility is symmetric. After generation, each list is sorted and deduplicated so that later intersections are linear scans over ordered data.
Once the graph exists, the next phase is to enumerate every ordered triple \(p<q<r\) that forms a clique. For a fixed \(p\), the implementation scans its neighbors \(q\) with \(q>p\). Any admissible \(r\) must be a common neighbor of \(p\) and \(q\) and must also satisfy \(r>q\). The sorted-list intersection enforces all of that at once, and whenever \(p+q+r \le 120{,}000\), the sum is recorded.
The Java implementation illustrates the same mathematics in a more direct style. Instead of generating compatible pairs from the parametrization, it checks every \(p<q\) with \(p+q \le N\), tests whether \(p^2+pq+q^2\) is a square, stores the successful pairs, and then searches for common neighbors to complete triangles. That approach is conceptually simple but spends much more time on failed pair tests. The C++ and Python implementations avoid most of that work by generating only genuine compatible pairs from the start.
Let \(E\) be the number of compatible pairs up to the limit \(N\). The optimized construction spends \(O(E)\) time generating scaled pairs from primitive seeds, plus the cost of sorting the adjacency lists, plus the cost of all ordered list intersections used to enumerate cliques. A conservative worst-case bound is still quadratic in \(N\), but the arithmetic graph is sparse enough that the full limit is practical.
The direct construction used in the Java version performs \(O(N^2)\) pair tests just to build the graph, and only afterward begins the common-neighbor search. All versions use \(O(E)\) memory for the adjacency structure, together with a set of distinct perimeter sums. The main speedup comes from replacing a naive search over triples of distances with a search over edges and their common neighbors.
Sei \(T\) der Torricelli-Punkt eines Dreiecks \(ABC\), und setze \(p=TA\), \(q=TB\), \(r=TC\). Gesucht ist die Summe aller verschiedenen Werte von \(p+q+r\) mit \(p+q+r \le 120{,}000\), wobei \(p\), \(q\) und \(r\) ganze Zahlen sind und zugleich auch die drei Seitenlängen des Dreiecks ganzzahlig sein müssen.
Die Schlüsselform ist, dass die drei Winkel bei \(T\) alle \(120^\circ\) betragen. Dadurch wird die Geometrie zu einer Zahlentheorie-Aufgabe über die Frage, wann Ausdrücke der Form \(x^2+xy+y^2\) Quadratzahlen sind. Genau diese Struktur wird von den Implementierungen ausgenutzt.
Bezeichne die Dreiecksseiten mit \(a=BC\), \(b=CA\) und \(c=AB\). Weil die Winkel \(\angle ATB\), \(\angle BTC\) und \(\angle CTA\) jeweils \(120^\circ\) sind, folgt jede Seitenlänge direkt aus dem Kosinussatz.
Mit dem Kosinussatz und \(\cos 120^\circ=-\tfrac12\) erhält man
$$a^2=q^2+qr+r^2,\qquad b^2=r^2+rp+p^2,\qquad c^2=p^2+pq+q^2.$$
Ein Tripel \((p,q,r)\) ist also genau dann zulässig, wenn die drei quadratischen Formen
$$p^2+pq+q^2,\qquad q^2+qr+r^2,\qquad r^2+rp+p^2$$
allesamt Quadratzahlen sind. Sobald das gilt, sind die drei Seiten ganzzahlig, und die durch drei \(120^\circ\)-Strahlen gegebene Konfiguration ist genau die im Problem verlangte Torricelli-Situation.
Nenne zwei positive ganze Zahlen \(x\) und \(y\) kompatibel, wenn
$$x^2+xy+y^2=z^2$$
für eine ganze Zahl \(z\) gilt. Geometrisch können \(x\) und \(y\) dann als zwei Torricelli-Abstände auftreten, die einen Winkel von \(120^\circ\) einschließen, und \(z\) ist die gegenüberliegende Dreiecksseite. Das Gesamtproblem beginnt also nicht mit beliebigen Dreiergruppen, sondern mit der Suche nach drei paarweise kompatiblen Distanzen.
Damit wird die Suche zu einem Graphenproblem. Die Zahlen \(1,2,\dots,N\) mit \(N=120{,}000\) sind die Knoten, und zwischen \(x\) und \(y\) wird eine Kante gezogen, wenn sie kompatibel sind. Ein gültiges \((p,q,r)\) ist dann exakt eine 3-Klique in diesem Graphen, denn alle drei Paarbedingungen müssen gleichzeitig erfüllt sein.
Die optimierten Implementierungen testen nicht jedes Paar \((x,y)\) einzeln. Sie verwenden die Standardparametrisierung primitiver Lösungen von
$$x^2+xy+y^2=z^2,$$
nämlich bis auf Vertauschung von \(x\) und \(y\)
$$x_0=m^2-n^2,\qquad y_0=n(2m+n),\qquad z_0=m^2+mn+n^2,$$
unter den Bedingungen
$$m>n>0,\qquad \gcd(m,n)=1,\qquad m-n\not\equiv 0 \pmod 3.$$
Jedes nichtprimitive kompatible Paar ist dann einfach ein Vielfaches \((kx_0,ky_0)\). Deshalb laufen die schnellen Versionen über \((m,n)\), erzeugen primitive Startpaare und skalieren diese mit \(k\), bis die Schranke erreicht ist. Die Seitenlänge \(z\) muss später gar nicht gespeichert werden; entscheidend ist nur, dass die Kante existiert.
Angenommen \(p<q<r\). In Graphensprache ist \((p,q,r)\) genau dann gültig, wenn \(q\) und \(r\) Nachbarn von \(p\) sind und \(r\) außerdem Nachbar von \(q\) ist. Nach dem Aufbau sortierter Adjazenzlisten kann man also \(p\) festhalten, ein \(q>p\) aus den Nachbarn von \(p\) wählen und dann gemeinsame Nachbarn von \(p\) und \(q\) suchen, die größer als \(q\) sind. Der Schnitt der beiden sortierten Listenenden liefert genau diese \(r\).
Diese geordnete Suche hat zwei wichtige Invarianten. Erstens verhindert \(p<q<r\), dass dasselbe Tripel in sechs Permutationen erneut auftaucht. Zweitens verlangt das Problem verschiedene Summen \(p+q+r\), nicht verschiedene Tripel. Deshalb werden die gefundenen Summen in einer Menge gesammelt, bevor sie addiert werden. Verschiedene Tripel können denselben Umfang liefern, und dieser darf nur einmal zählen.
Ein konkretes Beispiel ist
$$ (p,q,r)=(195,264,325). $$
Denn es gilt
$$195^2+195\cdot264+264^2=399^2,$$
$$195^2+195\cdot325+325^2=455^2,$$
$$264^2+264\cdot325+325^2=511^2.$$
Die Dreiecksseiten sind also \(399\), \(455\) und \(511\), alle ganzzahlig, und die Summe der Torricelli-Abstände ist
$$195+264+325=784.$$
Genau dieses kleine Beispiel wird in den Implementierungen als Plausibilitätskontrolle verwendet, bevor die volle Schranke bearbeitet wird.
Die C++-, Python- und Java-Implementierungen arbeiten alle mit demselben Graphen kompatibler Distanzpaare. Die optimierten C++- und Python-Versionen erzeugen diesen Graphen aus der Parametrisierung oben und tragen jedes Paar in beide Adjazenzlisten ein, weil Kompatibilität symmetrisch ist. Anschließend werden die Listen sortiert und dedupliziert, sodass spätere Schnitte als lineare Durchläufe über geordnete Daten ausgeführt werden können.
Sobald der Graph vorliegt, werden alle geordneten Tripel \(p<q<r\) gesucht, die eine Klique bilden. Für festes \(p\) durchläuft die Implementierung die Nachbarn \(q\) mit \(q>p\). Ein zulässiges \(r\) muss gemeinsamer Nachbar von \(p\) und \(q\) sein und zugleich \(r>q\) erfüllen. Der Schnitt der sortierten Listen erzwingt all das in einem Schritt, und wenn zusätzlich \(p+q+r \le 120{,}000\) gilt, wird die Summe gespeichert.
Die Java-Implementierung zeigt dieselbe Mathematik in direkterer Form. Statt kompatible Paare aus der Parametrisierung zu erzeugen, prüft sie jedes \(p<q\) mit \(p+q \le N\), testet, ob \(p^2+pq+q^2\) eine Quadratzahl ist, speichert die erfolgreichen Paare und sucht danach gemeinsame Nachbarn, um Dreiecke zu schließen. Das ist konzeptionell einfach, verbringt aber deutlich mehr Zeit mit erfolglosen Paarprüfungen. Die C++- und Python-Implementierungen vermeiden den größten Teil dieser Arbeit, indem sie von Anfang an nur echte kompatible Paare erzeugen.
Sei \(E\) die Anzahl kompatibler Paare bis zur Grenze \(N\). Der optimierte Aufbau benötigt \(O(E)\) Zeit zum Erzeugen skalierter Paare aus primitiven Startlösungen, dazu die Sortierkosten für die Adjazenzlisten und die Kosten aller Listenschnitte, mit denen die Kliquen aufgezählt werden. Eine grobe Worst-Case-Schranke bleibt zwar quadratisch in \(N\), aber der arithmetische Graph ist so dünn, dass die volle Grenze praktisch erreichbar ist.
Der direkte Aufbau in der Java-Version führt bereits \(O(N^2)\) Paarprüfungen aus, nur um den Graphen zu konstruieren, und startet erst danach die Suche nach gemeinsamen Nachbarn. Alle Versionen benötigen \(O(E)\) Speicher für die Adjazenzstruktur sowie eine Menge der verschiedenen Umfangssummen. Der eigentliche Gewinn entsteht dadurch, dass die naive Suche über Dreiergruppen von Distanzen durch eine Suche über Kanten und deren gemeinsame Nachbarn ersetzt wird.
\(T\), \(ABC\) üçgeninin Torricelli noktası olsun ve \(p=TA\), \(q=TB\), \(r=TC\) yazalım. İstenen şey, \(p+q+r \le 120{,}000\) koşulunu sağlayan tüm farklı \(p+q+r\) değerlerinin toplamıdır; burada \(p\), \(q\), \(r\) tamsayıdır ve üçgenin üç kenarı da tamsayı uzunluklara sahiptir.
Belirleyici özellik, \(T\) noktasındaki üç açının da \(120^\circ\) olmasıdır. Bu bilgi geometriyi, \(x^2+xy+y^2\) biçimindeki ifadelerin ne zaman tam kare olduğuna dair bir aritmetik soruya çevirir. Uygulamalar da üçgeni koordinatlarla kurmak yerine doğrudan bu aritmetik yapıyı kullanır.
Üçgen kenarlarını \(a=BC\), \(b=CA\) ve \(c=AB\) ile gösterelim. \(\angle ATB\), \(\angle BTC\) ve \(\angle CTA\) açılarının her biri \(120^\circ\) olduğundan, her kenar uzunluğu kosinüs teoremiyle elde edilir.
\(\cos 120^\circ=-\tfrac12\) kullanılarak kosinüs teoremi uygulanırsa
$$a^2=q^2+qr+r^2,\qquad b^2=r^2+rp+p^2,\qquad c^2=p^2+pq+q^2$$
elde edilir. Dolayısıyla bir \((p,q,r)\) üçlüsü ancak ve ancak şu üç ifade de tam kare ise geçerlidir:
$$p^2+pq+q^2,\qquad q^2+qr+r^2,\qquad r^2+rp+p^2.$$
Bu sağlandığında üçgenin tüm kenarları tam sayı olur ve üç adet \(120^\circ\) ışınla tanımlanan nokta tam olarak sorudaki Torricelli konfigürasyonunu verir.
İki pozitif tamsayı \(x\) ve \(y\) için
$$x^2+xy+y^2=z^2$$
eşitliğini sağlayan bir tamsayı \(z\) varsa bu iki sayıya uyumlu diyelim. Geometrik olarak böyle bir çift, aralarındaki açı \(120^\circ\) olan iki Torricelli mesafesi olabilir; \(z\) de bu iki kenarın karşısındaki üçgen kenarıdır. Bu yüzden asıl problem, önce keyfi üçlüler aramak değil, birbirleriyle ikili olarak uyumlu üç uzaklık bulmaktır.
Böyle bakınca problem bir graf problemine dönüşür. \(N=120{,}000\) için \(1,2,\dots,N\) sayıları düğüm olsun; \(x\) ile \(y\) uyumluysa aralarına bir kenar çizelim. O zaman geçerli her \((p,q,r)\), bu grafın tam bir 3-kliğidir; çünkü üç ikili koşulun da aynı anda sağlanması gerekir.
Hızlı uygulamalar her \((x,y)\) çiftini tek tek denemez. Bunun yerine
$$x^2+xy+y^2=z^2$$
denkleminin asal çözümleri için standart parametrelemeyi kullanır. \(x\) ile \(y\) yer değiştirmesi dışında
$$x_0=m^2-n^2,\qquad y_0=n(2m+n),\qquad z_0=m^2+mn+n^2,$$
ve şu koşullar geçerlidir:
$$m>n>0,\qquad \gcd(m,n)=1,\qquad m-n\not\equiv 0 \pmod 3.$$
Asal olmayan her uyumlu çift de yalnızca \((kx_0,ky_0)\) biçimindeki bir kattır. Bu nedenle hızlı sürümler \((m,n)\) üzerinde dolaşır, asal tohum çiftleri üretir ve limit dolana kadar bunları \(k\) ile çarpar. Karşı kenar uzunluğu olan \(z\) daha sonra kullanılmadığı için saklanmaz; önemli olan yalnızca iki sayı arasında gerçekten bir kenar bulunmasıdır.
\(p<q<r\) olduğunu varsayalım. Graf dilinde \((p,q,r)\) ancak ve ancak \(q\) ile \(r\), \(p\)'nin komşusuysa ve \(r\) aynı zamanda \(q\)'nun da komşusuysa geçerlidir. Bu yüzden sıralı komşuluk listeleri kurulduktan sonra \(p\) sabitlenir, \(p\)'nin komşuları içinden \(q>p\) seçilir ve hem \(p\)'ye hem \(q\)'ya komşu olan, ayrıca \(q\)'dan büyük olan ortak düğümler aranır. İki sıralı kuyruğun kesişimi tam olarak bu \(r\) değerlerini verir.
Bu düzenli aramanın iki önemli invarianti vardır. Birincisi, \(p<q<r\) şartı aynı üçlünün altı farklı permütasyonla tekrar üretilmesini engeller. İkincisi, soru farklı üçlüleri değil, farklı \(p+q+r\) toplamlarını ister. Bu yüzden bulunan toplamlar önce bir kümeye eklenir, sonra toplanır. Farklı üçlüler aynı toplamı verebilir ve bu toplam yalnızca bir kez sayılmalıdır.
Somut bir çözüm
$$ (p,q,r)=(195,264,325) $$
şeklindedir. Gerçekten de
$$195^2+195\cdot264+264^2=399^2,$$
$$195^2+195\cdot325+325^2=455^2,$$
$$264^2+264\cdot325+325^2=511^2.$$
Buna göre üçgenin kenarları \(399\), \(455\) ve \(511\) olur; hepsi tamsayıdır. Torricelli mesafelerinin toplamı da
$$195+264+325=784$$
eder. Uygulamalar tam limite geçmeden önce bu küçük örneği bir sağlamlık kontrolü olarak kullanır.
C++, Python ve Java uygulamalarının ortak noktası, uyumlu uzaklık çiftlerinden oluşan aynı graf üzerinde çalışmalarıdır. Optimize edilmiş C++ ve Python sürümleri bu grafı yukarıdaki parametrelemeden üretir; uyumluluk simetrik olduğu için her çift her iki komşuluk listesine de eklenir. Üretim bittikten sonra listeler sıralanır ve tekrarlar temizlenir; böylece sonraki kesişim işlemleri sıralı veriler üzerinde doğrusal taramalar hâline gelir.
Graf hazır olduktan sonra sıra \(p<q<r\) biçimindeki tüm klikleri bulmaya gelir. Sabit bir \(p\) için uygulama, komşular içindeki \(q>p\) değerlerini tarar. Geçerli bir \(r\), hem \(p\)'nin hem \(q\)'nun komşusu olmalı ve ayrıca \(r>q\) koşulunu sağlamalıdır. Sıralı liste kesişimi tüm bu koşulları tek adımda uygular; eğer ayrıca \(p+q+r \le 120{,}000\) ise bu toplam kaydedilir.
Java uygulaması aynı matematiği daha doğrudan bir biçimde gösterir. Parametrelemeden gerçek uyumlu çiftleri üretmek yerine, \(p+q \le N\) koşulunu sağlayan her \(p<q\) çifti için \(p^2+pq+q^2\) ifadesinin tam kare olup olmadığını sınar; başarılı çiftleri saklar ve sonra üçgenleri kapatmak için ortak komşuları arar. Kavramsal olarak daha basittir, fakat başarısız çift denemelerine çok daha fazla zaman harcar. C++ ve Python sürümleri ise baştan yalnızca gerçek uyumlu çiftleri üreterek bu yükün büyük kısmını ortadan kaldırır.
\(E\), limit \(N\) altındaki uyumlu çift sayısı olsun. Optimize edilmiş kurulum, asal tohumlardan ölçeklenmiş çiftleri üretmek için \(O(E)\) zaman harcar; buna komşuluk listelerini sıralama maliyeti ve klikleri bulmak için yapılan tüm sıralı kesişimlerin maliyeti eklenir. Kaba bir üst sınır yine \(N\)'de karesel kalabilir, ancak aritmetik graf yeterince seyrek olduğu için tam sınır pratikte çalıştırılabilir.
Java sürümündeki doğrudan kurulum ise grafı oluşturabilmek için daha baştan \(O(N^2)\) adet çift testi yapar ve ortak komşu aramasına ancak bundan sonra geçer. Tüm sürümlerde bellek kullanımı, komşuluk yapısı için \(O(E)\) ve farklı çevre toplamlarını tutan küme için ek alandır. Asıl hız kazancı, uzaklık üçlüleri üzerinde kör arama yapmak yerine kenarlar ve onların ortak komşuları üzerinden arama yapmaktan gelir.
Sea \(T\) el punto de Torricelli de un triángulo \(ABC\), y escribamos \(p=TA\), \(q=TB\), \(r=TC\). Hay que sumar todos los valores distintos de \(p+q+r\) con \(p+q+r \le 120{,}000\), bajo la condición de que \(p\), \(q\) y \(r\) sean enteros y de que las tres longitudes de los lados del triángulo también sean enteras.
La clave es que los tres ángulos en \(T\) valen \(120^\circ\). Eso transforma la geometría en una pregunta aritmética sobre cuándo expresiones del tipo \(x^2+xy+y^2\) son cuadrados perfectos. Las implementaciones explotan precisamente esa estructura y no necesitan reconstruir el triángulo mediante coordenadas.
Denotemos los lados del triángulo por \(a=BC\), \(b=CA\) y \(c=AB\). Como \(\angle ATB\), \(\angle BTC\) y \(\angle CTA\) son todos \(120^\circ\), cada lado se obtiene mediante la ley de cosenos.
Aplicando la ley de cosenos con \(\cos 120^\circ=-\tfrac12\), se obtiene
$$a^2=q^2+qr+r^2,\qquad b^2=r^2+rp+p^2,\qquad c^2=p^2+pq+q^2.$$
Por tanto, un triple \((p,q,r)\) es válido exactamente cuando las tres formas cuadráticas
$$p^2+pq+q^2,\qquad q^2+qr+r^2,\qquad r^2+rp+p^2$$
son cuadrados perfectos. Cuando eso ocurre, los tres lados del triángulo son enteros y la configuración de tres rayos con \(120^\circ\) entre sí es justamente la situación de Torricelli pedida en el problema.
Llamemos compatibles a dos enteros positivos \(x\) e \(y\) si existe un entero \(z\) tal que
$$x^2+xy+y^2=z^2.$$
Geométricamente, \(x\) e \(y\) pueden entonces aparecer como dos distancias desde el punto de Torricelli que forman un ángulo de \(120^\circ\), y \(z\) es el lado opuesto del triángulo. Así, el problema completo no consiste primero en buscar ternas arbitrarias, sino en encontrar tres distancias compatibles por pares.
Esto convierte la búsqueda en un problema de grafos. Tomamos como vértices los enteros \(1,2,\dots,N\) con \(N=120{,}000\), y unimos \(x\) con \(y\) mediante una arista cuando son compatibles. Entonces cada triple válido \((p,q,r)\) es exactamente un 3-clique de ese grafo, porque las tres condiciones de cuadrado perfecto deben cumplirse a la vez.
Las implementaciones optimizadas no prueban todos los pares \((x,y)\) desde cero. Utilizan la parametrización estándar de las soluciones primitivas de
$$x^2+xy+y^2=z^2,$$
que, salvo intercambio de \(x\) e \(y\), es
$$x_0=m^2-n^2,\qquad y_0=n(2m+n),\qquad z_0=m^2+mn+n^2,$$
con las condiciones
$$m>n>0,\qquad \gcd(m,n)=1,\qquad m-n\not\equiv 0 \pmod 3.$$
Todo par compatible no primitivo es simplemente un múltiplo \((kx_0,ky_0)\). Por eso las versiones rápidas recorren \((m,n)\), generan semillas primitivas y luego las escalan con \(k\) hasta alcanzar el límite. La longitud \(z\) ni siquiera necesita almacenarse después, porque lo único importante es saber que existe la arista entre esos dos valores.
Supongamos \(p<q<r\). En el lenguaje del grafo, \((p,q,r)\) es válido exactamente cuando \(q\) y \(r\) son vecinos de \(p\), y \(r\) también es vecino de \(q\). Así, una vez construidas listas de adyacencia ordenadas, se fija \(p\), se elige un vecino \(q>p\) y se buscan los vecinos comunes de \(p\) y \(q\) que además sean mayores que \(q\). La intersección de las dos colas ordenadas produce precisamente esos valores \(r\).
Esta búsqueda ordenada mantiene dos invariantes importantes. Primero, la condición \(p<q<r\) evita generar la misma terna en seis permutaciones distintas. Segundo, el problema pide sumas distintas \(p+q+r\), no ternas distintas. Por eso los valores encontrados se guardan en un conjunto antes de sumarse. Dos ternas diferentes pueden producir el mismo perímetro, y ese perímetro debe contarse una sola vez.
Una solución concreta es
$$ (p,q,r)=(195,264,325). $$
En efecto,
$$195^2+195\cdot264+264^2=399^2,$$
$$195^2+195\cdot325+325^2=455^2,$$
$$264^2+264\cdot325+325^2=511^2.$$
Así, los tres lados del triángulo son \(399\), \(455\) y \(511\), todos enteros, y la suma de distancias al punto de Torricelli es
$$195+264+325=784.$$
Ese es el pequeño ejemplo que las implementaciones usan como comprobación antes de atacar el límite completo.
Las implementaciones en C++, Python y Java trabajan todas con el mismo grafo de pares compatibles. Las versiones optimizadas en C++ y Python lo construyen a partir de la parametrización anterior, añadiendo cada par a las dos listas de adyacencia porque la compatibilidad es simétrica. Después, cada lista se ordena y se depura de repetidos para que las intersecciones posteriores sean recorridos lineales sobre datos ordenados.
Una vez construido el grafo, la fase siguiente consiste en enumerar todas las ternas ordenadas \(p<q<r\) que forman un clique. Para un \(p\) fijo, la implementación recorre sus vecinos \(q\) con \(q>p\). Un valor \(r\) válido debe ser vecino común de \(p\) y \(q\), y además cumplir \(r>q\). La intersección de las listas ordenadas impone todo eso de una vez; si además \(p+q+r \le 120{,}000\), la suma se registra.
La implementación en Java muestra la misma matemática de forma más directa. En lugar de generar pares compatibles desde la parametrización, examina cada \(p<q\) con \(p+q \le N\), comprueba si \(p^2+pq+q^2\) es un cuadrado, guarda los pares exitosos y luego busca vecinos comunes para cerrar triángulos. Es una idea más simple, pero dedica mucho más tiempo a pruebas fallidas. Las versiones en C++ y Python evitan la mayor parte de ese trabajo generando solo pares realmente compatibles desde el principio.
Sea \(E\) el número de pares compatibles hasta el límite \(N\). La construcción optimizada invierte \(O(E)\) tiempo en generar pares escalados a partir de semillas primitivas, más el coste de ordenar las listas de adyacencia y el de todas las intersecciones ordenadas utilizadas para enumerar cliques. Una cota conservadora sigue siendo cuadrática en \(N\), pero el grafo aritmético es lo bastante disperso como para que el límite completo resulte práctico.
La construcción directa usada en Java realiza \(O(N^2)\) pruebas de pares simplemente para formar el grafo, y solo después inicia la búsqueda de vecinos comunes. Todas las versiones consumen \(O(E)\) memoria para la estructura de adyacencia, además del conjunto de perímetros distintos. La verdadera mejora consiste en reemplazar una búsqueda ingenua sobre ternas de distancias por una búsqueda sobre aristas y sus vecinos comunes.
设 \(T\) 是三角形 \(ABC\) 的托里拆利点，记 \(p=TA\)、\(q=TB\)、\(r=TC\)。题目要求把所有不同的 \(p+q+r\) 求和，其中 \(p+q+r \le 120{,}000\)，并且 \(p\)、\(q\)、\(r\) 都是整数，三角形的三条边长也都必须是整数。
核心事实是 \(T\) 点处的三条夹角全部等于 \(120^\circ\)。这会把几何条件转化为一个纯粹的算术条件：形如 \(x^2+xy+y^2\) 的表达式何时是完全平方数。实现真正利用的就是这层结构，而不是去显式构造坐标。
把三角形三边记作 \(a=BC\)、\(b=CA\)、\(c=AB\)。由于 \(\angle ATB\)、\(\angle BTC\)、\(\angle CTA\) 都是 \(120^\circ\)，每一条边都可以由余弦定理直接表示出来。
在 \(\cos 120^\circ=-\tfrac12\) 下应用余弦定理，可得
$$a^2=q^2+qr+r^2,\qquad b^2=r^2+rp+p^2,\qquad c^2=p^2+pq+q^2.$$
因此，一个三元组 \((p,q,r)\) 可行，当且仅当下面三个二次型全部是完全平方数：
$$p^2+pq+q^2,\qquad q^2+qr+r^2,\qquad r^2+rp+p^2.$$
一旦这三个量都为平方数，三角形三边就是整数，而由三条两两夹角为 \(120^\circ\) 的射线确定的内部点，正是题目要求的托里拆利构型。
如果两个正整数 \(x\) 与 \(y\) 满足
$$x^2+xy+y^2=z^2$$
对某个整数 \(z\) 成立，就称 \(x\) 和 \(y\) 是相容的。几何上，这意味着 \(x\) 与 \(y\) 可以作为两条夹角为 \(120^\circ\) 的托里拆利距离，而 \(z\) 就是它们对面的三角形边长。于是，这道题的本质不是先找任意三元组，而是寻找三个两两相容的距离。
这一步把问题变成了图论问题。令 \(N=120{,}000\)，把 \(1,2,\dots,N\) 视为图的顶点；若 \(x\) 与 \(y\) 相容，就在两者之间连一条边。这样一来，每个有效的 \((p,q,r)\) 恰好对应图中的一个 3-团，因为三组平方条件必须同时成立。
优化后的实现并不会从头枚举每一对 \((x,y)\)。它们使用方程
$$x^2+xy+y^2=z^2$$
的原始解标准参数化。除去 \(x\) 与 \(y\) 交换的情形，原始解可以写成
$$x_0=m^2-n^2,\qquad y_0=n(2m+n),\qquad z_0=m^2+mn+n^2,$$
其中满足
$$m>n>0,\qquad \gcd(m,n)=1,\qquad m-n\not\equiv 0 \pmod 3.$$
所有非原始解都只是 \((kx_0,ky_0)\) 这样的整数倍。因此，快速版本会遍历 \((m,n)\)，先生成原始种子对，再不断乘以 \(k\) 直到超过上界。对后续搜索来说，边是否存在才是关键，所以对边长 \(z\) 本身并不需要额外保存。
设 \(p<q<r\)。用图的语言来表达，\((p,q,r)\) 有效，当且仅当 \(q\) 与 \(r\) 都是 \(p\) 的邻居，并且 \(r\) 还是 \(q\) 的邻居。于是，在建立好有序邻接表以后，可以先固定 \(p\)，再从 \(p\) 的邻居中取 \(q>p\)，然后寻找同时属于 \(p\) 和 \(q\) 的邻接表、并且大于 \(q\) 的那些公共邻居。两个有序尾部的交集恰好给出所有这样的 \(r\)。
这种有序搜索依赖两个重要不变量。第一，要求 \(p<q<r\) 可以避免同一个三元组以六种排列方式被重复生成。第二，题目要的是不同的和 \(p+q+r\)，而不是不同的三元组。因此，找到的和必须先放入集合，再统一求和。不同的三元组完全可能得到相同的周长值，而那个值只能计算一次。
一个实际可行的例子是
$$ (p,q,r)=(195,264,325). $$
因为
$$195^2+195\cdot264+264^2=399^2,$$
$$195^2+195\cdot325+325^2=455^2,$$
$$264^2+264\cdot325+325^2=511^2.$$
所以这个三角形的三边分别是 \(399\)、\(455\)、\(511\)，全部为整数，而托里拆利距离之和为
$$195+264+325=784.$$
实现会先用这个较小的例子做健全性检查，再继续计算完整上界。
C++、Python 和 Java 实现本质上都在处理同一张“相容距离对”图。优化后的 C++ 与 Python 版本根据上面的参数化直接生成边；由于相容关系是对称的，每个成功生成的整数对都会分别加入双方的邻接表。完成生成后，邻接表会被排序并去重，从而保证后面的交集操作只是对有序数据做线性扫描。
图构造完成后，下一步就是枚举所有满足 \(p<q<r\) 的 3-团。对固定的 \(p\)，实现会遍历所有 \(q>p\) 的邻居。有效的 \(r\) 必须同时是 \(p\) 和 \(q\) 的公共邻居，而且还要满足 \(r>q\)。有序邻接表的交集在一次扫描中就把这些条件全部落实；若再满足 \(p+q+r \le 120{,}000\)，这个和就会被记录下来。
Java 实现展示的是同一数学思路的更直接版本。它不是从参数化生成真正的相容对，而是检查每一对满足 \(p<q\) 且 \(p+q \le N\) 的整数，测试 \(p^2+pq+q^2\) 是否为平方数，把成功的对保存下来，再通过寻找公共邻居闭合成三角形。这样的写法概念上更直观，但会在失败的二元测试上耗费大量时间。C++ 与 Python 版本则通过“只生成真的相容对”这一点省去了大部分无效工作。
记 \(E\) 为不超过上界 \(N\) 的相容整数对总数。优化后的构造需要 \(O(E)\) 时间来从原始种子生成所有缩放后的边，再加上邻接表排序的代价，以及所有有序交集用于枚举 3-团的代价。保守地说，它的最坏界仍可写成 \(N\) 的二次量级，但实际的算术图相当稀疏，因此在 \(N=120{,}000\) 时是可行的。
Java 中的直接构造为了建立图本身就要做 \(O(N^2)\) 次二元测试，随后才开始搜索公共邻居。所有版本都需要 \(O(E)\) 级别的空间来存储邻接结构，并额外保留一个不同周长和的集合。真正的提速来源于：不再对距离三元组进行盲目搜索，而是沿着图的边及其公共邻居来找解。
Пусть \(T\) — точка Торричелли треугольника \(ABC\), а \(p=TA\), \(q=TB\), \(r=TC\). Нужно просуммировать все различные значения \(p+q+r\), для которых \(p+q+r \le 120{,}000\), сами \(p\), \(q\), \(r\) являются целыми числами, и все три стороны треугольника тоже имеют целую длину.
Ключевой факт состоит в том, что три угла при \(T\) равны \(120^\circ\). Это переводит задачу из геометрии в арифметику: нужно понять, когда выражения вида \(x^2+xy+y^2\) оказываются полными квадратами. Именно эту структуру и используют реализации, не прибегая к явному построению координат.
Обозначим стороны треугольника через \(a=BC\), \(b=CA\) и \(c=AB\). Поскольку \(\angle ATB\), \(\angle BTC\) и \(\angle CTA\) все равны \(120^\circ\), каждая сторона выражается через закон косинусов.
Подставляя \(\cos 120^\circ=-\tfrac12\) в закон косинусов, получаем
$$a^2=q^2+qr+r^2,\qquad b^2=r^2+rp+p^2,\qquad c^2=p^2+pq+q^2.$$
Значит, тройка \((p,q,r)\) допустима тогда и только тогда, когда все три квадратичные формы
$$p^2+pq+q^2,\qquad q^2+qr+r^2,\qquad r^2+rp+p^2$$
являются полными квадратами. Как только это выполнено, стороны треугольника целые, а конфигурация с тремя лучами под углом \(120^\circ\) ровно соответствует условию задачи.
Назовем положительные целые \(x\) и \(y\) совместимыми, если существует целое \(z\), такое что
$$x^2+xy+y^2=z^2.$$
Геометрически это означает, что \(x\) и \(y\) могут быть двумя расстояниями от точки Торричелли, заключающими угол \(120^\circ\), а \(z\) — противоположной стороной треугольника. Тем самым полная задача сводится не к перебору произвольных троек, а к поиску трех расстояний, совместимых попарно.
После этого задача естественно превращается в задачу на граф. Берем числа \(1,2,\dots,N\) при \(N=120{,}000\) как вершины и соединяем \(x\) и \(y\) ребром, если они совместимы. Тогда любой допустимый набор \((p,q,r)\) — это в точности 3-клика такого графа, потому что все три парные квадратные проверки должны выполняться одновременно.
Оптимизированные реализации не проверяют каждую пару \((x,y)\) отдельно. Они используют стандартную параметризацию примитивных решений уравнения
$$x^2+xy+y^2=z^2,$$
которая, с точностью до перестановки \(x\) и \(y\), имеет вид
$$x_0=m^2-n^2,\qquad y_0=n(2m+n),\qquad z_0=m^2+mn+n^2,$$
при условиях
$$m>n>0,\qquad \gcd(m,n)=1,\qquad m-n\not\equiv 0 \pmod 3.$$
Любая непримитивная совместимая пара затем получается просто масштабированием \((kx_0,ky_0)\). Поэтому быстрые версии перебирают \((m,n)\), строят примитивные заготовки и затем умножают их на \(k\), пока не достигнут лимита. Значение \(z\) дальше хранить не нужно: важно лишь наличие ребра между двумя расстояниями.
Пусть \(p<q<r\). В терминах графа тройка \((p,q,r)\) допустима тогда и только тогда, когда \(q\) и \(r\) являются соседями \(p\), а \(r\) также является соседом \(q\). Значит, после построения отсортированных списков смежности можно зафиксировать \(p\), выбрать соседа \(q>p\), а затем искать общих соседей \(p\) и \(q\), которые также больше \(q\). Пересечение двух отсортированных хвостов списков и дает ровно такие значения \(r\).
У этого упорядоченного поиска есть два важных инварианта. Во-первых, условие \(p<q<r\) не дает одной и той же тройке появляться в шести перестановках. Во-вторых, задача просит разные суммы \(p+q+r\), а не разные тройки. Поэтому найденные суммы помещаются в множество перед суммированием. Разные тройки могут дать один и тот же периметр, и учитывать его нужно только один раз.
Конкретный пример решения:
$$ (p,q,r)=(195,264,325). $$
Действительно,
$$195^2+195\cdot264+264^2=399^2,$$
$$195^2+195\cdot325+325^2=455^2,$$
$$264^2+264\cdot325+325^2=511^2.$$
Следовательно, стороны треугольника равны \(399\), \(455\) и \(511\), все они целые, а сумма расстояний до точки Торричелли равна
$$195+264+325=784.$$
Именно этот маленький пример реализации используют как проверку корректности перед полным запуском.
Реализации на C++, Python и Java работают с одним и тем же графом совместимых пар расстояний. Оптимизированные версии на C++ и Python строят его из параметризации выше, добавляя каждую найденную пару в оба списка смежности, поскольку совместимость симметрична. После генерации списки сортируются и очищаются от повторов, чтобы дальнейшие пересечения были линейными проходами по упорядоченным данным.
Когда граф готов, следующая фаза — перечислить все упорядоченные тройки \(p<q<r\), образующие клику. Для фиксированного \(p\) реализация перебирает соседей \(q\) с условием \(q>p\). Допустимое \(r\) должно быть общим соседом для \(p\) и \(q\) и одновременно удовлетворять \(r>q\). Пересечение отсортированных списков реализует все эти условия за один проход; если еще и \(p+q+r \le 120{,}000\), сумма записывается.
Java-реализация показывает ту же математику в более прямой форме. Вместо генерации только настоящих совместимых пар из параметризации она проверяет каждую пару \(p<q\) с \(p+q \le N\), тестирует, является ли \(p^2+pq+q^2\) квадратом, сохраняет успешные пары, а затем ищет общих соседей для замыкания треугольников. Такая версия проще концептуально, но тратит гораздо больше времени на неудачные проверки. C++ и Python избегают этой лишней работы, потому что с самого начала генерируют только совместимые пары.
Пусть \(E\) — число совместимых пар до верхней границы \(N\). Оптимизированное построение требует \(O(E)\) времени на генерацию масштабированных пар из примитивных заготовок, плюс время на сортировку списков смежности и на все пересечения отсортированных списков, которыми перечисляются клики. Консервативная верхняя оценка все еще может быть квадратичной по \(N\), но арифметический граф достаточно разрежен, чтобы полный предел был практичен.
Прямой вариант в Java делает \(O(N^2)\) проверок пар уже на этапе построения графа и только потом приступает к поиску общих соседей. Все версии используют \(O(E)\) памяти на структуру смежности и дополнительно хранят множество различных сумм периметров. Главный выигрыш состоит в том, что слепой перебор троек расстояний заменяется поиском по ребрам и их общим соседям.
لتكن \(T\) هي نقطة توريتشيلي للمثلث \(ABC\)، ولنكتب \(p=TA\) و\(q=TB\) و\(r=TC\). المطلوب هو جمع جميع القيم المختلفة لـ \(p+q+r\) التي تحقق \(p+q+r \le 120{,}000\)، مع كون \(p\) و\(q\) و\(r\) أعدادًا صحيحة، وكذلك أطوال أضلاع المثلث الثلاثة أعدادًا صحيحة.
الحقيقة الحاسمة هنا أن الزوايا الثلاث عند \(T\) كلها تساوي \(120^\circ\). وهذا يحوّل المسألة من هندسة مباشرة إلى سؤال عددي عن متى تكون التعبيرات من الشكل \(x^2+xy+y^2\) مربعات كاملة. الحلول البرمجية تستغل هذا البناء الحسابي مباشرة، ولا تحتاج إلى بناء إحداثيات للمثلث.
لنرمز لأضلاع المثلث بـ \(a=BC\) و\(b=CA\) و\(c=AB\). وبما أن \(\angle ATB\) و\(\angle BTC\) و\(\angle CTA\) كلها تساوي \(120^\circ\)، فإن كل ضلع ينتج مباشرة من قانون جيب التمام.
بتطبيق قانون جيب التمام مع \(\cos 120^\circ=-\tfrac12\) نحصل على
$$a^2=q^2+qr+r^2,\qquad b^2=r^2+rp+p^2,\qquad c^2=p^2+pq+q^2.$$
إذًا تكون الثلاثية \((p,q,r)\) صالحة إذا وفقط إذا كانت الأشكال التربيعية الثلاثة
$$p^2+pq+q^2,\qquad q^2+qr+r^2,\qquad r^2+rp+p^2$$
كلها مربعات كاملة. وعندما يحدث ذلك تكون أضلاع المثلث صحيحة، ويكون الترتيب الناتج من ثلاثة أشعة تفصل بينها زوايا \(120^\circ\) هو بالضبط تركيب توريتشيلي المطلوب في المسألة.
سنقول إن العددين الصحيحين الموجبين \(x\) و\(y\) متوافقان إذا وجد عدد صحيح \(z\) يحقق
$$x^2+xy+y^2=z^2.$$
هندسيًا، هذا يعني أن \(x\) و\(y\) يمكن أن يكونا مسافتين من نقطة توريتشيلي بينهما زاوية \(120^\circ\)، وأن \(z\) هو ضلع المثلث المقابل لهما. لذلك فالمسألة الكاملة لا تبدأ بالبحث عن ثلاثيات اعتباطية، بل بالعثور على ثلاث مسافات متوافقة زوجيًا.
وهذا يحول البحث إلى مسألة بيانية. نأخذ الأعداد \(1,2,\dots,N\) حيث \(N=120{,}000\) على أنها رؤوس، ونصل بين \(x\) و\(y\) بحافة إذا كانا متوافقين. عندئذ تكون كل ثلاثية صالحة \((p,q,r)\) عبارة عن 3-clique في هذا الرسم البياني، لأن شروط الأزواج الثلاثة يجب أن تتحقق معًا.
التنفيذات المحسنة لا تختبر كل زوج \((x,y)\) من الصفر. بل تستخدم البارامترة القياسية للحلول الأولية للمعادلة
$$x^2+xy+y^2=z^2,$$
والتي يمكن كتابتها، مع السماح بتبديل \(x\) و\(y\)، على الصورة
$$x_0=m^2-n^2,\qquad y_0=n(2m+n),\qquad z_0=m^2+mn+n^2,$$
مع الشروط
$$m>n>0,\qquad \gcd(m,n)=1,\qquad m-n\not\equiv 0 \pmod 3.$$
وأي زوج متوافق غير أولي لا يكون إلا مضاعفًا من الشكل \((kx_0,ky_0)\). ولهذا تدور النسخ السريعة على \((m,n)\)، وتولد الأزواج الأولية، ثم تضربها في \(k\) إلى أن تصل إلى الحد المطلوب. ولا حاجة إلى حفظ طول الضلع \(z\) لاحقًا، لأن المهم هو مجرد وجود الحافة بين العددين.
افترض أن \(p<q<r\). بلغة الرسم البياني، تكون \((p,q,r)\) صالحة إذا وفقط إذا كان \(q\) و\(r\) جارين لـ \(p\)، وكان \(r\) أيضًا جارًا لـ \(q\). لذلك، بعد بناء قوائم جوار مرتبة، يمكن تثبيت \(p\)، ثم اختيار \(q>p\) من جيرانه، وبعد ذلك البحث عن الجيران المشتركين بين \(p\) و\(q\) الذين هم أكبر من \(q\). إن تقاطع ذيلي القائمتين المرتبتين يعطينا بالضبط قيم \(r\) المطلوبة.
لهذا البحث المرتب ثابتان مهمان. الأول أن الشرط \(p<q<r\) يمنع ظهور نفس الثلاثية في ستة ترتيبات مختلفة. والثاني أن المسألة تطلب القيم المختلفة لـ \(p+q+r\)، لا الثلاثيات المختلفة نفسها. ولهذا تُضاف المجاميع المكتشفة إلى مجموعة قبل جمعها النهائي. فقد تعطي ثلاثيات مختلفة نفس المحيط، ويجب احتسابه مرة واحدة فقط.
من الأمثلة الصالحة
$$ (p,q,r)=(195,264,325). $$
ذلك لأن
$$195^2+195\cdot264+264^2=399^2,$$
$$195^2+195\cdot325+325^2=455^2,$$
$$264^2+264\cdot325+325^2=511^2.$$
إذن أضلاع المثلث هي \(399\) و\(455\) و\(511\)، وكلها أعداد صحيحة، ويكون مجموع مسافات توريتشيلي
$$195+264+325=784.$$
وهذا هو المثال الصغير الذي تستخدمه التنفيذات بوصفه فحصًا أوليًا قبل الانتقال إلى الحد الكامل.
تعمل تنفيذات C++ وPython وJava كلها على الرسم البياني نفسه للأزواج المتوافقة. فالنسختان المحسنتان في C++ وPython تبنيان الرسم من البارامترة السابقة، وتضيفان كل زوج مولد إلى قائمتي الجوار معًا لأن التوافق علاقة متناظرة. وبعد التوليد تُرتب القوائم وتزال التكرارات منها، بحيث تصبح التقاطعات اللاحقة مجرد مسوح خطية على بيانات مرتبة.
بعد اكتمال الرسم تبدأ مرحلة تعداد جميع الثلاثيات المرتبة \(p<q<r\) التي تشكل clique. بالنسبة إلى قيمة ثابتة \(p\)، يستعرض التنفيذ الجيران \(q\) الذين يحققون \(q>p\). وأي \(r\) صالح يجب أن يكون جارًا مشتركًا لكل من \(p\) و\(q\)، وأن يحقق أيضًا \(r>q\). إن تقاطع القوائم المرتبة يفرض هذه الشروط كلها دفعة واحدة، وإذا تحقق أيضًا \(p+q+r \le 120{,}000\) فإن هذا المجموع يُسجل.
يعرض تنفيذ Java الرياضيات نفسها بصورة أكثر مباشرة. فبدلًا من توليد الأزواج المتوافقة من البارامترة، يفحص كل زوج \(p<q\) يحقق \(p+q \le N\)، ويختبر هل \(p^2+pq+q^2\) مربع كامل، ثم يحفظ الأزواج الناجحة ويبحث بعدها عن الجيران المشتركين لإغلاق المثلثات. هذه طريقة أبسط من حيث الفكرة، لكنها تهدر وقتًا أكبر بكثير على اختبارات أزواج فاشلة. أما تنفيذات C++ وPython فتتجنب معظم هذا العمل لأنها لا تولد منذ البداية إلا الأزواج المتوافقة فعلًا.
لنرمز بـ \(E\) إلى عدد الأزواج المتوافقة حتى الحد \(N\). فالإنشاء المحسن يستهلك زمنًا مقداره \(O(E)\) لتوليد الأزواج المضروبة من البذور الأولية، إضافة إلى كلفة ترتيب قوائم الجوار وكلفة جميع تقاطعات القوائم المرتبة اللازمة لتعداد cliques. ويمكن وضع حد علوي محافظ ما يزال تربيعيًا في \(N\)، لكن الرسم الحسابي متناثر بما يكفي لجعل الحد الكامل عمليًا.
أما النسخة المباشرة في Java فتجري \(O(N^2)\) من اختبارات الأزواج لمجرد بناء الرسم، ثم تبدأ فقط بعد ذلك البحث عن الجيران المشتركين. وتستخدم جميع النسخ ذاكرة من رتبة \(O(E)\) لبنية الجوار، بالإضافة إلى مجموعة القيم المختلفة للمحيط. مصدر التسريع الحقيقي هو استبدال البحث الأعمى على ثلاثيات المسافات ببحث على الحواف وجيرانها المشتركين.