Let \(S(N)\) denote the sum of \(a+b+c\) over all integer triples \((a,b,c)\) with \(1\le a\le b\le N\) such that
$$\sqrt{ab}\in \mathbb{Z},\qquad c=\frac{ab}{a+b+2\sqrt{ab}}\in \mathbb{Z}_{>0}.$$
The tangent-circle geometry is already condensed into this arithmetic condition. The difficulty is that \(a\) and \(b\) are tied together by both a square-root constraint and a divisibility constraint, so scanning all pairs up to \(N=10^9\) is far too slow. The key is to show that every valid triple comes from one coprime parameter pair and one scale factor.
The solution derives a complete parameterization and then sums one whole family at a time.
Write
$$a=g u,\qquad b=g v,\qquad \gcd(u,v)=1,$$
where \(g=\gcd(a,b)\). Because \(\sqrt{ab}\) is an integer, the product \(ab=g^2uv\) is a perfect square, so \(uv\) is also a perfect square. Since \(u\) and \(v\) are coprime, each of them must already be a square:
$$u=m^2,\qquad v=n^2,\qquad \gcd(m,n)=1.$$
Therefore every valid pair can be written as
$$a=g m^2,\qquad b=g n^2,\qquad \sqrt{ab}=gmn.$$
Substituting the previous form into the definition of \(c\) gives
$$c=\frac{g^2m^2n^2}{g(m^2+n^2+2mn)}=\frac{g m^2n^2}{(m+n)^2}.$$
Now
$$\gcd(m+n,m)=\gcd(m+n,n)=1,$$
so \((m+n)\) is coprime to both \(m\) and \(n\), hence
$$\gcd\left((m+n)^2,m^2n^2\right)=1.$$
That means the entire denominator \((m+n)^2\) must come from the common factor \(g\). So there is a positive integer \(t\) with
$$g=t(m+n)^2.$$
We obtain the exact shape of every valid triple:
$$a=t(m+n)^2m^2,\qquad b=t(m+n)^2n^2,\qquad c=t m^2n^2.$$
The converse is immediate. If \(\gcd(m,n)=1\) and \(t\ge 1\), then
$$\sqrt{ab}=t(m+n)^2mn\in \mathbb{Z},$$
and
$$a+b+2\sqrt{ab}=t(m+n)^2(m^2+n^2+2mn)=t(m+n)^4.$$
Therefore
$$\frac{ab}{a+b+2\sqrt{ab}}=\frac{t^2(m+n)^4m^2n^2}{t(m+n)^4}=t m^2n^2=c,$$
so every triple of this form is valid. The coprime pair \((m,n)\) is unique up to swapping the two entries, so enforcing
$$m\le n$$
removes double counting. For one coprime pair, the primitive triple is
$$a_0=(m+n)^2m^2,\qquad b_0=(m+n)^2n^2,\qquad c_0=m^2n^2.$$
When \(m\le n\), the three components satisfy
$$c_0\le a_0\le b_0.$$
So after scaling by \(t\), the condition that all components lie under \(N\) reduces to the single inequality
$$t b_0\le N.$$
Hence the admissible scales are exactly
$$1\le t\le t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor.$$
The entire family generated by one primitive triple contributes
$$\sum_{t=1}^{t_{\max}} t(a_0+b_0+c_0)=(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
For fixed \(n\), the quantity \(b_0=(m+n)^2n^2\) increases with \(m\), so once \(b_0>N\) the inner search can stop immediately. The smallest possible \(b_0\) for that \(n\) occurs at \(m=1\):
$$b_{0,\min}=(n+1)^2n^2.$$
If this already exceeds \(N\), then no larger \(n\) can work. Because \(b_{0,\min}\) is on the order of \(n^4\), only values
$$n=O(N^{1/4})$$
must be inspected.
The feasible coprime pairs with \(m\le n\) are very few.
For \((m,n)=(1,1)\), the primitive triple is
$$(a_0,b_0,c_0)=(4,4,1),\qquad t_{\max}=\left\lfloor\frac{100}{4}\right\rfloor=25.$$
Its contribution is
$$(4+4+1)\frac{25\cdot 26}{2}=9\cdot 325=2925.$$
For \((m,n)=(1,2)\), the primitive triple is
$$(a_0,b_0,c_0)=(9,36,4),\qquad t_{\max}=\left\lfloor\frac{100}{36}\right\rfloor=2,$$
so the contribution is
$$(9+36+4)\frac{2\cdot 3}{2}=49\cdot 3=147.$$
The pair \((2,2)\) is excluded because it is not coprime, and for \(n=3\) even the smallest possible largest term is
$$(3+1)^2\cdot 3^2=144>100.$$
Therefore
$$S(100)=2925+147=3072,$$
matching the checkpoint used by the implementation.
The C++, Python, and Java implementations all use the parameterization above instead of testing arbitrary pairs \((a,b)\). They iterate the larger coprime parameter upward, stop as soon as \((n+1)^2n^2>N\), and for each admissible value scan the smaller parameter up to \(n\).
Non-coprime pairs are skipped immediately. For each remaining pair, the implementation builds the primitive triple \((a_0,b_0,c_0)\), breaks the inner loop when \(b_0>N\), computes
$$t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor,$$
and adds
$$(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
So the code never searches invalid triples and never performs an expensive global brute-force scan. It sums complete scaling families directly.
Let \(R=\lfloor N^{1/4}\rfloor\). Because the search only considers \(1\le m\le n\le R\), the number of candidate pairs is at most \(R(R+1)/2=O(\sqrt{N})\). Each pair needs one coprimality test and a constant amount of integer arithmetic, so the overall running time is \(O(\sqrt{N})\) in arithmetic operations, with \(O(1)\) extra memory.
Sei \(S(N)\) die Summe von \(a+b+c\) über alle ganzzahligen Tripel \((a,b,c)\) mit \(1\le a\le b\le N\), für die
$$\sqrt{ab}\in \mathbb{Z},\qquad c=\frac{ab}{a+b+2\sqrt{ab}}\in \mathbb{Z}_{>0}$$
gilt. Die Geometrie der Tangentialkreise ist damit bereits auf eine rein arithmetische Bedingung reduziert. Schwer ist, dass \(a\) und \(b\) zugleich durch eine Quadratwurzelbedingung und durch eine Teilbarkeitsbedingung gekoppelt sind. Ein Durchlauf aller Paare bis \(N=10^9\) ist daher unmöglich; stattdessen zeigt man, dass jedes gültige Tripel aus genau einem teilerfremden Parameterpaar und einem Skalierungsfaktor entsteht.
Die Lösung gewinnt zunächst eine vollständige Parametrisierung und summiert dann ganze Skalierungsfamilien auf einmal.
Schreibe
$$a=g u,\qquad b=g v,\qquad \gcd(u,v)=1,$$
wobei \(g=\gcd(a,b)\) ist. Da \(\sqrt{ab}\) ganzzahlig ist, ist \(ab=g^2uv\) ein Quadrat, also auch \(uv\). Weil \(u\) und \(v\) teilerfremd sind, müssen beide selbst Quadrate sein:
$$u=m^2,\qquad v=n^2,\qquad \gcd(m,n)=1.$$
Damit hat jedes zulässige Paar die Form
$$a=g m^2,\qquad b=g n^2,\qquad \sqrt{ab}=gmn.$$
Einsetzen in die Definition von \(c\) liefert
$$c=\frac{g^2m^2n^2}{g(m^2+n^2+2mn)}=\frac{g m^2n^2}{(m+n)^2}.$$
Nun gilt
$$\gcd(m+n,m)=\gcd(m+n,n)=1,$$
also ist \((m+n)\) zu \(m\) und \(n\) teilerfremd und daher
$$\gcd\left((m+n)^2,m^2n^2\right)=1.$$
Folglich muss der gesamte Nenner \((m+n)^2\) aus dem gemeinsamen Faktor \(g\) stammen. Es gibt also ein \(t\in\mathbb{Z}_{>0}\) mit
$$g=t(m+n)^2.$$
Damit erhält man die exakte Gestalt jedes gültigen Tripels:
$$a=t(m+n)^2m^2,\qquad b=t(m+n)^2n^2,\qquad c=t m^2n^2.$$
Die Umkehrung ist unmittelbar. Für \(\gcd(m,n)=1\) und \(t\ge 1\) gilt
$$\sqrt{ab}=t(m+n)^2mn\in \mathbb{Z},$$
und außerdem
$$a+b+2\sqrt{ab}=t(m+n)^2(m^2+n^2+2mn)=t(m+n)^4.$$
Daher
$$\frac{ab}{a+b+2\sqrt{ab}}=\frac{t^2(m+n)^4m^2n^2}{t(m+n)^4}=t m^2n^2=c,$$
also ist jedes Tripel dieser Form tatsächlich gültig. Das teilerfremde Paar \((m,n)\) ist bis auf Vertauschung eindeutig; die Nebenbedingung
$$m\le n$$
verhindert daher Doppelzählungen. Für ein festes Paar entsteht das primitive Tripel
$$a_0=(m+n)^2m^2,\qquad b_0=(m+n)^2n^2,\qquad c_0=m^2n^2.$$
Für \(m\le n\) gilt
$$c_0\le a_0\le b_0.$$
Nach Skalierung mit \(t\) genügt es also, nur
$$t b_0\le N$$
zu fordern. Die zulässigen Skalierungsfaktoren sind genau
$$1\le t\le t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor.$$
Der gesamte Beitrag einer primitiven Familie ist damit
$$\sum_{t=1}^{t_{\max}} t(a_0+b_0+c_0)=(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
Für festes \(n\) wächst \(b_0=(m+n)^2n^2\) mit \(m\). Sobald also \(b_0>N\) ist, kann die innere Schleife sofort enden. Das kleinste mögliche \(b_0\) zu diesem \(n\) erhält man bei \(m=1\):
$$b_{0,\min}=(n+1)^2n^2.$$
Ist schon dieser Wert größer als \(N\), so funktioniert kein größeres \(n\) mehr. Weil \(b_{0,\min}\) von der Größenordnung \(n^4\) ist, müssen nur
$$n=O(N^{1/4})$$
betrachtet werden.
Die Zahl zulässiger teilerfremder Paare mit \(m\le n\) ist hier sehr klein.
Für \((m,n)=(1,1)\) ist das primitive Tripel
$$(a_0,b_0,c_0)=(4,4,1),\qquad t_{\max}=\left\lfloor\frac{100}{4}\right\rfloor=25.$$
Sein Beitrag ist
$$(4+4+1)\frac{25\cdot 26}{2}=9\cdot 325=2925.$$
Für \((m,n)=(1,2)\) erhält man
$$(a_0,b_0,c_0)=(9,36,4),\qquad t_{\max}=\left\lfloor\frac{100}{36}\right\rfloor=2,$$
also den Beitrag
$$(9+36+4)\frac{2\cdot 3}{2}=49\cdot 3=147.$$
Das Paar \((2,2)\) fällt weg, weil es nicht teilerfremd ist, und für \(n=3\) ist bereits der kleinste mögliche größte Term
$$(3+1)^2\cdot 3^2=144>100.$$
Somit
$$S(100)=2925+147=3072,$$
genau der Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen verwenden alle die obige Parametrisierung, anstatt beliebige Paare \((a,b)\) zu testen. Sie erhöhen den größeren teilerfremden Parameter schrittweise, brechen ab, sobald \((n+1)^2n^2>N\) gilt, und durchlaufen für jeden zulässigen Wert den kleineren Parameter bis \(n\).
Nicht teilerfremde Paare werden sofort übersprungen. Für jedes verbleibende Paar konstruiert die Implementierung das primitive Tripel \((a_0,b_0,c_0)\), beendet die innere Schleife bei \(b_0>N\), berechnet
$$t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor,$$
und addiert
$$(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
Dadurch sucht der Code nie nach ungültigen Tripeln und führt keinen globalen Brute-Force-Durchlauf aus. Er summiert direkt ganze Skalierungsfamilien.
Sei \(R=\lfloor N^{1/4}\rfloor\). Da die Suche nur \(1\le m\le n\le R\) betrachtet, gibt es höchstens \(R(R+1)/2=O(\sqrt{N})\) Kandidatenpaare. Jedes Paar benötigt einen Teilerfremdheitstest und konstant viele ganzzahlige Rechenoperationen. Somit beträgt die Laufzeit \(O(\sqrt{N})\) in arithmetischen Operationen, bei \(O(1)\) zusätzlichem Speicher.
\(S(N)\),
$$\sqrt{ab}\in \mathbb{Z},\qquad c=\frac{ab}{a+b+2\sqrt{ab}}\in \mathbb{Z}_{>0}$$
koşullarını sağlayan ve \(1\le a\le b\le N\) sınırı altında kalan tüm \((a,b,c)\) üçlüleri için \(a+b+c\) toplamı olsun. Teğet çember geometrisi burada tamamen aritmetik bir koşula indirgenmiştir. Zorluk şuradadır: \(a\) ile \(b\) hem karekök şartı hem de bölünebilme şartı ile birbirine bağlanır. Bu yüzden \(N=10^9\) düzeyinde bütün \((a,b)\) çiftlerini denemek imkansızdır. Çözüm, her geçerli üçlünün bir aralarında asal parametre çifti ile bir ölçek katsayısından geldiğini gösterir.
Önce tam bir parametrizasyon elde edilir, sonra her ilkel aile tek hamlede toplanır.
Şöyle yazalım:
$$a=g u,\qquad b=g v,\qquad \gcd(u,v)=1,$$
burada \(g=\gcd(a,b)\). \(\sqrt{ab}\) tam sayı olduğundan \(ab=g^2uv\) tam karedir; dolayısıyla \(uv\) de tam karedir. \(u\) ve \(v\) aralarında asal olduğu için her biri ayrı ayrı kare olmak zorundadır:
$$u=m^2,\qquad v=n^2,\qquad \gcd(m,n)=1.$$
Böylece her geçerli çift
$$a=g m^2,\qquad b=g n^2,\qquad \sqrt{ab}=gmn$$
şeklinde yazılır.
Bu ifadeyi \(c\)'nin tanımında yerine koyunca
$$c=\frac{g^2m^2n^2}{g(m^2+n^2+2mn)}=\frac{g m^2n^2}{(m+n)^2}$$
elde edilir. Ayrıca
$$\gcd(m+n,m)=\gcd(m+n,n)=1,$$
yani \((m+n)\), hem \(m\) hem de \(n\) ile aralarında asaldır. Bu yüzden
$$\gcd\left((m+n)^2,m^2n^2\right)=1.$$
O halde paydadaki \((m+n)^2\) çarpanının tamamı ortak katsayı \(g\)'den gelmelidir. Demek ki bir \(t\in\mathbb{Z}_{>0}\) vardır ve
$$g=t(m+n)^2.$$
Böylece her geçerli üçlü tam olarak şu biçimdedir:
$$a=t(m+n)^2m^2,\qquad b=t(m+n)^2n^2,\qquad c=t m^2n^2.$$
Tersi yön de hemen görülür. Eğer \(\gcd(m,n)=1\) ve \(t\ge 1\) ise
$$\sqrt{ab}=t(m+n)^2mn\in \mathbb{Z},$$
ve
$$a+b+2\sqrt{ab}=t(m+n)^2(m^2+n^2+2mn)=t(m+n)^4.$$
Dolayısıyla
$$\frac{ab}{a+b+2\sqrt{ab}}=\frac{t^2(m+n)^4m^2n^2}{t(m+n)^4}=t m^2n^2=c,$$
yani bu biçimdeki her üçlü gerçekten geçerlidir. \((m,n)\) aralarında asal çifti, iki bileşenin yer değiştirmesi dışında tektir. Bu nedenle
$$m\le n$$
şartı tekrar sayımı önler. Sabit bir çift için ilkel üçlü
$$a_0=(m+n)^2m^2,\qquad b_0=(m+n)^2n^2,\qquad c_0=m^2n^2$$
olur.
\(m\le n\) iken
$$c_0\le a_0\le b_0$$
olduğu için, \(t\) ile ölçeklendirdikten sonra tüm bileşenlerin \(N\) altında kalması sadece
$$t b_0\le N$$
eşitsizliğine indirgenir. Bu yüzden uygun ölçek değerleri tam olarak
$$1\le t\le t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor$$
aralığındadır. Bir ilkel ailenin toplam katkısı da
$$\sum_{t=1}^{t_{\max}} t(a_0+b_0+c_0)=(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}$$
şeklindedir.
Sabit \(n\) için \(b_0=(m+n)^2n^2\) ifadesi \(m\) arttıkça büyür. Bu yüzden \(b_0>N\) olur olmaz iç döngü güvenle durdurulabilir. Bu \(n\) için en küçük olası \(b_0\), \(m=1\) durumunda gelir:
$$b_{0,\min}=(n+1)^2n^2.$$
Eğer bu değer bile \(N\)'yi aşıyorsa daha büyük hiçbir \(n\) çalışmaz. Çünkü \(b_{0,\min}\) kabaca \(n^4\) mertebesindedir; dolayısıyla yalnızca
$$n=O(N^{1/4})$$
seviyesine kadar bakmak yeterlidir.
\(m\le n\) koşulundaki uygun aralarında asal çiftler çok azdır.
\((m,n)=(1,1)\) için ilkel üçlü
$$(a_0,b_0,c_0)=(4,4,1),\qquad t_{\max}=\left\lfloor\frac{100}{4}\right\rfloor=25.$$
Bunun katkısı
$$(4+4+1)\frac{25\cdot 26}{2}=9\cdot 325=2925$$
olur. \((m,n)=(1,2)\) için
$$(a_0,b_0,c_0)=(9,36,4),\qquad t_{\max}=\left\lfloor\frac{100}{36}\right\rfloor=2,$$
dolayısıyla katkı
$$(9+36+4)\frac{2\cdot 3}{2}=49\cdot 3=147$$
çıkar. \((2,2)\) çifti aralarında asal olmadığı için elenir. \(n=3\) için ise mümkün olan en küçük en büyük terim bile
$$(3+1)^2\cdot 3^2=144>100$$
olduğundan arama biter. Sonuç olarak
$$S(100)=2925+147=3072,$$
ve bu değer uygulamanın kontrol noktasıyla aynıdır.
C++, Python ve Java implementasyonlarının üçü de yukarıdaki parametrizasyonu kullanır; yani rastgele \((a,b)\) çiftlerini test etmezler. Daha büyük olan aralarında asal parametre artarak ilerler, \((n+1)^2n^2>N\) olur olmaz durur ve her uygun değer için küçük parametre \(n\)'ye kadar denenir.
Aralarında asal olmayan çiftler hemen atlanır. Kalan her çift için implementasyon ilkel üçlüyü \((a_0,b_0,c_0)\) kurar, \(b_0>N\) olduğunda iç döngüyü keser,
$$t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor$$
hesabını yapar ve
$$(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}$$
terimini toplama ekler. Böylece kod hiçbir zaman geçersiz üçlüleri aramaz; bunun yerine geçerli ölçek ailelerini doğrudan toplar.
\(R=\lfloor N^{1/4}\rfloor\) olsun. Arama yalnızca \(1\le m\le n\le R\) bölgesine baktığı için aday çift sayısı en fazla \(R(R+1)/2=O(\sqrt{N})\) olur. Her çift için bir aralarında asallık testi ve sabit sayıda tamsayı işlemi yeterlidir. Bu nedenle aritmetik işlem sayısı açısından toplam süre \(O(\sqrt{N})\), ek bellek ise \(O(1)\)'dir.
Sea \(S(N)\) la suma de \(a+b+c\) sobre todos los tríos enteros \((a,b,c)\) con \(1\le a\le b\le N\) tales que
$$\sqrt{ab}\in \mathbb{Z},\qquad c=\frac{ab}{a+b+2\sqrt{ab}}\in \mathbb{Z}_{>0}.$$
La geometría de los círculos tangentes ya quedó condensada en esta condición aritmética. La dificultad es que \(a\) y \(b\) están acoplados a la vez por una restricción de raíz cuadrada y por una restricción de divisibilidad, así que recorrer todos los pares hasta \(N=10^9\) es demasiado lento. La idea central es demostrar que cada trío válido proviene de un único par coprimo y de un factor de escala.
La solución obtiene primero una parametrización completa y después suma familias enteras de una sola vez.
Escribimos
$$a=g u,\qquad b=g v,\qquad \gcd(u,v)=1,$$
donde \(g=\gcd(a,b)\). Como \(\sqrt{ab}\) es entero, el producto \(ab=g^2uv\) es un cuadrado perfecto, así que \(uv\) también lo es. Dado que \(u\) y \(v\) son coprimos, cada uno debe ser ya un cuadrado:
$$u=m^2,\qquad v=n^2,\qquad \gcd(m,n)=1.$$
Por lo tanto, todo par válido puede escribirse como
$$a=g m^2,\qquad b=g n^2,\qquad \sqrt{ab}=gmn.$$
Sustituyendo en la definición de \(c\) obtenemos
$$c=\frac{g^2m^2n^2}{g(m^2+n^2+2mn)}=\frac{g m^2n^2}{(m+n)^2}.$$
Además,
$$\gcd(m+n,m)=\gcd(m+n,n)=1,$$
de modo que \((m+n)\) es coprimo tanto con \(m\) como con \(n\), y por consiguiente
$$\gcd\left((m+n)^2,m^2n^2\right)=1.$$
Eso significa que todo el denominador \((m+n)^2\) debe venir del factor común \(g\). Existe entonces un entero positivo \(t\) tal que
$$g=t(m+n)^2.$$
Se llega así a la forma exacta de cualquier trío válido:
$$a=t(m+n)^2m^2,\qquad b=t(m+n)^2n^2,\qquad c=t m^2n^2.$$
La recíproca es inmediata. Si \(\gcd(m,n)=1\) y \(t\ge 1\), entonces
$$\sqrt{ab}=t(m+n)^2mn\in \mathbb{Z},$$
y también
$$a+b+2\sqrt{ab}=t(m+n)^2(m^2+n^2+2mn)=t(m+n)^4.$$
Por tanto,
$$\frac{ab}{a+b+2\sqrt{ab}}=\frac{t^2(m+n)^4m^2n^2}{t(m+n)^4}=t m^2n^2=c,$$
de modo que todo trío de esa forma es válido. El par coprimo \((m,n)\) es único salvo por el intercambio de sus dos entradas, así que imponer
$$m\le n$$
elimina el doble conteo. Para un par coprimo fijo, el trío primitivo es
$$a_0=(m+n)^2m^2,\qquad b_0=(m+n)^2n^2,\qquad c_0=m^2n^2.$$
Cuando \(m\le n\), los tres componentes cumplen
$$c_0\le a_0\le b_0.$$
Después de multiplicar por \(t\), basta exigir
$$t b_0\le N.$$
Así, los factores de escala admisibles son exactamente
$$1\le t\le t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor.$$
La contribución completa de una familia primitiva es
$$\sum_{t=1}^{t_{\max}} t(a_0+b_0+c_0)=(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
Para un \(n\) fijo, la cantidad \(b_0=(m+n)^2n^2\) crece con \(m\), así que en cuanto \(b_0>N\) la búsqueda interior puede detenerse. El menor valor posible de \(b_0\) para ese \(n\) aparece en \(m=1\):
$$b_{0,\min}=(n+1)^2n^2.$$
Si incluso este valor ya supera \(N\), entonces ningún \(n\) mayor puede funcionar. Como \(b_{0,\min}\) es del orden de \(n^4\), solo hace falta revisar
$$n=O(N^{1/4}).$$
Los pares coprimos factibles con \(m\le n\) son muy pocos.
Para \((m,n)=(1,1)\), el trío primitivo es
$$(a_0,b_0,c_0)=(4,4,1),\qquad t_{\max}=\left\lfloor\frac{100}{4}\right\rfloor=25.$$
Su contribución vale
$$(4+4+1)\frac{25\cdot 26}{2}=9\cdot 325=2925.$$
Para \((m,n)=(1,2)\), el trío primitivo es
$$(a_0,b_0,c_0)=(9,36,4),\qquad t_{\max}=\left\lfloor\frac{100}{36}\right\rfloor=2,$$
así que la contribución es
$$(9+36+4)\frac{2\cdot 3}{2}=49\cdot 3=147.$$
El par \((2,2)\) se descarta por no ser coprimo, y para \(n=3\) incluso el mayor término mínimo posible ya es
$$(3+1)^2\cdot 3^2=144>100.$$
Por lo tanto,
$$S(100)=2925+147=3072,$$
que coincide con el punto de verificación utilizado por la implementación.
Las implementaciones en C++, Python y Java usan directamente la parametrización anterior en lugar de probar pares arbitrarios \((a,b)\). Recorren en orden creciente el parámetro coprimo mayor, se detienen en cuanto \((n+1)^2n^2>N\), y para cada valor admisible exploran el parámetro menor hasta \(n\).
Los pares no coprimos se omiten al instante. Para cada par restante, la implementación construye el trío primitivo \((a_0,b_0,c_0)\), rompe el bucle interior cuando \(b_0>N\), calcula
$$t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor,$$
y suma
$$(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
Así, el código nunca busca tríos inválidos y tampoco hace un barrido global por fuerza bruta. Suma directamente familias completas de escalado.
Sea \(R=\lfloor N^{1/4}\rfloor\). Como la búsqueda solo considera \(1\le m\le n\le R\), el número de pares candidatos es a lo sumo \(R(R+1)/2=O(\sqrt{N})\). Cada par requiere una prueba de coprimalidad y una cantidad constante de operaciones enteras. En consecuencia, el tiempo total es \(O(\sqrt{N})\) en operaciones aritméticas y la memoria adicional es \(O(1)\).
设 \(S(N)\) 表示所有整数三元组 \((a,b,c)\) 的 \(a+b+c\) 之和，其中
$$1\le a\le b\le N,\qquad \sqrt{ab}\in \mathbb{Z},\qquad c=\frac{ab}{a+b+2\sqrt{ab}}\in \mathbb{Z}_{>0}.$$
题目中的切圆几何关系已经被压缩成上面的整数条件。真正的困难在于，\(a\) 和 \(b\) 同时受到“乘积必须是完全平方数”和“分母必须整除分子”这两层限制，因此直接枚举所有 \((a,b)\) 对在 \(N=10^9\) 时完全不可行。实现采用的核心思路是：证明每个合法三元组都可以唯一地拆成一个互素参数对和一个缩放因子。
整个解法分成两步：先把所有合法三元组完整参数化，再按参数族一次性求和。
先写成
$$a=g u,\qquad b=g v,\qquad \gcd(u,v)=1,$$
其中 \(g=\gcd(a,b)\)。由于 \(\sqrt{ab}\) 是整数，所以 \(ab=g^2uv\) 是完全平方数，从而 \(uv\) 也必须是完全平方数。现在 \(u\) 与 \(v\) 已经互素，而两个互素整数的乘积若是完全平方数，那么它们各自都必须是完全平方数，因此可以写成
$$u=m^2,\qquad v=n^2,\qquad \gcd(m,n)=1.$$
于是每个合法的 \((a,b)\) 都能表示为
$$a=g m^2,\qquad b=g n^2,\qquad \sqrt{ab}=gmn.$$
这一步把原问题化成了“互素平方部分”加上“公共因子”的结构。
把上式代回 \(c\) 的定义：
$$c=\frac{g^2m^2n^2}{g(m^2+n^2+2mn)}=\frac{g m^2n^2}{(m+n)^2}.$$
接下来观察互素性：
$$\gcd(m+n,m)=\gcd(m+n,n)=1.$$
这说明 \((m+n)\) 与 \(m\)、\(n\) 都互素，因此
$$\gcd\left((m+n)^2,m^2n^2\right)=1.$$
既然分子中的 \(m^2n^2\) 与分母 \((m+n)^2\) 没有公共因子，那么要使 \(c\) 成为整数，整个分母 \((m+n)^2\) 只能从公共因子 \(g\) 中提供。于是必存在正整数 \(t\) 使得
$$g=t(m+n)^2.$$
代回去之后，任意合法三元组都必须具有以下精确形式：
$$a=t(m+n)^2m^2,\qquad b=t(m+n)^2n^2,\qquad c=t m^2n^2.$$
上面的推导给出了必要性，还要检查它是否也是充分条件。若 \(\gcd(m,n)=1\) 且 \(t\ge 1\)，则
$$\sqrt{ab}=t(m+n)^2mn\in \mathbb{Z}.$$
同时
$$a+b+2\sqrt{ab}=t(m+n)^2(m^2+n^2+2mn)=t(m+n)^4.$$
所以
$$\frac{ab}{a+b+2\sqrt{ab}}=\frac{t^2(m+n)^4m^2n^2}{t(m+n)^4}=t m^2n^2=c,$$
确实得到整数 \(c\)。因此，这个形式不仅必要，而且已经穷尽了全部合法三元组。
参数对 \((m,n)\) 的唯一性只差一个交换顺序，因为交换 \(m\) 和 \(n\) 只会交换 \(a\) 与 \(b\)。为了避免重复计数，只需规定
$$m\le n.$$
在固定的互素参数对下，对应的原始三元组为
$$a_0=(m+n)^2m^2,\qquad b_0=(m+n)^2n^2,\qquad c_0=m^2n^2.$$
当 \(m\le n\) 时，三个分量满足
$$c_0\le a_0\le b_0.$$
因此，把原始三元组整体放大 \(t\) 倍以后，只需要检查最大的那个分量是否仍然不超过 \(N\)，也就是
$$t b_0\le N.$$
于是所有可行的缩放因子恰好是
$$1\le t\le t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor.$$
同一个原始三元组所生成的整个缩放族，对答案的总贡献就是
$$\sum_{t=1}^{t_{\max}} t(a_0+b_0+c_0)=(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
这一步非常重要，因为它把大量单独三元组的枚举，压缩成一个等差求和公式。
对固定的 \(n\)，有
$$b_0=(m+n)^2n^2.$$
它随着 \(m\) 的增大而单调增加，所以一旦某个 \(m\) 使 \(b_0>N\)，这一行后面的所有更大 \(m\) 都不可能再合法，内层枚举可以立刻停止。
对固定的 \(n\) 而言，最小的 \(b_0\) 出现在 \(m=1\)：
$$b_{0,\min}=(n+1)^2n^2.$$
如果连这个最小值都已经超过 \(N\)，那么更大的 \(n\) 当然也全部无效，所以外层枚举也可以终止。由于 \(b_{0,\min}\) 的量级大约是 \(n^4\)，所以只需要检查
$$n=O(N^{1/4})$$
范围内的参数即可。
在 \(m\le n\) 的条件下，可行的互素参数对非常少。
先看 \((m,n)=(1,1)\)。此时原始三元组是
$$(a_0,b_0,c_0)=(4,4,1),\qquad t_{\max}=\left\lfloor\frac{100}{4}\right\rfloor=25.$$
这一族的贡献为
$$(4+4+1)\frac{25\cdot 26}{2}=9\cdot 325=2925.$$
再看 \((m,n)=(1,2)\)。原始三元组为
$$(a_0,b_0,c_0)=(9,36,4),\qquad t_{\max}=\left\lfloor\frac{100}{36}\right\rfloor=2,$$
所以贡献是
$$(9+36+4)\frac{2\cdot 3}{2}=49\cdot 3=147.$$
\((2,2)\) 不满足互素条件，因此不能计入。再往下看 \(n=3\) 时，即便最小可能的最大分量也已经是
$$(3+1)^2\cdot 3^2=144>100,$$
这说明枚举可以直接结束。最终得到
$$S(100)=2925+147=3072,$$
正好与实现中的校验值一致。
C++、Python 和 Java 实现都不去暴力测试任意的 \((a,b)\) 组合，而是直接使用上面的参数化形式。它们从较大的互素参数开始递增枚举，一旦发现 \((n+1)^2n^2>N\)，就说明后面再也不可能出现合法原始三元组，外层循环立刻结束。
对于每个固定的较大参数，程序再扫描较小参数直到 \(n\)。不互素的参数对会被立即跳过。对每个保留下来的参数对，程序计算原始三元组 \((a_0,b_0,c_0)\)，若 \(b_0>N\) 就停止当前内层循环；否则先求出
$$t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor,$$
再把
$$(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}$$
加入总和。也就是说，代码从一开始就只生成必然合法的三元组族，而不是在巨大搜索空间中先生成再筛选。
设 \(R=\lfloor N^{1/4}\rfloor\)。搜索区域只包含 \(1\le m\le n\le R\)，因此候选参数对的数量最多为 \(R(R+1)/2=O(\sqrt{N})\)。每个参数对只需要一次互素判断和常数次整数运算，所以总的算术时间复杂度是 \(O(\sqrt{N})\)，额外空间复杂度是 \(O(1)\)。
Пусть \(S(N)\) обозначает сумму \(a+b+c\) по всем целочисленным тройкам \((a,b,c)\), для которых
$$1\le a\le b\le N,\qquad \sqrt{ab}\in \mathbb{Z},\qquad c=\frac{ab}{a+b+2\sqrt{ab}}\in \mathbb{Z}_{>0}.$$
Геометрия касающихся окружностей уже сведена здесь к чисто арифметическому условию. Трудность в том, что \(a\) и \(b\) одновременно связаны требованием о целой квадратной корне и условием делимости. Поэтому полный перебор всех пар до \(N=10^9\) слишком дорог. Ключевая идея состоит в том, чтобы доказать: каждая допустимая тройка получается из одной взаимно простой пары параметров и одного коэффициента масштабирования.
Сначала выводится полная параметризация, а затем суммируются целые семейства сразу.
Запишем
$$a=g u,\qquad b=g v,\qquad \gcd(u,v)=1,$$
где \(g=\gcd(a,b)\). Так как \(\sqrt{ab}\) является целым, произведение \(ab=g^2uv\) есть полный квадрат, следовательно, \(uv\) тоже полный квадрат. Но \(u\) и \(v\) взаимно просты, значит, каждый из них по отдельности обязан быть квадратом:
$$u=m^2,\qquad v=n^2,\qquad \gcd(m,n)=1.$$
Тем самым любая допустимая пара имеет вид
$$a=g m^2,\qquad b=g n^2,\qquad \sqrt{ab}=gmn.$$
Подставляя это в формулу для \(c\), получаем
$$c=\frac{g^2m^2n^2}{g(m^2+n^2+2mn)}=\frac{g m^2n^2}{(m+n)^2}.$$
Кроме того,
$$\gcd(m+n,m)=\gcd(m+n,n)=1,$$
поэтому \((m+n)\) взаимно просто и с \(m\), и с \(n\), а значит
$$\gcd\left((m+n)^2,m^2n^2\right)=1.$$
Следовательно, весь знаменатель \((m+n)^2\) должен быть поглощен общим множителем \(g\). Значит, существует положительное целое \(t\), для которого
$$g=t(m+n)^2.$$
Отсюда получается точная форма любой допустимой тройки:
$$a=t(m+n)^2m^2,\qquad b=t(m+n)^2n^2,\qquad c=t m^2n^2.$$
Обратное утверждение также верно. Если \(\gcd(m,n)=1\) и \(t\ge 1\), то
$$\sqrt{ab}=t(m+n)^2mn\in \mathbb{Z},$$
а также
$$a+b+2\sqrt{ab}=t(m+n)^2(m^2+n^2+2mn)=t(m+n)^4.$$
Поэтому
$$\frac{ab}{a+b+2\sqrt{ab}}=\frac{t^2(m+n)^4m^2n^2}{t(m+n)^4}=t m^2n^2=c,$$
и всякая тройка такого вида действительно допустима. Пара \((m,n)\) единственна с точностью до перестановки местами, поэтому условие
$$m\le n$$
устраняет двойной счет. Для фиксированной взаимно простой пары получаем примитивную тройку
$$a_0=(m+n)^2m^2,\qquad b_0=(m+n)^2n^2,\qquad c_0=m^2n^2.$$
При \(m\le n\) выполнено
$$c_0\le a_0\le b_0.$$
Значит, после умножения на \(t\) достаточно проверить только неравенство
$$t b_0\le N.$$
Допустимые коэффициенты масштабирования задаются точно так:
$$1\le t\le t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor.$$
Вклад всего семейства, порожденного одной примитивной тройкой, равен
$$\sum_{t=1}^{t_{\max}} t(a_0+b_0+c_0)=(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
Для фиксированного \(n\) величина \(b_0=(m+n)^2n^2\) возрастает вместе с \(m\). Поэтому, как только \(b_0>N\), внутренний перебор можно немедленно остановить. Минимально возможное значение \(b_0\) при данном \(n\) получается при \(m=1\):
$$b_{0,\min}=(n+1)^2n^2.$$
Если уже оно больше \(N\), то ни одно большее \(n\) тоже не подойдет. Поскольку \(b_{0,\min}\) имеет порядок \(n^4\), достаточно рассматривать только
$$n=O(N^{1/4}).$$
Подходящих взаимно простых пар с условием \(m\le n\) здесь очень мало.
Для \((m,n)=(1,1)\) примитивная тройка равна
$$(a_0,b_0,c_0)=(4,4,1),\qquad t_{\max}=\left\lfloor\frac{100}{4}\right\rfloor=25.$$
Ее вклад составляет
$$(4+4+1)\frac{25\cdot 26}{2}=9\cdot 325=2925.$$
Для \((m,n)=(1,2)\) получаем
$$(a_0,b_0,c_0)=(9,36,4),\qquad t_{\max}=\left\lfloor\frac{100}{36}\right\rfloor=2,$$
поэтому вклад равен
$$(9+36+4)\frac{2\cdot 3}{2}=49\cdot 3=147.$$
Пара \((2,2)\) исключается, потому что она не взаимно проста. Уже при \(n=3\) даже минимально возможный максимальный член равен
$$(3+1)^2\cdot 3^2=144>100,$$
поэтому перебор заканчивается. В итоге
$$S(100)=2925+147=3072,$$
что совпадает с контрольным значением реализации.
Реализации на C++, Python и Java используют именно эту параметризацию, а не проверяют произвольные пары \((a,b)\). Они увеличивают больший взаимно простой параметр, останавливаются, как только \((n+1)^2n^2>N\), и для каждого допустимого значения перебирают меньший параметр до \(n\).
Невзаимно простые пары сразу пропускаются. Для каждой оставшейся пары реализация строит примитивную тройку \((a_0,b_0,c_0)\), завершает внутренний цикл при \(b_0>N\), вычисляет
$$t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor,$$
а затем прибавляет
$$(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
Таким образом, код не ищет недопустимые тройки и не делает дорогостоящего полного перебора. Он сразу суммирует целые семейства масштабирования.
Пусть \(R=\lfloor N^{1/4}\rfloor\). Поиск ограничивается областью \(1\le m\le n\le R\), значит число кандидатных пар не превосходит \(R(R+1)/2=O(\sqrt{N})\). Для каждой пары требуется одна проверка взаимной простоты и константное число целочисленных операций. Итак, общая трудоемкость равна \(O(\sqrt{N})\) арифметических операций, а дополнительная память равна \(O(1)\).
لتكن \(S(N)\) هي مجموع \(a+b+c\) على جميع الثلاثيات الصحيحة \((a,b,c)\) التي تحقق
$$1\le a\le b\le N,\qquad \sqrt{ab}\in \mathbb{Z},\qquad c=\frac{ab}{a+b+2\sqrt{ab}}\in \mathbb{Z}_{>0}.$$
هندسة الدوائر المتماسة اختُزلت هنا إلى شرط عددي خالص. الصعوبة أن \(a\) و\(b\) مرتبطان معًا بشرط أن يكون الجذر التربيعي صحيحًا وبشرط قسمة آخر في الوقت نفسه، ولذلك فإن تعداد جميع الأزواج حتى \(N=10^9\) غير عملي تمامًا. الفكرة الأساسية هي إثبات أن كل ثلاثية صالحة تنتج من زوج بارامترات متباين أوليًا ومن عامل تحجيم واحد.
نستخرج أولًا بارامتريزاشن كاملًا، ثم نجمع كل عائلة تحجيم دفعة واحدة.
نكتب
$$a=g u,\qquad b=g v,\qquad \gcd(u,v)=1,$$
حيث \(g=\gcd(a,b)\). بما أن \(\sqrt{ab}\) عدد صحيح، فإن \(ab=g^2uv\) مربع كامل، وبالتالي \(uv\) مربع كامل أيضًا. ولأن \(u\) و\(v\) متباينان أوليًا، فلا بد أن يكون كل واحد منهما مربعًا كاملًا على حدة:
$$u=m^2,\qquad v=n^2,\qquad \gcd(m,n)=1.$$
إذن يمكن كتابة كل زوج صالح بالشكل
$$a=g m^2,\qquad b=g n^2,\qquad \sqrt{ab}=gmn.$$
بالتعويض في تعريف \(c\) نحصل على
$$c=\frac{g^2m^2n^2}{g(m^2+n^2+2mn)}=\frac{g m^2n^2}{(m+n)^2}.$$
ولدينا أيضًا
$$\gcd(m+n,m)=\gcd(m+n,n)=1,$$
أي إن \((m+n)\) متباين أوليًا مع \(m\) ومع \(n\)، ومن ثم
$$\gcd\left((m+n)^2,m^2n^2\right)=1.$$
وهذا يعني أن المقام كله، أي \((m+n)^2\)، لا بد أن يأتي من العامل المشترك \(g\). لذلك يوجد عدد صحيح موجب \(t\) بحيث
$$g=t(m+n)^2.$$
وعندئذ تصبح الصيغة الدقيقة لأي ثلاثية صالحة هي
$$a=t(m+n)^2m^2,\qquad b=t(m+n)^2n^2,\qquad c=t m^2n^2.$$
العكس صحيح مباشرة. إذا كان \(\gcd(m,n)=1\) و\(t\ge 1\)، فحينها
$$\sqrt{ab}=t(m+n)^2mn\in \mathbb{Z},$$
وكذلك
$$a+b+2\sqrt{ab}=t(m+n)^2(m^2+n^2+2mn)=t(m+n)^4.$$
إذن
$$\frac{ab}{a+b+2\sqrt{ab}}=\frac{t^2(m+n)^4m^2n^2}{t(m+n)^4}=t m^2n^2=c,$$
فتكون كل ثلاثية من هذا الشكل صالحة فعلًا. الزوج \((m,n)\) وحيد حتى تبديل الترتيب فقط، لأن تبديل \(m\) و\(n\) يبدل \(a\) و\(b\) لا أكثر. لذلك يكفي فرض الشرط
$$m\le n$$
لمنع العد المكرر. وعند تثبيت زوج متباين أوليًا نحصل على الثلاثية الأولية
$$a_0=(m+n)^2m^2,\qquad b_0=(m+n)^2n^2,\qquad c_0=m^2n^2.$$
عندما يكون \(m\le n\)، تتحقق العلاقة
$$c_0\le a_0\le b_0.$$
وبالتالي بعد الضرب في \(t\) يكفي أن نتحقق من
$$t b_0\le N.$$
إذن جميع قيم التحجيم المسموح بها هي
$$1\le t\le t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor.$$
ومساهمة العائلة الكاملة الناتجة من ثلاثية أولية واحدة تساوي
$$\sum_{t=1}^{t_{\max}} t(a_0+b_0+c_0)=(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
عند تثبيت \(n\)، فإن
$$b_0=(m+n)^2n^2$$
تزداد بزيادة \(m\). لذلك بمجرد أن يصبح \(b_0>N\) يمكن إيقاف الحلقة الداخلية فورًا. وأصغر قيمة ممكنة لـ \(b_0\) عند هذا \(n\) تظهر عندما \(m=1\):
$$b_{0,\min}=(n+1)^2n^2.$$
إذا كانت هذه القيمة نفسها أكبر من \(N\)، فلن ينجح أي \(n\) أكبر منها. وبما أن رتبة \(b_{0,\min}\) تقارب \(n^4\)، فلا حاجة إلى فحص سوى
$$n=O(N^{1/4}).$$
عدد الأزواج المتباينة أوليًا الممكنة مع \(m\le n\) صغير جدًا هنا.
بالنسبة إلى \((m,n)=(1,1)\)، تكون الثلاثية الأولية
$$(a_0,b_0,c_0)=(4,4,1),\qquad t_{\max}=\left\lfloor\frac{100}{4}\right\rfloor=25.$$
ومساهمتها
$$(4+4+1)\frac{25\cdot 26}{2}=9\cdot 325=2925.$$
وبالنسبة إلى \((m,n)=(1,2)\)، نحصل على
$$(a_0,b_0,c_0)=(9,36,4),\qquad t_{\max}=\left\lfloor\frac{100}{36}\right\rfloor=2,$$
ومن ثم تكون المساهمة
$$(9+36+4)\frac{2\cdot 3}{2}=49\cdot 3=147.$$
أما الزوج \((2,2)\) فيُستبعد لأنه ليس متباينًا أوليًا، وعند \(n=3\) نجد أن أصغر قيمة ممكنة لأكبر حد تساوي
$$(3+1)^2\cdot 3^2=144>100,$$
فتنتهي عملية التعداد. إذن
$$S(100)=2925+147=3072,$$
وهو نفس مقدار التحقق الذي تستخدمه التطبيقات.
تستخدم تطبيقات C++ وPython وJava هذا البارامتريزاشن مباشرة بدل اختبار أزواج عشوائية \((a,b)\). فهي تزيد البارامتر المتباين أوليًا الأكبر تدريجيًا، وتتوقف فور تحقق \((n+1)^2n^2>N\)، ثم تفحص البارامتر الأصغر حتى \(n\) لكل قيمة مسموحة.
الأزواج غير المتباينة أوليًا تُتجاوز فورًا. ولكل زوج باق، تبني التطبيقات الثلاثية الأولية \((a_0,b_0,c_0)\)، وتقطع الحلقة الداخلية عندما يصبح \(b_0>N\)، ثم تحسب
$$t_{\max}=\left\lfloor\frac{N}{b_0}\right\rfloor,$$
وتضيف
$$(a_0+b_0+c_0)\frac{t_{\max}(t_{\max}+1)}{2}.$$
وبهذه الطريقة لا يبحث الكود أبدًا في ثلاثيات غير صالحة، ولا يجري مسحًا خامًا واسعًا؛ بل يجمع عائلات التحجيم الصحيحة مباشرة.
لنضع \(R=\lfloor N^{1/4}\rfloor\). بما أن البحث يقتصر على المنطقة \(1\le m\le n\le R\)، فإن عدد الأزواج المرشحة لا يتجاوز \(R(R+1)/2=O(\sqrt{N})\). وكل زوج يحتاج إلى اختبار تباين أولي واحد وإلى عدد ثابت من العمليات الصحيحة. لذلك يكون الزمن الكلي \(O(\sqrt{N})\) من حيث العمليات الحسابية، بينما الذاكرة الإضافية \(O(1)\).