Problem 962 asks for all integer triples \((a,b,c)\) with \(a \le b \le c \lt a+b\) and \(a+b+c \le N\) for which the geometric construction in the statement leads to
\[ Q=\frac{a^3(a+b-c)(a+b+c)}{b(a+b)^2} \]
being an integer perfect square. For the Project Euler instance, \(N=10^6\). A direct sweep over all triangles is far too slow, so the solution replaces the \((a,b,c)\)-search by a number-theoretic count over a much smaller parameter space.
The key step is to separate the common scale of \(a\) and \(b\), prove that every valid triangle has a rigid difference-of-squares form, and then count the remaining possibilities through squarefree data and interval arithmetic.
Let
\[ g=\gcd(a,b), \qquad a=ug, \qquad b=vg, \]
with \(\gcd(u,v)=1\) and \(u \le v\). Write
\[ k=u+v. \]
Then \(a+b=kg\), so the square test becomes
\[ Q=\frac{u^3\bigl(k^2g^2-c^2\bigr)}{vk^2}. \]
This already shows why the reduced ratio \(u:v\) is the real state space: once \(u\) and \(v\) are fixed, the remaining freedom sits inside \(g\) and \(c\).
If \(Q\) is an integer, then \(k^2\) divides the numerator \(u^3(k^2g^2-c^2)\). Because \(\gcd(u,k)=1\), the factor \(u^3\) is irrelevant for divisibility by \(k^2\), so
\[ k^2 \mid \bigl(k^2g^2-c^2\bigr). \]
The term \(k^2g^2\) is already a multiple of \(k^2\), hence \(k^2 \mid c^2\), which implies
\[ k \mid c. \]
So every valid triangle can be written as
\[ c=kt \]
for some integer \(t\) with \(0 \lt t \lt g\). Substituting this into the previous formula collapses the \(k^2\)-denominator:
\[ Q=\frac{u^3(g^2-t^2)}{v}. \]
Now factor the difference of squares by setting
\[ r=g-t, \qquad s=g+t. \]
Then
\[ g=\frac{r+s}{2}, \qquad t=\frac{s-r}{2}, \]
so \(r\) and \(s\) are positive integers with \(r \lt s\) and
\[ r \equiv s \pmod 2. \]
The triangle sides become
\[ a=\frac{u(r+s)}{2}, \qquad b=\frac{v(r+s)}{2}, \qquad c=\frac{k(s-r)}{2}, \]
and the perimeter is especially simple:
\[ a+b+c=ks. \]
The square test is now
\[ Q=\frac{u^3rs}{v}. \]
This is the form used by the optimized algorithm. Instead of iterating over \(c\), it counts admissible pairs \((r,s)\) for each reduced ratio \(u:v\).
Write
\[ u=d\,h^2, \]
where \(d=\operatorname{sf}(u)\) is the squarefree part of \(u\). Then
\[ u^3=d^3h^6=d^2(dh^3)^2, \]
so \(u^3\) contributes one squarefree copy of \(d\) and everything else is already a square. Therefore
\[ Q \text{ is a perfect square } \Longleftrightarrow \frac{drs}{v} \text{ is a perfect square.} \]
That is why the implementations precompute the squarefree kernel of \(u\). For primes dividing \(v\), the product \(rs\) must supply enough exponent to cancel the denominator and leave an even valuation. For primes dividing \(d\), the product \(rs\) must carry an odd valuation. These prime-by-prime requirements are compressed into a smallest admissible base value \(s_0\), and every valid \(s\) for fixed \((u,v,r)\) has the form
\[ s=s_0n^2 \]
with \(n \ge 1\).
Let
\[ L=\left\lfloor\frac{N}{k}\right\rfloor. \]
Since the perimeter equals \(ks\), we must have \(s \le L\). The remaining geometric restriction is \(c \ge b\), which becomes
\[ \frac{k(s-r)}{2} \ge \frac{v(r+s)}{2}. \]
After simplifying with \(k=u+v\), this becomes
\[ us \ge (u+2v)r. \]
So for fixed \(u,v,r\), the first feasible value of \(s\) is
\[ s_{\min}=\left\lceil\frac{(u+2v)r}{u}\right\rceil. \]
Because \(s=s_0n^2\), the allowed range for \(n\) is
\[ n_{\min}=\left\lceil\sqrt{\left\lceil\frac{s_{\min}}{s_0}\right\rceil}\right\rceil, \qquad n_{\max}=\left\lfloor\sqrt{\frac{L}{s_0}}\right\rfloor. \]
The parity condition \(r \equiv s \pmod 2\) now becomes a filter on \(n\). If \(s_0\) is even, then every admissible \(s\) is even, so only even \(r\) can contribute. If \(s_0\) is odd, then \(s \equiv n^2 \equiv n \pmod 2\), so we need
\[ n \equiv r \pmod 2. \]
Each branch therefore contributes only the number of integers \(n\) in a short interval with the correct parity.
The solutions use a sharp global bound on \(k\). Since \(v \ge k/2\) and \(d \ge 1\), any valid branch must satisfy
\[ vd \le rs \le s^2 \le L^2 \le \left(\frac{N}{k}\right)^2. \]
Therefore
\[ \frac{k}{2} \le \left(\frac{N}{k}\right)^2, \qquad\text{so}\qquad k^3 \le 2N^2. \]
This is why only \(k\) up to roughly \((2N^2)^{1/3}\) need to be examined.
Consider the valid triangle \((a,b,c)=(12,15,18)\). Then
\[ g=\gcd(12,15)=3,\qquad u=4,\qquad v=5,\qquad k=9. \]
Since \(c=18=9\cdot 2\), we have \(t=2\). Hence
\[ r=g-t=1,\qquad s=g+t=5. \]
Recovering the sides from \((u,v,r,s)\) gives
\[ a=\frac{4(1+5)}{2}=12,\qquad b=\frac{5(1+5)}{2}=15,\qquad c=\frac{9(5-1)}{2}=18. \]
The square test becomes
\[ Q=\frac{4^3 \cdot 1 \cdot 5}{5}=64=8^2. \]
Here \(\operatorname{sf}(4)=1\), so the square condition reduces to \(s/5\) being a square when \(r=1\). The smallest choice is \(s_0=5\), and \(s=5=s_0\cdot 1^2\) is indeed the first admissible value above
\[ s_{\min}=\left\lceil\frac{(4+2\cdot 5)\cdot 1}{4}\right\rceil=4. \]
This single example mirrors the whole algorithm: fix a reduced ratio \(u:v\), turn the triangle into \(r\) and \(s\), build the minimal base \(s_0\), then count square multiples inside the allowed interval.
The C++, Python, and Java implementations begin by computing a smallest-prime-factor table. From it they derive two reusable data sets: the squarefree part \(\operatorname{sf}(u)\) for every possible \(u\), and a compact prime-exponent factorization for every integer that can appear as \(v\), \(r\), or \(\operatorname{sf}(u)\). This removes repeated factorization work from the main count.
For each \(k\), the implementation iterates over \(v\) from \(\lceil k/2 \rceil\) to \(k-1\), keeps only \(\gcd(v,k)=1\), and sets \(u=k-v\). It then computes \(L=\lfloor N/k \rfloor\) and discards the branch immediately when \(v\operatorname{sf}(u) \gt L^2\), because then even the largest possible product \(rs\) cannot satisfy the square condition.
Next it loops over
\[ 1 \le r \le \left\lfloor\frac{uL}{u+2v}\right\rfloor. \]
For each such \(r\), the implementation merges the prime data of \(r\), \(v\), and \(\operatorname{sf}(u)\) to construct the smallest \(s_0\) that can make \(drs/v\) a square. If \(s_0 \gt L\), the branch is impossible. Otherwise the code converts the conditions into the interval \([n_{\min},n_{\max}]\), applies the parity rule, and adds the number of admissible \(n\).
The total answer is the sum of these contributions over all \(k\). The Python implementation evaluates the outer \(k\)-loop serially. The C++ and Java implementations use parallel execution for that outer sweep, because each \(k\) contributes independently once the factor tables have been built.
The outer bound \(k \le O(N^{2/3})\) already cuts the search space drastically. For a fixed \(k\), there are \(O(k)\) candidates for \(v\), and for each surviving \((u,v)\) the parameter \(r\) ranges up to \(O(N/k)\). A coarse upper bound for the arithmetic branches is therefore
\[ \sum_{k \le O(N^{2/3})} O(k)\,O\!\left(\frac{N}{k}\right)=O(N^{5/3}). \]
Each branch only performs a short merge of prime-exponent lists together with constant-time integer-root and interval calculations, so the practical runtime is much better than a triangle-by-triangle scan. The early coprimality filter and the \(v\operatorname{sf}(u) \le L^2\) pruning remove many branches before any expensive work happens.
Memory usage is dominated by the prime tables: the smallest-prime-factor sieve, the squarefree-part array, and the factor table up to the largest needed integer. This is essentially linear in the sieve bound, with only a small logarithmic factor from storing prime exponents.
Problem 962 verlangt alle ganzzahligen Tripel \((a,b,c)\) mit \(a \le b \le c \lt a+b\) und \(a+b+c \le N\), fuer die die geometrische Konstruktion der Aufgabe auf
\[ Q=\frac{a^3(a+b-c)(a+b+c)}{b(a+b)^2} \]
fuehrt und dieser Ausdruck ein ganzzahliges Quadrat ist. Im eigentlichen Euler-Fall gilt \(N=10^6\). Eine direkte Enumeration aller Dreiecke ist zu teuer, deshalb zaehlt die Loesung nicht ueber \((a,b,c)\), sondern ueber eine viel kleinere arithmetische Parametrisierung.
Der zentrale Gedanke besteht darin, zuerst den gemeinsamen Faktor von \(a\) und \(b\) abzuspalten, dann zu zeigen, dass jedes gueltige Dreieck eine starre Differenz-von-Quadraten-Struktur besitzt, und die restlichen Faelle schliesslich ueber quadratfreie Kerne und Intervallsummen zu zaehlen.
Setze
\[ g=\gcd(a,b), \qquad a=ug, \qquad b=vg, \]
mit \(\gcd(u,v)=1\) und \(u \le v\). Definiere ausserdem
\[ k=u+v. \]
Dann ist \(a+b=kg\), und der Testausdruck wird zu
\[ Q=\frac{u^3\bigl(k^2g^2-c^2\bigr)}{vk^2}. \]
Damit ist klar, dass das reduzierte Verhaeltnis \(u:v\) die eigentliche Struktur des Problems traegt. Sind \(u\) und \(v\) fest, dann steckt die restliche Freiheit nur noch in \(g\) und \(c\).
Wenn \(Q\) ganzzahlig ist, dann muss \(k^2\) den Zaehler \(u^3(k^2g^2-c^2)\) teilen. Wegen \(\gcd(u,k)=1\) spielt \(u^3\) fuer die Teilbarkeit durch \(k^2\) keine Rolle, also gilt
\[ k^2 \mid \bigl(k^2g^2-c^2\bigr). \]
Da \(k^2g^2\) bereits ein Vielfaches von \(k^2\) ist, folgt \(k^2 \mid c^2\), also
\[ k \mid c. \]
Jedes gueltige Dreieck laesst sich daher als
\[ c=kt \]
mit einem ganzzahligen \(t\) und \(0 \lt t \lt g\) schreiben. Einsetzen liefert sofort
\[ Q=\frac{u^3(g^2-t^2)}{v}. \]
Nun faktorisiert man die Differenz zweier Quadrate mit
\[ r=g-t, \qquad s=g+t. \]
Dann gilt
\[ g=\frac{r+s}{2}, \qquad t=\frac{s-r}{2}, \]
also sind \(r\) und \(s\) positive ganze Zahlen mit \(r \lt s\) und
\[ r \equiv s \pmod 2. \]
Die Seitenlaengen werden zu
\[ a=\frac{u(r+s)}{2}, \qquad b=\frac{v(r+s)}{2}, \qquad c=\frac{k(s-r)}{2}, \]
und der Umfang vereinfacht sich zu
\[ a+b+c=ks. \]
Der Quadrattest lautet jetzt
\[ Q=\frac{u^3rs}{v}. \]
Genau diese Darstellung verwendet die schnelle Loesung: Statt ueber \(c\) zu iterieren, zaehlt sie fuer jedes reduzierte Verhaeltnis \(u:v\) die moeglichen Paare \((r,s)\).
Schreibe
\[ u=d\,h^2, \]
wobei \(d=\operatorname{sf}(u)\) der quadratfreie Kern von \(u\) ist. Dann gilt
\[ u^3=d^3h^6=d^2(dh^3)^2, \]
also bringt \(u^3\) nur eine einzige quadratfreie Kopie von \(d\) mit; der Rest ist bereits quadratisch. Damit ist
\[ Q \text{ genau dann ein Quadrat, wenn } \frac{drs}{v} \text{ ein Quadrat ist.} \]
Darum berechnen die Implementierungen den quadratfreien Kern von \(u\) vorab. Fuer Primzahlen aus \(v\) muss das Produkt \(rs\) genug Exponenten liefern, um den Nenner zu neutralisieren und am Ende eine gerade Bewertung zu hinterlassen. Fuer Primzahlen aus \(d\) muss \(rs\) eine ungerade Bewertung liefern. Diese Bedingungen werden in einen kleinsten zulaessigen Basiswert \(s_0\) verdichtet, und jedes gueltige \(s\) fuer festes \((u,v,r)\) hat die Form
\[ s=s_0n^2 \]
mit \(n \ge 1\).
Definiere
\[ L=\left\lfloor\frac{N}{k}\right\rfloor. \]
Wegen \(a+b+c=ks\) muss \(s \le L\) gelten. Die verbleibende geometrische Bedingung ist \(c \ge b\), also
\[ \frac{k(s-r)}{2} \ge \frac{v(r+s)}{2}. \]
Mit \(k=u+v\) vereinfacht sich das zu
\[ us \ge (u+2v)r. \]
Somit ist fuer festes \(u,v,r\) der erste moegliche Wert
\[ s_{\min}=\left\lceil\frac{(u+2v)r}{u}\right\rceil. \]
Da \(s=s_0n^2\), folgt fuer \(n\)
\[ n_{\min}=\left\lceil\sqrt{\left\lceil\frac{s_{\min}}{s_0}\right\rceil}\right\rceil, \qquad n_{\max}=\left\lfloor\sqrt{\frac{L}{s_0}}\right\rfloor. \]
Die Paritaetsbedingung \(r \equiv s \pmod 2\) wird damit zu einem Filter auf \(n\). Ist \(s_0\) gerade, dann ist jedes zulaessige \(s\) gerade und nur gerades \(r\) kann beitragen. Ist \(s_0\) ungerade, dann gilt \(s \equiv n^2 \equiv n \pmod 2\), also
\[ n \equiv r \pmod 2. \]
Jeder Zweig liefert also lediglich die Anzahl der ganzen Zahlen \(n\) in einem kurzen Intervall mit korrekter Paritaet.
Die Loesungen verwenden eine globale Schranke fuer \(k\). Da \(v \ge k/2\) und \(d \ge 1\) gilt, muss in jedem moeglichen Zweig
\[ vd \le rs \le s^2 \le L^2 \le \left(\frac{N}{k}\right)^2 \]
erfuellt sein. Also folgt
\[ \frac{k}{2} \le \left(\frac{N}{k}\right)^2, \qquad\text{also}\qquad k^3 \le 2N^2. \]
Deshalb muessen nur Werte von \(k\) bis ungefähr \((2N^2)^{1/3}\) untersucht werden.
Betrachte das gueltige Dreieck \((a,b,c)=(12,15,18)\). Dann ist
\[ g=\gcd(12,15)=3,\qquad u=4,\qquad v=5,\qquad k=9. \]
Weil \(c=18=9\cdot 2\), folgt \(t=2\). Also
\[ r=g-t=1,\qquad s=g+t=5. \]
Aus \((u,v,r,s)\) bekommt man die Seiten sofort zurueck:
\[ a=\frac{4(1+5)}{2}=12,\qquad b=\frac{5(1+5)}{2}=15,\qquad c=\frac{9(5-1)}{2}=18. \]
Der Quadrattest liefert
\[ Q=\frac{4^3 \cdot 1 \cdot 5}{5}=64=8^2. \]
Hier ist \(\operatorname{sf}(4)=1\), also reduziert sich die Bedingung bei \(r=1\) auf \(s/5\) als Quadrat. Der kleinste moegliche Basiswert ist \(s_0=5\), und \(s=5=s_0\cdot 1^2\) ist tatsaechlich der erste zulaessige Wert oberhalb von
\[ s_{\min}=\left\lceil\frac{(4+2\cdot 5)\cdot 1}{4}\right\rceil=4. \]
Dieses Beispiel zeigt bereits den kompletten Mechanismus des Algorithmus.
Die C++-, Python- und Java-Implementierungen beginnen mit einer Tabelle des kleinsten Primteilers. Daraus werden zwei wiederverwendbare Strukturen erzeugt: der quadratfreie Kern \(\operatorname{sf}(u)\) fuer alle moeglichen \(u\) und eine kompakte Primfaktorzerlegung fuer jede Zahl, die als \(v\), \(r\) oder \(\operatorname{sf}(u)\) auftreten kann. So wird wiederholte Faktorisierung in der Hauptschleife vermieden.
Fuer jedes \(k\) iteriert die Implementierung \(v\) von \(\lceil k/2 \rceil\) bis \(k-1\), behaelt nur Faelle mit \(\gcd(v,k)=1\) und setzt \(u=k-v\). Danach werden \(L=\lfloor N/k \rfloor\) und \(v\operatorname{sf}(u)\) berechnet. Wenn \(v\operatorname{sf}(u) \gt L^2\) gilt, wird der ganze Zweig sofort verworfen, weil dann selbst das groesste moegliche Produkt \(rs\) die Quadratbedingung nicht mehr erfuellen kann.
Anschliessend laeuft
\[ 1 \le r \le \left\lfloor\frac{uL}{u+2v}\right\rfloor. \]
Fuer jedes \(r\) werden die Primdaten von \(r\), \(v\) und \(\operatorname{sf}(u)\) zusammengefuehrt, um den kleinsten Wert \(s_0\) zu bestimmen, der \(drs/v\) zu einem Quadrat machen kann. Falls \(s_0 \gt L\), ist der Zweig unmoeglich. Andernfalls verwandelt der Code alle Bedingungen in das Intervall \([n_{\min},n_{\max}]\), wendet den Paritaetsfilter an und addiert die Anzahl der zulaessigen \(n\).
Die gesuchte Anzahl ist die Summe dieser Beitraege ueber alle \(k\). Die Python-Implementierung durchlaeuft die aeussere \(k\)-Schleife seriell. Die C++- und Java-Implementierungen parallelisieren genau diese aeussere Schleife, weil nach dem Aufbau der Faktortabellen jeder Wert von \(k\) unabhaengig behandelt werden kann.
Die Schranke \(k \le O(N^{2/3})\) reduziert den Suchraum bereits massiv. Fuer festes \(k\) gibt es \(O(k)\) Kandidaten fuer \(v\), und fuer jedes ueberlebende \((u,v)\) laeuft \(r\) bis \(O(N/k)\). Damit ergibt sich als grobe obere Schranke
\[ \sum_{k \le O(N^{2/3})} O(k)\,O\!\left(\frac{N}{k}\right)=O(N^{5/3}). \]
In jedem Zweig muessen nur kurze Primexponentenlisten zusammengefuehrt sowie ein paar ganzzahlige Wurzel- und Intervallrechnungen ausgefuehrt werden. Praktisch ist das Verfahren deshalb sehr viel schneller als eine direkte Dreiecksuche. Zusaetzlich werden viele Zweige schon durch die Koprimalitaetsbedingung und durch die Schranke \(v\operatorname{sf}(u) \le L^2\) aussortiert.
Der Speicherbedarf wird von den Primtabellen dominiert: Tabelle des kleinsten Primteilers, Array der quadratfreien Kerne und Faktortabelle bis zur groessten benoetigten Zahl. Das ist im Wesentlichen linear in der Siebgrenze, bis auf einen kleinen logarithmischen Faktor fuer die gespeicherten Primexponenten.
Problem 962, \(a \le b \le c \lt a+b\) ve \(a+b+c \le N\) kosullarini saglayan tum tam sayi ucluleri \((a,b,c)\) icin sorudaki geometrik kurulusun
\[ Q=\frac{a^3(a+b-c)(a+b+c)}{b(a+b)^2} \]
ifadesini tam kare yapan durumlari saymayi ister. Project Euler surumunde \(N=10^6\) alinmistir. Tum ucluleri dogrudan taramak cok pahali oldugu icin cozum, \((a,b,c)\) uzayini daha kucuk bir sayi teorisi parametrelemesine indirger.
Ana fikir, once \(a\) ile \(b\)'nin ortak olcegini ayirmak, sonra her gecerli ucgenin katı bir fark-kareler yapisina sahip oldugunu gostermek ve son olarak kalan olasiliklari karekoksuz cekirdekler ile aralik sayimi uzerinden hesaplamaktir.
Su sekilde yazalim:
\[ g=\gcd(a,b), \qquad a=ug, \qquad b=vg, \]
burada \(\gcd(u,v)=1\) ve \(u \le v\). Ayrica
\[ k=u+v \]
olsun. Boylece \(a+b=kg\) ve kare testi
\[ Q=\frac{u^3\bigl(k^2g^2-c^2\bigr)}{vk^2} \]
haline gelir. Bu adim, problemin asil durum uzayinin indirgenmis oran \(u:v\) oldugunu gosterir. \(u\) ve \(v\) sabitlenince geri kalan degiskenlik yalnizca \(g\) ve \(c\) icinde kalir.
\(Q\) tam sayi ise \(k^2\), \(u^3(k^2g^2-c^2)\) sayisini bolmelidir. \(\gcd(u,k)=1\) oldugu icin \(u^3\) carpaninin \(k^2\) bolunebilirligine etkisi yoktur; dolayisiyla
\[ k^2 \mid \bigl(k^2g^2-c^2\bigr) \]
olur. \(k^2g^2\) zaten \(k^2\)'nin kati oldugu icin \(k^2 \mid c^2\) ve oradan da
\[ k \mid c \]
sonucu gelir. Demek ki her gecerli ucgen
\[ c=kt \]
seklinde yazilabilir; burada \(0 \lt t \lt g\). Bunu yerine koyunca
\[ Q=\frac{u^3(g^2-t^2)}{v} \]
elde edilir.
Simdi kare farkini
\[ r=g-t, \qquad s=g+t \]
ile ayiralim. O zaman
\[ g=\frac{r+s}{2}, \qquad t=\frac{s-r}{2} \]
olur; yani \(r\) ve \(s\) pozitif tam sayilardir, \(r \lt s\) saglanir ve
\[ r \equiv s \pmod 2 \]
kosulu vardir. Kenarlar su hale gelir:
\[ a=\frac{u(r+s)}{2}, \qquad b=\frac{v(r+s)}{2}, \qquad c=\frac{k(s-r)}{2}. \]
Toplam cevre ise cok temizdir:
\[ a+b+c=ks. \]
Kare testi de artik
\[ Q=\frac{u^3rs}{v} \]
seklindedir. Hizli algoritma tam olarak bu formu kullanir: \(c\) uzerinde dolasmak yerine, her indirgenmis \(u:v\) orani icin uygun \((r,s)\) ciftlerini sayar.
\[ u=d\,h^2 \]
olsun; burada \(d=\operatorname{sf}(u)\), yani \(u\)'nun karekoksuz kismidir. O halde
\[ u^3=d^3h^6=d^2(dh^3)^2 \]
olur. Yani \(u^3\), kare olmayan kisim olarak yalnizca tek bir \(d\) kopyasi tasir; geri kalan bolum zaten karedir. Bu yuzden
\[ Q \text{ tam kare } \Longleftrightarrow \frac{drs}{v} \text{ tam karedir.} \]
Uygulamalar bu nedenle once \(\operatorname{sf}(u)\) degerlerini hazirlar. \(v\)'yi bolen asallar icin \(rs\) carpimi, paydadaki us eksigini kapatip son degerlemeyi cift yapmak zorundadir. \(d\)'yi bolen asallar icin ise \(rs\) icindeki toplam us tek olmalidir. Butun bu yerel kosullar, en kucuk uygun taban deger olan \(s_0\)'da toplanir ve sabit \((u,v,r)\) icin her uygun \(s\)
\[ s=s_0n^2 \]
seklini alir.
\[ L=\left\lfloor\frac{N}{k}\right\rfloor \]
olsun. Cevre \(ks\) oldugundan \(s \le L\) gerekir. Geriye kalan geometrik kisit \(c \ge b\) esitligidir:
\[ \frac{k(s-r)}{2} \ge \frac{v(r+s)}{2}. \]
\(k=u+v\) kullanilirsa bu
\[ us \ge (u+2v)r \]
haline gelir. Dolayisiyla sabit \(u,v,r\) icin ilk uygun \(s\) degeri
\[ s_{\min}=\left\lceil\frac{(u+2v)r}{u}\right\rceil \]
olur. \(s=s_0n^2\) yazildigi icin \(n\) araligi
\[ n_{\min}=\left\lceil\sqrt{\left\lceil\frac{s_{\min}}{s_0}\right\rceil}\right\rceil, \qquad n_{\max}=\left\lfloor\sqrt{\frac{L}{s_0}}\right\rfloor \]
seklindedir. Ayrica \(r \equiv s \pmod 2\) kosulu, \(n\) uzerinde bir parity filtresine donusur. \(s_0\) ciftse her uygun \(s\) de cifttir; bu durumda ancak cift \(r\) katkida bulunabilir. \(s_0\) tekse \(s \equiv n^2 \equiv n \pmod 2\) oldugundan
\[ n \equiv r \pmod 2 \]
gereklidir. Yani her dal yalnizca kisa bir araliktaki ve dogru parity'ye sahip \(n\) sayisini ekler.
Cozumler \(k\) icin keskin bir ust sinir kullanir. Cunku \(v \ge k/2\) ve \(d \ge 1\) oldugundan herhangi bir gecerli dalda
\[ vd \le rs \le s^2 \le L^2 \le \left(\frac{N}{k}\right)^2 \]
olmak zorundadir. Buradan
\[ \frac{k}{2} \le \left(\frac{N}{k}\right)^2, \qquad\text{dolayisiyla}\qquad k^3 \le 2N^2 \]
elde edilir. Bu nedenle yalnizca \((2N^2)^{1/3}\) mertebesine kadar \(k\) denenir.
\((a,b,c)=(12,15,18)\) gecerli ucgenini ele alalim. O zaman
\[ g=\gcd(12,15)=3,\qquad u=4,\qquad v=5,\qquad k=9 \]
olur. \(c=18=9\cdot 2\) oldugu icin \(t=2\) ve dolayisiyla
\[ r=g-t=1,\qquad s=g+t=5 \]
bulunur. Bu parametrelerden kenarlar geri kazanilir:
\[ a=\frac{4(1+5)}{2}=12,\qquad b=\frac{5(1+5)}{2}=15,\qquad c=\frac{9(5-1)}{2}=18. \]
Kare testi ise
\[ Q=\frac{4^3 \cdot 1 \cdot 5}{5}=64=8^2 \]
verir. Burada \(\operatorname{sf}(4)=1\) oldugundan, \(r=1\) icin kosul \(s/5\)'in kare olmasina indirgenir. En kucuk taban deger \(s_0=5\)'tir ve
\[ s_{\min}=\left\lceil\frac{(4+2\cdot 5)\cdot 1}{4}\right\rceil=4 \]
oldugundan \(s=5=s_0\cdot 1^2\) ilk gecerli secimdir. Tum algoritma bunun genellestirilmis halidir.
C++, Python ve Java uygulamalari once en kucuk asal bolen tablosunu uretir. Buradan iki temel veri yapisi elde edilir: her olasi \(u\) icin \(\operatorname{sf}(u)\) degeri ve \(v\), \(r\), \(\operatorname{sf}(u)\) olarak gerekebilecek her sayinin kisa asal-us acilimi. Boylece ana sayim dongusunde tekrar tekrar faktorleme yapilmaz.
Her \(k\) icin uygulama, \(v\)'yi \(\lceil k/2 \rceil\) ile \(k-1\) arasinda gezer, sadece \(\gcd(v,k)=1\) olanlari tutar ve \(u=k-v\) yazar. Sonra \(L=\lfloor N/k \rfloor\) hesaplanir. Eger \(v\operatorname{sf}(u) \gt L^2\) ise dal hemen atilir; cunku bu durumda en buyuk mumkun \(rs\) carpimi bile kare kosulunu saglayamaz.
Bundan sonra
\[ 1 \le r \le \left\lfloor\frac{uL}{u+2v}\right\rfloor \]
araliginda dolasilir. Her \(r\) icin, \(r\), \(v\) ve \(\operatorname{sf}(u)\)'nun asal-us bilgileri birlestirilerek \(drs/v\)'yi kare yapabilecek en kucuk \(s_0\) bulunur. \(s_0 \gt L\) ise dal imkansizdir. Aksi halde kod, kosullari \([n_{\min},n_{\max}]\) araligina cevirir, parity filtresini uygular ve uygun \(n\) sayisini toplama ekler.
Nihai cevap, tum \(k\) degerlerinden gelen katkilarin toplamidir. Python uygulamasi bu dis \(k\) dongusunu seri calistirir. C++ ve Java uygulamalari ise faktor tablolarini kurduktan sonra bu dis taramayi paralellestirir; cunku her \(k\) dali bagimsizdir.
\(k \le O(N^{2/3})\) siniri arama uzayini zaten ciddi bicimde daraltir. Sabit \(k\) icin \(v\) adaylarinin sayisi \(O(k)\), her sag kalan \((u,v)\) icin \(r\) araligi da \(O(N/k)\) mertebesindedir. Bu nedenle kaba bir ust sinir
\[ \sum_{k \le O(N^{2/3})} O(k)\,O\!\left(\frac{N}{k}\right)=O(N^{5/3}) \]
olur. Her dalda yalnizca kisa asal-us listeleri birlestirilir ve sabit zamanda tamsayi karekok ile aralik hesabı yapilir. Bu da pratikte cozumun naif ucgen taramasindan cok daha hizli olmasini saglar. Ayrica esasal olma filtresi ve \(v\operatorname{sf}(u) \le L^2\) budamasi, cok sayida dali daha baslangicta eler.
Bellek kullanimi esas olarak asal tablolarindan gelir: en kucuk asal bolen eleği, karekoksuz parca dizisi ve gerekli en buyuk sayiya kadar faktor tablosu. Bu maliyet, kucuk bir logaritmik katsayi haricinde eleme ust sinirinda yaklasik dogrusaldir.
El Problema 962 pide contar todos los ternos enteros \((a,b,c)\) con \(a \le b \le c \lt a+b\) y \(a+b+c \le N\) para los que la construccion geometrica del enunciado conduce a
\[ Q=\frac{a^3(a+b-c)(a+b+c)}{b(a+b)^2} \]
y ese valor resulta ser un cuadrado perfecto entero. En la instancia de Project Euler se usa \(N=10^6\). Un barrido directo sobre todos los triangulos es demasiado costoso, asi que la solucion cambia la busqueda en \((a,b,c)\) por un conteo aritmetico sobre un espacio de parametros mucho mas pequeno.
La idea central es separar primero la escala comun de \(a\) y \(b\), demostrar despues que todo triangulo valido adopta una forma rigida basada en diferencia de cuadrados, y finalmente contar los casos restantes con nucleos libres de cuadrados y conteo por intervalos.
Escribamos
\[ g=\gcd(a,b), \qquad a=ug, \qquad b=vg, \]
con \(\gcd(u,v)=1\) y \(u \le v\). Definimos ademas
\[ k=u+v. \]
Entonces \(a+b=kg\), y la condicion cuadratica toma la forma
\[ Q=\frac{u^3\bigl(k^2g^2-c^2\bigr)}{vk^2}. \]
Esto muestra que el cociente reducido \(u:v\) es el estado matematico correcto. Una vez fijados \(u\) y \(v\), toda la libertad restante esta dentro de \(g\) y \(c\).
Si \(Q\) es entero, entonces \(k^2\) divide al numerador \(u^3(k^2g^2-c^2)\). Como \(\gcd(u,k)=1\), el factor \(u^3\) no afecta la divisibilidad por \(k^2\), de modo que
\[ k^2 \mid \bigl(k^2g^2-c^2\bigr). \]
El termino \(k^2g^2\) ya es multiplo de \(k^2\), asi que \(k^2 \mid c^2\), y por tanto
\[ k \mid c. \]
Todo triangulo valido puede escribirse entonces como
\[ c=kt \]
con \(0 \lt t \lt g\). Al sustituir, la expresion se simplifica a
\[ Q=\frac{u^3(g^2-t^2)}{v}. \]
Factorizamos ahora la diferencia de cuadrados poniendo
\[ r=g-t, \qquad s=g+t. \]
Asi,
\[ g=\frac{r+s}{2}, \qquad t=\frac{s-r}{2}, \]
de modo que \(r\) y \(s\) son enteros positivos, \(r \lt s\), y ademas
\[ r \equiv s \pmod 2. \]
Las longitudes pasan a ser
\[ a=\frac{u(r+s)}{2}, \qquad b=\frac{v(r+s)}{2}, \qquad c=\frac{k(s-r)}{2}, \]
y el perimetro queda especialmente limpio:
\[ a+b+c=ks. \]
La condicion de cuadrado se convierte en
\[ Q=\frac{u^3rs}{v}. \]
Esta es exactamente la forma que usa el algoritmo rapido. En vez de recorrer \(c\), cuenta los pares \((r,s)\) admisibles para cada razon reducida \(u:v\).
Escribimos
\[ u=d\,h^2, \]
donde \(d=\operatorname{sf}(u)\) es la parte libre de cuadrados de \(u\). Entonces
\[ u^3=d^3h^6=d^2(dh^3)^2, \]
asi que \(u^3\) solo aporta una copia libre de cuadrados de \(d\); todo lo demas ya es cuadrado. Por eso
\[ Q \text{ es cuadrado perfecto } \Longleftrightarrow \frac{drs}{v} \text{ es cuadrado perfecto.} \]
De ahi que las implementaciones precalculen el nucleo libre de cuadrados de \(u\). Para los primos que dividen a \(v\), el producto \(rs\) debe aportar exponente suficiente para cancelar el denominador y dejar una valuacion par. Para los primos que dividen a \(d\), el producto \(rs\) debe aportar una valuacion impar. Todas esas exigencias se resumen en un menor valor base \(s_0\), y todo \(s\) valido para un \((u,v,r)\) fijo tiene la forma
\[ s=s_0n^2 \]
con \(n \ge 1\).
Definimos
\[ L=\left\lfloor\frac{N}{k}\right\rfloor. \]
Como el perimetro es \(ks\), debemos tener \(s \le L\). La restriccion geometrica restante es \(c \ge b\), es decir,
\[ \frac{k(s-r)}{2} \ge \frac{v(r+s)}{2}. \]
Usando \(k=u+v\), esto se simplifica a
\[ us \ge (u+2v)r. \]
Por tanto, para \(u,v,r\) fijos, el primer valor posible es
\[ s_{\min}=\left\lceil\frac{(u+2v)r}{u}\right\rceil. \]
Como \(s=s_0n^2\), el intervalo de \(n\) pasa a ser
\[ n_{\min}=\left\lceil\sqrt{\left\lceil\frac{s_{\min}}{s_0}\right\rceil}\right\rceil, \qquad n_{\max}=\left\lfloor\sqrt{\frac{L}{s_0}}\right\rfloor. \]
La condicion de paridad \(r \equiv s \pmod 2\) se transforma ahora en un filtro sobre \(n\). Si \(s_0\) es par, todo \(s\) admisible sera par, de modo que solo pueden contribuir los \(r\) pares. Si \(s_0\) es impar, entonces \(s \equiv n^2 \equiv n \pmod 2\), asi que necesitamos
\[ n \equiv r \pmod 2. \]
Cada rama aporta simplemente el numero de enteros \(n\) dentro de un intervalo corto con la paridad correcta.
Las soluciones usan una cota global para \(k\). Como \(v \ge k/2\) y \(d \ge 1\), toda rama valida debe satisfacer
\[ vd \le rs \le s^2 \le L^2 \le \left(\frac{N}{k}\right)^2. \]
Por lo tanto,
\[ \frac{k}{2} \le \left(\frac{N}{k}\right)^2, \qquad\text{y por consiguiente}\qquad k^3 \le 2N^2. \]
Eso explica por que solo hay que examinar \(k\) hasta el orden de \((2N^2)^{1/3}\).
Tomemos el triangulo valido \((a,b,c)=(12,15,18)\). Entonces
\[ g=\gcd(12,15)=3,\qquad u=4,\qquad v=5,\qquad k=9. \]
Como \(c=18=9\cdot 2\), tenemos \(t=2\). Asi,
\[ r=g-t=1,\qquad s=g+t=5. \]
Las longitudes se recuperan como
\[ a=\frac{4(1+5)}{2}=12,\qquad b=\frac{5(1+5)}{2}=15,\qquad c=\frac{9(5-1)}{2}=18. \]
La prueba cuadratica da
\[ Q=\frac{4^3 \cdot 1 \cdot 5}{5}=64=8^2. \]
Aqui \(\operatorname{sf}(4)=1\), de modo que, con \(r=1\), la condicion se reduce a que \(s/5\) sea un cuadrado. El menor valor base es \(s_0=5\), y \(s=5=s_0\cdot 1^2\) es efectivamente el primer valor admisible por encima de
\[ s_{\min}=\left\lceil\frac{(4+2\cdot 5)\cdot 1}{4}\right\rceil=4. \]
Este ejemplo pequeño refleja el mecanismo completo del algoritmo.
Las implementaciones en C++, Python y Java empiezan construyendo una tabla del menor factor primo. A partir de ella obtienen dos estructuras reutilizables: la parte libre de cuadrados \(\operatorname{sf}(u)\) para cada posible \(u\), y una factorizacion compacta en exponentes primos para cada entero que puede aparecer como \(v\), \(r\) o \(\operatorname{sf}(u)\). Asi se evita factorizar una y otra vez dentro del conteo principal.
Para cada \(k\), la implementacion recorre \(v\) desde \(\lceil k/2 \rceil\) hasta \(k-1\), conserva solo los casos con \(\gcd(v,k)=1\) y define \(u=k-v\). Luego calcula \(L=\lfloor N/k \rfloor\) y descarta la rama en cuanto \(v\operatorname{sf}(u) \gt L^2\), porque en ese caso ni siquiera el producto maximo posible \(rs\) puede satisfacer la condicion cuadratica.
Despues recorre
\[ 1 \le r \le \left\lfloor\frac{uL}{u+2v}\right\rfloor. \]
Para cada \(r\), la implementacion combina los datos primos de \(r\), \(v\) y \(\operatorname{sf}(u)\) para construir el menor \(s_0\) capaz de hacer cuadrado a \(drs/v\). Si \(s_0 \gt L\), la rama es imposible. Si no, el codigo convierte todas las restricciones en el intervalo \([n_{\min},n_{\max}]\), aplica el filtro de paridad y suma la cantidad de \(n\) validos.
La respuesta total es la suma de esas contribuciones sobre todos los \(k\). La implementacion en Python evalua el bucle exterior en serie. Las versiones en C++ y Java paralelizan precisamente ese barrido exterior, porque una vez construidas las tablas de factores cada valor de \(k\) puede tratarse de forma independiente.
La cota \(k \le O(N^{2/3})\) ya reduce mucho el espacio de busqueda. Para un \(k\) fijo hay \(O(k)\) candidatos para \(v\), y para cada \((u,v)\) superviviente el parametro \(r\) llega hasta \(O(N/k)\). Una cota superior grosera para el numero de ramas aritmeticas es entonces
\[ \sum_{k \le O(N^{2/3})} O(k)\,O\!\left(\frac{N}{k}\right)=O(N^{5/3}). \]
Cada rama solo necesita combinar listas cortas de exponentes primos y hacer unas pocas cuentas de raiz entera e intervalos, de modo que el rendimiento real es mucho mejor que el de un barrido triangulo por triangulo. Ademas, el filtro de coprimalidad y la poda \(v\operatorname{sf}(u) \le L^2\) eliminan muchas ramas antes de cualquier trabajo costoso.
El uso de memoria esta dominado por las tablas primas: el cribado del menor factor primo, el arreglo de partes libres de cuadrados y la tabla de factorizaciones hasta el mayor entero necesario. Eso es esencialmente lineal en el limite del cribado, salvo por un pequeno factor logaritmico debido a los exponentes almacenados.
第 962 题要求统计所有满足 \(a \le b \le c \lt a+b\) 且 \(a+b+c \le N\) 的整数三元组 \((a,b,c)\)，使得题目中的几何构造最终对应到
\[ Q=\frac{a^3(a+b-c)(a+b+c)}{b(a+b)^2} \]
这个量，并且 \(Q\) 是整数完全平方。Project Euler 的正式参数是 \(N=10^6\)。如果直接枚举所有三角形，规模会非常大；因此实现代码改为先做代数化简，再在更小的数论参数空间里计数。
这道题的关键不在于暴力检查每个 \((a,b,c)\)，而在于把三角形拆成“互素比例 + 公共缩放 + 一个平方条件”。一旦这个结构被找出来，原问题就会变成对 \((u,v,r,s)\) 的筛选与区间计数。
设
\[ g=\gcd(a,b), \qquad a=ug, \qquad b=vg, \]
其中 \(\gcd(u,v)=1\)，并且因为 \(a \le b\)，所以 \(u \le v\)。再记
\[ k=u+v. \]
于是 \(a+b=kg\)，原式可以写成
\[ Q=\frac{u^3\bigl(k^2g^2-c^2\bigr)}{vk^2}. \]
这一步非常重要，因为它说明真正需要枚举的不是所有边长，而是最简比例 \(u:v\)。在 \(u\) 和 \(v\) 固定后，剩下的自由度只体现在 \(g\) 和 \(c\) 上。
如果 \(Q\) 是整数，那么 \(k^2\) 必须整除分子 \(u^3(k^2g^2-c^2)\)。由于 \(\gcd(u,k)=1\)，\(u^3\) 不会帮助提供任何 \(k\) 的因子，因此必须有
\[ k^2 \mid \bigl(k^2g^2-c^2\bigr). \]
而 \(k^2g^2\) 本身已经是 \(k^2\) 的倍数，所以只能推出
\[ k^2 \mid c^2. \]
于是
\[ k \mid c. \]
也就是说，每一个有效三角形都可以写成
\[ c=kt \]
其中 \(0 \lt t \lt g\)。代回之后，表达式立刻化简为
\[ Q=\frac{u^3(g^2-t^2)}{v}. \]
接下来把平方差拆开，定义
\[ r=g-t, \qquad s=g+t. \]
于是
\[ g=\frac{r+s}{2}, \qquad t=\frac{s-r}{2}. \]
因此 \(r\) 与 \(s\) 都是正整数，满足 \(r \lt s\)，并且
\[ r \equiv s \pmod 2. \]
三条边可以完全用这些参数表示为
\[ a=\frac{u(r+s)}{2}, \qquad b=\frac{v(r+s)}{2}, \qquad c=\frac{k(s-r)}{2}. \]
更关键的是，周长直接变成
\[ a+b+c=ks. \]
而平方条件则化为
\[ Q=\frac{u^3rs}{v}. \]
到这里，原本依赖 \(c\) 的搜索已经变成：对每一个最简比例 \(u:v\)，统计哪些 \((r,s)\) 会让上式成为完全平方。
把 \(u\) 写成
\[ u=d\,h^2, \]
其中 \(d=\operatorname{sf}(u)\) 表示 \(u\) 的平方自由部分。于是
\[ u^3=d^3h^6=d^2(dh^3)^2. \]
这说明 \(u^3\) 中除了一个平方自由的 \(d\) 以外，其余部分全都是平方。因此
\[ Q \text{ 是完全平方 } \Longleftrightarrow \frac{drs}{v} \text{ 是完全平方。} \]
这正是代码预处理 \(\operatorname{sf}(u)\) 的原因。对于出现在 \(v\) 中的质因子，\(rs\) 必须提供足够的指数来抵消分母并让最终指数变成偶数；对于出现在 \(d\) 中的质因子，\(rs\) 则必须让总指数变成奇数。实现代码把这些逐质数的要求压缩成一个最小基值 \(s_0\)，于是固定 \((u,v,r)\) 后，一切可行的 \(s\) 都写成
\[ s=s_0n^2 \]
的形式。
令
\[ L=\left\lfloor\frac{N}{k}\right\rfloor. \]
因为周长就是 \(ks\)，所以一定有 \(s \le L\)。另一方面，还需要满足 \(c \ge b\)。代入参数表示后得到
\[ \frac{k(s-r)}{2} \ge \frac{v(r+s)}{2}. \]
用 \(k=u+v\) 化简，可得
\[ us \ge (u+2v)r. \]
因此对于固定的 \(u,v,r\)，最小可行值是
\[ s_{\min}=\left\lceil\frac{(u+2v)r}{u}\right\rceil. \]
再利用 \(s=s_0n^2\)，就把问题转成对 \(n\) 的区间统计：
\[ n_{\min}=\left\lceil\sqrt{\left\lceil\frac{s_{\min}}{s_0}\right\rceil}\right\rceil, \qquad n_{\max}=\left\lfloor\sqrt{\frac{L}{s_0}}\right\rfloor. \]
此外还有奇偶性条件 \(r \equiv s \pmod 2\)。如果 \(s_0\) 是偶数，那么所有可行的 \(s\) 都是偶数，此时只有偶数 \(r\) 才可能贡献答案。如果 \(s_0\) 是奇数，那么 \(s \equiv n^2 \equiv n \pmod 2\)，所以必须满足
\[ n \equiv r \pmod 2. \]
也就是说，每个分支最后只需要在一个很短的整数区间里，数一数满足奇偶条件的 \(n\) 有多少个。
代码里的外层上界不是拍脑袋写出来的，而是来自一个必要条件。由于 \(v \ge k/2\)，并且 \(d \ge 1\)，任何有效分支都必须满足
\[ vd \le rs \le s^2 \le L^2 \le \left(\frac{N}{k}\right)^2. \]
因此必有
\[ \frac{k}{2} \le \left(\frac{N}{k}\right)^2, \qquad\text{于是}\qquad k^3 \le 2N^2. \]
这就说明，\(k\) 的范围只有大约 \((2N^2)^{1/3}\) 这么大，而不是线性增长到 \(N\)。
看一个实际有效的三角形 \((a,b,c)=(12,15,18)\)。此时
\[ g=\gcd(12,15)=3,\qquad u=4,\qquad v=5,\qquad k=9. \]
又因为 \(c=18=9\cdot 2\)，所以 \(t=2\)。于是
\[ r=g-t=1,\qquad s=g+t=5. \]
把这些值代回参数公式，可以重新得到三条边：
\[ a=\frac{4(1+5)}{2}=12,\qquad b=\frac{5(1+5)}{2}=15,\qquad c=\frac{9(5-1)}{2}=18. \]
平方判定也变得很直接：
\[ Q=\frac{4^3 \cdot 1 \cdot 5}{5}=64=8^2. \]
这里 \(\operatorname{sf}(4)=1\)，所以当 \(r=1\) 时，条件就是 \(s/5\) 必须是平方。最小基值恰好是 \(s_0=5\)，而
\[ s_{\min}=\left\lceil\frac{(4+2\cdot 5)\cdot 1}{4}\right\rceil=4 \]
说明 \(s=5=s_0\cdot 1^2\) 正好是第一个可行值。这个小例子和完整程序做的事情完全同构。
C++、Python 和 Java 实现都会先建立最小质因子表。基于这张表，再预先计算两类可复用的数据：每个可能的 \(u\) 的平方自由部分 \(\operatorname{sf}(u)\)，以及所有可能出现在 \(v\)、\(r\)、\(\operatorname{sf}(u)\) 中的整数的质因数分解。这样主循环里就不需要反复试除分解。
对每个 \(k\)，程序枚举 \(v\in[\lceil k/2\rceil,\,k-1]\)，只保留 \(\gcd(v,k)=1\) 的情况，然后设 \(u=k-v\)。接着计算 \(L=\lfloor N/k \rfloor\)。如果 \(v\operatorname{sf}(u) \gt L^2\)，这一整个分支会被立刻剪掉，因为此时即便把 \(rs\) 取得尽可能大，也不可能满足平方条件。
然后程序遍历
\[ 1 \le r \le \left\lfloor\frac{uL}{u+2v}\right\rfloor. \]
对每个 \(r\)，它会把 \(r\)、\(v\)、\(\operatorname{sf}(u)\) 的质因数指数要求合并起来，构造出能够让 \(drs/v\) 成为平方的最小 \(s_0\)。如果 \(s_0 \gt L\)，这条分支就不可能成功。否则就把所有条件转成 \([n_{\min},n_{\max}]\) 的区间，再施加奇偶性过滤，最后把满足条件的 \(n\) 的个数累加进去。
总答案就是对所有 \(k\) 的贡献求和。Python 实现按顺序执行这个外层 \(k\) 循环；C++ 与 Java 实现则把这一层并行化，因为在质因数表准备好之后，各个 \(k\) 之间彼此独立。
\(k \le O(N^{2/3})\) 这一外层界已经把搜索空间大幅压缩。对固定的 \(k\)，\(v\) 的候选数是 \(O(k)\)；对每个保留下来的 \((u,v)\)，\(r\) 的范围是 \(O(N/k)\)。因此一个粗略但安全的上界是
\[ \sum_{k \le O(N^{2/3})} O(k)\,O\!\left(\frac{N}{k}\right)=O(N^{5/3}). \]
每个分支内部只需要合并很短的质因数指数列表，再做常数次整数平方根与区间计算，所以实际运行速度远快于直接枚举三角形。再加上互素筛选和 \(v\operatorname{sf}(u) \le L^2\) 的剪枝，很多分支在早期就被排除掉了。
空间方面，主要成本来自几张预处理表：最小质因子筛、平方自由部分数组，以及到所需最大整数为止的因式分解表。总体上可以看成对筛法上界近似线性的内存开销，只附带一个很小的对数级存储因子。
В задаче 962 нужно посчитать все целочисленные тройки \((a,b,c)\), для которых выполнены условия \(a \le b \le c \lt a+b\) и \(a+b+c \le N\), а геометрическая конструкция из условия приводит к величине
\[ Q=\frac{a^3(a+b-c)(a+b+c)}{b(a+b)^2} \]
и эта величина оказывается целым полным квадратом. В версии Project Euler используется \(N=10^6\). Полный перебор всех треугольников слишком дорог, поэтому решение переводит задачу из пространства \((a,b,c)\) в гораздо более компактную арифметическую параметризацию.
Главная идея состоит в том, чтобы сначала вынести общий масштаб сторон \(a\) и \(b\), затем показать, что любой допустимый треугольник имеет жесткую форму через разность квадратов, и после этого считать варианты уже не по самим сторонам, а по параметрам \((u,v,r,s)\).
Положим
\[ g=\gcd(a,b), \qquad a=ug, \qquad b=vg, \]
где \(\gcd(u,v)=1\) и \(u \le v\). Также введем
\[ k=u+v. \]
Тогда \(a+b=kg\), и проверяемое выражение принимает вид
\[ Q=\frac{u^3\bigl(k^2g^2-c^2\bigr)}{vk^2}. \]
Это сразу показывает, что основное состояние задачи задается приведенным отношением \(u:v\). Когда \(u\) и \(v\) фиксированы, вся оставшаяся свобода находится только в \(g\) и \(c\).
Если \(Q\) целое, то \(k^2\) должно делить числитель \(u^3(k^2g^2-c^2)\). Поскольку \(\gcd(u,k)=1\), множитель \(u^3\) не помогает с делимостью на \(k^2\), значит
\[ k^2 \mid \bigl(k^2g^2-c^2\bigr). \]
Но \(k^2g^2\) уже кратно \(k^2\), следовательно \(k^2 \mid c^2\), а значит
\[ k \mid c. \]
Итак, любой допустимый треугольник можно записать в виде
\[ c=kt \]
с некоторым целым \(t\), где \(0 \lt t \lt g\). После подстановки получаем
\[ Q=\frac{u^3(g^2-t^2)}{v}. \]
Теперь разложим разность квадратов, положив
\[ r=g-t, \qquad s=g+t. \]
Тогда
\[ g=\frac{r+s}{2}, \qquad t=\frac{s-r}{2}, \]
поэтому \(r\) и \(s\) являются положительными целыми числами, \(r \lt s\), и выполняется условие
\[ r \equiv s \pmod 2. \]
Стороны выражаются как
\[ a=\frac{u(r+s)}{2}, \qquad b=\frac{v(r+s)}{2}, \qquad c=\frac{k(s-r)}{2}, \]
а периметр становится особенно простым:
\[ a+b+c=ks. \]
Условие на квадрат принимает вид
\[ Q=\frac{u^3rs}{v}. \]
Это и есть форма, на которой строится быстрый алгоритм: вместо перебора \(c\) он считает допустимые пары \((r,s)\) для каждого приведенного отношения \(u:v\).
Запишем
\[ u=d\,h^2, \]
где \(d=\operatorname{sf}(u)\) - квадратсвободная часть числа \(u\). Тогда
\[ u^3=d^3h^6=d^2(dh^3)^2, \]
то есть в \(u^3\) остается ровно одна квадратсвободная копия \(d\), а все остальное уже является квадратом. Следовательно,
\[ Q \text{ является полным квадратом } \Longleftrightarrow \frac{drs}{v} \text{ является полным квадратом.} \]
Именно поэтому реализации предварительно вычисляют \(\operatorname{sf}(u)\). Для простых, входящих в \(v\), произведение \(rs\) должно дать достаточно степени, чтобы убрать знаменатель и оставить четную итоговую оценку. Для простых, входящих в \(d\), произведение \(rs\) должно дать нечетную оценку. Все эти локальные требования сжимаются в минимальное базовое значение \(s_0\), и любой допустимый \(s\) при фиксированных \((u,v,r)\) имеет вид
\[ s=s_0n^2 \]
для некоторого \(n \ge 1\).
Пусть
\[ L=\left\lfloor\frac{N}{k}\right\rfloor. \]
Так как периметр равен \(ks\), обязано выполняться \(s \le L\). Оставшееся геометрическое условие - это \(c \ge b\), то есть
\[ \frac{k(s-r)}{2} \ge \frac{v(r+s)}{2}. \]
После подстановки \(k=u+v\) получаем
\[ us \ge (u+2v)r. \]
Поэтому для фиксированных \(u,v,r\) минимально возможное значение равно
\[ s_{\min}=\left\lceil\frac{(u+2v)r}{u}\right\rceil. \]
Так как \(s=s_0n^2\), разрешенный диапазон для \(n\) имеет вид
\[ n_{\min}=\left\lceil\sqrt{\left\lceil\frac{s_{\min}}{s_0}\right\rceil}\right\rceil, \qquad n_{\max}=\left\lfloor\sqrt{\frac{L}{s_0}}\right\rfloor. \]
Условие четности \(r \equiv s \pmod 2\) теперь превращается в фильтр по \(n\). Если \(s_0\) четно, то любой допустимый \(s\) четен, и тогда только четные \(r\) могут дать вклад. Если \(s_0\) нечетно, то \(s \equiv n^2 \equiv n \pmod 2\), поэтому нужно
\[ n \equiv r \pmod 2. \]
Итак, каждый рассматриваемый случай сводится к подсчету количества целых \(n\) в коротком интервале с нужной четностью.
Решения используют жесткую глобальную оценку для \(k\). Поскольку \(v \ge k/2\) и \(d \ge 1\), в любой допустимой ветви должно выполняться
\[ vd \le rs \le s^2 \le L^2 \le \left(\frac{N}{k}\right)^2. \]
Отсюда следует
\[ \frac{k}{2} \le \left(\frac{N}{k}\right)^2, \qquad\text{а значит}\qquad k^3 \le 2N^2. \]
Вот почему нужно просматривать только значения \(k\) порядка \((2N^2)^{1/3}\), а не все числа до \(N\).
Возьмем допустимый треугольник \((a,b,c)=(12,15,18)\). Тогда
\[ g=\gcd(12,15)=3,\qquad u=4,\qquad v=5,\qquad k=9. \]
Так как \(c=18=9\cdot 2\), имеем \(t=2\), а значит
\[ r=g-t=1,\qquad s=g+t=5. \]
По формулам восстановления получаем
\[ a=\frac{4(1+5)}{2}=12,\qquad b=\frac{5(1+5)}{2}=15,\qquad c=\frac{9(5-1)}{2}=18. \]
Проверяемое значение равно
\[ Q=\frac{4^3 \cdot 1 \cdot 5}{5}=64=8^2. \]
Здесь \(\operatorname{sf}(4)=1\), поэтому при \(r=1\) условие сводится к тому, что \(s/5\) должно быть квадратом. Минимальное базовое значение равно \(s_0=5\), и
\[ s_{\min}=\left\lceil\frac{(4+2\cdot 5)\cdot 1}{4}\right\rceil=4 \]
показывает, что \(s=5=s_0\cdot 1^2\) действительно является первым допустимым значением. Этот маленький пример отражает весь ход алгоритма.
Реализации на C++, Python и Java начинают с построения таблицы минимального простого делителя. На ее основе заранее вычисляются два вида данных: квадратсвободная часть \(\operatorname{sf}(u)\) для всех возможных \(u\) и компактные разложения на простые множители для всех чисел, которые могут появиться как \(v\), \(r\) или \(\operatorname{sf}(u)\). Благодаря этому основному счету не приходится постоянно выполнять факторизацию заново.
Для каждого \(k\) программа перебирает \(v\) от \(\lceil k/2 \rceil\) до \(k-1\), оставляет только случаи с \(\gcd(v,k)=1\) и затем ставит \(u=k-v\). После этого вычисляется \(L=\lfloor N/k \rfloor\). Если \(v\operatorname{sf}(u) \gt L^2\), ветвь отбрасывается сразу, потому что даже максимально возможное произведение \(rs\) не сможет удовлетворить квадратному условию.
Далее выполняется цикл
\[ 1 \le r \le \left\lfloor\frac{uL}{u+2v}\right\rfloor. \]
Для каждого \(r\) объединяются простые данные из \(r\), \(v\) и \(\operatorname{sf}(u)\), чтобы построить наименьшее \(s_0\), способное сделать \(drs/v\) квадратом. Если \(s_0 \gt L\), ветвь невозможна. Иначе все ограничения переводятся в интервал \([n_{\min},n_{\max}]\), применяется фильтр четности, и число допустимых \(n\) добавляется к ответу.
Итоговый ответ есть сумма всех таких вкладов по всем \(k\). Версия на Python выполняет внешний цикл по \(k\) последовательно. Реализации на C++ и Java распараллеливают именно этот внешний проход, потому что после подготовки таблиц факторов каждый \(k\) можно обрабатывать независимо.
Ограничение \(k \le O(N^{2/3})\) уже радикально уменьшает пространство поиска. Для фиксированного \(k\) имеется \(O(k)\) кандидатов для \(v\), а для каждой surviving пары \((u,v)\) параметр \(r\) пробегает диапазон длины \(O(N/k)\). Поэтому грубая верхняя оценка числа арифметических ветвей такова:
\[ \sum_{k \le O(N^{2/3})} O(k)\,O\!\left(\frac{N}{k}\right)=O(N^{5/3}). \]
Внутри каждой ветви выполняется лишь слияние коротких списков простых степеней и несколько вычислений целого квадратного корня и границ интервала, поэтому на практике метод намного быстрее полного перебора треугольников. Дополнительную экономию дают фильтр взаимной простоты и отсечение по условию \(v\operatorname{sf}(u) \le L^2\).
Память в основном расходуется на предвычисленные таблицы: решето минимального простого делителя, массив квадратсвободных частей и таблицу факторизаций до наибольшего нужного числа. Это почти линейно по верхней границе решета, если не считать небольшого логарифмического множителя на хранение простых степеней.
تطلب المسألة 962 عدّ جميع الثلاثيات الصحيحة \((a,b,c)\) التي تحقق \(a \le b \le c \lt a+b\) و \(a+b+c \le N\)، بحيث تؤدي البنية الهندسية في نص المسألة إلى الكمية
\[ Q=\frac{a^3(a+b-c)(a+b+c)}{b(a+b)^2} \]
ويكون هذا المقدار مربعًا كاملًا صحيحًا. في نسخة Project Euler المعتمدة لدينا \(N=10^6\). التعداد المباشر لكل المثلثات بطيء جدًا، لذلك تنتقل الحلول إلى إعادة صياغة عددية أصغر كثيرًا من فضاء \((a,b,c)\) الأصلي.
الفكرة الأساسية هي فصل العامل المشترك بين \(a\) و\(b\)، ثم إثبات أن كل مثلث صالح يملك تمثيلًا صارمًا يعتمد على فرق مربعين، وبعد ذلك عدّ الحالات المتبقية عبر الجزء الخالي من المربعات وحسابات فترات بسيطة.
لنكتب
\[ g=\gcd(a,b), \qquad a=ug, \qquad b=vg, \]
حيث \(\gcd(u,v)=1\) ومع \(u \le v\). ونعرّف كذلك
\[ k=u+v. \]
عندها يصبح \(a+b=kg\)، ويتحول الشرط إلى
\[ Q=\frac{u^3\bigl(k^2g^2-c^2\bigr)}{vk^2}. \]
هذه الخطوة توضح أن النسبة المختزلة \(u:v\) هي الكائن الرياضي الحقيقي في الحل. فإذا ثبتت \(u\) و\(v\)، بقيت الحرية كلها تقريبًا داخل \(g\) و\(c\).
إذا كان \(Q\) عددًا صحيحًا، فلا بد أن يقسم \(k^2\) البسط \(u^3(k^2g^2-c^2)\). وبما أن \(\gcd(u,k)=1\)، فإن العامل \(u^3\) لا يساعد في توفير قوى من \(k\)، ولذلك يجب أن يكون
\[ k^2 \mid \bigl(k^2g^2-c^2\bigr). \]
لكن \(k^2g^2\) مضاعف لـ \(k^2\) أصلًا، ومن ثم نحصل على
\[ k^2 \mid c^2 \]
وبالتالي
\[ k \mid c. \]
إذن كل مثلث صالح يمكن كتابته على صورة
\[ c=kt \]
حيث \(0 \lt t \lt g\). وبعد التعويض يتبسط التعبير إلى
\[ Q=\frac{u^3(g^2-t^2)}{v}. \]
الآن نحلل فرق المربعين بتعريف
\[ r=g-t, \qquad s=g+t. \]
وعندها
\[ g=\frac{r+s}{2}, \qquad t=\frac{s-r}{2}. \]
إذن \(r\) و\(s\) عددان صحيحان موجبان، و\(r \lt s\)، كما أن
\[ r \equiv s \pmod 2. \]
فتصبح أضلاع المثلث
\[ a=\frac{u(r+s)}{2}, \qquad b=\frac{v(r+s)}{2}, \qquad c=\frac{k(s-r)}{2}, \]
ويتبسط المحيط إلى
\[ a+b+c=ks. \]
أما شرط المربع الكامل فيصير
\[ Q=\frac{u^3rs}{v}. \]
وهذه بالضبط هي الصيغة التي تعتمد عليها الخوارزمية السريعة. فبدل الدوران على \(c\) مباشرة، يجري عدّ الأزواج \((r,s)\) الممكنة لكل نسبة مختزلة \(u:v\).
اكتب
\[ u=d\,h^2, \]
حيث \(d=\operatorname{sf}(u)\) هو الجزء الخالي من المربعات في \(u\). عندها
\[ u^3=d^3h^6=d^2(dh^3)^2, \]
أي إن \(u^3\) يترك نسخة واحدة فقط غير مربعة من \(d\)، بينما كل ما تبقى مربع أصلًا. لهذا فإن
\[ Q \text{ يكون مربعًا كاملًا } \Longleftrightarrow \frac{drs}{v} \text{ يكون مربعًا كاملًا.} \]
ولهذا السبب تبني الحلول الجزء \(\operatorname{sf}(u)\) مسبقًا. بالنسبة إلى العوامل الأولية الموجودة في \(v\)، يجب على \(rs\) أن يوفر الأسس اللازمة لإزالة المقام وجعل الأس النهائي زوجيًا. وبالنسبة إلى العوامل الأولية الموجودة في \(d\)، يجب أن يوفّر \(rs\) أسًا فرديًا. تُضغط هذه الشروط كلها في أصغر قيمة أساسية ممكنة \(s_0\)، وبعدها يصبح كل \(s\) صالح عند ثبات \((u,v,r)\) من الشكل
\[ s=s_0n^2 \]
لعدد صحيح \(n \ge 1\).
لنعرّف
\[ L=\left\lfloor\frac{N}{k}\right\rfloor. \]
بما أن المحيط يساوي \(ks\)، فلا بد أن يكون \(s \le L\). ويبقى القيد الهندسي \(c \ge b\)، أي
\[ \frac{k(s-r)}{2} \ge \frac{v(r+s)}{2}. \]
وباستخدام \(k=u+v\) نحصل على
\[ us \ge (u+2v)r. \]
إذًا لأجل \(u,v,r\) ثابتة تكون أول قيمة ممكنة هي
\[ s_{\min}=\left\lceil\frac{(u+2v)r}{u}\right\rceil. \]
ومع \(s=s_0n^2\) يصبح مجال \(n\)
\[ n_{\min}=\left\lceil\sqrt{\left\lceil\frac{s_{\min}}{s_0}\right\rceil}\right\rceil, \qquad n_{\max}=\left\lfloor\sqrt{\frac{L}{s_0}}\right\rfloor. \]
كما أن شرط التوافق \(r \equiv s \pmod 2\) يتحول إلى قيد على \(n\). فإذا كان \(s_0\) زوجيًا، فكل \(s\) صالح سيكون زوجيًا أيضًا، وبالتالي لا يمكن أن يساهم إلا \(r\) الزوجي. وإذا كان \(s_0\) فرديًا، فلدينا \(s \equiv n^2 \equiv n \pmod 2\)، ومن ثم يجب أن يتحقق
\[ n \equiv r \pmod 2. \]
وهكذا تختزل مساهمة كل فرع إلى عدد صحيح قصير داخل فترة مع شرط زوجية أو فردية مناسب.
تستخدم الحلول حدًا علويًا حادًا على \(k\). بما أن \(v \ge k/2\) و\(d \ge 1\)، فلا بد لأي فرع صالح أن يحقق
\[ vd \le rs \le s^2 \le L^2 \le \left(\frac{N}{k}\right)^2. \]
ومن هنا ينتج
\[ \frac{k}{2} \le \left(\frac{N}{k}\right)^2, \qquad\text{وبالتالي}\qquad k^3 \le 2N^2. \]
لهذا لا يلزم فحص إلا قيم \(k\) حتى رتبة \((2N^2)^{1/3}\) تقريبًا.
لنأخذ المثلث الصالح \((a,b,c)=(12,15,18)\). عندئذ
\[ g=\gcd(12,15)=3,\qquad u=4,\qquad v=5,\qquad k=9. \]
وبما أن \(c=18=9\cdot 2\)، فإن \(t=2\). ومن ثم
\[ r=g-t=1,\qquad s=g+t=5. \]
وباستخدام الصيغ نستعيد الأضلاع مباشرة:
\[ a=\frac{4(1+5)}{2}=12,\qquad b=\frac{5(1+5)}{2}=15,\qquad c=\frac{9(5-1)}{2}=18. \]
أما الاختبار فيعطي
\[ Q=\frac{4^3 \cdot 1 \cdot 5}{5}=64=8^2. \]
هنا \(\operatorname{sf}(4)=1\)، ولذلك عندما \(r=1\) يختزل الشرط إلى أن يكون \(s/5\) مربعًا. أصغر قيمة أساسية هي \(s_0=5\)، ومع
\[ s_{\min}=\left\lceil\frac{(4+2\cdot 5)\cdot 1}{4}\right\rceil=4 \]
نرى أن \(s=5=s_0\cdot 1^2\) هو أول اختيار صالح. هذا المثال الصغير يلخص بدقة ما تفعله الخوارزمية الكاملة.
تبدأ تطبيقات C++ وPython وJava ببناء جدول أصغر عامل أولي. ومن هذا الجدول تُستخرج بنيتان يعاد استخدامهما: الجزء الخالي من المربعات \(\operatorname{sf}(u)\) لكل \(u\) محتمل، وتحليل أولي مضغوط لكل عدد يمكن أن يظهر بوصفه \(v\) أو \(r\) أو \(\operatorname{sf}(u)\). وبهذا لا تعود الخوارزمية بحاجة إلى إعادة التحليل الأولي داخل الحلقة الرئيسية.
لكل \(k\)، تدور الخوارزمية على \(v\) من \(\lceil k/2 \rceil\) حتى \(k-1\)، ثم تبقي فقط الحالات التي تحقق \(\gcd(v,k)=1\)، وتضع \(u=k-v\). بعد ذلك تحسب \(L=\lfloor N/k \rfloor\). وإذا تحقق \(v\operatorname{sf}(u) \gt L^2\)، فإن الفرع يُستبعد فورًا، لأن أكبر قيمة ممكنة لـ \(rs\) لن تكفي عندئذ لتحقيق شرط المربع الكامل.
ثم يجري التكرار على
\[ 1 \le r \le \left\lfloor\frac{uL}{u+2v}\right\rfloor. \]
ولكل \(r\)، تدمج الخوارزمية المعلومات الأولية القادمة من \(r\) و\(v\) و\(\operatorname{sf}(u)\) لبناء أصغر \(s_0\) قادر على جعل \(drs/v\) مربعًا. إذا كان \(s_0 \gt L\)، فالفرع مستحيل. وإلا تتحول الشروط كلها إلى الفترة \([n_{\min},n_{\max}]\)، ثم يطبّق مرشح الزوجية، ثم يضاف عدد قيم \(n\) الصالحة إلى المجموع.
الجواب النهائي هو مجموع هذه المساهمات على جميع قيم \(k\). تنفيذ Python ينفذ الحلقة الخارجية على \(k\) بصورة تسلسلية. أما C++ وJava فيوازيان هذا المسح الخارجي تحديدًا، لأن كل قيمة \(k\) تصبح مستقلة بعد تجهيز جداول التحليل الأولي.
الحد \(k \le O(N^{2/3})\) يقلص فضاء البحث بصورة كبيرة من البداية. فلكل \(k\) ثابت هناك \(O(k)\) خيارات ممكنة لـ \(v\)، ولكل زوج ناجٍ \((u,v)\) يمتد \(r\) حتى \(O(N/k)\). لذلك يكون حد علوي خشن لكنه آمن لعدد الفروع الحسابية هو
\[ \sum_{k \le O(N^{2/3})} O(k)\,O\!\left(\frac{N}{k}\right)=O(N^{5/3}). \]
وكل فرع ينفذ فقط دمجًا قصيرًا لقوائم الأسس الأولية مع حسابات بسيطة للجذر التربيعي الصحيح وحدود الفترات، ولذلك يكون الأداء العملي أفضل بكثير من تعداد المثلثات مباشرة. كما أن شرط التوافق النسبي ومرشح \(v\operatorname{sf}(u) \le L^2\) يحذفان عددًا كبيرًا من الفروع في وقت مبكر.
استهلاك الذاكرة تهيمن عليه جداول المعالجة المسبقة: غربال أصغر عامل أولي، ومصفوفة الأجزاء الخالية من المربعات، وجدول التحليلات الأولية حتى أكبر عدد مطلوب. وهذا يساوي تقريبًا كلفة خطية في حد الغربال، مع عامل لوغاريتمي صغير لتخزين الأسس.