For each integer \(k \ge 1\), consider the parabola \(y=\dfrac{x^2}{k}\). We choose three distinct integers \(a \lt b \lt c\) with \(|a|,|b|,|c|\le X\), form the points \(A=\left(a,\dfrac{a^2}{k}\right)\), \(B=\left(b,\dfrac{b^2}{k}\right)\), \(C=\left(c,\dfrac{c^2}{k}\right)\), and ask whether triangle \(ABC\) has at least one \(45^\circ\) angle. Let \(T_k(X)\) be that count for fixed \(k\). The program computes
$$F(K,X)=\sum_{k=1}^{K} T_k(X).$$
The key reduction is that chord slopes on this parabola depend only on pair sums such as \(a+b\), so the geometry becomes a divisor problem for \(2k^2\) plus interval counting for the remaining coordinate.
Define
$$x=a+b,\qquad y=a+c,\qquad z=b+c,$$
so \(x \lt y \lt z\) because \(a \lt b \lt c\). The slope of a chord between two points on \(y=\dfrac{x^2}{k}\) is
$$m_{uv}=\frac{v^2-u^2}{k(v-u)}=\frac{u+v}{k}.$$
Therefore the three side slopes are exactly
$$m_{AB}=\frac{x}{k},\qquad m_{AC}=\frac{y}{k},\qquad m_{BC}=\frac{z}{k}.$$
This is the crucial simplification: once \((x,y,z)\) are known, the angle conditions no longer involve quadratic expressions in \(a,b,c\).
At vertex \(A\), the two scaled direction vectors are proportional to \((k,x)\) and \((k,y)\). A \(45^\circ\) angle means that the cross-product magnitude equals the dot product:
$$k(y-x)=k^2+xy.$$
After rearranging, we obtain
$$xy+kx-ky+k^2=0,$$
hence
$$\boxed{(x-k)(y+k)=-2k^2.}$$
At vertex \(B\), the relevant scaled direction vectors are proportional to \((-k,-x)\) and \((k,z)\). The same \(45^\circ\) criterion gives
$$k(z-x)=-(k^2+xz),$$
so
$$\boxed{(x+k)(z-k)=-2k^2.}$$
At vertex \(C\), the symmetric computation yields
$$\boxed{(y-k)(z+k)=-2k^2.}$$
Thus every admissible triangle is encoded by one of three factor equations whose right-hand side is the fixed integer \(-2k^2\). No floating-point trigonometry is needed anywhere in the solver.
Write \(pq=-2k^2\). The implementation enumerates every positive divisor \(d\mid 2k^2\), then uses the two signs \(p=\pm d\) and sets \(q=-2k^2/p\).
For the \(A\)- and \(C\)-families we solve \((u-k)(v+k)=-2k^2\), so
$$u=p+k,\qquad v=q-k.$$
For the \(B\)-family we solve \((u+k)(v-k)=-2k^2\), so
$$u=p-k,\qquad v=q+k.$$
Only pairs with \(u \lt v\) and \(|u|,|v|\le 2X\) can come from actual sums of numbers in \([-X,X]\), so the code filters to that range immediately, sorts the resulting lists, and removes duplicates. Different divisors and sign choices can generate the same \((u,v)\), so this deduplication is essential.
Once a valid pair of sums is known, the third step is not another search; it is just an interval-length computation.
For an angle at \(A\), the pair is \((x,y)=(a+b,a+c)\). Then \(b=x-a\) and \(c=y-a\). Using \(-X\le a,b,c\le X\) and \(a \lt b \lt c\), the allowed values of \(a\) satisfy
$$a\in\left[\max(-X,y-X),\ \min\!\left(X,x+X,\left\lfloor\frac{x-1}{2}\right\rfloor\right)\right].$$
For an angle at \(B\), the pair is \((x,z)=(a+b,b+c)\), so \(a=x-b\), \(c=z-b\), and
$$b\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{x}{2}\right\rfloor+1\right),\ \min\!\left(X,x+X,\left\lfloor\frac{z-1}{2}\right\rfloor\right)\right].$$
For an angle at \(C\), the pair is \((y,z)=(a+c,b+c)\), so \(a=y-c\), \(b=z-c\), and
$$c\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{z}{2}\right\rfloor+1\right),\ \min(X,y+X)\right].$$
The helper functions count_angle_a_for_pair, count_angle_b_for_pair, and
count_angle_c_for_pair implement exactly these formulas. Because sums can be negative, the C++ and
Java versions use a custom floor_div instead of truncating division.
A triangle can have two \(45^\circ\) angles, so inclusion-exclusion is needed:
$$T_k(X)=N_A+N_B+N_C-N_{AB}-N_{AC}-N_{BC}.$$
When two families agree on the shared sum, we recover the original integer parameters from the ordered sums \(x \lt y \lt z\):
$$a=\frac{x+y-z}{2},\qquad b=\frac{x+z-y}{2},\qquad c=\frac{y+z-x}{2}.$$
The function valid_triangle_from_sums checks exactly what this reconstruction requires: strict order,
even parity of \(x+y+z\), and \(|a|,|b|,|c|\le X\). The overlaps are found by linear merges of sorted pair lists,
so the correction step is \(O(n)\) after sorting.
Take \(k=1\) and \((a,b,c)=(-3,0,2)\). Then the points are \(A=(-3,9)\), \(B=(0,0)\), \(C=(2,4)\), and
$$x=a+b=-3,\qquad z=b+c=2.$$
The middle-angle equation becomes
$$\left(x+1\right)\left(z-1\right)=(-2)(1)=-2=-2\cdot 1^2,$$
so the code classifies this triangle in the \(B\)-family and counts it as a \(45^\circ\) triangle. At a larger checkpoint, the program verifies that
$$F(1,10)=41,$$
which is the same reference value hardcoded in the C++ solution.
The C++ implementation builds an SPF table once up to the maximum required \(k\), factors each \(2k^2\) in
factor_2k_squared, recursively generates all divisors, constructs the two candidate pair lists in
build_pairs_for_k, evaluates the interval formulas, and subtracts overlaps with three sorted
merge-scans. The C++ version can split the \(k\)-range across threads. The Python file is intentionally not a
second mathematical implementation: it is a thin bridge that compiles and runs the C++ solver, then parses the
final line. The Java file is a direct arithmetic port of the same method and parallelizes with
LongStream.rangeClosed(...).parallel().
Building the SPF sieve up to \(K\) costs \(O(K\log\log K)\) time and \(O(K)\) memory. For fixed \(k\), let \(D_k=d(2k^2)\) be the number of divisors of \(2k^2\). Divisor generation is \(O(D_k)\), interval accumulation is linear in the number of surviving pairs, and sorting/deduplication dominates at roughly \(O(D_k\log D_k)\). The three overlap corrections are linear merges after sorting. Therefore the overall complexity is
$$O\!\left(K\log\log K+\sum_{k=1}^{K} D_k\log D_k\right),$$
with \(O(K)\) global memory for the sieve and \(O(D_k)\) temporary memory per worker.
Für jedes ganze \(k \ge 1\) betrachten wir die Parabel \(y=\dfrac{x^2}{k}\). Wir wählen drei verschiedene ganze Zahlen \(a \lt b \lt c\) mit \(|a|,|b|,|c|\le X\) und die Punkte \(A=\left(a,\dfrac{a^2}{k}\right)\), \(B=\left(b,\dfrac{b^2}{k}\right)\), \(C=\left(c,\dfrac{c^2}{k}\right)\). Gesucht sind genau die Dreiecke \(ABC\), die mindestens einen \(45^\circ\)-Winkel besitzen. Bezeichnet \(T_k(X)\) diese Anzahl für festes \(k\), dann berechnet das Programm
$$F(K,X)=\sum_{k=1}^{K} T_k(X).$$
Die zentrale Idee ist, die Geometrie über Sehnensteigungen auf Paar-Summen wie \(a+b\) zu reduzieren. Danach bleibt kein Gleitkomma-Problem mehr übrig, sondern ein Divisorenproblem für \(2k^2\) plus Intervallzählung.
Setze
$$x=a+b,\qquad y=a+c,\qquad z=b+c,$$
dann gilt \(x \lt y \lt z\). Die Steigung einer Sehne zwischen zwei Punkten der Parabel \(y=\dfrac{x^2}{k}\) ist
$$m_{uv}=\frac{v^2-u^2}{k(v-u)}=\frac{u+v}{k}.$$
Somit sind die drei Seitensteigungen
$$m_{AB}=\frac{x}{k},\qquad m_{AC}=\frac{y}{k},\qquad m_{BC}=\frac{z}{k}.$$
Damit hängt die Winkelbedingung nur noch von \(x,y,z\) ab und nicht mehr direkt quadratisch von \(a,b,c\).
Am Punkt \(A\) sind die skalierten Richtungsvektoren proportional zu \((k,x)\) und \((k,y)\). Ein \(45^\circ\)-Winkel bedeutet: Betrag des Kreuzprodukts gleich Skalarprodukt, also
$$k(y-x)=k^2+xy.$$
Nach Umformen folgt
$$xy+kx-ky+k^2=0,$$
also
$$\boxed{(x-k)(y+k)=-2k^2.}$$
Am Punkt \(B\) sind die skalierten Richtungsvektoren proportional zu \((-k,-x)\) und \((k,z)\). Daraus ergibt sich
$$k(z-x)=-(k^2+xz),$$
und damit
$$\boxed{(x+k)(z-k)=-2k^2.}$$
Symmetrisch erhält man am Punkt \(C\)
$$\boxed{(y-k)(z+k)=-2k^2.}$$
Damit ist jedes zulässige Dreieck in eine Faktorisierungsbedingung mit rechter Seite \(-2k^2\) übersetzt.
Schreibe \(pq=-2k^2\). Der Code läuft über alle positiven Divisoren \(d\mid 2k^2\), wählt beide Vorzeichen \(p=\pm d\) und setzt \(q=-2k^2/p\).
Für die \(A\)- und \(C\)-Familien wird \((u-k)(v+k)=-2k^2\) gelöst, also
$$u=p+k,\qquad v=q-k.$$
Für die \(B\)-Familie wird \((u+k)(v-k)=-2k^2\) gelöst, also
$$u=p-k,\qquad v=q+k.$$
Behalten werden nur Paare mit \(u \lt v\) und \(|u|,|v|\le 2X\), denn nur solche können als Summen zweier Zahlen aus \([-X,X]\) auftreten. Danach sortiert und dedupliziert die Implementierung, weil verschiedene Divisoren zum selben Paar \((u,v)\) führen können.
Ist ein zulässiges Summenpaar bekannt, muss nicht weiter gesucht werden: Die fehlende Koordinate liegt in einem expliziten ganzzahligen Intervall.
Für einen Winkel bei \(A\) ist \((x,y)=(a+b,a+c)\). Mit \(b=x-a\), \(c=y-a\), den Schranken \(-X\le a,b,c\le X\) und der Ordnung \(a \lt b \lt c\) erhält man
$$a\in\left[\max(-X,y-X),\ \min\!\left(X,x+X,\left\lfloor\frac{x-1}{2}\right\rfloor\right)\right].$$
Für einen Winkel bei \(B\) mit \((x,z)=(a+b,b+c)\) gilt
$$b\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{x}{2}\right\rfloor+1\right),\ \min\!\left(X,x+X,\left\lfloor\frac{z-1}{2}\right\rfloor\right)\right].$$
Für einen Winkel bei \(C\) mit \((y,z)=(a+c,b+c)\) gilt
$$c\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{z}{2}\right\rfloor+1\right),\ \min(X,y+X)\right].$$
Genau diese Formeln stehen hinter count_angle_a_for_pair,
count_angle_b_for_pair und count_angle_c_for_pair. Weil Summen negativ sein können,
implementieren C++ und Java eine echte mathematische Bodenfunktion floor_div.
Ein Dreieck kann zwei \(45^\circ\)-Winkel besitzen. Deshalb gilt
$$T_k(X)=N_A+N_B+N_C-N_{AB}-N_{AC}-N_{BC}.$$
Aus geordneten Summen \(x \lt y \lt z\) rekonstruiert man
$$a=\frac{x+y-z}{2},\qquad b=\frac{x+z-y}{2},\qquad c=\frac{y+z-x}{2}.$$
valid_triangle_from_sums prüft daher genau die nötigen Bedingungen: strikte Ordnung, gerade Parität
von \(x+y+z\) und die Schranken \(|a|,|b|,|c|\le X\). Die Überlappungen werden per linearem Merge über sortierte
Listen gefunden.
Für \(k=1\) und \((a,b,c)=(-3,0,2)\) liegen die Punkte bei \(A=(-3,9)\), \(B=(0,0)\), \(C=(2,4)\). Dann ist
$$x=a+b=-3,\qquad z=b+c=2.$$
Die Bedingung für den Winkel bei \(B\) lautet
$$\left(x+1\right)\left(z-1\right)=(-2)(1)=-2=-2\cdot 1^2,$$
also wird dieses Dreieck in der \(B\)-Familie gezählt. Als größerer Prüfwert bestätigt das Programm außerdem
$$F(1,10)=41,$$
genau wie im C++-Code hinterlegt.
Die C++-Lösung baut zunächst eine SPF-Tabelle bis zum maximal benötigten \(k\) auf, faktorisiert in
factor_2k_squared jedes \(2k^2\), erzeugt rekursiv alle Divisoren, konstruiert die beiden
Kandidatenlisten in build_pairs_for_k, zählt Intervalllängen und entfernt Überlappungen durch drei
lineare Merge-Scans. Die C++-Version kann den \(k\)-Bereich auf mehrere Threads aufteilen. Die Python-Datei ist
bewusst nur eine Brücke: Sie kompiliert und startet den C++-Solver und liest dessen Ausgabe. Die Java-Datei ist
eine direkte Portierung desselben arithmetischen Kerns und parallelisiert über
LongStream.rangeClosed(...).parallel().
Das SPF-Sieb bis \(K\) kostet \(O(K\log\log K)\) Zeit und \(O(K)\) Speicher. Für festes \(k\) sei \(D_k=d(2k^2)\) die Anzahl der Divisoren von \(2k^2\). Das Erzeugen der Divisoren kostet \(O(D_k)\), die Intervallzählung ist linear in der Zahl der überlebenden Paare, und Sortieren/Deduplizieren dominiert mit ungefähr \(O(D_k\log D_k)\). Die drei Überlappungskorrekturen sind nach dem Sortieren linear. Insgesamt also
$$O\!\left(K\log\log K+\sum_{k=1}^{K} D_k\log D_k\right),$$
bei \(O(K)\) globalem Speicher für das Sieb und \(O(D_k)\) Arbeitsspeicher pro Thread.
Her \(k \ge 1\) tamsayısı için \(y=\dfrac{x^2}{k}\) parabolünü ele alıyoruz. \(|a|,|b|,|c|\le X\) olacak şekilde \(a \lt b \lt c\) tamsayılarını seçip \(A=\left(a,\dfrac{a^2}{k}\right)\), \(B=\left(b,\dfrac{b^2}{k}\right)\), \(C=\left(c,\dfrac{c^2}{k}\right)\) noktalarını kuruyoruz. Amaç, en az bir açısı \(45^\circ\) olan üçgenleri saymaktır. Sabit \(k\) için bu sayı \(T_k(X)\) olsun. Programın hesapladığı toplam
$$F(K,X)=\sum_{k=1}^{K} T_k(X)$$
şeklindedir. Kritik fikir şudur: parabol üzerindeki iki nokta arasındaki kirişin eğimi yalnızca iki \(x\)-koordinatının toplamına bağlıdır. Böylece geometri, \(2k^2\) için bölen denklemlerine ve kalan değişkeni kapalı aralıklarla saymaya indirgenir.
Tanımlayalım:
$$x=a+b,\qquad y=a+c,\qquad z=b+c.$$
\(a \lt b \lt c\) olduğundan \(x \lt y \lt z\) olur. \(y=\dfrac{x^2}{k}\) parabolünde iki nokta arasındaki kiriş eğimi
$$m_{uv}=\frac{v^2-u^2}{k(v-u)}=\frac{u+v}{k}$$
olduğuna göre üç kenarın eğimleri tam olarak
$$m_{AB}=\frac{x}{k},\qquad m_{AC}=\frac{y}{k},\qquad m_{BC}=\frac{z}{k}$$
şeklindedir. Böylece açı koşulu artık doğrudan \(a,b,c\) yerine \(x,y,z\) üzerinden ifade edilir.
\(A\) köşesinde ölçeklenmiş yön vektörleri \((k,x)\) ve \((k,y)\) ile orantılıdır. \(45^\circ\) için vektörel determinantın mutlak değeri ile skaler çarpım eşit olmalıdır:
$$k(y-x)=k^2+xy.$$
Buradan
$$xy+kx-ky+k^2=0$$
ve dolayısıyla
$$\boxed{(x-k)(y+k)=-2k^2}$$
elde edilir. \(B\) köşesinde ölçeklenmiş yönler \((-k,-x)\) ve \((k,z)\) ile orantılıdır. Aynı koşul
$$k(z-x)=-(k^2+xz)$$
eşitliğini verir ve bu da
$$\boxed{(x+k)(z-k)=-2k^2}$$
olur. Simetrik olarak \(C\) köşesinde
$$\boxed{(y-k)(z+k)=-2k^2}$$
çıkar. Böylece bütün geçerli üçgenler, sağ tarafı sabit \(-2k^2\) olan üç çarpan denkleminden birine düşer.
\(pq=-2k^2\) yazalım. Kod, \(2k^2\)'nin tüm pozitif bölenlerini dolaşıp \(p=\pm d\) seçer ve \(q=-2k^2/p\) hesaplar.
\(A\) ve \(C\) ailelerinde \((u-k)(v+k)=-2k^2\) çözüldüğü için
$$u=p+k,\qquad v=q-k$$
kullanılır. \(B\) ailesinde \((u+k)(v-k)=-2k^2\) çözüldüğü için
$$u=p-k,\qquad v=q+k$$
alınır. Yalnızca \(u \lt v\) ve \(|u|,|v|\le 2X\) olan çiftler tutulur; çünkü ancak bunlar \([-X,X]\) içindeki iki sayının toplamı olabilir. Daha sonra listeler sıralanır ve yinelenen çiftler atılır.
Geçerli bir toplam çifti bulunduktan sonra son adım yeni bir arama değildir; eksik değişken için kapalı bir tam sayı aralığı hesaplanır.
\(A\) açısı için \((x,y)=(a+b,a+c)\) olduğundan \(b=x-a\), \(c=y-a\) yazılır. Sınırlar \(-X\le a,b,c\le X\) ve sıra \(a \lt b \lt c\) ile
$$a\in\left[\max(-X,y-X),\ \min\!\left(X,x+X,\left\lfloor\frac{x-1}{2}\right\rfloor\right)\right]$$
elde edilir. \(B\) açısı için \((x,z)=(a+b,b+c)\) olduğundan
$$b\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{x}{2}\right\rfloor+1\right),\ \min\!\left(X,x+X,\left\lfloor\frac{z-1}{2}\right\rfloor\right)\right]$$
ve \(C\) açısı için \((y,z)=(a+c,b+c)\) olduğundan
$$c\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{z}{2}\right\rfloor+1\right),\ \min(X,y+X)\right]$$
çıkar. count_angle_a_for_pair, count_angle_b_for_pair ve
count_angle_c_for_pair fonksiyonları tam olarak bu aralıkları uygular. Toplamlar negatif
olabildiğinden C++ ve Java tarafında gerçek taban bölmesi yapan özel bir floor_div bulunur.
Bir üçgenin iki adet \(45^\circ\) açısı olabilir. Bu nedenle
$$T_k(X)=N_A+N_B+N_C-N_{AB}-N_{AC}-N_{BC}$$
kullanılır. Sıralı toplamlar \(x \lt y \lt z\) verildiğinde orijinal parametreler
$$a=\frac{x+y-z}{2},\qquad b=\frac{x+z-y}{2},\qquad c=\frac{y+z-x}{2}$$
ile geri kurulur. valid_triangle_from_sums bu yüzden sıra koşulunu, \(x+y+z\)'nin çift olmasını ve
\(|a|,|b|,|c|\le X\) sınırlarını kontrol eder. Çakışmalar, sıralı listeler üzerinde doğrusal merge ile bulunur.
\(k=1\) ve \((a,b,c)=(-3,0,2)\) için noktalar \(A=(-3,9)\), \(B=(0,0)\), \(C=(2,4)\) olur. Bu durumda
$$x=a+b=-3,\qquad z=b+c=2.$$
\(B\) açısı denklemi
$$\left(x+1\right)\left(z-1\right)=(-2)(1)=-2=-2\cdot 1^2$$
olduğundan üçgen \(B\) ailesinde sayılır. Daha büyük kontrol değeri olarak program
$$F(1,10)=41$$
sonucunu da doğrular; bu değer C++ dosyasında sabit olarak yer alır.
C++ çözümü önce gerekli en büyük \(k\)'ye kadar SPF tablosu kurar, factor_2k_squared içinde her
\(2k^2\)'yi çarpanlara ayırır, tüm bölenleri özyinelemeli üretir, build_pairs_for_k ile iki aday
çift listesini hazırlar, aralık uzunluklarını toplar ve üç sıralı merge geçişiyle çakışmaları çıkarır. C++ sürümü
\(k\) aralığını iş parçacıklarına bölebilir. Python dosyası ikinci bir matematiksel çözüm değildir; C++ ikilisini
derleyip çalıştıran ince bir köprüdür. Java dosyası ise aynı aritmetik çekirdeğin doğrudan portudur ve
LongStream.rangeClosed(...).parallel() kullanır.
\(K\)'ye kadar SPF süzgeci \(O(K\log\log K)\) zaman ve \(O(K)\) bellek gerektirir. Sabit bir \(k\) için \(D_k=d(2k^2)\) olsun. Bölen üretimi \(O(D_k)\), aralık toplamları kalan çift sayısına göre lineer, sıralama ve tekilleştirme ise yaklaşık \(O(D_k\log D_k)\) maliyetlidir. Üç çakışma düzeltmesi sıralamadan sonra lineerdir. Dolayısıyla toplam karmaşıklık
$$O\!\left(K\log\log K+\sum_{k=1}^{K} D_k\log D_k\right)$$
ve bellek kullanımı süzgeç için \(O(K)\), iş parçacığı başına geçici çalışma alanı için \(O(D_k)\) düzeyindedir.
Para cada entero \(k \ge 1\) se considera la parábola \(y=\dfrac{x^2}{k}\). Elegimos tres enteros distintos \(a \lt b \lt c\) con \(|a|,|b|,|c|\le X\), formamos los puntos \(A=\left(a,\dfrac{a^2}{k}\right)\), \(B=\left(b,\dfrac{b^2}{k}\right)\), \(C=\left(c,\dfrac{c^2}{k}\right)\), y contamos los triángulos \(ABC\) que tienen al menos un ángulo de \(45^\circ\). Si \(T_k(X)\) denota esa cantidad para \(k\) fijo, el programa calcula
$$F(K,X)=\sum_{k=1}^{K} T_k(X).$$
La reducción decisiva es que la pendiente de una cuerda en esta parábola depende sólo de una suma de dos abscisas, por ejemplo \(a+b\). Así la geometría pasa a ser un problema de divisores de \(2k^2\) más conteos exactos por intervalos.
Definimos
$$x=a+b,\qquad y=a+c,\qquad z=b+c,$$
de modo que \(x \lt y \lt z\). La pendiente de la cuerda entre dos puntos de \(y=\dfrac{x^2}{k}\) es
$$m_{uv}=\frac{v^2-u^2}{k(v-u)}=\frac{u+v}{k}.$$
Por tanto, las pendientes de los tres lados son
$$m_{AB}=\frac{x}{k},\qquad m_{AC}=\frac{y}{k},\qquad m_{BC}=\frac{z}{k}.$$
Con esto, la condición angular se expresa por completo en términos de \(x,y,z\).
En el vértice \(A\), los vectores directores escalados son proporcionales a \((k,x)\) y \((k,y)\). La condición de \(45^\circ\) equivale a igualar módulo del producto vectorial y producto escalar:
$$k(y-x)=k^2+xy.$$
Reordenando se obtiene
$$xy+kx-ky+k^2=0,$$
es decir,
$$\boxed{(x-k)(y+k)=-2k^2.}$$
En el vértice \(B\), los vectores directores escalados son proporcionales a \((-k,-x)\) y \((k,z)\), y resulta
$$k(z-x)=-(k^2+xz),$$
luego
$$\boxed{(x+k)(z-k)=-2k^2.}$$
De forma simétrica, para el vértice \(C\) se llega a
$$\boxed{(y-k)(z+k)=-2k^2.}$$
Así, la parte geométrica queda sustituida por tres ecuaciones de factorización con término derecho fijo \(-2k^2\).
Escribimos \(pq=-2k^2\). La implementación recorre todos los divisores positivos \(d\mid 2k^2\), toma ambos signos \(p=\pm d\) y define \(q=-2k^2/p\).
Para las familias \(A\) y \(C\) se resuelve \((u-k)(v+k)=-2k^2\), por lo que
$$u=p+k,\qquad v=q-k.$$
Para la familia \(B\) se resuelve \((u+k)(v-k)=-2k^2\), por lo que
$$u=p-k,\qquad v=q+k.$$
Sólo se conservan los pares con \(u \lt v\) y \(|u|,|v|\le 2X\), ya que sólo ellos pueden ser sumas de dos enteros de \([-X,X]\). Después se ordenan y se eliminan duplicados.
Una vez conocido un par de sumas válido, no hace falta enumerar el tercer valor: basta contar una longitud de intervalo.
Si el ángulo está en \(A\), entonces \((x,y)=(a+b,a+c)\), con \(b=x-a\) y \(c=y-a\). Usando \(-X\le a,b,c\le X\) y \(a \lt b \lt c\), se obtiene
$$a\in\left[\max(-X,y-X),\ \min\!\left(X,x+X,\left\lfloor\frac{x-1}{2}\right\rfloor\right)\right].$$
Si el ángulo está en \(B\), \((x,z)=(a+b,b+c)\), y por tanto
$$b\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{x}{2}\right\rfloor+1\right),\ \min\!\left(X,x+X,\left\lfloor\frac{z-1}{2}\right\rfloor\right)\right].$$
Si el ángulo está en \(C\), \((y,z)=(a+c,b+c)\), y entonces
$$c\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{z}{2}\right\rfloor+1\right),\ \min(X,y+X)\right].$$
Las funciones count_angle_a_for_pair, count_angle_b_for_pair y
count_angle_c_for_pair implementan exactamente estas fórmulas. Como las sumas pueden ser negativas,
las versiones C++ y Java usan una floor_div matemática real, no división truncada.
Un triángulo puede tener dos ángulos de \(45^\circ\). Por eso
$$T_k(X)=N_A+N_B+N_C-N_{AB}-N_{AC}-N_{BC}.$$
A partir de las sumas ordenadas \(x \lt y \lt z\), se reconstruyen los parámetros originales como
$$a=\frac{x+y-z}{2},\qquad b=\frac{x+z-y}{2},\qquad c=\frac{y+z-x}{2}.$$
La rutina valid_triangle_from_sums comprueba precisamente lo necesario: orden estricto, paridad par de
\(x+y+z\) y cotas \(|a|,|b|,|c|\le X\). Los solapamientos se detectan con fusiones lineales de listas ya
ordenadas.
Tomemos \(k=1\) y \((a,b,c)=(-3,0,2)\). Los puntos son \(A=(-3,9)\), \(B=(0,0)\), \(C=(2,4)\), y
$$x=a+b=-3,\qquad z=b+c=2.$$
La ecuación del ángulo en \(B\) queda
$$\left(x+1\right)\left(z-1\right)=(-2)(1)=-2=-2\cdot 1^2,$$
de modo que el triángulo se cuenta en la familia \(B\). Como verificación mayor, el programa también confirma
$$F(1,10)=41,$$
que es el primer punto de control codificado en C++.
La versión en C++ construye una tabla SPF una sola vez hasta el mayor \(k\) necesario, factoriza cada \(2k^2\) en
factor_2k_squared, genera recursivamente todos sus divisores, construye las dos listas de pares
candidatos en build_pairs_for_k, suma longitudes de intervalos y resta los solapamientos mediante tres
fusiones lineales. La implementación en C++ puede repartir el rango de \(k\) entre varios hilos. El archivo de
Python no es otra solución matemática: es un puente que compila y ejecuta el binario C++ y luego interpreta la
salida. El archivo Java es una traslación directa del mismo núcleo aritmético y usa
LongStream.rangeClosed(...).parallel().
Construir la criba SPF hasta \(K\) cuesta \(O(K\log\log K)\) tiempo y \(O(K)\) memoria. Para un \(k\) fijo, sea \(D_k=d(2k^2)\) el número de divisores de \(2k^2\). Generar divisores cuesta \(O(D_k)\), las cuentas por intervalos son lineales en el número de pares supervivientes y el coste dominante es ordenar y deduplicar, con orden aproximado \(O(D_k\log D_k)\). Las tres correcciones por solapamiento son lineales una vez ordenadas las listas. En conjunto:
$$O\!\left(K\log\log K+\sum_{k=1}^{K} D_k\log D_k\right),$$
con \(O(K)\) memoria global para la criba y \(O(D_k)\) memoria temporal por hilo.
对每个整数 \(k \ge 1\)，考虑抛物线 \(y=\dfrac{x^2}{k}\)。取满足 \(|a|,|b|,|c|\le X\) 的整数 \(a \lt b \lt c\)，并定义点 \(A=\left(a,\dfrac{a^2}{k}\right)\)、\(B=\left(b,\dfrac{b^2}{k}\right)\)、 \(C=\left(c,\dfrac{c^2}{k}\right)\)。我们要统计三角形 \(ABC\) 至少有一个 \(45^\circ\) 内角的情形。若固定 \(k\) 时该数量记为 \(T_k(X)\)，那么程序计算的是
$$F(K,X)=\sum_{k=1}^{K} T_k(X).$$
核心化简在于：抛物线上两点连线的斜率只取决于两点横坐标之和，因此几何条件可以改写成 \(2k^2\) 的因子方程，再配合对剩余坐标的整数区间计数。
设
$$x=a+b,\qquad y=a+c,\qquad z=b+c,$$
则由于 \(a \lt b \lt c\)，有 \(x \lt y \lt z\)。在抛物线 \(y=\dfrac{x^2}{k}\) 上，两点之间弦的斜率为
$$m_{uv}=\frac{v^2-u^2}{k(v-u)}=\frac{u+v}{k}.$$
因此三条边的斜率恰好是
$$m_{AB}=\frac{x}{k},\qquad m_{AC}=\frac{y}{k},\qquad m_{BC}=\frac{z}{k}.$$
这一步非常关键，因为角度条件从此只依赖于 \(x,y,z\)，不再直接依赖 \(a,b,c\) 的平方项。
在顶点 \(A\) 处，缩放后的方向向量与 \((k,x)\)、\((k,y)\) 成比例。夹角为 \(45^\circ\) 等价于叉积绝对值等于点积：
$$k(y-x)=k^2+xy.$$
整理得
$$xy+kx-ky+k^2=0,$$
也就是
$$\boxed{(x-k)(y+k)=-2k^2.}$$
在顶点 \(B\) 处，相关向量与 \((-k,-x)\)、\((k,z)\) 成比例，于是得到
$$k(z-x)=-(k^2+xz),$$
从而
$$\boxed{(x+k)(z-k)=-2k^2.}$$
对称地，在顶点 \(C\) 处有
$$\boxed{(y-k)(z+k)=-2k^2.}$$
于是“有一个 \(45^\circ\) 角”的几何问题，转化成了右端固定为 \(-2k^2\) 的三个因式分解条件。
写成 \(pq=-2k^2\)。实现中先枚举每个正因子 \(d\mid 2k^2\)，再取两种符号 \(p=\pm d\)，并设 \(q=-2k^2/p\)。
对于 \(A\) 与 \(C\) 两类，要解 \((u-k)(v+k)=-2k^2\)，于是
$$u=p+k,\qquad v=q-k.$$
对于 \(B\) 类，要解 \((u+k)(v-k)=-2k^2\)，于是
$$u=p-k,\qquad v=q+k.$$
只有满足 \(u \lt v\) 且 \(|u|,|v|\le 2X\) 的对才可能来自 \([-X,X]\) 内两个整数之和，因此代码会先做 这一步过滤，然后排序并去重。不同因子和符号组合可能生成同一个 \((u,v)\)。
一旦某个和对合法，剩下的工作就不是暴力搜索，而是计算一个闭区间长度。
若角在 \(A\)，则 \((x,y)=(a+b,a+c)\)，于是 \(b=x-a\)、\(c=y-a\)。结合 \(-X\le a,b,c\le X\) 与 \(a \lt b \lt c\)，得到
$$a\in\left[\max(-X,y-X),\ \min\!\left(X,x+X,\left\lfloor\frac{x-1}{2}\right\rfloor\right)\right].$$
若角在 \(B\)，则 \((x,z)=(a+b,b+c)\)，得到
$$b\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{x}{2}\right\rfloor+1\right),\ \min\!\left(X,x+X,\left\lfloor\frac{z-1}{2}\right\rfloor\right)\right].$$
若角在 \(C\)，则 \((y,z)=(a+c,b+c)\)，得到
$$c\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{z}{2}\right\rfloor+1\right),\ \min(X,y+X)\right].$$
count_angle_a_for_pair、count_angle_b_for_pair、
count_angle_c_for_pair 正是这三条公式。因为和可能为负，C++ 与 Java 都实现了真正的
floor_div，避免截断除法带来的错误。
一个三角形可能有两个 \(45^\circ\) 角，所以必须做容斥：
$$T_k(X)=N_A+N_B+N_C-N_{AB}-N_{AC}-N_{BC}.$$
若已知有序和 \(x \lt y \lt z\)，原始整数参数可由
$$a=\frac{x+y-z}{2},\qquad b=\frac{x+z-y}{2},\qquad c=\frac{y+z-x}{2}$$
恢复出来。函数 valid_triangle_from_sums 因而要检查：顺序严格、\(x+y+z\) 为偶数，以及
\(|a|,|b|,|c|\le X\)。三种交集通过排序后的线性归并完成。
取 \(k=1\)、\((a,b,c)=(-3,0,2)\)。此时 \(A=(-3,9)\)、\(B=(0,0)\)、\(C=(2,4)\)，并且
$$x=a+b=-3,\qquad z=b+c=2.$$
\(B\) 点的条件变为
$$\left(x+1\right)\left(z-1\right)=(-2)(1)=-2=-2\cdot 1^2,$$
所以该三角形会被归入 \(B\) 类。更大的检查点上，程序还验证了
$$F(1,10)=41,$$
这与 C++ 文件中的硬编码检查值完全一致。
C++ 版本先为所需最大 \(k\) 建立 SPF 表，然后在 factor_2k_squared 中分解每个 \(2k^2\)，
递归生成全部因子，在 build_pairs_for_k 中构造两类候选和对，接着累计区间长度，并用三次
有序归并减去重叠。C++ 还能把 \(k\) 的范围分给多个线程。Python 文件并不是独立的数学重写，而是一个薄
封装：它编译并执行 C++ 求解器，再解析输出。Java 文件则是同一套算术逻辑的直接移植，并通过
LongStream.rangeClosed(...).parallel() 并行遍历 \(k\)。
建立到 \(K\) 的 SPF 筛需要 \(O(K\log\log K)\) 时间和 \(O(K)\) 空间。对固定的 \(k\)，记 \(D_k=d(2k^2)\) 为 \(2k^2\) 的因子个数。生成因子是 \(O(D_k)\)，区间累计与保留下来的对数线性相关， 排序与去重约为 \(O(D_k\log D_k)\)，而三次重叠修正在线性时间内完成。因此总复杂度为
$$O\!\left(K\log\log K+\sum_{k=1}^{K} D_k\log D_k\right),$$
全局空间为筛表的 \(O(K)\)，每个工作线程另需 \(O(D_k)\) 的临时存储。
Для каждого целого \(k \ge 1\) рассматривается парабола \(y=\dfrac{x^2}{k}\). Берём целые \(a \lt b \lt c\) при \(|a|,|b|,|c|\le X\), задаём точки \(A=\left(a,\dfrac{a^2}{k}\right)\), \(B=\left(b,\dfrac{b^2}{k}\right)\), \(C=\left(c,\dfrac{c^2}{k}\right)\) и считаем треугольники \(ABC\), у которых хотя бы один угол равен \(45^\circ\). Если для фиксированного \(k\) это число обозначить через \(T_k(X)\), то программа вычисляет
$$F(K,X)=\sum_{k=1}^{K} T_k(X).$$
Главное упрощение состоит в том, что наклон хорды на этой параболе зависит только от суммы двух абсцисс. Поэтому геометрия сводится к уравнениям на делители числа \(2k^2\) и к подсчёту целых точек в явных интервалах.
Положим
$$x=a+b,\qquad y=a+c,\qquad z=b+c,$$
тогда \(x \lt y \lt z\). Наклон хорды между двумя точками параболы \(y=\dfrac{x^2}{k}\) равен
$$m_{uv}=\frac{v^2-u^2}{k(v-u)}=\frac{u+v}{k}.$$
Следовательно, наклоны трёх сторон равны
$$m_{AB}=\frac{x}{k},\qquad m_{AC}=\frac{y}{k},\qquad m_{BC}=\frac{z}{k}.$$
После этого условие на угол выражается только через \(x,y,z\), без прямого перебора квадратов \(a^2,b^2,c^2\).
В вершине \(A\) масштабированные направляющие векторы пропорциональны \((k,x)\) и \((k,y)\). Угол в \(45^\circ\) означает равенство модуля векторного произведения и скалярного произведения:
$$k(y-x)=k^2+xy.$$
После преобразования получаем
$$xy+kx-ky+k^2=0,$$
то есть
$$\boxed{(x-k)(y+k)=-2k^2.}$$
В вершине \(B\) соответствующие векторы пропорциональны \((-k,-x)\) и \((k,z)\), поэтому
$$k(z-x)=-(k^2+xz),$$
а значит
$$\boxed{(x+k)(z-k)=-2k^2.}$$
Симметрично для вершины \(C\) имеем
$$\boxed{(y-k)(z+k)=-2k^2.}$$
Итак, задача о треугольниках с углом \(45^\circ\) сведена к трём уравнениям факторизации с фиксированной правой частью \(-2k^2\).
Запишем \(pq=-2k^2\). Реализация перебирает каждый положительный делитель \(d\mid 2k^2\), берёт два знака \(p=\pm d\) и ставит \(q=-2k^2/p\).
Для семейств \(A\) и \(C\) решается \((u-k)(v+k)=-2k^2\), значит
$$u=p+k,\qquad v=q-k.$$
Для семейства \(B\) решается \((u+k)(v-k)=-2k^2\), значит
$$u=p-k,\qquad v=q+k.$$
Оставляются только пары с \(u \lt v\) и \(|u|,|v|\le 2X\), потому что только такие величины могут быть суммами двух чисел из \([-X,X]\). Затем списки сортируются и очищаются от повторов.
Когда пара сумм уже известна, третью координату не нужно искать перебором: она лежит в явном целочисленном интервале.
Если угол в \(A\), то \((x,y)=(a+b,a+c)\), поэтому \(b=x-a\), \(c=y-a\). Из условий \(-X\le a,b,c\le X\) и \(a \lt b \lt c\) следует
$$a\in\left[\max(-X,y-X),\ \min\!\left(X,x+X,\left\lfloor\frac{x-1}{2}\right\rfloor\right)\right].$$
Если угол в \(B\), то \((x,z)=(a+b,b+c)\), откуда
$$b\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{x}{2}\right\rfloor+1\right),\ \min\!\left(X,x+X,\left\lfloor\frac{z-1}{2}\right\rfloor\right)\right].$$
Если угол в \(C\), то \((y,z)=(a+c,b+c)\), откуда
$$c\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{z}{2}\right\rfloor+1\right),\ \min(X,y+X)\right].$$
Именно эти формулы реализованы в count_angle_a_for_pair,
count_angle_b_for_pair и count_angle_c_for_pair. Поскольку суммы могут быть
отрицательными, в C++ и Java используется собственная функция floor_div, а не обычное усечение при
делении.
У треугольника могут быть два угла по \(45^\circ\), поэтому нужно применять формулу
$$T_k(X)=N_A+N_B+N_C-N_{AB}-N_{AC}-N_{BC}.$$
По упорядоченным суммам \(x \lt y \lt z\) исходные параметры восстанавливаются так:
$$a=\frac{x+y-z}{2},\qquad b=\frac{x+z-y}{2},\qquad c=\frac{y+z-x}{2}.$$
Функция valid_triangle_from_sums проверяет именно это: строгий порядок, чётность суммы
\(x+y+z\) и ограничения \(|a|,|b|,|c|\le X\). Пересечения семейств находятся линейным слиянием отсортированных
списков.
Возьмём \(k=1\) и \((a,b,c)=(-3,0,2)\). Тогда точки равны \(A=(-3,9)\), \(B=(0,0)\), \(C=(2,4)\), а
$$x=a+b=-3,\qquad z=b+c=2.$$
Условие для угла в \(B\) принимает вид
$$\left(x+1\right)\left(z-1\right)=(-2)(1)=-2=-2\cdot 1^2,$$
поэтому этот треугольник попадает в семейство \(B\). Более крупная контрольная проверка даёт
$$F(1,10)=41,$$
и это именно то значение, которое зашито в C++-коде как checkpoint.
C++-решение один раз строит таблицу SPF до максимального нужного \(k\), в
factor_2k_squared факторизует каждое \(2k^2\), рекурсивно порождает все делители, в
build_pairs_for_k собирает два списка пар-кандидатов, суммирует длины интервалов и затем тремя
линейными merge-проходами вычитает пересечения. В C++ диапазон по \(k\) можно распараллелить по потокам. Файл
Python не является отдельной математической реализацией: это тонкая обёртка, которая компилирует и запускает
C++-решение и разбирает его вывод. Файл Java — прямой порт той же арифметической схемы с
LongStream.rangeClosed(...).parallel().
Построение SPF-решета до \(K\) требует \(O(K\log\log K)\) времени и \(O(K)\) памяти. Для фиксированного \(k\) обозначим через \(D_k=d(2k^2)\) число делителей \(2k^2\). Генерация делителей стоит \(O(D_k)\), интервальный подсчёт линейный по числу отфильтрованных пар, а сортировка с удалением дублей доминирует и стоит порядка \(O(D_k\log D_k)\). Все три коррекции пересечений после сортировки линейны. Итого:
$$O\!\left(K\log\log K+\sum_{k=1}^{K} D_k\log D_k\right),$$
при \(O(K)\) глобальной памяти для решета и \(O(D_k)\) временной памяти на поток.
لكل عدد صحيح \(k \ge 1\) ندرس القطع المكافئ \(y=\dfrac{x^2}{k}\). نختار أعدادًا صحيحة \(a \lt b \lt c\) بحيث \(|a|,|b|,|c|\le X\)، ثم نبني النقاط \(A=\left(a,\dfrac{a^2}{k}\right)\)، \(B=\left(b,\dfrac{b^2}{k}\right)\)، \(C=\left(c,\dfrac{c^2}{k}\right)\). المطلوب هو عدّ المثلثات \(ABC\) التي تملك زاوية واحدة على الأقل مقدارها \(45^\circ\). إذا رمزنا لهذا العدد عند \(k\) ثابتة بـ \(T_k(X)\)، فإن البرنامج يحسب
$$F(K,X)=\sum_{k=1}^{K} T_k(X).$$
الاختزال الحاسم هو أن ميل الوتر على هذا القطع المكافئ يعتمد فقط على مجموع إحداثيي \(x\) للنقطتين، مثل \(a+b\). لذلك تتحول المسألة من هندسة مباشرة إلى معادلات قواسم للعدد \(2k^2\) مع عدّ دقيق عبر فترات صحيحة.
نعرّف
$$x=a+b,\qquad y=a+c,\qquad z=b+c.$$
وبما أن \(a \lt b \lt c\) فإن \(x \lt y \lt z\). ميل الوتر بين نقطتين على \(y=\dfrac{x^2}{k}\) يساوي
$$m_{uv}=\frac{v^2-u^2}{k(v-u)}=\frac{u+v}{k}.$$
إذن ميول أضلاع المثلث هي
$$m_{AB}=\frac{x}{k},\qquad m_{AC}=\frac{y}{k},\qquad m_{BC}=\frac{z}{k}.$$
وهذا يعني أن شرط الزاوية يمكن كتابته بالكامل بدلالة \(x,y,z\) بدلًا من التعامل المباشر مع \(a^2,b^2,c^2\).
عند الرأس \(A\)، يكون متجها الاتجاه بعد التحجيم متناسبين مع \((k,x)\) و\((k,y)\). شرط الزاوية \(45^\circ\) يعني أن مقدار حاصل الضرب الاتجاهي يساوي حاصل الضرب القياسي:
$$k(y-x)=k^2+xy.$$
وبإعادة الترتيب نحصل على
$$xy+kx-ky+k^2=0,$$
أي
$$\boxed{(x-k)(y+k)=-2k^2.}$$
وعند الرأس \(B\) يكون المتجهان المتناسبان هما \((-k,-x)\) و\((k,z)\)، ومنه
$$k(z-x)=-(k^2+xz),$$
وبالتالي
$$\boxed{(x+k)(z-k)=-2k^2.}$$
وبالتماثل نحصل عند الرأس \(C\) على
$$\boxed{(y-k)(z+k)=-2k^2.}$$
إذًا تتحول مسألة الزاوية \(45^\circ\) إلى ثلاث معادلات تحليل بعامل ثابت هو \(-2k^2\)، من دون أي حسابات عائمة للزوايا.
نكتب \(pq=-2k^2\). التنفيذ يمرّ على كل قاسم موجب \(d\mid 2k^2\)، ثم يأخذ الإشارتين \(p=\pm d\)، ويحسب \(q=-2k^2/p\).
في عائلتي \(A\) و\(C\) نحل \((u-k)(v+k)=-2k^2\)، ولذلك
$$u=p+k,\qquad v=q-k.$$
وفي عائلة \(B\) نحل \((u+k)(v-k)=-2k^2\)، ولذلك
$$u=p-k,\qquad v=q+k.$$
لا نحتفظ إلا بالأزواج التي تحقق \(u \lt v\) و\(|u|,|v|\le 2X\)، لأن هذه فقط يمكن أن تظهر كمجاميع لعددين من \([-X,X]\). ثم تُرتّب القوائم وتُزال التكرارات.
بعد معرفة زوج المجاميع الصحيح، لا نحتاج إلى بحث جديد؛ بل يكفي حساب طول فترة صحيحة صريحة.
إذا كانت الزاوية عند \(A\)، فإن \((x,y)=(a+b,a+c)\)، ومنه \(b=x-a\) و\(c=y-a\). باستخدام القيود \(-X\le a,b,c\le X\) والترتيب \(a \lt b \lt c\)، نحصل على
$$a\in\left[\max(-X,y-X),\ \min\!\left(X,x+X,\left\lfloor\frac{x-1}{2}\right\rfloor\right)\right].$$
إذا كانت الزاوية عند \(B\)، بحيث \((x,z)=(a+b,b+c)\)، نحصل على
$$b\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{x}{2}\right\rfloor+1\right),\ \min\!\left(X,x+X,\left\lfloor\frac{z-1}{2}\right\rfloor\right)\right].$$
وإذا كانت الزاوية عند \(C\)، بحيث \((y,z)=(a+c,b+c)\)، نحصل على
$$c\in\left[\max\!\left(-X,z-X,\left\lfloor\frac{z}{2}\right\rfloor+1\right),\ \min(X,y+X)\right].$$
الدوال count_angle_a_for_pair وcount_angle_b_for_pair و
count_angle_c_for_pair تطبق هذه الصيغ حرفيًا. ولأن المجاميع قد تكون سالبة، فإن C++ وJava
تستخدمان دالة floor_div حقيقية بدل القسمة المقتطعة.
قد يملك مثلث واحد زاويتين مقدار كل منهما \(45^\circ\)، لذلك نستخدم
$$T_k(X)=N_A+N_B+N_C-N_{AB}-N_{AC}-N_{BC}.$$
ومن المجاميع المرتبة \(x \lt y \lt z\) نستعيد القيم الأصلية عبر
$$a=\frac{x+y-z}{2},\qquad b=\frac{x+z-y}{2},\qquad c=\frac{y+z-x}{2}.$$
ولهذا تفحص الدالة valid_triangle_from_sums الترتيب الصارم، وكون \(x+y+z\) زوجيًا، والحدود
\(|a|,|b|,|c|\le X\). أما التقاطعات فتعالجها الخوارزمية بعمليات دمج خطية على قوائم مرتبة.
خذ \(k=1\) و\((a,b,c)=(-3,0,2)\). حينها تكون النقاط \(A=(-3,9)\)، \(B=(0,0)\)، \(C=(2,4)\)، ولدينا
$$x=a+b=-3,\qquad z=b+c=2.$$
فتصبح معادلة الزاوية عند \(B\)
$$\left(x+1\right)\left(z-1\right)=(-2)(1)=-2=-2\cdot 1^2,$$
ومن ثم يُحسب هذا المثلث ضمن عائلة \(B\). وكفحص أكبر يؤكد البرنامج أيضًا أن
$$F(1,10)=41,$$
وهي نفس القيمة المرجعية المضمّنة في ملف C++.
نسخة C++ تبني جدول SPF مرة واحدة حتى أكبر \(k\) مطلوب، ثم تفكك كل \(2k^2\) في
factor_2k_squared، وتولد جميع القواسم تكراريًا، وتبني قائمتي الأزواج المرشحة في
build_pairs_for_k، ثم تجمع أطوال الفترات وتطرح التقاطعات عبر ثلاث عمليات دمج مرتبة. ويمكن لنسخة
C++ توزيع قيم \(k\) على عدة خيوط. ملف Python ليس تنفيذًا رياضيًا ثانيًا، بل جسرًا خفيفًا يترجم ويشغّل محلل
C++ ثم يقرأ الناتج. أما ملف Java فهو نقل مباشر لنفس القلب الحسابي ويوازي العمل باستخدام
LongStream.rangeClosed(...).parallel().
بناء غربال SPF حتى \(K\) يكلف \(O(K\log\log K)\) زمنًا و\(O(K)\) ذاكرة. ولـ \(k\) ثابتة، إذا رمزنا بعدد قواسم \(2k^2\) بـ \(D_k=d(2k^2)\)، فإن توليد القواسم يكلف \(O(D_k)\)، وعدّ الفترات خطي في عدد الأزواج المتبقية، بينما تهيمن عمليتا الفرز وإزالة التكرار بكلفة تقريبية \(O(D_k\log D_k)\). وتصحيحات التقاطع الثلاثة خطية بعد الفرز. لذلك يكون التعقيد الكلي
$$O\!\left(K\log\log K+\sum_{k=1}^{K} D_k\log D_k\right),$$
مع \(O(K)\) ذاكرة عامة للغربال و\(O(D_k)\) ذاكرة عمل مؤقتة لكل خيط.