A Cardano triplet is a triple of positive integers \((a,b,c)\) satisfying
$$\sqrt[3]{a+b\sqrt{c}}+\sqrt[3]{a-b\sqrt{c}}=1.$$
The task is to count all such triplets with \(a+b+c\le L\). The implementation does not search directly in \((a,b,c)\)-space; it first converts the radical identity into a Diophantine equation and then enumerates the resulting factorization patterns.
Let
$$x=\sqrt[3]{a+b\sqrt{c}},\qquad y=\sqrt[3]{a-b\sqrt{c}}.$$
Then \(x+y=1\). The whole solution comes from extracting arithmetic consequences of this identity.
Using
$$x^3+y^3=(x+y)^3-3xy(x+y),$$
we get
$$2a=x^3+y^3=1-3xy,$$
so
$$xy=\frac{1-2a}{3}.$$
Multiplying the two cube-root arguments also gives
$$x^3y^3=(a+b\sqrt{c})(a-b\sqrt{c})=a^2-b^2c,$$
hence
$$a^2-b^2c=\left(\frac{1-2a}{3}\right)^3.$$
After rearranging,
$$27b^2c=27a^2+(2a-1)^3=(a+1)^2(8a-1).$$
This factorization is the key algebraic simplification behind the code.
The left-hand side is divisible by \(27\), so \((a+1)^2(8a-1)\) must also be divisible by \(27\). Modulo \(3\), this forces
$$a\equiv 2\pmod 3.$$
Therefore we write
$$a=3u-1,\qquad u\ge 1.$$
Then \(a+1=3u\) and \(8a-1=3(8u-3)\), so the previous equation becomes
$$b^2c=u^2(8u-3).$$
Thus every Cardano triplet corresponds to a positive integer \(u\) together with a decomposition of \(u^2(8u-3)\) into a square part and a residual part.
Set
$$m=8u-3.$$
We need positive integers \(b,c\) such that
$$b^2c=u^2m.$$
Let
$$g=\gcd(b,u),\qquad u=gh,\qquad b=gb_1,$$
so that \(\gcd(h,b_1)=1\). Substituting into \(b^2c=u^2m\) gives
$$g^2b_1^2c=g^2h^2m\qquad\Longrightarrow\qquad b_1^2c=h^2m.$$
Because \(\gcd(h,b_1)=1\), every prime dividing \(b_1\) must come from \(m\), so \(b_1^2\mid m\). Write
$$m=b_1^2r.$$
Then automatically
$$c=h^2r,\qquad b=\frac{u}{h}b_1.$$
Hence every solution enumerated by the code has the form
$$a=3u-1,\qquad m=8u-3=b_1^2r,\qquad h\mid u,\qquad \gcd(h,b_1)=1,$$
$$b=\frac{u}{h}b_1,\qquad c=h^2r.$$
Conversely, any such choice satisfies \(b^2c=u^2m\), so this parameterization is complete.
For fixed \(u\), the value of \(a=3u-1\) is already known. Define the remaining budget
$$R=L-a.$$
Any candidate must satisfy
$$b+c=\frac{u}{h}b_1+h^2r\le R.$$
The code derives two strong bounds for \(h\). Since \(u/h\ge 1\), we have \(b\ge b_1\), hence
$$c=h^2r\le R-b_1,$$
which yields
$$h\le\left\lfloor\sqrt{\frac{R-b_1}{r}}\right\rfloor.$$
Also \(h\ge 1\) implies \(c=h^2r\ge r\), so \(b\le R-r\). Therefore
$$\frac{u}{h}b_1\le R-r\qquad\Longrightarrow\qquad h\ge\left\lceil\frac{ub_1}{R-r}\right\rceil$$
whenever \(R-r\gt 0\). The implementation checks only divisors \(h\mid u\) inside this interval.
Before the main enumeration starts, the code computes a safe maximal \(u\) by lower-bounding \(b+c\). Let
$$x=\frac{u}{h}b_1,\qquad y=h^2r.$$
Then \(x+y=b+c\) and
$$x^2y=u^2b_1^2r=u^2(8u-3).$$
For fixed \(x^2y=K\), the minimum of \(x+y\) is \(3\sqrt[3]{K/4}\), by calculus or the weighted AM-GM inequality. Therefore every valid triplet must satisfy
$$a+b+c\ge 3u-1+3\sqrt[3]{\frac{u^2(8u-3)}{4}}.$$
If this lower bound already exceeds \(L\), then that \(u\) cannot contribute. Since the bound grows with \(u\), binary search yields the cutoff used by max_u_bound.
Take \(u=1\). Then
$$a=3\cdot 1-1=2,\qquad m=8\cdot 1-3=5.$$
The only square divisor of \(m=5\) is \(b_1=1\), and the only divisor of \(u=1\) is \(h=1\). Thus
$$b=\frac{1}{1}\cdot 1=1,\qquad c=1^2\cdot 5=5.$$
This reproduces the example \((2,1,5)\), and the parameterization counts it exactly once.
The implementation first computes max_u_bound(limit), then builds an SPF table for fast factorization of every \(u\), and a prime table up to \(\sqrt{8u_{\max}-3}\) for factoring \(m=8u-3\). For each \(u\), it enumerates all divisors \(h\mid u\), all square-divisor choices \(b_1\) of \(m\), applies the interval bounds for \(h\), checks \(\gcd(h,b_1)=1\), and finally verifies \(b+c\le R\). The outer loop over \(u\) is split across threads because different \(u\)-values are independent.
Precomputation costs \(O(u_{\max})\) time and memory for the SPF table, plus a smaller prime sieve up to \(\sqrt{8u_{\max}-3}\). The counting phase is dominated by divisor generation: for each \(u\), the algorithm enumerates divisors of \(u\) and square divisors of \(8u-3\). A simple closed form is awkward because divisor counts fluctuate, but the effective runtime is far below naive search thanks to the global \(u\)-bound, the \(h\)-interval pruning, and the coprimality filter.
Ein Cardano-Tripel ist ein Tripel positiver ganzer Zahlen \((a,b,c)\) mit
$$\sqrt[3]{a+b\sqrt{c}}+\sqrt[3]{a-b\sqrt{c}}=1.$$
Gesucht ist die Anzahl aller solcher Tripel mit \(a+b+c\le L\). Der Code durchsucht nicht direkt den Raum aller \((a,b,c)\), sondern formt die Wurzelgleichung zuerst in eine diophantische Gleichung um und zählt dann nur die zulässigen Faktorisierungen.
Setze
$$x=\sqrt[3]{a+b\sqrt{c}},\qquad y=\sqrt[3]{a-b\sqrt{c}}.$$
Dann gilt \(x+y=1\). Der gesamte Ansatz besteht darin, aus dieser Identität arithmetische Bedingungen abzuleiten.
Mit
$$x^3+y^3=(x+y)^3-3xy(x+y)$$
folgt
$$2a=x^3+y^3=1-3xy,$$
also
$$xy=\frac{1-2a}{3}.$$
Außerdem ist
$$x^3y^3=(a+b\sqrt{c})(a-b\sqrt{c})=a^2-b^2c,$$
somit
$$a^2-b^2c=\left(\frac{1-2a}{3}\right)^3.$$
Nach Umformen erhält man
$$27b^2c=27a^2+(2a-1)^3=(a+1)^2(8a-1).$$
Genau diese Faktorisierung macht die spätere Enumeration möglich.
Die linke Seite ist durch \(27\) teilbar, also muss auch \((a+1)^2(8a-1)\) durch \(27\) teilbar sein. Modulo \(3\) erzwingt das
$$a\equiv 2\pmod 3.$$
Daher schreiben wir
$$a=3u-1,\qquad u\ge 1.$$
Dann sind \(a+1=3u\) und \(8a-1=3(8u-3)\), also wird die Gleichung zu
$$b^2c=u^2(8u-3).$$
Jedes Cardano-Tripel entspricht damit einem positiven \(u\) und einer Zerlegung von \(u^2(8u-3)\) in einen Quadratteil und einen Rest.
Setze
$$m=8u-3.$$
Gesucht sind positive \(b,c\) mit
$$b^2c=u^2m.$$
Sei
$$g=\gcd(b,u),\qquad u=gh,\qquad b=gb_1,$$
sodass \(\gcd(h,b_1)=1\). Einsetzen liefert
$$g^2b_1^2c=g^2h^2m\qquad\Longrightarrow\qquad b_1^2c=h^2m.$$
Wegen \(\gcd(h,b_1)=1\) muss jeder Primfaktor von \(b_1\) aus \(m\) stammen, also \(b_1^2\mid m\). Schreibe daher
$$m=b_1^2r.$$
Dann folgt automatisch
$$c=h^2r,\qquad b=\frac{u}{h}b_1.$$
Somit hat jede vom Code gezählte Lösung die Form
$$a=3u-1,\qquad m=8u-3=b_1^2r,\qquad h\mid u,\qquad \gcd(h,b_1)=1,$$
$$b=\frac{u}{h}b_1,\qquad c=h^2r.$$
Umgekehrt erfüllt jede solche Wahl wieder \(b^2c=u^2m\); die Parametrisierung ist also vollständig.
Für festes \(u\) ist \(a=3u-1\) bereits bestimmt. Definiere das Restbudget
$$R=L-a.$$
Dann muss gelten
$$b+c=\frac{u}{h}b_1+h^2r\le R.$$
Der Code gewinnt daraus zwei starke Schranken für \(h\). Weil \(u/h\ge 1\), gilt \(b\ge b_1\), also
$$c=h^2r\le R-b_1,$$
und damit
$$h\le\left\lfloor\sqrt{\frac{R-b_1}{r}}\right\rfloor.$$
Außerdem folgt aus \(h\ge 1\), dass \(c=h^2r\ge r\), also \(b\le R-r\). Daher
$$\frac{u}{h}b_1\le R-r\qquad\Longrightarrow\qquad h\ge\left\lceil\frac{ub_1}{R-r}\right\rceil$$
falls \(R-r\gt 0\). Es werden also nur Teiler \(h\mid u\) in diesem Intervall getestet.
Bevor gezählt wird, berechnet der Code eine sichere Obergrenze für \(u\), indem \(b+c\) von unten abgeschätzt wird. Setze
$$x=\frac{u}{h}b_1,\qquad y=h^2r.$$
Dann ist \(x+y=b+c\) und
$$x^2y=u^2b_1^2r=u^2(8u-3).$$
Für festes \(x^2y=K\) ist das Minimum von \(x+y\) gleich \(3\sqrt[3]{K/4}\), per Analysis oder gewichteter AM-GM-Ungleichung. Also muss jedes gültige Tripel erfüllen
$$a+b+c\ge 3u-1+3\sqrt[3]{\frac{u^2(8u-3)}{4}}.$$
Liegt diese Untergrenze bereits über \(L\), dann kann dieses \(u\) keine Lösung mehr liefern. Weil die Schranke mit \(u\) wächst, findet eine Binärsuche den in max_u_bound verwendeten Grenzwert.
Für \(u=1\) erhält man
$$a=3\cdot 1-1=2,\qquad m=8\cdot 1-3=5.$$
Der einzige quadratische Teiler von \(m=5\) ist \(b_1=1\), und der einzige Teiler von \(u=1\) ist \(h=1\). Also
$$b=\frac{1}{1}\cdot 1=1,\qquad c=1^2\cdot 5=5.$$
Damit entsteht genau das Beispiel \((2,1,5)\), und zwar genau einmal.
Die Implementierung berechnet zuerst max_u_bound(limit), baut dann eine SPF-Tabelle für die schnelle Faktorisierung jedes \(u\) sowie eine Primtabelle bis \(\sqrt{8u_{\max}-3}\) für \(m=8u-3\) auf. Für jedes \(u\) werden alle Teiler \(h\mid u\) und alle quadratischen Teiler \(b_1\) von \(m\) erzeugt, die Schranken für \(h\) angewandt, \(\gcd(h,b_1)=1\) geprüft und am Ende \(b+c\le R\) validiert. Die äußere Schleife über \(u\) ist problemlos parallelisierbar.
Die Vorverarbeitung kostet \(O(u_{\max})\) Zeit und Speicher für die SPF-Tabelle sowie etwas Zusatzaufwand für ein kleineres Primzahlsieb bis \(\sqrt{8u_{\max}-3}\). Die eigentliche Laufzeit wird von der Teilererzeugung bestimmt: für jedes \(u\) werden die Teiler von \(u\) und die quadratischen Teiler von \(8u-3\) betrachtet. Eine einfache geschlossene Formel für die Gesamtkosten gibt es wegen der schwankenden Teileranzahlen nicht, aber globale \(u\)-Schranke, \(h\)-Intervall und Koprimalitätsfilter schneiden den Suchraum stark zusammen.
Bir Cardano üçlüsü,
$$\sqrt[3]{a+b\sqrt{c}}+\sqrt[3]{a-b\sqrt{c}}=1$$
koşulunu sağlayan pozitif tamsayı üçlüsü \((a,b,c)\)'dir. Amaç,
$$a+b+c\le L$$
şartını sağlayan tüm böyle üçlüleri saymaktır. Kod bunu \((a,b,c)\) uzayında kör tarama yaparak değil, köklü ifadeyi bir Diofant denkleme dönüştürerek yapar.
Önce
$$x=\sqrt[3]{a+b\sqrt{c}},\qquad y=\sqrt[3]{a-b\sqrt{c}}$$
tanımlayalım. Verilen eşitlik doğrudan
$$x+y=1$$
anlamına gelir. Bütün çözüm, bu basit eşitliğin aritmetik sonuçlarını çıkarmaya dayanır.
Bilinen özdeşlik
$$x^3+y^3=(x+y)^3-3xy(x+y)$$
uygulanırsa
$$2a=x^3+y^3=1-3xy$$
elde edilir. Buradan
$$xy=\frac{1-2a}{3}$$
çıkar.
Öte yandan köklerin içlerini çarparsak
$$x^3y^3=(a+b\sqrt{c})(a-b\sqrt{c})=a^2-b^2c,$$
dolayısıyla
$$a^2-b^2c=\left(\frac{1-2a}{3}\right)^3.$$
Düzenlersek
$$27b^2c=27a^2+(2a-1)^3=(a+1)^2(8a-1)$$
sonucuna ulaşırız. Kodun kullandığı bütün parametrizasyon bu çarpanlaşmadan gelir.
Sol taraf \(27\)'ye bölündüğü için sağ tarafın da \(27\)'ye bölünmesi gerekir. Mod \(3\) altında bu ancak
$$a\equiv 2\pmod 3$$
olduğunda mümkündür. Bu yüzden
$$a=3u-1,\qquad u\ge 1$$
yazarız. O zaman \(a+1=3u\) ve \(8a-1=3(8u-3)\) olur; böylece ana denklem
$$b^2c=u^2(8u-3)$$
biçimine iner. Yani sorun artık, \(u^2(8u-3)\) sayısını bir kare ile bir kalan çarpanı olarak üretme problemidir.
Şimdi
$$m=8u-3$$
tanımlayalım. Aradığımız \(b\) ve \(c\) sayıları
$$b^2c=u^2m$$
eşitliğini sağlamalıdır. Bunun için
$$g=\gcd(b,u),\qquad u=gh,\qquad b=gb_1$$
yazalım; böylece \(\gcd(h,b_1)=1\) olur. Bu ifadeleri yerine koyarsak
$$g^2b_1^2c=g^2h^2m\qquad\Longrightarrow\qquad b_1^2c=h^2m$$
elde edilir.
\(\gcd(h,b_1)=1\) olduğundan, \(b_1\)'in asal çarpanları yalnızca \(m\)'den gelebilir; dolayısıyla \(b_1^2\mid m\). O halde
$$m=b_1^2r$$
şeklinde yazabiliriz. Bu durumda otomatik olarak
$$c=h^2r,\qquad b=\frac{u}{h}b_1$$
olur.
Sonuç olarak kodun taradığı bütün çözümler şu biçimdedir:
$$a=3u-1,\qquad m=8u-3=b_1^2r,\qquad h\mid u,\qquad \gcd(h,b_1)=1,$$
$$b=\frac{u}{h}b_1,\qquad c=h^2r.$$
Tersine, bu şartları sağlayan her seçim de yeniden \(b^2c=u^2m\) verdiği için parametrizasyon eksiksizdir.
Sabit bir \(u\) için \(a=3u-1\) zaten belirlenmiştir. Geriye kalan toplam bütçeyi
$$R=L-a$$
diye tanımlayalım. O zaman mutlaka
$$b+c=\frac{u}{h}b_1+h^2r\le R$$
olmalıdır.
Kod, buradan \(h\) için iki kuvvetli sınır türetir. Önce \(u/h\ge 1\) olduğu için \(b\ge b_1\). Dolayısıyla
$$c=h^2r\le R-b_1,$$
ve buradan
$$h\le\left\lfloor\sqrt{\frac{R-b_1}{r}}\right\rfloor$$
elde edilir.
Ayrıca \(h\ge 1\) olduğundan \(c=h^2r\ge r\), yani \(b\le R-r\). Bu da
$$\frac{u}{h}b_1\le R-r\qquad\Longrightarrow\qquad h\ge\left\lceil\frac{ub_1}{R-r}\right\rceil$$
sonucunu verir; tabii \(R-r\gt 0\) ise. Böylece kod, \(u\)'nun bütün bölenlerini denemek yerine yalnız bu aralıkta kalan \(h\mid u\) adaylarını test eder.
Asıl sayım başlamadan önce kod, \(u\) için güvenli bir üst sınır bulur. Bunun için \(b+c\) toplamı aşağıdan sınırlandırılır. Şöyle tanımlayalım:
$$x=\frac{u}{h}b_1,\qquad y=h^2r.$$
O zaman \(x+y=b+c\) ve
$$x^2y=u^2b_1^2r=u^2(8u-3)$$
olur.
Sabit \(x^2y=K\) altında \(x+y\) toplamının minimumu \(3\sqrt[3]{K/4}\)'tür; bu sonuç türev hesabıyla ya da ağırlıklı AM-GM eşitsizliğiyle elde edilir. Demek ki her geçerli üçlü için
$$a+b+c\ge 3u-1+3\sqrt[3]{\frac{u^2(8u-3)}{4}}$$
olmak zorundadır. Bu alt sınır bile \(L\)'yi aşıyorsa, o \(u\) için artık hiç çözüm yoktur. Sınır \(u\) ile büyüdüğünden, kod ikili arama ile max_u_bound değerini bulur.
\(u=1\) alalım. O zaman
$$a=3\cdot 1-1=2,\qquad m=8\cdot 1-3=5.$$
\(m=5\)'in tek kare böleni \(b_1=1\), \(u=1\)'in tek böleni de \(h=1\)'dir. Böylece
$$b=\frac{1}{1}\cdot 1=1,\qquad c=1^2\cdot 5=5$$
elde edilir. Yani bilinen örnek \((2,1,5)\) bu parametrizasyonla tam bir kez üretilir.
Uygulama önce max_u_bound(limit) ile taranacak en büyük \(u\)'yu hesaplar. Sonra her \(u\)'yu hızlı çarpanlara ayırmak için SPF tablosu, \(m=8u-3\) sayısını ayırmak için de \(\sqrt{8u_{\max}-3}\)'e kadar bir asal listesi üretir. Her \(u\) için \(u\)'nun tüm bölenleri \(h\), \(m\)'nin kare böleni seçenekleri \(b_1\) oluşturulur; ardından \(h\) aralığı uygulanır, \(\gcd(h,b_1)=1\) şartı kontrol edilir ve son adımda \(b+c\le R\) doğrulanır. Farklı \(u\) değerleri bağımsız olduğu için dış döngü iş parçacıklarına dağıtılır.
Ön işlem maliyeti, SPF tablosu için \(O(u_{\max})\) zaman ve bellek düzeyindedir; buna ek olarak \(\sqrt{8u_{\max}-3}\)'e kadar daha küçük bir asal eleği kurulur. Asıl çalışma süresi bölen üretiminden gelir: her \(u\) için hem \(u\)'nun bölenleri hem de \(8u-3\)'ün kare bölenleri dolaşılır. Bölen sayıları düzensiz değiştiği için tek satırlık kesin bir kapalı form vermek zordur; fakat global \(u\) sınırı, \(h\) aralığı ve aralarında asal olma filtresi, naif aramaya göre arama uzayını çok ciddi biçimde küçültür.
Una terna de Cardano es un triple de enteros positivos \((a,b,c)\) que satisface
$$\sqrt[3]{a+b\sqrt{c}}+\sqrt[3]{a-b\sqrt{c}}=1.$$
La tarea consiste en contar todas esas ternas con \(a+b+c\le L\). La implementación no busca directamente en el espacio \((a,b,c)\); primero transforma la identidad radical en una ecuación diofántica y luego enumera las factorizaciones compatibles.
Sea
$$x=\sqrt[3]{a+b\sqrt{c}},\qquad y=\sqrt[3]{a-b\sqrt{c}}.$$
Entonces \(x+y=1\). Toda la solución nace de extraer consecuencias aritméticas de esta identidad.
Usando
$$x^3+y^3=(x+y)^3-3xy(x+y),$$
obtenemos
$$2a=x^3+y^3=1-3xy,$$
de donde
$$xy=\frac{1-2a}{3}.$$
Además, al multiplicar los dos argumentos de las raíces cúbicas se tiene
$$x^3y^3=(a+b\sqrt{c})(a-b\sqrt{c})=a^2-b^2c,$$
y por tanto
$$a^2-b^2c=\left(\frac{1-2a}{3}\right)^3.$$
Reordenando, se llega a
$$27b^2c=27a^2+(2a-1)^3=(a+1)^2(8a-1).$$
Esta factorización es la simplificación algebraica central de la solución.
El lado izquierdo es divisible por \(27\), así que \((a+1)^2(8a-1)\) también debe ser divisible por \(27\). Módulo \(3\), esto fuerza
$$a\equiv 2\pmod 3.$$
Por ello escribimos
$$a=3u-1,\qquad u\ge 1.$$
Entonces \(a+1=3u\) y \(8a-1=3(8u-3)\), de modo que la ecuación anterior se reduce a
$$b^2c=u^2(8u-3).$$
Así, cada terna de Cardano corresponde a un entero positivo \(u\) junto con una descomposición de \(u^2(8u-3)\) en parte cuadrada y parte residual.
Definimos
$$m=8u-3.$$
Buscamos enteros positivos \(b,c\) tales que
$$b^2c=u^2m.$$
Sea
$$g=\gcd(b,u),\qquad u=gh,\qquad b=gb_1,$$
de modo que \(\gcd(h,b_1)=1\). Sustituyendo en \(b^2c=u^2m\), obtenemos
$$g^2b_1^2c=g^2h^2m\qquad\Longrightarrow\qquad b_1^2c=h^2m.$$
Como \(\gcd(h,b_1)=1\), todos los primos que dividen \(b_1\) deben venir de \(m\), así que \(b_1^2\mid m\). Escribimos entonces
$$m=b_1^2r.$$
Con ello se obtiene automáticamente
$$c=h^2r,\qquad b=\frac{u}{h}b_1.$$
Por tanto, toda solución enumerada por la implementación tiene la forma
$$a=3u-1,\qquad m=8u-3=b_1^2r,\qquad h\mid u,\qquad \gcd(h,b_1)=1,$$
$$b=\frac{u}{h}b_1,\qquad c=h^2r.$$
Recíprocamente, cualquier elección así satisface \(b^2c=u^2m\), de modo que la parametrización es completa.
Para un \(u\) fijo, el valor \(a=3u-1\) ya está determinado. Definimos el presupuesto restante
$$R=L-a.$$
Cualquier candidata debe cumplir
$$b+c=\frac{u}{h}b_1+h^2r\le R.$$
El código deduce dos cotas fuertes para \(h\). Como \(u/h\ge 1\), se tiene \(b\ge b_1\), y por tanto
$$c=h^2r\le R-b_1,$$
de donde
$$h\le\left\lfloor\sqrt{\frac{R-b_1}{r}}\right\rfloor.$$
Además, \(h\ge 1\) implica \(c=h^2r\ge r\), luego \(b\le R-r\). Entonces
$$\frac{u}{h}b_1\le R-r\qquad\Longrightarrow\qquad h\ge\left\lceil\frac{ub_1}{R-r}\right\rceil$$
siempre que \(R-r\gt 0\). La implementación solo prueba divisores \(h\mid u\) dentro de este intervalo.
Antes de empezar la enumeración principal, el código calcula un máximo seguro para \(u\) acotando \(b+c\) por abajo. Sea
$$x=\frac{u}{h}b_1,\qquad y=h^2r.$$
Entonces \(x+y=b+c\) y
$$x^2y=u^2b_1^2r=u^2(8u-3).$$
Para \(x^2y=K\) fijo, el mínimo de \(x+y\) es \(3\sqrt[3]{K/4}\), por cálculo o por la desigualdad AM-GM ponderada. Por lo tanto, toda terna válida debe satisfacer
$$a+b+c\ge 3u-1+3\sqrt[3]{\frac{u^2(8u-3)}{4}}.$$
Si esta cota inferior ya supera \(L\), ese valor de \(u\) no puede aportar soluciones. Como la cota crece con \(u\), una búsqueda binaria produce el corte utilizado en max_u_bound.
Tomemos \(u=1\). Entonces
$$a=3\cdot 1-1=2,\qquad m=8\cdot 1-3=5.$$
El único divisor cuadrado de \(m=5\) es \(b_1=1\), y el único divisor de \(u=1\) es \(h=1\). Así,
$$b=\frac{1}{1}\cdot 1=1,\qquad c=1^2\cdot 5=5.$$
Esto reproduce el ejemplo \((2,1,5)\), y la parametrización lo cuenta exactamente una vez.
La implementación calcula primero max_u_bound(limit), luego construye una tabla SPF para factorizar rápidamente cada \(u\) y una lista de primos hasta \(\sqrt{8u_{\max}-3}\) para factorizar \(m=8u-3\). Para cada \(u\), enumera todos los divisores \(h\mid u\), todas las elecciones de \(b_1\) como divisor cuadrado de \(m\), aplica las cotas del intervalo para \(h\), verifica \(\gcd(h,b_1)=1\) y finalmente comprueba \(b+c\le R\). El bucle exterior sobre \(u\) se reparte entre hilos porque los distintos valores de \(u\) son independientes.
La precomputación cuesta \(O(u_{\max})\) tiempo y memoria para la tabla SPF, más una criba de primos más pequeña hasta \(\sqrt{8u_{\max}-3}\). La fase de conteo está dominada por la enumeración de divisores: para cada \(u\), el algoritmo recorre los divisores de \(u\) y los divisores cuadrados de \(8u-3\). No hay una forma cerrada simple porque el número de divisores fluctúa, pero el tiempo efectivo queda muy por debajo de una búsqueda ingenua gracias a la cota global sobre \(u\), al recorte del intervalo de \(h\) y al filtro de coprimalidad.
Cardano 三元组是满足
$$\sqrt[3]{a+b\sqrt{c}}+\sqrt[3]{a-b\sqrt{c}}=1$$
的正整数三元组 \((a,b,c)\)。题目要求统计所有满足
$$a+b+c\le L$$
的此类三元组。实现并不是直接在 \((a,b,c)\) 空间里暴力搜索，而是先把根式恒等式化为一个丢番图方程，再枚举相应的因式分解结构。
令
$$x=\sqrt[3]{a+b\sqrt{c}},\qquad y=\sqrt[3]{a-b\sqrt{c}}.$$
则有 \(x+y=1\)。整个解法都建立在从这条恒等式中提取算术条件之上。
利用
$$x^3+y^3=(x+y)^3-3xy(x+y),$$
得到
$$2a=x^3+y^3=1-3xy,$$
因此
$$xy=\frac{1-2a}{3}.$$
另一方面，两个立方根内部相乘可得
$$x^3y^3=(a+b\sqrt{c})(a-b\sqrt{c})=a^2-b^2c,$$
于是
$$a^2-b^2c=\left(\frac{1-2a}{3}\right)^3.$$
整理后得到
$$27b^2c=27a^2+(2a-1)^3=(a+1)^2(8a-1).$$
这正是代码所利用的关键代数分解。
左边显然被 \(27\) 整除，因此右边 \((a+1)^2(8a-1)\) 也必须被 \(27\) 整除。模 \(3\) 分析可知这迫使
$$a\equiv 2\pmod 3.$$
因此写作
$$a=3u-1,\qquad u\ge 1.$$
这时 \(a+1=3u\)，\(8a-1=3(8u-3)\)，原方程化简为
$$b^2c=u^2(8u-3).$$
于是每个 Cardano 三元组都对应于一个正整数 \(u\)，以及对 \(u^2(8u-3)\) 的“平方部分 + 剩余部分”分解。
设
$$m=8u-3.$$
我们需要正整数 \(b,c\) 满足
$$b^2c=u^2m.$$
令
$$g=\gcd(b,u),\qquad u=gh,\qquad b=gb_1,$$
于是 \(\gcd(h,b_1)=1\)。代入后得到
$$g^2b_1^2c=g^2h^2m\qquad\Longrightarrow\qquad b_1^2c=h^2m.$$
由于 \(\gcd(h,b_1)=1\)，所以 \(b_1\) 的每个素因子都必须来自 \(m\)，从而 \(b_1^2\mid m\)。于是可写
$$m=b_1^2r.$$
这样便自动得到
$$c=h^2r,\qquad b=\frac{u}{h}b_1.$$
因此代码所枚举的所有解都具有如下形式：
$$a=3u-1,\qquad m=8u-3=b_1^2r,\qquad h\mid u,\qquad \gcd(h,b_1)=1,$$
$$b=\frac{u}{h}b_1,\qquad c=h^2r.$$
反过来，任何这样的选择都会满足 \(b^2c=u^2m\)，所以这个参数化是完整的。
固定 \(u\) 后，\(a=3u-1\) 已经确定。定义剩余预算
$$R=L-a.$$
任何候选都必须满足
$$b+c=\frac{u}{h}b_1+h^2r\le R.$$
代码从中推出 \(h\) 的两个强界。因为 \(u/h\ge 1\)，有 \(b\ge b_1\)，于是
$$c=h^2r\le R-b_1,$$
从而得到
$$h\le\left\lfloor\sqrt{\frac{R-b_1}{r}}\right\rfloor.$$
另外，由 \(h\ge 1\) 可知 \(c=h^2r\ge r\)，所以 \(b\le R-r\)。因此
$$\frac{u}{h}b_1\le R-r\qquad\Longrightarrow\qquad h\ge\left\lceil\frac{ub_1}{R-r}\right\rceil$$
只要 \(R-r\gt 0\)。实现只检查落在这个区间中的那些 \(h\mid u\)。
在主枚举开始之前，代码先通过对 \(b+c\) 做下界估计来求出一个安全的 \(u\) 上界。令
$$x=\frac{u}{h}b_1,\qquad y=h^2r.$$
则 \(x+y=b+c\)，并且
$$x^2y=u^2b_1^2r=u^2(8u-3).$$
当 \(x^2y=K\) 固定时，\(x+y\) 的最小值为 \(3\sqrt[3]{K/4}\)，这可由微积分或加权 AM-GM 不等式得到。因此任何合法三元组都必须满足
$$a+b+c\ge 3u-1+3\sqrt[3]{\frac{u^2(8u-3)}{4}}.$$
如果这个下界已经超过 \(L\)，那么该 \(u\) 不可能再产生解。由于该下界随 \(u\) 增长，代码可以用二分搜索求出 max_u_bound 所使用的截断值。
取 \(u=1\)。则
$$a=3\cdot 1-1=2,\qquad m=8\cdot 1-3=5.$$
\(m=5\) 的唯一平方因子是 \(b_1=1\)，而 \(u=1\) 的唯一因子是 \(h=1\)。因此
$$b=\frac{1}{1}\cdot 1=1,\qquad c=1^2\cdot 5=5.$$
这就重新得到题目中的例子 \((2,1,5)\)，而且参数化恰好只会计数一次。
实现首先计算 max_u_bound(limit)，然后构建 SPF 表以快速分解每个 \(u\)，并建立到 \(\sqrt{8u_{\max}-3}\) 为止的素数表来分解 \(m=8u-3\)。对于每个 \(u\)，代码枚举所有 \(h\mid u\)、所有作为 \(m\) 平方因子的 \(b_1\)，应用 \(h\) 的区间界，检查 \(\gcd(h,b_1)=1\)，最后验证 \(b+c\le R\)。外层按 \(u\) 的循环可以自然地并行化，因为不同的 \(u\) 彼此独立。
预处理的时间与空间复杂度为 \(O(u_{\max})\)，用于构建 SPF 表；此外还要做一个规模较小的素数筛，到 \(\sqrt{8u_{\max}-3}\) 为止。计数阶段的主要开销来自因子枚举：对每个 \(u\)，算法都要枚举 \(u\) 的因子和 \(8u-3\) 的平方因子。由于因子个数起伏较大，很难写出一个简单的闭式表达式，但借助 \(u\) 的全局上界、\(h\) 的区间剪枝以及互素过滤，实际运行时间远小于朴素搜索。
Тройка Кардано — это тройка положительных целых чисел \((a,b,c)\), удовлетворяющая
$$\sqrt[3]{a+b\sqrt{c}}+\sqrt[3]{a-b\sqrt{c}}=1.$$
Нужно подсчитать все такие тройки, для которых \(a+b+c\le L\). Реализация не перебирает напрямую пространство \((a,b,c)\); сначала она преобразует радикальное тождество в диофантово уравнение, а затем перечисляет допустимые схемы факторизации.
Положим
$$x=\sqrt[3]{a+b\sqrt{c}},\qquad y=\sqrt[3]{a-b\sqrt{c}}.$$
Тогда \(x+y=1\). Всё решение строится на извлечении арифметических следствий из этого равенства.
Используя
$$x^3+y^3=(x+y)^3-3xy(x+y),$$
получаем
$$2a=x^3+y^3=1-3xy,$$
откуда
$$xy=\frac{1-2a}{3}.$$
С другой стороны, произведение подкоренных выражений даёт
$$x^3y^3=(a+b\sqrt{c})(a-b\sqrt{c})=a^2-b^2c,$$
следовательно,
$$a^2-b^2c=\left(\frac{1-2a}{3}\right)^3.$$
После преобразований получаем
$$27b^2c=27a^2+(2a-1)^3=(a+1)^2(8a-1).$$
Именно эта факторизация лежит в основе кода.
Левая часть делится на \(27\), значит и \((a+1)^2(8a-1)\) тоже должна делиться на \(27\). По модулю \(3\) это возможно только если
$$a\equiv 2\pmod 3.$$
Поэтому записываем
$$a=3u-1,\qquad u\ge 1.$$
Тогда \(a+1=3u\), а \(8a-1=3(8u-3)\), и исходное уравнение превращается в
$$b^2c=u^2(8u-3).$$
Итак, каждой тройке Кардано соответствует положительное \(u\) и разложение числа \(u^2(8u-3)\) на квадратную часть и остаток.
Положим
$$m=8u-3.$$
Нужно найти положительные \(b,c\), удовлетворяющие
$$b^2c=u^2m.$$
Пусть
$$g=\gcd(b,u),\qquad u=gh,\qquad b=gb_1,$$
тогда \(\gcd(h,b_1)=1\). Подстановка даёт
$$g^2b_1^2c=g^2h^2m\qquad\Longrightarrow\qquad b_1^2c=h^2m.$$
Поскольку \(\gcd(h,b_1)=1\), каждый простой делитель \(b_1\) обязан происходить из \(m\), то есть \(b_1^2\mid m\). Поэтому можно написать
$$m=b_1^2r.$$
Тогда автоматически получаем
$$c=h^2r,\qquad b=\frac{u}{h}b_1.$$
Значит, каждая перебираемая программой тройка имеет вид
$$a=3u-1,\qquad m=8u-3=b_1^2r,\qquad h\mid u,\qquad \gcd(h,b_1)=1,$$
$$b=\frac{u}{h}b_1,\qquad c=h^2r.$$
И наоборот, любой такой выбор удовлетворяет \(b^2c=u^2m\), так что параметризация является полной.
Для фиксированного \(u\) значение \(a=3u-1\) уже известно. Обозначим оставшийся бюджет через
$$R=L-a.$$
Тогда любой кандидат обязан удовлетворять
$$b+c=\frac{u}{h}b_1+h^2r\le R.$$
Код выводит отсюда две сильные оценки для \(h\). Так как \(u/h\ge 1\), то \(b\ge b_1\), а значит
$$c=h^2r\le R-b_1,$$
откуда следует
$$h\le\left\lfloor\sqrt{\frac{R-b_1}{r}}\right\rfloor.$$
Кроме того, \(h\ge 1\) даёт \(c=h^2r\ge r\), следовательно \(b\le R-r\). Поэтому
$$\frac{u}{h}b_1\le R-r\qquad\Longrightarrow\qquad h\ge\left\lceil\frac{ub_1}{R-r}\right\rceil$$
при условии \(R-r\gt 0\). Реализация проверяет только те делители \(h\mid u\), которые попадают в этот интервал.
Перед основным перебором программа вычисляет безопасную верхнюю границу для \(u\), оценивая \(b+c\) снизу. Положим
$$x=\frac{u}{h}b_1,\qquad y=h^2r.$$
Тогда \(x+y=b+c\), и при этом
$$x^2y=u^2b_1^2r=u^2(8u-3).$$
При фиксированном \(x^2y=K\) минимум суммы \(x+y\) равен \(3\sqrt[3]{K/4}\); это следует либо из анализа, либо из взвешенного неравенства AM-GM. Следовательно, любая допустимая тройка должна удовлетворять
$$a+b+c\ge 3u-1+3\sqrt[3]{\frac{u^2(8u-3)}{4}}.$$
Если эта нижняя граница уже превышает \(L\), то такой \(u\) не может дать решений. Поскольку оценка растёт вместе с \(u\), бинарный поиск находит отсечение, используемое в max_u_bound.
Возьмём \(u=1\). Тогда
$$a=3\cdot 1-1=2,\qquad m=8\cdot 1-3=5.$$
Единственный квадратный делитель числа \(m=5\) — это \(b_1=1\), а единственный делитель числа \(u=1\) — это \(h=1\). Поэтому
$$b=\frac{1}{1}\cdot 1=1,\qquad c=1^2\cdot 5=5.$$
Мы получаем пример \((2,1,5)\), причём параметризация считает его ровно один раз.
Сначала программа вычисляет max_u_bound(limit), затем строит SPF-таблицу для быстрого разложения каждого \(u\) и список простых чисел до \(\sqrt{8u_{\max}-3}\) для факторизации числа \(m=8u-3\). Для каждого \(u\) перечисляются все делители \(h\mid u\), все варианты \(b_1\) как квадратного делителя числа \(m\), затем применяются интервальные границы для \(h\), проверяется условие \(\gcd(h,b_1)=1\), и в конце тестируется неравенство \(b+c\le R\). Внешний цикл по \(u\) естественно распараллеливается, поскольку разные значения \(u\) независимы.
Предварительные вычисления требуют \(O(u_{\max})\) времени и памяти для SPF-таблицы, плюс более маленькое решето простых чисел до \(\sqrt{8u_{\max}-3}\). Основная стоимость стадии подсчёта связана с перечислением делителей: для каждого \(u\) программа перебирает делители числа \(u\) и квадратные делители числа \(8u-3\). Простую замкнутую формулу дать трудно, поскольку число делителей сильно колеблется, но глобальная граница на \(u\), интервальная отсечка по \(h\) и фильтр взаимной простоты резко сокращают пространство поиска по сравнению с наивным перебором.
ثلاثية Cardano هي ثلاثية من الأعداد الصحيحة الموجبة \((a,b,c)\) تحقق
$$\sqrt[3]{a+b\sqrt{c}}+\sqrt[3]{a-b\sqrt{c}}=1.$$
المطلوب هو عدّ جميع هذه الثلاثيات التي تحقق أيضًا \(a+b+c\le L\). التنفيذ لا يفتش مباشرة في فضاء \((a,b,c)\)، بل يحوّل أولًا هذه العلاقة الجذرية إلى معادلة ديوفانتية ثم يعدّ أنماط التحليل العاملية الموافقة.
لنضع
$$x=\sqrt[3]{a+b\sqrt{c}},\qquad y=\sqrt[3]{a-b\sqrt{c}}.$$
عندئذٍ \(x+y=1\). وكل الحل يقوم على استخراج النتائج الحسابية لهذه الهوية.
باستخدام
$$x^3+y^3=(x+y)^3-3xy(x+y),$$
نحصل على
$$2a=x^3+y^3=1-3xy,$$
ومن ثم
$$xy=\frac{1-2a}{3}.$$
ومن جهة أخرى، فإن ضرب المقدارين داخل الجذرين التكعيبيين يعطي
$$x^3y^3=(a+b\sqrt{c})(a-b\sqrt{c})=a^2-b^2c,$$
وبالتالي
$$a^2-b^2c=\left(\frac{1-2a}{3}\right)^3.$$
وبإعادة الترتيب نحصل على
$$27b^2c=27a^2+(2a-1)^3=(a+1)^2(8a-1).$$
هذا التحليل هو التبسيط الجبري الأساسي الذي يعتمد عليه الكود.
الطرف الأيسر قابل للقسمة على \(27\)، ولذلك يجب أن يكون \((a+1)^2(8a-1)\) قابلًا للقسمة على \(27\) أيضًا. وبالعمل modulo \(3\) ينتج أن
$$a\equiv 2\pmod 3.$$
لذلك نكتب
$$a=3u-1,\qquad u\ge 1.$$
وعندئذٍ \(a+1=3u\)، و\(8a-1=3(8u-3)\)، فتتبسط المعادلة إلى
$$b^2c=u^2(8u-3).$$
وهكذا تقابل كل ثلاثية Cardano عددًا صحيحًا موجبًا \(u\) مع تحليل للعدد \(u^2(8u-3)\) إلى جزء مربع وجزء متبقٍّ.
لنعرّف
$$m=8u-3.$$
نحتاج إلى عددين موجبين \(b,c\) يحققان
$$b^2c=u^2m.$$
ولذلك نأخذ
$$g=\gcd(b,u),\qquad u=gh,\qquad b=gb_1,$$
بحيث \(\gcd(h,b_1)=1\). بالتعويض نحصل على
$$g^2b_1^2c=g^2h^2m\qquad\Longrightarrow\qquad b_1^2c=h^2m.$$
وبما أن \(\gcd(h,b_1)=1\)، فإن كل عامل أولي في \(b_1\) يجب أن يأتي من \(m\)، ومن ثم \(b_1^2\mid m\). ولذلك نكتب
$$m=b_1^2r.$$
ومن هنا ينتج تلقائيًا
$$c=h^2r,\qquad b=\frac{u}{h}b_1.$$
إذن كل حل يعدّه الكود له الشكل
$$a=3u-1,\qquad m=8u-3=b_1^2r,\qquad h\mid u,\qquad \gcd(h,b_1)=1,$$
$$b=\frac{u}{h}b_1,\qquad c=h^2r.$$
وبالعكس، فإن أي اختيار بهذه الصورة يحقق \(b^2c=u^2m\)، ولذلك فالتمثيل كامل.
عند تثبيت \(u\) يصبح \(a=3u-1\) معلومًا. ولنعرّف الميزانية الباقية بـ
$$R=L-a.$$
ولا بد لكل مرشح أن يحقق
$$b+c=\frac{u}{h}b_1+h^2r\le R.$$
ويستخرج الكود من هذا الشرط حدين قويين لـ \(h\). فبما أن \(u/h\ge 1\)، فإن \(b\ge b_1\)، ومن ثم
$$c=h^2r\le R-b_1,$$
ومنها
$$h\le\left\lfloor\sqrt{\frac{R-b_1}{r}}\right\rfloor.$$
كذلك من \(h\ge 1\) ينتج \(c=h^2r\ge r\)، ولذلك \(b\le R-r\). وبالتالي
$$\frac{u}{h}b_1\le R-r\qquad\Longrightarrow\qquad h\ge\left\lceil\frac{ub_1}{R-r}\right\rceil$$
عندما يكون \(R-r\gt 0\). ومن ثم لا يفحص التنفيذ إلا القيم \(h\mid u\) الواقعة داخل هذا المجال.
قبل بدء العد الرئيسي، يحسب الكود حدًا أعلى آمنًا لـ \(u\) عن طريق تقدير \(b+c\) من الأسفل. لنضع
$$x=\frac{u}{h}b_1,\qquad y=h^2r.$$
فعندئذٍ \(x+y=b+c\)، كما أن
$$x^2y=u^2b_1^2r=u^2(8u-3).$$
وعندما يكون \(x^2y=K\) ثابتًا، فإن أصغر قيمة ممكنة لـ \(x+y\) هي \(3\sqrt[3]{K/4}\)، ويمكن إثبات ذلك إما بالحساب التفاضلي أو بمتراجحة AM-GM الموزونة. لذلك يجب أن تحقق كل ثلاثية صالحة
$$a+b+c\ge 3u-1+3\sqrt[3]{\frac{u^2(8u-3)}{4}}.$$
فإذا تجاوز هذا الحد الأدنى القيمة \(L\)، فلن يعطي هذا \(u\) أي حلول. وبما أن هذا الحد يزداد مع \(u\)، فإن البحث الثنائي يعطي القطع المستخدم في max_u_bound.
لنأخذ \(u=1\). عندئذٍ
$$a=3\cdot 1-1=2,\qquad m=8\cdot 1-3=5.$$
القاسم المربع الوحيد لـ \(m=5\) هو \(b_1=1\)، والقاسم الوحيد لـ \(u=1\) هو \(h=1\). ولذلك
$$b=\frac{1}{1}\cdot 1=1,\qquad c=1^2\cdot 5=5.$$
وهذا يعيد المثال \((2,1,5)\)، كما أن التمثيل يعدّه مرة واحدة فقط.
يحسب التنفيذ أولًا max_u_bound(limit)، ثم يبني جدول SPF لتحليل كل \(u\) بسرعة، وقائمة أولية حتى \(\sqrt{8u_{\max}-3}\) لتحليل العدد \(m=8u-3\). ولكل \(u\) يعدد جميع القواسم \(h\mid u\)، وجميع اختيارات \(b_1\) بوصفه قاسمًا مربعًا لـ \(m\)، ثم يطبق حدود المجال على \(h\)، ويتحقق من الشرط \(\gcd(h,b_1)=1\)، وأخيرًا يفحص العلاقة \(b+c\le R\). والحلقة الخارجية على \(u\) قابلة للتوازي طبيعيًا لأن القيم المختلفة لـ \(u\) مستقلة عن بعضها.
تكلفة التهيئة المسبقة هي \(O(u_{\max})\) زمنًا وذاكرةً لبناء جدول SPF، بالإضافة إلى غربال أولي أصغر حتى \(\sqrt{8u_{\max}-3}\). أما مرحلة العد فتهيمن عليها عملية تعداد القواسم: فلكل \(u\) يجري الكود تعداد قواسم \(u\) والقواسم المربعة لـ \(8u-3\). لا توجد صيغة مغلقة بسيطة لأن عدد القواسم يتذبذب كثيرًا، لكن الحد العام على \(u\)، وتقليم مجال \(h\)، وشرط التباين الأولي، كلها تقلص فضاء البحث كثيرًا مقارنةً بالبحث الساذج.