A geometric triangle here means an integer-sided triangle whose side lengths are in geometric progression. If the sides are ordered as \(a \le b \le c\), then the condition is \(b^2 = ac\). For a perimeter limit \(L\), we must count all such triangles with \(a+b+c \le L\).
The local solution files reduce the problem to a sum over primitive parameter pairs \((p,q)\). The full argument has three layers: an exact parameterization of all integer geometric triangles, a triangle-inequality bound on the ratio \(q/p\), and a scaling count for all multiples of each primitive triangle.
Let \((a,b,c)\) be an integer geometric triangle with \(a \le b \le c\). Since the sides are in geometric progression,
$$b^2 = ac.$$
Set \(m=\gcd(a,c)\), and write
$$a=mu,\qquad c=mv,\qquad \gcd(u,v)=1.$$
Then \(b^2 = m^2uv\), so \(uv\) is a square. Because \(u\) and \(v\) are coprime, each must itself be a square. Hence there exist coprime integers \(p,q\) such that
$$u=p^2,\qquad v=q^2,\qquad \gcd(p,q)=1.$$
Therefore every integer geometric triangle has the form
$$a=mp^2,\qquad b=mpq,\qquad c=mq^2,$$
with \(m \ge 1\), \(1 \le p \le q\), and \(\gcd(p,q)=1\). Conversely, every triple of this form satisfies \(b^2=ac\), so the parameterization is exact and unique once \(p \le q\) and \(\gcd(p,q)=1\) are imposed.
The only nontrivial triangle inequality is \(c \lt a+b\). Substituting the parameterization gives
$$mq^2 \lt mp^2 + mpq \iff q^2 \lt p^2 + pq.$$
Divide by \(p^2\) and set \(x=q/p\). Then
$$x^2 - x - 1 \lt 0.$$
The positive root is the golden ratio
$$\varphi = \frac{1+\sqrt{5}}{2},$$
so admissible ratios satisfy
$$1 \le \frac{q}{p} \lt \varphi,\qquad q \lt \varphi p.$$
This is why the code computes an integer upper bound `q_max_triangle(p)` by starting from \(\varphi p\) and then correcting the boundary with exact arithmetic.
The perimeter of the triangle \((mp^2,mpq,mq^2)\) is
$$P = m(p^2 + pq + q^2).$$
For a fixed primitive pair \((p,q)\), the allowed scale factors \(m\) are exactly
$$1 \le m \le \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.$$
So the primitive pair \((p,q)\) contributes
$$\left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor$$
different triangles. Summing over all primitive ratios yields the counting formula used by the solver:
$$\boxed{G(L)=\sum_{\substack{p\ge 1\\ q\ge p\\ \gcd(p,q)=1\\ q^2 \lt p^2+pq}} \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.}$$
Because \(q \ge p\), the smallest primitive perimeter for a fixed \(p\) occurs at \(q=p\), namely \(p^2+pq+q^2=3p^2\). Therefore no contribution is possible once
$$3p^2 \gt L,$$
so the outer loop only needs
$$p \le p_{\max} = \left\lfloor\sqrt{\frac{L}{3}}\right\rfloor.$$
For fixed \(p\), the perimeter inequality
$$p^2+pq+q^2 \le L$$
is quadratic in \(q\). Solving it gives
$$q \le \left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor.$$
The implementation names this second bound `q_max_for_norm(p, L)`, and finally uses
$$q_{\max}(p)=\min\!\left(\left\lfloor \varphi p \right\rfloor,\left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor\right).$$
The primitive pairs \((p,q)\) that survive both bounds are
$$ (1,1),\ (2,3),\ (3,4),\ (4,5),\ (5,6). $$
Their primitive perimeters are
$$3,\ 19,\ 37,\ 61,\ 91.$$
Hence
$$G(100)=\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{19}\right\rfloor+\left\lfloor\frac{100}{37}\right\rfloor+\left\lfloor\frac{100}{61}\right\rfloor+\left\lfloor\frac{100}{91}\right\rfloor=33+5+2+1+1=42.$$
This matches the statement checkpoint \(G(100)=42\) that the C++ file verifies automatically.
A naive implementation would inspect every \(q\) individually. The optimized solver instead counts coprime values in an interval \([A,B]\) by inclusion-exclusion over the prime divisors of \(p\):
$$C_p(A,B)=\left|\{q\in[A,B]:\gcd(p,q)=1\}\right|=\sum_{d\mid p}\mu(d)\left(\left\lfloor\frac{B}{d}\right\rfloor-\left\lfloor\frac{A-1}{d}\right\rfloor\right).$$
To evaluate this quickly, the code factors \(p\) with a smallest-prime-factor sieve, extracts the distinct primes of \(p\), and enumerates the squarefree divisors together with their Möbius signs \(\mu(d)\in\{-1,1\}\). For very short intervals, both the C++ and Java implementations switch to direct \(\gcd\) tests because that is cheaper than running the divisor sum.
For fixed \(p\), define the primitive perimeter form
$$N(p,q)=p^2+pq+q^2,\qquad t(q)=\left\lfloor\frac{L}{N(p,q)}\right\rfloor.$$
Since \(N(p,q)\) is increasing in \(q\), the quotient \(t(q)\) stays constant on contiguous ranges of \(q\). If a block starts at \(q=\ell\), the code sets
$$t=\left\lfloor\frac{L}{N(p,\ell)}\right\rfloor,\qquad M=\left\lfloor\frac{L}{t}\right\rfloor.$$
Then the same quotient holds precisely while \(N(p,q)\le M\). So the block ends at the largest \(r\) satisfying that inequality, which is found by another call to `q_max_for_norm(p, M)`. The whole block contributes
$$t\cdot C_p(\ell,r).$$
This quotient-blocking step is the main reason the optimized solution avoids a full scan over all \(q\).
The C++ file is the main optimized implementation. It precomputes smallest prime factors up to \(p_{\max}=\lfloor\sqrt{L/3}\rfloor\), processes each \(p\), and optionally parallelizes independent \(p\)-values across threads. It also validates the mathematics by checking the statement values \(G(100)=42\), \(G(1000)=532\), \(G(10^4)=6427\), \(G(10^5)=75243\), \(G(10^6)=861805\), and by comparing fast and brute-force counts on several small limits. The Java file implements the same mathematics in a simpler single-threaded form with `long`. The Python file is intentionally a bridge: it compiles and runs the C++ solver so that Python returns exactly the same validated result.
The sieve up to \(p_{\max}\) costs \(O(p_{\max}\log\log p_{\max})\) time and \(O(p_{\max})\) memory. A naive double loop over all admissible \((p,q)\) pairs is essentially linear in \(L\), because \(p\) ranges up to \(O(\sqrt L)\) and each \(p\) has \(O(p)\) possible \(q\)-values. The implemented solver replaces that raw scan by quotient blocks and Möbius-weighted interval counts. The exact number of blocks depends on the floor-division structure, so the sharp asymptotic is subtle, but in practice it is dramatically smaller than the naive scan, and each block touches only the squarefree divisors of one \(p\).
Ein geometrisches Dreieck bedeutet hier ein ganzzahliges Dreieck, dessen Seitenlängen eine geometrische Folge bilden. Sind die Seiten als \(a \le b \le c\) geordnet, dann gilt \(b^2 = ac\). Für eine Umfangsschranke \(L\) sollen alle solchen Dreiecke mit \(a+b+c \le L\) gezählt werden.
Die lokalen Lösungsdateien reduzieren das Problem auf eine Summe über primitive Parameterpaare \((p,q)\). Die Argumentation besteht aus drei Teilen: einer exakten Parametrisierung aller ganzzahligen geometrischen Dreiecke, einer Schranke aus der Dreiecksungleichung und einer Skalierungszählung für alle Vielfachen jedes primitiven Dreiecks.
Sei \((a,b,c)\) ein ganzzahliges geometrisches Dreieck mit \(a \le b \le c\). Wegen der geometrischen Folge gilt
$$b^2 = ac.$$
Setze \(m=\gcd(a,c)\) und schreibe
$$a=mu,\qquad c=mv,\qquad \gcd(u,v)=1.$$
Dann ist \(b^2=m^2uv\), also ist \(uv\) ein Quadrat. Da \(u\) und \(v\) teilerfremd sind, muss jeder Faktor einzeln ein Quadrat sein. Es existieren also teilerfremde ganze Zahlen \(p,q\) mit
$$u=p^2,\qquad v=q^2,\qquad \gcd(p,q)=1.$$
Somit hat jedes ganzzahlige geometrische Dreieck die Form
$$a=mp^2,\qquad b=mpq,\qquad c=mq^2,$$
mit \(m \ge 1\), \(1 \le p \le q\) und \(\gcd(p,q)=1\). Umgekehrt erfüllt jedes Tripel dieser Form \(b^2=ac\). Mit den Bedingungen \(p \le q\) und \(\gcd(p,q)=1\) ist die Darstellung eindeutig.
Die einzige nichttriviale Dreiecksungleichung ist \(c \lt a+b\). Eingesetzt ergibt das
$$mq^2 \lt mp^2 + mpq \iff q^2 \lt p^2 + pq.$$
Nach Division durch \(p^2\) und mit \(x=q/p\) folgt
$$x^2 - x - 1 \lt 0.$$
Die positive Nullstelle ist der Goldene Schnitt
$$\varphi = \frac{1+\sqrt{5}}{2},$$
also gilt für zulässige Verhältnisse
$$1 \le \frac{q}{p} \lt \varphi,\qquad q \lt \varphi p.$$
Darum startet der Code für `q_max_triangle(p)` mit \(\varphi p\) und korrigiert anschließend die Grenze mit exakter Ganzzahlarithmetik.
Der Umfang des Dreiecks \((mp^2,mpq,mq^2)\) ist
$$P = m(p^2 + pq + q^2).$$
Für ein festes primitives Paar \((p,q)\) sind die zulässigen Skalierungsfaktoren genau
$$1 \le m \le \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.$$
Damit liefert \((p,q)\) genau
$$\left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor$$
Dreiecke. Summiert man über alle primitiven Verhältnisse, erhält man die im Solver verwendete Formel:
$$\boxed{G(L)=\sum_{\substack{p\ge 1\\ q\ge p\\ \gcd(p,q)=1\\ q^2 \lt p^2+pq}} \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.}$$
Wegen \(q \ge p\) tritt der kleinste primitive Umfang für festes \(p\) bei \(q=p\) auf, also bei \(3p^2\). Deshalb gibt es keinen Beitrag mehr, sobald
$$3p^2 \gt L,$$
und die äußere Schleife braucht nur
$$p \le p_{\max} = \left\lfloor\sqrt{\frac{L}{3}}\right\rfloor.$$
Für festes \(p\) ist die Umfangsbedingung
$$p^2+pq+q^2 \le L$$
eine quadratische Ungleichung in \(q\). Aufgelöst ergibt sie
$$q \le \left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor.$$
Diese zweite Grenze heißt im Code `q_max_for_norm(p, L)`, und tatsächlich wird verwendet
$$q_{\max}(p)=\min\!\left(\left\lfloor \varphi p \right\rfloor,\left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor\right).$$
Die primitiven Paare \((p,q)\), die beide Schranken erfüllen, sind
$$ (1,1),\ (2,3),\ (3,4),\ (4,5),\ (5,6). $$
Die zugehörigen primitiven Umfänge sind
$$3,\ 19,\ 37,\ 61,\ 91.$$
Also
$$G(100)=\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{19}\right\rfloor+\left\lfloor\frac{100}{37}\right\rfloor+\left\lfloor\frac{100}{61}\right\rfloor+\left\lfloor\frac{100}{91}\right\rfloor=33+5+2+1+1=42.$$
Das stimmt mit dem Prüfwert \(G(100)=42\) überein, den die C++-Datei direkt verifiziert.
Eine naive Lösung würde jedes \(q\) einzeln prüfen. Der optimierte Solver zählt teilerfremde Werte in einem Intervall \([A,B]\) stattdessen per Inklusion-Exklusion über die Primteiler von \(p\):
$$C_p(A,B)=\left|\{q\in[A,B]:\gcd(p,q)=1\}\right|=\sum_{d\mid p}\mu(d)\left(\left\lfloor\frac{B}{d}\right\rfloor-\left\lfloor\frac{A-1}{d}\right\rfloor\right).$$
Zur schnellen Auswertung faktorisiert der Code \(p\) mit einer SPF-Tabelle (smallest prime factor), extrahiert die verschiedenen Primfaktoren und erzeugt daraus alle quadratfreien Teiler mit ihren Möbius-Vorzeichen \(\mu(d)\in\{-1,1\}\). Für sehr kurze Intervalle schalten sowohl C++ als auch Java auf direkte \(\gcd\)-Tests um, weil das dort billiger ist.
Für festes \(p\) definiert der Code die primitive Umfangsform
$$N(p,q)=p^2+pq+q^2,\qquad t(q)=\left\lfloor\frac{L}{N(p,q)}\right\rfloor.$$
Da \(N(p,q)\) mit \(q\) wächst, bleibt der Quotient \(t(q)\) auf zusammenhängenden \(q\)-Blöcken konstant. Beginnt ein Block bei \(q=\ell\), dann setzt der Code
$$t=\left\lfloor\frac{L}{N(p,\ell)}\right\rfloor,\qquad M=\left\lfloor\frac{L}{t}\right\rfloor.$$
Genau solange \(N(p,q)\le M\) gilt, bleibt derselbe Quotient erhalten. Das Blockende ist also das größte \(r\) mit dieser Eigenschaft, gefunden durch einen weiteren Aufruf von `q_max_for_norm(p, M)`. Der gesamte Block trägt bei mit
$$t\cdot C_p(\ell,r).$$
Dieses Quotienten-Blocking ist der Hauptgrund, warum der optimierte Solver nicht alle \(q\) einzeln besuchen muss.
Die C++-Datei ist die voll optimierte Hauptimplementierung. Sie berechnet zunächst kleinste Primfaktoren bis \(p_{\max}=\lfloor\sqrt{L/3}\rfloor\), verarbeitet dann jedes \(p\) und kann unabhängige \(p\)-Werte über Threads parallel auswerten. Zusätzlich überprüft sie die Mathematik mit den Statement-Werten \(G(100)=42\), \(G(1000)=532\), \(G(10^4)=6427\), \(G(10^5)=75243\), \(G(10^6)=861805\) sowie mit Fast-vs-Brute-Force-Tests für kleine Grenzen. Die Java-Datei implementiert dieselbe Mathematik in einer einfacheren einthreadigen Form mit `long`. Die Python-Datei ist bewusst nur eine Brücke: Sie kompiliert und startet den C++-Solver, damit Python exakt dasselbe validierte Ergebnis liefert.
Das Sieb bis \(p_{\max}\) benötigt \(O(p_{\max}\log\log p_{\max})\) Zeit und \(O(p_{\max})\) Speicher. Eine naive Doppelschleife über alle zulässigen \((p,q)\)-Paare ist im Wesentlichen linear in \(L\), weil \(p\) bis \(O(\sqrt L)\) läuft und jedes \(p\) noch \(O(p)\) mögliche \(q\)-Werte hat. Der implementierte Solver ersetzt diesen Rohscan durch Quotientenblöcke und Möbius-gewichtete Intervallsummen. Die exakte Blockanzahl hängt von der Struktur der Floor-Divisionen ab und ist daher asymptotisch nicht ganz so sauber zu formulieren, liegt in der Praxis aber weit unter der naiven Vollsuche, und jeder Block berührt nur die quadratfreien Teiler eines einzigen \(p\).
Buradaki geometrik üçgen, kenar uzunlukları geometrik dizide olan bir tamsayı üçgenidir. Kenarlar \(a \le b \le c\) sırasına konursa koşul \(b^2 = ac\) olur. Çevre sınırı \(L\) verildiğinde amaç, \(a+b+c \le L\) koşulunu sağlayan tüm bu üçgenleri saymaktır.
Yerel çözüm dosyaları problemi ilkel parametre çiftleri \((p,q)\) üzerinden bir toplama indirger. Gerekçe üç parçadan oluşur: tüm tamsayı geometrik üçgenlerin tam parametrelemesi, üçgen eşitsizliğinin verdiği oran sınırı ve her ilkel üçgenin katlarını sayan ölçekleme adımı.
\((a,b,c)\), \(a \le b \le c\) olacak şekilde bir tamsayı geometrik üçgen olsun. Geometrik dizi şartı
$$b^2 = ac$$
eşitliğini verir. \(m=\gcd(a,c)\) alıp
$$a=mu,\qquad c=mv,\qquad \gcd(u,v)=1$$
yazalım. O zaman \(b^2=m^2uv\) olur; yani \(uv\) bir tam karedir. \(u\) ile \(v\) aralarında asal olduğundan her biri tek başına kare olmak zorundadır. Dolayısıyla aralarında asal \(p,q\) tamsayıları için
$$u=p^2,\qquad v=q^2,\qquad \gcd(p,q)=1$$
yazabiliriz. Böylece her tamsayı geometrik üçgen şu biçimdedir:
$$a=mp^2,\qquad b=mpq,\qquad c=mq^2,$$
burada \(m \ge 1\), \(1 \le p \le q\) ve \(\gcd(p,q)=1\). Tersine, bu biçimdeki her üçlü için \(b^2=ac\) sağlandığından parametreleme tamdır. \(p \le q\) ve \(\gcd(p,q)=1\) koşullarıyla gösterim tektir.
Üçgen eşitsizliklerinden yalnızca \(c \lt a+b\) yeni bilgi verir. Yerine koyarsak
$$mq^2 \lt mp^2 + mpq \iff q^2 \lt p^2 + pq.$$
\(p^2\) ile bölelim ve \(x=q/p\) yazalım:
$$x^2 - x - 1 \lt 0.$$
Bunun pozitif kökü altın orandır:
$$\varphi = \frac{1+\sqrt{5}}{2}.$$
Demek ki geçerli oranlar
$$1 \le \frac{q}{p} \lt \varphi,\qquad q \lt \varphi p$$
koşulunu sağlar. Kodun `q_max_triangle(p)` fonksiyonunun önce \(\varphi p\) civarından başlayıp sonra tam sayı aritmetiğiyle düzeltme yapmasının nedeni budur.
\((mp^2,mpq,mq^2)\) üçgeninin çevresi
$$P = m(p^2 + pq + q^2)$$
olur. Sabit bir ilkel \((p,q)\) çifti için uygun ölçek katsayıları
$$1 \le m \le \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor$$
aralığındadır. Yani \((p,q)\) çifti tam olarak
$$\left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor$$
adet üçgen üretir. Tüm ilkel oranlar üzerinde toplarsak çözümde kullanılan formül elde edilir:
$$\boxed{G(L)=\sum_{\substack{p\ge 1\\ q\ge p\\ \gcd(p,q)=1\\ q^2 \lt p^2+pq}} \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.}$$
\(q \ge p\) olduğundan sabit \(p\) için en küçük ilkel çevre \(q=p\) durumunda oluşur ve değeri \(3p^2\)'dir. Bu yüzden
$$3p^2 \gt L$$
olduğunda katkı kalmaz; dış döngü yalnızca
$$p \le p_{\max} = \left\lfloor\sqrt{\frac{L}{3}}\right\rfloor$$
değerlerine kadar gider. Sabit \(p\) için çevre eşitsizliği
$$p^2+pq+q^2 \le L$$
\(q\) açısından ikinci dereceden bir eşitsizliktir ve çözümü
$$q \le \left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor$$
şeklindedir. Kod bu ikinci üst sınırı `q_max_for_norm(p, L)` olarak hesaplar ve sonunda
$$q_{\max}(p)=\min\!\left(\left\lfloor \varphi p \right\rfloor,\left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor\right)$$
kullanılır.
Her iki sınırı da geçen ilkel çiftler
$$ (1,1),\ (2,3),\ (3,4),\ (4,5),\ (5,6) $$
olur. Bunların ilkel çevreleri
$$3,\ 19,\ 37,\ 61,\ 91$$
şeklindedir. Dolayısıyla
$$G(100)=\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{19}\right\rfloor+\left\lfloor\frac{100}{37}\right\rfloor+\left\lfloor\frac{100}{61}\right\rfloor+\left\lfloor\frac{100}{91}\right\rfloor=33+5+2+1+1=42.$$
Bu, C++ dosyasındaki \(G(100)=42\) kontrol noktasıyla aynıdır.
Naif yaklaşım her \(q\) değerini tek tek kontrol eder. Hızlı çözümdese \([A,B]\) aralığındaki \(\gcd(p,q)=1\) sayısı, \(p\)'nin asal bölenleri üzerinden içerme-dışlama ile hesaplanır:
$$C_p(A,B)=\left|\{q\in[A,B]:\gcd(p,q)=1\}\right|=\sum_{d\mid p}\mu(d)\left(\left\lfloor\frac{B}{d}\right\rfloor-\left\lfloor\frac{A-1}{d}\right\rfloor\right).$$
Bunu hızlı yapmak için kod, en küçük asal bölen tablosu ile \(p\)'yi çarpanlara ayırır, farklı asal çarpanları çıkarır, sonra kareden arınmış bölenleri ve Möbius işaretlerini \(\mu(d)\in\{-1,1\}\) oluşturur. Aralık çok kısaysa hem C++ hem Java doğrudan \(\gcd\) testi yapar; çünkü bu durumda bölen toplamı kurmaktan daha ucuzdur.
Sabit \(p\) için ilkel çevre biçimini
$$N(p,q)=p^2+pq+q^2,\qquad t(q)=\left\lfloor\frac{L}{N(p,q)}\right\rfloor$$
olarak tanımlayalım. \(N(p,q)\), \(q\) ile arttığı için bölüm değeri \(t(q)\) ardışık \(q\) bloklarında sabit kalır. Bir blok \(q=\ell\) noktasında başlıyorsa kod
$$t=\left\lfloor\frac{L}{N(p,\ell)}\right\rfloor,\qquad M=\left\lfloor\frac{L}{t}\right\rfloor$$
değerlerini alır. Aynı bölüm, tam olarak \(N(p,q)\le M\) olduğu sürece geçerlidir. Bu yüzden blok sonu, bu koşulu sağlayan en büyük \(r\) değeridir; kod bunu `q_max_for_norm(p, M)` ile bulur. Tüm blok katkısı
$$t\cdot C_p(\ell,r)$$
olur. İç döngüyü hızlandıran ana fikir budur.
C++ dosyası ana optimize çözümdür. Önce \(p_{\max}=\lfloor\sqrt{L/3}\rfloor\) değerine kadar en küçük asal bölen tablosunu kurar, sonra her \(p\) için katkıyı hesaplar ve istenirse bağımsız \(p\) değerlerini çok iş parçacıklı çalıştırır. Ayrıca matematiği doğrulamak için \(G(100)=42\), \(G(1000)=532\), \(G(10^4)=6427\), \(G(10^5)=75243\), \(G(10^6)=861805\) kontrol noktalarını ve küçük limitlerde brute-force karşılaştırmalarını çalıştırır. Java dosyası aynı matematiği `long` ile daha sade ve tek iş parçacıklı biçimde uygular. Python dosyası ise bilerek köprü olarak yazılmıştır; C++ çözücüyü derleyip çalıştırır ve böylece Python tarafı da aynı doğrulanmış sonucu üretir.
\(p_{\max}\)'e kadar olan sieve aşaması \(O(p_{\max}\log\log p_{\max})\) zaman ve \(O(p_{\max})\) bellek ister. Tüm geçerli \((p,q)\) çiftlerini çift döngüyle gezmek pratikte \(L\) mertebesinde maliyetlidir; çünkü \(p=O(\sqrt L)\) ve her \(p\) için \(O(p)\) kadar \(q\) vardır. Gerçek implementasyon bu ham taramayı bölüm blokları ve Möbius ağırlıklı aralık sayımlarıyla değiştirir. Tam blok sayısı floor-bölme yapısına bağlı olduğu için keskin asimptotik yazmak zordur; yine de pratikte naif taramadan çok daha az iş yapılır ve her blok yalnızca tek bir \(p\)'nin kareden arınmış bölenlerini kullanır.
Aquí un triángulo geométrico es un triángulo con lados enteros cuyos lados están en progresión geométrica. Si los ordenamos como \(a \le b \le c\), la condición es \(b^2 = ac\). Dado un límite de perímetro \(L\), hay que contar todos esos triángulos con \(a+b+c \le L\).
Los archivos de solución locales reducen el problema a una suma sobre pares primitivos \((p,q)\). La idea completa tiene tres partes: una parametrización exacta de todos los triángulos geométricos enteros, una cota procedente de la desigualdad triangular y un conteo por escalado de todos los múltiplos de cada triángulo primitivo.
Sea \((a,b,c)\) un triángulo geométrico entero con \(a \le b \le c\). Como los lados forman una progresión geométrica,
$$b^2 = ac.$$
Tomamos \(m=\gcd(a,c)\) y escribimos
$$a=mu,\qquad c=mv,\qquad \gcd(u,v)=1.$$
Entonces \(b^2=m^2uv\), de modo que \(uv\) es un cuadrado. Como \(u\) y \(v\) son coprimos, cada uno debe ser un cuadrado por separado. Existen por tanto enteros coprimos \(p,q\) tales que
$$u=p^2,\qquad v=q^2,\qquad \gcd(p,q)=1.$$
Así, todo triángulo geométrico entero tiene la forma
$$a=mp^2,\qquad b=mpq,\qquad c=mq^2,$$
con \(m \ge 1\), \(1 \le p \le q\) y \(\gcd(p,q)=1\). A la inversa, todo triple de esta forma satisface \(b^2=ac\), así que la parametrización es exacta. Con \(p \le q\) y \(\gcd(p,q)=1\), la representación es única.
La única desigualdad triangular no trivial es \(c \lt a+b\). Sustituyendo, obtenemos
$$mq^2 \lt mp^2 + mpq \iff q^2 \lt p^2 + pq.$$
Dividiendo entre \(p^2\) y poniendo \(x=q/p\), resulta
$$x^2 - x - 1 \lt 0.$$
La raíz positiva es el número áureo
$$\varphi = \frac{1+\sqrt{5}}{2},$$
de modo que los cocientes válidos cumplen
$$1 \le \frac{q}{p} \lt \varphi,\qquad q \lt \varphi p.$$
Por eso el código calcula `q_max_triangle(p)` partiendo de \(\varphi p\) y luego corrige el borde con aritmética exacta.
El perímetro del triángulo \((mp^2,mpq,mq^2)\) es
$$P = m(p^2 + pq + q^2).$$
Para un par primitivo fijo \((p,q)\), los factores de escala permitidos son exactamente
$$1 \le m \le \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.$$
Por tanto, el par \((p,q)\) aporta
$$\left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor$$
triángulos distintos. Sumando sobre todas las razones primitivas se obtiene la fórmula central del programa:
$$\boxed{G(L)=\sum_{\substack{p\ge 1\\ q\ge p\\ \gcd(p,q)=1\\ q^2 \lt p^2+pq}} \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.}$$
Como \(q \ge p\), el perímetro primitivo mínimo para un \(p\) fijo ocurre en \(q=p\), y vale \(3p^2\). Así, ya no hay contribución cuando
$$3p^2 \gt L,$$
por lo que el bucle exterior solo necesita
$$p \le p_{\max} = \left\lfloor\sqrt{\frac{L}{3}}\right\rfloor.$$
Para un \(p\) fijo, la restricción de perímetro
$$p^2+pq+q^2 \le L$$
es cuadrática en \(q\). Al resolverla se obtiene
$$q \le \left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor.$$
El código llama a esta segunda cota `q_max_for_norm(p, L)` y usa finalmente
$$q_{\max}(p)=\min\!\left(\left\lfloor \varphi p \right\rfloor,\left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor\right).$$
Los pares primitivos que sobreviven a ambas cotas son
$$ (1,1),\ (2,3),\ (3,4),\ (4,5),\ (5,6). $$
Sus perímetros primitivos son
$$3,\ 19,\ 37,\ 61,\ 91.$$
Entonces
$$G(100)=\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{19}\right\rfloor+\left\lfloor\frac{100}{37}\right\rfloor+\left\lfloor\frac{100}{61}\right\rfloor+\left\lfloor\frac{100}{91}\right\rfloor=33+5+2+1+1=42.$$
Eso coincide con el punto de control \(G(100)=42\) codificado en la validación de C++.
Una implementación ingenua revisaría cada \(q\) por separado. El solver rápido cuenta en cambio los valores coprimos dentro de un intervalo \([A,B]\) mediante inclusión-exclusión sobre los primos que dividen a \(p\):
$$C_p(A,B)=\left|\{q\in[A,B]:\gcd(p,q)=1\}\right|=\sum_{d\mid p}\mu(d)\left(\left\lfloor\frac{B}{d}\right\rfloor-\left\lfloor\frac{A-1}{d}\right\rfloor\right).$$
Para evaluarlo rápido, el código factoriza \(p\) con una criba de menor factor primo, extrae los primos distintos de \(p\) y enumera los divisores libres de cuadrados junto con sus signos de Möbius \(\mu(d)\in\{-1,1\}\). Cuando el intervalo es muy corto, tanto C++ como Java cambian a pruebas directas de \(\gcd\), porque ahí resulta más barato.
Para un \(p\) fijo, definimos la forma de perímetro primitivo
$$N(p,q)=p^2+pq+q^2,\qquad t(q)=\left\lfloor\frac{L}{N(p,q)}\right\rfloor.$$
Como \(N(p,q)\) crece con \(q\), el cociente \(t(q)\) permanece constante en bloques contiguos. Si un bloque empieza en \(q=\ell\), el código toma
$$t=\left\lfloor\frac{L}{N(p,\ell)}\right\rfloor,\qquad M=\left\lfloor\frac{L}{t}\right\rfloor.$$
El mismo cociente vale exactamente mientras \(N(p,q)\le M\). Por eso el bloque termina en el mayor \(r\) que cumple esa desigualdad, calculado mediante otra llamada a `q_max_for_norm(p, M)`. La contribución del bloque entero es
$$t\cdot C_p(\ell,r).$$
Este agrupamiento es la razón principal por la que la solución optimizada evita recorrer todos los \(q\) uno por uno.
El archivo C++ es la implementación optimizada principal. Precalcula los menores factores primos hasta \(p_{\max}=\lfloor\sqrt{L/3}\rfloor\), procesa cada \(p\) y puede paralelizar los distintos valores de \(p\) entre varios hilos. Además verifica la matemática con los valores del enunciado \(G(100)=42\), \(G(1000)=532\), \(G(10^4)=6427\), \(G(10^5)=75243\), \(G(10^6)=861805\), y con comparaciones entre la versión rápida y la fuerza bruta para límites pequeños. El archivo Java implementa la misma matemática en una versión monohilo más simple con `long`. El archivo Python es deliberadamente un puente: compila y ejecuta el solver de C++, de modo que Python devuelve exactamente el mismo resultado validado.
La criba hasta \(p_{\max}\) cuesta \(O(p_{\max}\log\log p_{\max})\) tiempo y \(O(p_{\max})\) memoria. Un doble bucle ingenuo sobre todos los pares admisibles \((p,q)\) es esencialmente lineal en \(L\), porque \(p\) llega hasta \(O(\sqrt L)\) y cada \(p\) tiene \(O(p)\) posibles valores de \(q\). La implementación real sustituye ese barrido bruto por bloques de cociente y recuentos intervalares ponderados por Möbius. El número exacto de bloques depende de la estructura de las divisiones enteras, así que el asintótico fino es más delicado, pero en la práctica el trabajo es muy inferior al de la búsqueda ingenua, y cada bloque solo toca los divisores libres de cuadrados de un único \(p\).
这里的“几何三角形”指边长为整数、且三边构成等比数列的三角形。若按 \(a \le b \le c\) 排序，则条件就是 \(b^2 = ac\)。给定周长上界 \(L\)，目标是统计所有满足 \(a+b+c \le L\) 的这类三角形。
本地解法文件把问题化为对原始参数对 \((p,q)\) 的求和。核心分成三层：先精确参数化所有整数等比三角形，再由 三角不等式得到 \(q/p\) 的范围，最后计算每个原始三角形可以放缩多少次。
设 \((a,b,c)\) 是一个满足 \(a \le b \le c\) 的整数等比三角形。因为三边成等比数列，所以
$$b^2 = ac.$$
令 \(m=\gcd(a,c)\)，并写成
$$a=mu,\qquad c=mv,\qquad \gcd(u,v)=1.$$
于是 \(b^2=m^2uv\)，说明 \(uv\) 是完全平方数。由于 \(u,v\) 互素，它们各自都必须是平方数。因此存在互素整数 \(p,q\)，使得
$$u=p^2,\qquad v=q^2,\qquad \gcd(p,q)=1.$$
所以每个整数等比三角形都可唯一写成
$$a=mp^2,\qquad b=mpq,\qquad c=mq^2,$$
其中 \(m \ge 1\)、\(1 \le p \le q\)、\(\gcd(p,q)=1\)。反过来，任何这样的三元组都满足 \(b^2=ac\)，因此这正是 全部解的参数化。
真正有内容的三角不等式只有 \(c \lt a+b\)。代入后得到
$$mq^2 \lt mp^2 + mpq \iff q^2 \lt p^2 + pq.$$
再除以 \(p^2\)，记 \(x=q/p\)，可化为
$$x^2 - x - 1 \lt 0.$$
它的正根是黄金比例
$$\varphi = \frac{1+\sqrt{5}}{2},$$
因此可行比值满足
$$1 \le \frac{q}{p} \lt \varphi,\qquad q \lt \varphi p.$$
这就是代码中 `q_max_triangle(p)` 先用 \(\varphi p\) 估计、再用精确整数运算修正边界的原因。
三角形 \((mp^2,mpq,mq^2)\) 的周长是
$$P = m(p^2 + pq + q^2).$$
对固定原始对 \((p,q)\)，允许的放缩因子正好满足
$$1 \le m \le \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.$$
因此该原始对贡献的三角形个数正是
$$\left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.$$
对所有原始比值求和，就得到程序实现的主公式：
$$\boxed{G(L)=\sum_{\substack{p\ge 1\\ q\ge p\\ \gcd(p,q)=1\\ q^2 \lt p^2+pq}} \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.}$$
因为 \(q \ge p\)，对固定 \(p\) 而言，最小原始周长出现在 \(q=p\) 时，即 \(3p^2\)。所以一旦
$$3p^2 \gt L,$$
就不可能再有贡献。外层循环只需枚举到
$$p \le p_{\max} = \left\lfloor\sqrt{\frac{L}{3}}\right\rfloor.$$
对于固定 \(p\)，周长条件
$$p^2+pq+q^2 \le L$$
是关于 \(q\) 的二次不等式，解得
$$q \le \left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor.$$
代码把这一上界写成 `q_max_for_norm(p, L)`，最终使用
$$q_{\max}(p)=\min\!\left(\left\lfloor \varphi p \right\rfloor,\left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor\right).$$
同时满足两类上界的原始参数对是
$$ (1,1),\ (2,3),\ (3,4),\ (4,5),\ (5,6). $$
对应的原始周长分别是
$$3,\ 19,\ 37,\ 61,\ 91.$$
于是
$$G(100)=\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{19}\right\rfloor+\left\lfloor\frac{100}{37}\right\rfloor+\left\lfloor\frac{100}{61}\right\rfloor+\left\lfloor\frac{100}{91}\right\rfloor=33+5+2+1+1=42.$$
这与 C++ 校验中的检查点 \(G(100)=42\) 完全一致。
朴素做法会逐个检查 \(q\)。优化版则在区间 \([A,B]\) 上直接统计与 \(p\) 互素的整数个数：
$$C_p(A,B)=\left|\{q\in[A,B]:\gcd(p,q)=1\}\right|=\sum_{d\mid p}\mu(d)\left(\left\lfloor\frac{B}{d}\right\rfloor-\left\lfloor\frac{A-1}{d}\right\rfloor\right).$$
为快速求值，代码先用最小质因子筛分解 \(p\)，提取不同质因子，再枚举所有平方自由因子以及相应的 Möbius 符号 \(\mu(d)\in\{-1,1\}\)。当区间极短时，C++ 和 Java 都会退回到直接做 \(\gcd\) 判断，因为那样反而更便宜。
对固定 \(p\)，定义原始周长二次型
$$N(p,q)=p^2+pq+q^2,\qquad t(q)=\left\lfloor\frac{L}{N(p,q)}\right\rfloor.$$
由于 \(N(p,q)\) 随 \(q\) 单调增加，所以 \(t(q)\) 会在若干连续区间上保持不变。若某一块从 \(q=\ell\) 开始，则代码 先计算
$$t=\left\lfloor\frac{L}{N(p,\ell)}\right\rfloor,\qquad M=\left\lfloor\frac{L}{t}\right\rfloor.$$
当且仅当 \(N(p,q)\le M\) 时，商值仍等于这个 \(t\)。因此该块终点就是满足该条件的最大 \(r\)，代码通过 `q_max_for_norm(p, M)` 找到它。整块贡献为
$$t\cdot C_p(\ell,r).$$
这一步是优化版避免逐个遍历所有 \(q\) 的关键。
C++ 文件是主优化实现。它先预处理到 \(p_{\max}=\lfloor\sqrt{L/3}\rfloor\) 的最小质因子表，再逐个处理 \(p\)，并可 选用多线程并行不同的 \(p\) 值。它还会自动验证题目给出的检查点 \(G(100)=42\)、\(G(1000)=532\)、 \(G(10^4)=6427\)、\(G(10^5)=75243\)、\(G(10^6)=861805\)，并在若干小范围上把快速算法和暴力算法对比。Java 文件用 `long` 单线程实现同一套数学。Python 文件则刻意作为桥接层：它编译并运行 C++ 求解器，因此 Python 返回 的就是与主实现完全一致、已经验证过的结果。
筛到 \(p_{\max}\) 的预处理需要 \(O(p_{\max}\log\log p_{\max})\) 时间和 \(O(p_{\max})\) 空间。若直接双重枚举所有可行 \((p,q)\)，整体代价基本是 \(L\) 量级，因为 \(p\) 到 \(O(\sqrt L)\)，而每个 \(p\) 对应 \(O(p)\) 个候选 \(q\)。 实际实现用商值分块和 Möbius 加权区间计数替代了这种原始扫描。精确块数取决于整除结构，严格渐近式并不那么简洁， 但在实践中远小于朴素遍历，而且每一块只需要访问某个固定 \(p\) 的平方自由因子。
Здесь под геометрическим треугольником понимается треугольник с целыми сторонами, образующими геометрическую прогрессию. Если упорядочить стороны как \(a \le b \le c\), то условие имеет вид \(b^2 = ac\). Для заданного ограничения на периметр \(L\) нужно посчитать все такие треугольники с \(a+b+c \le L\).
Локальные файлы решения сводят задачу к сумме по примитивным парам параметров \((p,q)\). Полная схема состоит из трёх частей: точной параметризации всех целочисленных геометрических треугольников, ограничения из неравенства треугольника и подсчёта всех кратных каждого примитивного треугольника.
Пусть \((a,b,c)\) — целочисленный геометрический треугольник и \(a \le b \le c\). Поскольку стороны образуют геометрическую прогрессию,
$$b^2 = ac.$$
Положим \(m=\gcd(a,c)\) и запишем
$$a=mu,\qquad c=mv,\qquad \gcd(u,v)=1.$$
Тогда \(b^2=m^2uv\), значит \(uv\) является квадратом. Поскольку \(u\) и \(v\) взаимно просты, каждый из них обязан быть квадратом. Следовательно, существуют взаимно простые целые \(p,q\), для которых
$$u=p^2,\qquad v=q^2,\qquad \gcd(p,q)=1.$$
Отсюда любой целочисленный геометрический треугольник имеет вид
$$a=mp^2,\qquad b=mpq,\qquad c=mq^2,$$
где \(m \ge 1\), \(1 \le p \le q\) и \(\gcd(p,q)=1\). Обратно, любой такой тройке автоматически соответствует равенство \(b^2=ac\), так что параметризация точна и при условиях \(p \le q\), \(\gcd(p,q)=1\) единственна.
Единственное нетривиальное неравенство — это \(c \lt a+b\). Подстановка параметров даёт
$$mq^2 \lt mp^2 + mpq \iff q^2 \lt p^2 + pq.$$
Разделив на \(p^2\) и обозначив \(x=q/p\), получаем
$$x^2 - x - 1 \lt 0.$$
Положительный корень равен золотому сечению
$$\varphi = \frac{1+\sqrt{5}}{2},$$
поэтому допустимые отношения удовлетворяют
$$1 \le \frac{q}{p} \lt \varphi,\qquad q \lt \varphi p.$$
Именно поэтому функция `q_max_triangle(p)` в коде сначала оценивает границу через \(\varphi p\), а затем уточняет её точной целочисленной проверкой.
Периметр треугольника \((mp^2,mpq,mq^2)\) равен
$$P = m(p^2 + pq + q^2).$$
Для фиксированной примитивной пары \((p,q)\) разрешённые коэффициенты масштаба \(m\) задаются неравенством
$$1 \le m \le \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.$$
Следовательно, пара \((p,q)\) даёт ровно
$$\left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor$$
различных треугольников. Суммирование по всем примитивным отношениям приводит к формуле, реализованной в программе:
$$\boxed{G(L)=\sum_{\substack{p\ge 1\\ q\ge p\\ \gcd(p,q)=1\\ q^2 \lt p^2+pq}} \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.}$$
Так как \(q \ge p\), минимальный примитивный периметр при фиксированном \(p\) достигается при \(q=p\) и равен \(3p^2\). Значит, вклад исчезает, как только
$$3p^2 \gt L,$$
поэтому внешний цикл достаточно вести до
$$p \le p_{\max} = \left\lfloor\sqrt{\frac{L}{3}}\right\rfloor.$$
Для фиксированного \(p\) условие на периметр
$$p^2+pq+q^2 \le L$$
является квадратным неравенством по \(q\), и из него следует
$$q \le \left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor.$$
В коде эта вторая граница реализована как `q_max_for_norm(p, L)`, а фактически используется
$$q_{\max}(p)=\min\!\left(\left\lfloor \varphi p \right\rfloor,\left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor\right).$$
Примитивные пары \((p,q)\), проходящие обе границы, таковы:
$$ (1,1),\ (2,3),\ (3,4),\ (4,5),\ (5,6). $$
Их примитивные периметры равны
$$3,\ 19,\ 37,\ 61,\ 91.$$
Поэтому
$$G(100)=\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{19}\right\rfloor+\left\lfloor\frac{100}{37}\right\rfloor+\left\lfloor\frac{100}{61}\right\rfloor+\left\lfloor\frac{100}{91}\right\rfloor=33+5+2+1+1=42.$$
Это совпадает с контрольным значением \(G(100)=42\), зашитым в C++-проверки.
Наивный алгоритм проверял бы каждое \(q\) отдельно. Оптимизированный решатель считает количество значений в интервале \([A,B]\), взаимно простых с \(p\), через включение-исключение по простым делителям \(p\):
$$C_p(A,B)=\left|\{q\in[A,B]:\gcd(p,q)=1\}\right|=\sum_{d\mid p}\mu(d)\left(\left\lfloor\frac{B}{d}\right\rfloor-\left\lfloor\frac{A-1}{d}\right\rfloor\right).$$
Для быстрого вычисления код факторизует \(p\) с помощью массива наименьших простых делителей, выделяет различные простые множители и перечисляет все квадратсвободные делители вместе со знаками Мёбиуса \(\mu(d)\in\{-1,1\}\). Если интервал очень короткий, и C++, и Java переходят к прямым проверкам \(\gcd\), поскольку так дешевле.
Для фиксированного \(p\) вводится примитивная квадратичная форма периметра
$$N(p,q)=p^2+pq+q^2,\qquad t(q)=\left\lfloor\frac{L}{N(p,q)}\right\rfloor.$$
Поскольку \(N(p,q)\) возрастает по \(q\), значение \(t(q)\) постоянно на последовательных блоках. Если блок начинается в точке \(q=\ell\), код вычисляет
$$t=\left\lfloor\frac{L}{N(p,\ell)}\right\rfloor,\qquad M=\left\lfloor\frac{L}{t}\right\rfloor.$$
Один и тот же частный сохраняется ровно пока \(N(p,q)\le M\). Значит, конец блока — это максимальное \(r\), удовлетворяющее этому условию; он находится ещё одним вызовом `q_max_for_norm(p, M)`. Вклад всего блока равен
$$t\cdot C_p(\ell,r).$$
Именно эта блочная обработка позволяет не перебирать все \(q\) по одному.
Файл C++ содержит основную оптимизированную реализацию. Сначала строится таблица наименьших простых делителей до \(p_{\max}=\lfloor\sqrt{L/3}\rfloor\), затем обрабатываются все \(p\), причём независимые значения \(p\) при желании распараллеливаются по потокам. Кроме того, C++-код проверяет математику на значениях из условия \(G(100)=42\), \(G(1000)=532\), \(G(10^4)=6427\), \(G(10^5)=75243\), \(G(10^6)=861805\), а также сравнивает быстрый и грубый подсчёт на малых пределах. Файл Java реализует ту же математику в более простой однопоточной форме на `long`. Файл Python намеренно служит мостом: он компилирует и запускает C++-решатель, поэтому Python возвращает в точности тот же проверенный результат.
Построение решета до \(p_{\max}\) требует \(O(p_{\max}\log\log p_{\max})\) времени и \(O(p_{\max})\) памяти. Наивный двойной цикл по всем допустимым парам \((p,q)\) практически имеет линейную по \(L\) стоимость, потому что \(p\) доходит до \(O(\sqrt L)\), а для каждого \(p\) есть \(O(p)\) кандидатов \(q\). Реальная реализация заменяет этот грубый перебор блоками по постоянному частному и интервальными подсчётами с весами Мёбиуса. Точное число блоков зависит от структуры целочисленных делений, поэтому строгая асимптотика выглядит менее прозрачной, но на практике работы намного меньше, чем в наивном переборе, и каждый блок использует только квадратсвободные делители одного фиксированного \(p\).
المثلث الهندسي هنا هو مثلث ذو أضلاع صحيحة تكون أطوالها في متتالية هندسية. إذا رتّبنا الأضلاع على الصورة \(a \le b \le c\)، فإن الشرط يصبح \(b^2 = ac\). ومع حد للمحيط مقداره \(L\)، نريد عدّ جميع هذه المثلثات التي تحقق \(a+b+c \le L\).
ملفات الحل المحلية تختزل المسألة إلى مجموع على أزواج أولية نسبياً \((p,q)\). والفكرة الكاملة تتكوّن من ثلاث طبقات: توصيف دقيق لكل مثلث صحيح ذي نسبة هندسية، ثم حدّ ناتج من متباينة المثلث، ثم عدّ جميع مضاعفات كل مثلث بدائي.
لتكن \((a,b,c)\) أضلاع مثلث هندسي صحيح مع \(a \le b \le c\). بما أن الأضلاع في متتالية هندسية، فلدينا
$$b^2 = ac.$$
نأخذ \(m=\gcd(a,c)\) ونكتب
$$a=mu,\qquad c=mv,\qquad \gcd(u,v)=1.$$
عندئذٍ \(b^2=m^2uv\)، أي إن \(uv\) مربع كامل. وبما أن \(u\) و\(v\) أوليان نسبيًا، فلا بد أن يكون كل منهما مربعًا كاملًا بمفرده. لذلك توجد أعداد صحيحة \(p,q\) أولية نسبيًا بحيث
$$u=p^2,\qquad v=q^2,\qquad \gcd(p,q)=1.$$
ومن ثمّ فإن كل مثلث هندسي صحيح يمكن كتابته على الصورة
$$a=mp^2,\qquad b=mpq,\qquad c=mq^2,$$
حيث \(m \ge 1\) و\(1 \le p \le q\) و\(\gcd(p,q)=1\). وبالعكس، كل ثلاثية من هذا الشكل تحقق \(b^2=ac\)، إذن هذا التمثيل دقيق وكامل، وهو وحيد بعد فرض \(p \le q\) و\(\gcd(p,q)=1\).
المتباينة الوحيدة غير التافهة هي \(c \lt a+b\). وبعد التعويض نحصل على
$$mq^2 \lt mp^2 + mpq \iff q^2 \lt p^2 + pq.$$
وبالقسمة على \(p^2\) ووضع \(x=q/p\) يصبح الشرط
$$x^2 - x - 1 \lt 0.$$
والجذر الموجب هو النسبة الذهبية
$$\varphi = \frac{1+\sqrt{5}}{2},$$
لذلك لا بد أن يحقق الزوج المقبول
$$1 \le \frac{q}{p} \lt \varphi,\qquad q \lt \varphi p.$$
ولهذا يبدأ الكود في `q_max_triangle(p)` من قيمة تقريبية \(\varphi p\)، ثم يصحّح الحد باستعمال حساب صحيح دقيق.
محيط المثلث \((mp^2,mpq,mq^2)\) يساوي
$$P = m(p^2 + pq + q^2).$$
وبالنسبة إلى زوج بدائي ثابت \((p,q)\)، فإن معاملات التمديد الممكنة هي تمامًا
$$1 \le m \le \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.$$
إذن يساهم الزوج \((p,q)\) بعدد
$$\left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor$$
من المثلثات. وبجمع ذلك على جميع النسب البدائية نحصل على الصيغة التي يطبّقها الحل:
$$\boxed{G(L)=\sum_{\substack{p\ge 1\\ q\ge p\\ \gcd(p,q)=1\\ q^2 \lt p^2+pq}} \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.}$$
بما أن \(q \ge p\)، فإن أصغر محيط بدائي لقيمة ثابتة من \(p\) يحدث عند \(q=p\)، وقيمته \(3p^2\). لذلك تنعدم المساهمة عندما
$$3p^2 \gt L,$$
ومن ثم يكفي أن تدور الحلقة الخارجية حتى
$$p \le p_{\max} = \left\lfloor\sqrt{\frac{L}{3}}\right\rfloor.$$
أما مع تثبيت \(p\)، فإن شرط المحيط
$$p^2+pq+q^2 \le L$$
هو متباينة تربيعية في \(q\)، ومنها
$$q \le \left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor.$$
الكود يسمّي هذا الحد الثاني `q_max_for_norm(p, L)`، ويستخدم في النهاية
$$q_{\max}(p)=\min\!\left(\left\lfloor \varphi p \right\rfloor,\left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor\right).$$
الأزواج البدائية التي تحقق الحدين معًا هي
$$ (1,1),\ (2,3),\ (3,4),\ (4,5),\ (5,6). $$
ومحيطاتها البدائية هي
$$3,\ 19,\ 37,\ 61,\ 91.$$
إذًا
$$G(100)=\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{19}\right\rfloor+\left\lfloor\frac{100}{37}\right\rfloor+\left\lfloor\frac{100}{61}\right\rfloor+\left\lfloor\frac{100}{91}\right\rfloor=33+5+2+1+1=42.$$
وهذا يطابق نقطة التحقق \(G(100)=42\) الموجودة في ملف C++.
الأسلوب الساذج يفحص كل قيمة \(q\) على حدة. أما الحل السريع فيحسب عدد القيم الأولية نسبيًا مع \(p\) داخل الفترة \([A,B]\) بواسطة إدراج واستبعاد على القواسم الأولية لـ \(p\):
$$C_p(A,B)=\left|\{q\in[A,B]:\gcd(p,q)=1\}\right|=\sum_{d\mid p}\mu(d)\left(\left\lfloor\frac{B}{d}\right\rfloor-\left\lfloor\frac{A-1}{d}\right\rfloor\right).$$
ولتنفيذ ذلك بسرعة، يقوم الكود بتحليل \(p\) باستخدام جدول أصغر عامل أولي، ثم يستخرج العوامل الأولية المختلفة، ثم يولّد جميع القواسم الخالية من المربعات مع إشارات Möbius الموافقة \(\mu(d)\in\{-1,1\}\). وإذا كانت الفترة قصيرة جدًا، فإن C++ وJava يرجعان إلى فحوصات مباشرة لـ \(\gcd\)، لأن ذلك يكون أرخص.
عند تثبيت \(p\)، نعرّف صيغة المحيط البدائي
$$N(p,q)=p^2+pq+q^2,\qquad t(q)=\left\lfloor\frac{L}{N(p,q)}\right\rfloor.$$
وبما أن \(N(p,q)\) تزداد مع \(q\)، فإن القيمة \(t(q)\) تبقى ثابتة على كتل متتالية من قيم \(q\). إذا بدأت كتلة عند \(q=\ell\)، فإن الكود يحسب
$$t=\left\lfloor\frac{L}{N(p,\ell)}\right\rfloor,\qquad M=\left\lfloor\frac{L}{t}\right\rfloor.$$
وتبقى القيمة نفسها ما دام \(N(p,q)\le M\). لذلك ينتهي البلوك عند أكبر \(r\) يحقق هذا الشرط، ويجده الكود باستدعاء آخر إلى `q_max_for_norm(p, M)`. ومساهمة الكتلة كلها هي
$$t\cdot C_p(\ell,r).$$
وهذه هي الخطوة الأساسية التي تمنع المرور على كل \(q\) بشكل منفرد.
ملف C++ هو التنفيذ الرئيسي المحسّن. يبدأ بحساب أصغر عامل أولي حتى \(p_{\max}=\lfloor\sqrt{L/3}\rfloor\)، ثم يعالج كل قيمة \(p\)، ويمكنه أيضًا توزيع قيم \(p\) المستقلة على عدة خيوط. كما أنه يتحقق من صحة الرياضيات عبر نقاط الفحص \(G(100)=42\)، \(G(1000)=532\)، \(G(10^4)=6427\)، \(G(10^5)=75243\)، \(G(10^6)=861805\)، ويقارن أيضًا بين الحل السريع والحل بالقوة الغاشمة على حدود صغيرة. أما ملف Java فيطبّق الرياضيات نفسها بصورة أبسط وخيط واحد باستخدام `long`. وملف Python مكتوب عمدًا كطبقة ربط: فهو يترجم مشغّل C++ وينفّذه لكي يعيد Python النتيجة نفسها بعد التحقق.
المرحلة التمهيدية الخاصة بالغربال حتى \(p_{\max}\) تكلف \(O(p_{\max}\log\log p_{\max})\) زمنًا و \(O(p_{\max})\) ذاكرة. أمّا التعداد الساذج لجميع الأزواج المسموح بها \((p,q)\) فيبقى عمليًا ذا كلفة خطية في \(L\)، لأن \(p\) يصل إلى \(O(\sqrt L)\) ولكل \(p\) يوجد \(O(p)\) من قيم \(q\). التنفيذ الفعلي يستبدل هذا المسح الخام بكتل خارج القسمة وعدّ فترات موزونة بـ Möbius. العدد الدقيق للكتل يعتمد على بنية القسمة الصحيحة، لذلك يصعب إعطاء صيغة حدية حادة جدًا، لكنه عمليًا أصغر بكثير من التعداد الساذج، وكل كتلة لا تلمس إلا القواسم الخالية من المربعات لقيمة واحدة من \(p\).