For each positive integer \(n\), let \(s(n)\) be the number of cube-full divisors of \(n\). A positive integer \(d=\prod p_i^{e_i}\) is cube-full when every prime that appears has exponent at least \(3\). By the usual empty-product convention, \(1\) is cube-full as well. The goal is to compute
$$S(N)=\sum_{n=1}^{N}s(n)$$
for the huge value \(N=10^{18}\). Factoring every integer up to \(N\) is impossible, so the solution reorganizes the count around the cube-full divisors themselves.
The central observation is that it is much easier to count how often a fixed cube-full divisor occurs than to inspect every integer \(n\) separately.
For a fixed integer \(n\), the number of cube-full divisors is
$$s(n)=\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
Now sum this over all \(1\le n\le N\):
$$S(N)=\sum_{n=1}^{N}\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
Interchanging the two sums gives
$$S(N)=\sum_{\substack{d\le N\\ d\ \text{cube-full}}}\left\lfloor\frac{N}{d}\right\rfloor.$$
This formula is exact because \(\lfloor N/d\rfloor\) is precisely the number of multiples of \(d\) in \(\{1,2,\dots,N\}\). So the whole task reduces to enumerating all cube-full numbers \(d\le N\).
If
$$d=\prod_{i=1}^{k} p_i^{e_i},$$
then \(d\) is cube-full exactly when every exponent satisfies \(e_i\ge 3\). There are no allowed exponents \(1\) or \(2\). Therefore a cube-full number is determined by two pieces of data:
its distinct prime factors, listed in increasing order, and the exponent chosen for each of those primes from the set \(\{3,4,5,\dots\}\).
This is why the search naturally becomes a recursion over primes. The number \(1\) fits the same framework as the empty choice of primes and contributes the term \(\lfloor N/1\rfloor=N\).
If a prime \(p\) appears in a cube-full divisor \(d\le N\), then \(p^3\mid d\), hence
$$p^3\le d\le N.$$
So every relevant prime must satisfy
$$p\le \left\lfloor\sqrt[3]{N}\right\rfloor.$$
That is a dramatic reduction. For \(N=10^{18}\), the bound is only \(10^6\), so a simple prime sieve is sufficient to generate every prime that can possibly participate in the recursion.
Start from the current product \(d=1\). At each stage, choose the next prime only from positions after the primes already used. If the next chosen prime is \(p\), its first legal contribution is \(p^3\), and then the same prime may be raised to exponent \(4,5,6,\dots\) as long as the product stays at most \(N\).
This produces a unique construction path for every cube-full number. Indeed, if
$$d=q_1^{a_1}q_2^{a_2}\cdots q_m^{a_m},\qquad q_1<q_2<\cdots<q_m,\qquad a_i\ge 3,$$
then the recursion can reach \(d\) only by choosing \(q_1\) first with exponent \(a_1\), then \(q_2\), and so on. Because later recursive levels are allowed to use only larger primes, no alternative ordering is possible, so there is no double counting.
Suppose the current cube-full product is \(d\). For a candidate next prime \(p\), the smallest new factor would be \(p^3\). If
$$d\,p^3>N,$$
then this prime cannot be used, and neither can any larger prime, because larger primes have even larger cubes. The prime loop can stop immediately at that point. This monotonicity is the key reason the recursion stays small.
The cube-full numbers not exceeding \(100\) are
$$1,\ 8,\ 16,\ 27,\ 32,\ 64,\ 81.$$
Therefore
$$S(100)=\left\lfloor\frac{100}{1}\right\rfloor+\left\lfloor\frac{100}{8}\right\rfloor+\left\lfloor\frac{100}{16}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{32}\right\rfloor+\left\lfloor\frac{100}{64}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor.$$
Evaluating the floors gives
$$100+12+6+3+3+1+1=126.$$
This matches the small checkpoint used by the implementation, so the summation identity and the enumeration logic agree.
The C++, Python, and Java implementations all follow the same algorithm. First they compute the integer cube root \(L=\lfloor\sqrt[3]{N}\rfloor\) with a safe binary search, then they generate all primes up to \(L\) with a sieve.
After that, a depth-first recursion represents the current cube-full divisor \(d\). The moment such a value is constructed, the implementation adds \(\lfloor N/d\rfloor\) to the running total, because that is exactly the number of integers up to \(N\) divisible by \(d\).
From each recursive state, the implementation scans the remaining primes in increasing order. For each chosen prime it begins with the third power, then keeps multiplying by the same prime so that exponents \(3,4,5,\dots\) are all covered. The recursive call then moves to later primes only, which is what enforces uniqueness.
The three language versions differ only in low-level arithmetic safeguards. The C++ version uses wider integer arithmetic for some cube and product checks, the Java version rewrites an overflow-sensitive product test as a division test, and Python relies on arbitrary-precision integers. The underlying counting method is identical in all three.
The C++ implementation also includes a few tiny sanity checks, including one brute-force comparison on a small bound, before printing the final \(N=10^{18}\) result.
Let \(L=\lfloor\sqrt[3]{N}\rfloor\). Building the prime list up to \(L\) costs \(O(L\log\log L)\) time and \(O(L)\) memory. If \(C(N)\) denotes the number of cube-full integers not exceeding \(N\), the recursive part visits each of those values exactly once, so the dominant extra work is proportional to the generated search tree rather than to \(N\) itself.
Memory usage remains modest: the sieve or prime list up to \(L\), the recursion stack, and a few integer temporaries. The recursion depth is only the number of distinct primes that appear in the current cube-full number, so it stays small in practice.
Für jede positive ganze Zahl \(n\) sei \(s(n)\) die Anzahl ihrer cube-full-Teiler. Eine Zahl \(d=\prod p_i^{e_i}\) heißt cube-full, wenn jeder tatsächlich auftretende Primexponent mindestens \(3\) ist. Nach der üblichen Konvention zählt auch \(1\) dazu. Gesucht ist
$$S(N)=\sum_{n=1}^{N}s(n)$$
für den sehr großen Wert \(N=10^{18}\). Man kann also unmöglich alle Zahlen bis \(N\) einzeln faktorisieren; stattdessen muss man die Beiträge der cube-full-Teiler direkt aufsummieren.
Die Kernidee besteht darin, nicht über die Zahlen \(n\), sondern über die cube-full-Teiler selbst zu summieren.
Für ein festes \(n\) lässt sich \(s(n)\) schreiben als
$$s(n)=\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
Summiert man dies über alle \(1\le n\le N\), so erhält man
$$S(N)=\sum_{n=1}^{N}\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
Vertauscht man die Summationen, folgt
$$S(N)=\sum_{\substack{d\le N\\ d\ \text{cube-full}}}\left\lfloor\frac{N}{d}\right\rfloor.$$
Der Ausdruck \(\lfloor N/d\rfloor\) zählt nämlich genau die Vielfachen von \(d\) im Bereich \(1\) bis \(N\). Damit ist das Problem auf die Erzeugung aller cube-full-Zahlen \(d\le N\) reduziert.
Gilt
$$d=\prod_{i=1}^{k} p_i^{e_i},$$
dann ist \(d\) genau dann cube-full, wenn für jeden vorkommenden Primfaktor \(e_i\ge 3\) gilt. Exponenten \(1\) oder \(2\) sind also ausgeschlossen. Eine cube-full-Zahl wird deshalb vollständig beschrieben durch
ihre verschiedenen Primfaktoren in aufsteigender Reihenfolge und einen zu jedem dieser Primfaktoren gewählten Exponenten aus \(\{3,4,5,\dots\}\).
Genau diese Darstellung nutzt die Rekursion aus. Die Zahl \(1\) entspricht dabei der leeren Primfaktorauswahl und liefert den Beitrag \(\lfloor N/1\rfloor=N\).
Wenn eine Primzahl \(p\) in einem cube-full-Teiler \(d\le N\) vorkommt, dann gilt \(p^3\mid d\) und damit
$$p^3\le d\le N.$$
Also muss jede relevante Primzahl die Bedingung
$$p\le \left\lfloor\sqrt[3]{N}\right\rfloor$$
erfüllen. Für \(N=10^{18}\) ist diese Grenze nur \(10^6\). Eine gewöhnliche Primzahlsiebung reicht daher völlig aus.
Man beginnt mit dem aktuellen Produkt \(d=1\). In jedem Rekursionsschritt darf die nächste Primzahl nur aus den Positionen nach den bereits benutzten Primzahlen gewählt werden. Wird eine Primzahl \(p\) gewählt, so ist der erste zulässige Beitrag \(p^3\); anschließend kann dieselbe Primzahl weiter zu den Exponenten \(4,5,6,\dots\) erhöht werden, solange das Produkt höchstens \(N\) bleibt.
Damit besitzt jede cube-full-Zahl genau einen Konstruktionspfad. Ist nämlich
$$d=q_1^{a_1}q_2^{a_2}\cdots q_m^{a_m},\qquad q_1<q_2<\cdots<q_m,\qquad a_i\ge 3,$$
dann kann die Rekursion \(d\) nur erreichen, indem sie zuerst \(q_1\) mit Exponent \(a_1\), dann \(q_2\) usw. wählt. Da spätere Rekursionsebenen nur größere Primzahlen sehen, gibt es keine alternative Reihenfolge und somit keine Doppelerfassung.
Sei \(d\) das aktuelle cube-full-Produkt. Für eine Kandidatenprimzahl \(p\) wäre der kleinste neue Faktor \(p^3\). Falls
$$d\,p^3>N,$$
ist diese Primzahl unmöglich, und jede größere Primzahl ebenfalls, weil ihre Kuben noch größer sind. Die Schleife kann an dieser Stelle sofort abbrechen. Genau dieser monotone Cutoff macht die Suche effizient.
Die cube-full-Zahlen bis \(100\) sind
$$1,\ 8,\ 16,\ 27,\ 32,\ 64,\ 81.$$
Daher gilt
$$S(100)=\left\lfloor\frac{100}{1}\right\rfloor+\left\lfloor\frac{100}{8}\right\rfloor+\left\lfloor\frac{100}{16}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{32}\right\rfloor+\left\lfloor\frac{100}{64}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor.$$
Die Auswertung liefert
$$100+12+6+3+3+1+1=126.$$
Das stimmt mit dem kleinen Kontrollwert der Implementierung überein und bestätigt sowohl die Summationsformel als auch die Erzeugungslogik.
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zuerst berechnen sie die ganzzahlige Kubikwurzel \(L=\lfloor\sqrt[3]{N}\rfloor\) per sicherer binärer Suche. Anschließend erzeugen sie mit einem Sieb alle Primzahlen bis \(L\).
Danach repräsentiert eine Tiefensuche den aktuellen cube-full-Teiler \(d\). Sobald ein solcher Wert konstruiert ist, addiert die Implementierung \(\lfloor N/d\rfloor\) zur laufenden Summe, denn das ist genau die Anzahl der Zahlen bis \(N\), die durch \(d\) teilbar sind.
Von jedem Zustand aus werden die verbleibenden Primzahlen in aufsteigender Reihenfolge ausprobiert. Für eine gewählte Primzahl beginnt die Implementierung mit der dritten Potenz und multipliziert dann weiter mit derselben Primzahl, um die Exponenten \(3,4,5,\dots\) abzudecken. Der rekursive Aufruf wechselt anschließend nur noch zu späteren Primzahlen, was die Eindeutigkeit sicherstellt.
Die Unterschiede zwischen den drei Sprachversionen liegen nur in den arithmetischen Schutzmaßnahmen. C++ verwendet an einigen Stellen breitere Ganzzahltypen, Java formuliert einen überlaufkritischen Produkttest als Divisionstest um, und Python profitiert von beliebig großen Ganzzahlen. Der mathematische Kern ist in allen drei Varianten identisch.
Die C++-Implementierung enthält außerdem einige kleine Plausibilitätsprüfungen, darunter einen Vergleich mit Brute Force auf einer winzigen Schranke, bevor das Endergebnis für \(N=10^{18}\) ausgegeben wird.
Sei \(L=\lfloor\sqrt[3]{N}\rfloor\). Das Erzeugen der Primzahlen bis \(L\) kostet \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher. Bezeichnet \(C(N)\) die Anzahl der cube-full-Zahlen bis \(N\), so besucht die Rekursion jeden dieser Werte genau einmal. Die zusätzliche Arbeit wächst daher mit dem erzeugten Suchbaum und nicht mit \(N\) selbst.
Der Speicherbedarf bleibt klein: Sieb beziehungsweise Primliste bis \(L\), Rekursionsstapel und einige Ganzzahlvariablen. Die Rekursionstiefe entspricht nur der Anzahl verschiedener Primzahlen im aktuellen cube-full-Produkt und bleibt in der Praxis gering.
Her pozitif tamsayı \(n\) için \(s(n)\), \(n\)'in cube-full bölenlerinin sayısı olsun. Bir \(d=\prod p_i^{e_i}\) sayısı, içinde yer alan her asalın üssü en az \(3\) ise cube-full'dur. Boş çarpım kuralı gereği \(1\) de cube-full kabul edilir. İstenen değer
$$S(N)=\sum_{n=1}^{N}s(n)$$
olup burada \(N=10^{18}\) gibi çok büyük bir sayıdır. Bu yüzden \(1\) ile \(N\) arasındaki her sayıyı tek tek çarpanlara ayırmak yerine, cube-full bölenlerin toplam katkısını doğrudan saymak gerekir.
Ana gözlem, tek tek \(n\) değerlerine bakmak yerine sabit bir cube-full bölenin kaç kere göründüğünü saymanın çok daha kolay olmasıdır.
Sabit bir \(n\) için
$$s(n)=\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1$$
yazabiliriz. Bunu \(1\le n\le N\) için toplarsak
$$S(N)=\sum_{n=1}^{N}\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1$$
elde edilir. Toplamların sırasını değiştirince
$$S(N)=\sum_{\substack{d\le N\\ d\ \text{cube-full}}}\left\lfloor\frac{N}{d}\right\rfloor$$
olur. Çünkü \(\lfloor N/d\rfloor\), \(1\) ile \(N\) arasında \(d\)'ye bölünebilen sayıların tam sayısıdır. Böylece problem, \(N\)'i aşmayan bütün cube-full \(d\) değerlerini üretmeye indirgenir.
Eğer
$$d=\prod_{i=1}^{k} p_i^{e_i}$$
ise, \(d\)'nin cube-full olması tam olarak her \(e_i\ge 3\) olmasına eşdeğerdir. Yani \(1\) veya \(2\) üslü hiçbir asal çarpan kabul edilmez. Dolayısıyla bir cube-full sayı iki seçimden oluşur:
artan sıradaki farklı asal çarpanlar ve bu asalların her biri için \(\{3,4,5,\dots\}\) kümesinden seçilen üsler.
Özyinelemeli arama tam olarak bu yapıyı kullanır. \(1\) sayısı da hiç asal seçmemekle aynı anlama gelir ve \(\lfloor N/1\rfloor=N\) katkısını verir.
Eğer bir asal \(p\), \(d\le N\) olan bir cube-full böleni içinde yer alıyorsa \(p^3\mid d\) olur. Dolayısıyla
$$p^3\le d\le N$$
ve buradan
$$p\le \left\lfloor\sqrt[3]{N}\right\rfloor$$
çıkar. Bu sınır çok küçüktür. \(N=10^{18}\) için yalnızca \(10^6\)'ya kadar asallar gerekir; bunlar da basit bir asal süzgeciyle rahatça üretilebilir.
Mevcut çarpım \(d=1\) ile başlanır. Her aşamada sıradaki yeni asal, daha önce kullanılmış asalların sonrasından seçilir. Seçilen asal \(p\) ise ilk izin verilen çarpan \(p^3\)'tür; ardından ürün \(N\)'i aşmadığı sürece aynı asalın üssü \(4,5,6,\dots\) olacak şekilde yükseltilebilir.
Böylece her cube-full sayının tek bir yapım yolu olur. Gerçekten de
$$d=q_1^{a_1}q_2^{a_2}\cdots q_m^{a_m},\qquad q_1<q_2<\cdots<q_m,\qquad a_i\ge 3$$
şeklinde yazılan bir sayı, aramada ancak önce \(q_1\), sonra \(q_2\), sonra \(q_3\) seçilerek elde edilebilir. Daha derin seviyeler sadece daha büyük asallara izin verdiği için başka bir sıralama yoktur; dolayısıyla çift sayım da yoktur.
Mevcut cube-full çarpım \(d\) olsun. Sıradaki aday asal \(p\) için eklenebilecek en küçük yeni çarpan \(p^3\)'tür. Eğer
$$d\,p^3>N$$
ise bu asal kullanılamaz; daha büyük asalların küpleri daha da büyük olacağı için onlar da kullanılamaz. Bu noktada asal döngüsü hemen durabilir. Aramayı pratik hale getiren temel özellik budur.
\(100\)'ü aşmayan cube-full sayılar
$$1,\ 8,\ 16,\ 27,\ 32,\ 64,\ 81$$
olur. Bu yüzden
$$S(100)=\left\lfloor\frac{100}{1}\right\rfloor+\left\lfloor\frac{100}{8}\right\rfloor+\left\lfloor\frac{100}{16}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{32}\right\rfloor+\left\lfloor\frac{100}{64}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor$$
şeklindedir. Taban değerleri yazınca
$$100+12+6+3+3+1+1=126$$
elde edilir. Bu da uygulamadaki küçük kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı algoritmayı izler. Önce güvenli bir ikili arama ile \(L=\lfloor\sqrt[3]{N}\rfloor\) bulunur. Sonra \(L\)'ye kadar olan bütün asallar bir süzgeç yardımıyla üretilir.
Bundan sonra derinlik öncelikli özyineleme, mevcut cube-full böleni \(d\) olarak tutar. Geçerli bir \(d\) kurulur kurulmaz, uygulama \(\lfloor N/d\rfloor\) değerini toplam sonuca ekler; çünkü bu, \(d\)'ye bölünebilen ve \(N\)'i aşmayan sayıların tam sayısıdır.
Her özyineleme durumunda kalan asallar artan sırayla denenir. Seçilen bir asal için üçüncü kuvvetten başlanır, sonra aynı asal tekrar tekrar çarpılarak üslerin \(3,4,5,\dots\) olması sağlanır. Sonraki özyinelemeli çağrı yalnızca daha sonraki asallara geçtiği için her cube-full sayı tam bir kez üretilir.
Üç dil arasındaki farklar yalnızca taşma güvenliği gibi düşük seviye ayrıntılardadır. C++ bazı küp ve çarpım kontrollerinde daha geniş tamsayı türleri kullanır, Java taşmaya açık bir çarpım testini bölme eşitsizliğiyle ifade eder, Python ise keyfi büyüklükte tamsayılarla doğal olarak çalışır. Sayım yöntemi hepsinde aynıdır.
C++ uygulaması ayrıca, tam sonucu yazdırmadan önce, çok küçük girdiler üzerinde birkaç kısa akıl sağlama kontrolü ve bir brute-force karşılaştırması içerir.
\(L=\lfloor\sqrt[3]{N}\rfloor\) olsun. \(L\)'ye kadar asal üretmek \(O(L\log\log L)\) zaman ve \(O(L)\) bellek ister. \(C(N)\), \(N\)'i aşmayan cube-full sayıların sayısı olmak üzere, özyineleme bu sayıların her birini tam bir kez ziyaret eder. Dolayısıyla ek maliyet \(N\) ile değil, üretilen arama ağacının boyutuyla orantılıdır.
Bellek kullanımı küçüktür: süzgeç veya asal listesi, özyineleme yığını ve birkaç tamsayı değişkeni. Özyineleme derinliği sadece mevcut cube-full sayıda bulunan farklı asal sayısı kadardır ve pratikte oldukça düşüktür.
Para cada entero positivo \(n\), sea \(s(n)\) el número de divisores cube-full de \(n\). Un entero positivo \(d=\prod p_i^{e_i}\) es cube-full cuando todo primo que aparece lo hace con exponente al menos \(3\). Por la convención del producto vacío, \(1\) también cuenta como cube-full. Se desea calcular
$$S(N)=\sum_{n=1}^{N}s(n)$$
para el enorme valor \(N=10^{18}\). Recorrer y factorizar todos los enteros hasta \(N\) es imposible, así que la solución reorganiza el cómputo alrededor de los propios divisores cube-full.
La observación decisiva es que resulta mucho más fácil contar cuántas veces aparece un divisor cube-full fijo que inspeccionar cada entero \(n\) por separado.
Para un \(n\) fijo, se puede escribir
$$s(n)=\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
Al sumar esto para \(1\le n\le N\), obtenemos
$$S(N)=\sum_{n=1}^{N}\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
Si ahora intercambiamos el orden de las sumas, queda
$$S(N)=\sum_{\substack{d\le N\\ d\ \text{cube-full}}}\left\lfloor\frac{N}{d}\right\rfloor.$$
La razón es que \(\lfloor N/d\rfloor\) cuenta exactamente los múltiplos de \(d\) contenidos en \(\{1,2,\dots,N\}\). Por tanto, todo el problema se reduce a enumerar todos los números cube-full \(d\le N\).
Si
$$d=\prod_{i=1}^{k} p_i^{e_i},$$
entonces \(d\) es cube-full si y solo si cada exponente satisface \(e_i\ge 3\). Los exponentes \(1\) y \(2\) no están permitidos. Así, un número cube-full queda determinado por
sus primos distintos en orden creciente y un exponente elegido para cada uno de ellos dentro del conjunto \(\{3,4,5,\dots\}\).
Esa es precisamente la estructura que aprovecha la recursión. El valor \(1\) corresponde a no elegir ningún primo y aporta el término \(\lfloor N/1\rfloor=N\).
Si un primo \(p\) aparece en un divisor cube-full \(d\le N\), entonces \(p^3\mid d\), luego
$$p^3\le d\le N.$$
Por consiguiente, todo primo relevante cumple
$$p\le \left\lfloor\sqrt[3]{N}\right\rfloor.$$
La reducción es enorme. Para \(N=10^{18}\), esta cota es solo \(10^6\), de modo que una criba elemental basta para generar todos los primos candidatos.
Se comienza con el producto actual \(d=1\). En cada paso, el siguiente primo solo puede elegirse entre los que vienen después de los primos ya usados. Si el primo elegido es \(p\), la primera contribución legal es \(p^3\), y después se puede seguir multiplicando por \(p\) para cubrir los exponentes \(4,5,6,\dots\), mientras el producto no supere \(N\).
Esto da un camino único de construcción para cada número cube-full. En efecto, si
$$d=q_1^{a_1}q_2^{a_2}\cdots q_m^{a_m},\qquad q_1<q_2<\cdots<q_m,\qquad a_i\ge 3,$$
la recursión solo puede llegar a \(d\) escogiendo primero \(q_1\), luego \(q_2\), y así sucesivamente. Como los niveles posteriores solo pueden usar primos mayores, no existe un segundo orden posible y no hay doble conteo.
Sea \(d\) el producto cube-full actual. Para un primo candidato \(p\), el menor nuevo factor posible sería \(p^3\). Si
$$d\,p^3>N,$$
ese primo ya no sirve, y tampoco sirve ningún primo mayor porque sus cubos serían todavía más grandes. En ese punto la exploración puede detenerse de inmediato. Esa monotonía es la razón práctica de la eficiencia del método.
Los números cube-full no mayores que \(100\) son
$$1,\ 8,\ 16,\ 27,\ 32,\ 64,\ 81.$$
Por tanto,
$$S(100)=\left\lfloor\frac{100}{1}\right\rfloor+\left\lfloor\frac{100}{8}\right\rfloor+\left\lfloor\frac{100}{16}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{32}\right\rfloor+\left\lfloor\frac{100}{64}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor.$$
Al evaluar los pisos obtenemos
$$100+12+6+3+3+1+1=126.$$
Ese valor coincide con la pequeña comprobación incluida en la implementación.
Las implementaciones en C++, Python y Java siguen exactamente el mismo plan. Primero calculan la raíz cúbica entera \(L=\lfloor\sqrt[3]{N}\rfloor\) mediante una búsqueda binaria segura. Después generan todos los primos hasta \(L\) usando una criba.
A continuación, una recursión en profundidad representa el divisor cube-full actual \(d\). En cuanto se construye un valor válido, la implementación suma \(\lfloor N/d\rfloor\) al total acumulado, porque ese es exactamente el número de enteros hasta \(N\) divisibles por \(d\).
Desde cada estado, la implementación recorre los primos restantes en orden creciente. Para cada primo elegido empieza en la tercera potencia y luego sigue multiplicando por el mismo primo para cubrir los exponentes \(3,4,5,\dots\). La llamada recursiva posterior avanza solo a primos más grandes, lo que garantiza la unicidad de la enumeración.
Las tres versiones solo difieren en detalles de seguridad aritmética. La versión en C++ usa enteros más anchos en algunas comprobaciones de cubos y productos, la versión en Java convierte una prueba delicada de producto en una comparación por división, y Python se apoya en enteros de precisión arbitraria. El algoritmo matemático es el mismo en los tres casos.
La versión en C++ también conserva varias comprobaciones pequeñas de consistencia, incluida una comparación por fuerza bruta en un límite diminuto, antes de imprimir la respuesta final para \(N=10^{18}\).
Sea \(L=\lfloor\sqrt[3]{N}\rfloor\). Construir la lista de primos hasta \(L\) cuesta \(O(L\log\log L)\) tiempo y \(O(L)\) memoria. Si \(C(N)\) denota el número de enteros cube-full no mayores que \(N\), la parte recursiva visita cada uno exactamente una vez, de modo que el trabajo adicional depende del árbol realmente generado y no de \(N\) de forma lineal.
El uso de memoria es reducido: la criba o lista de primos hasta \(L\), la pila de recursión y unas pocas variables enteras. La profundidad de la recursión es solo el número de primos distintos presentes en el cube-full actual, así que en la práctica se mantiene baja.
对每个正整数 \(n\)，记 \(s(n)\) 为 \(n\) 的 cube-full 因子个数。若一个正整数
$$d=\prod p_i^{e_i}$$
中所有实际出现的素数指数都至少为 \(3\)，那么它就是 cube-full。按照空乘积的通常约定，\(1\) 也算 cube-full。题目要求计算
$$S(N)=\sum_{n=1}^{N}s(n)$$
其中 \(N=10^{18}\)。这个范围太大，不可能把 \(1\) 到 \(N\) 的每个整数都逐个分解质因数，所以必须把计数重心转移到 cube-full 因子本身。
最关键的观察是：与其逐个检查每个 \(n\)，不如固定一个 cube-full 因子，统计它会在多少个整数里出现。
对固定的 \(n\)，\(s(n)\) 可以写成
$$s(n)=\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
把它对所有 \(1\le n\le N\) 求和，有
$$S(N)=\sum_{n=1}^{N}\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
交换求和次序之后得到
$$S(N)=\sum_{\substack{d\le N\\ d\ \text{cube-full}}}\left\lfloor\frac{N}{d}\right\rfloor.$$
原因很直接：\(\lfloor N/d\rfloor\) 恰好等于区间 \(\{1,2,\dots,N\}\) 中 \(d\) 的倍数个数。于是整个问题就变成了枚举所有不超过 \(N\) 的 cube-full 数 \(d\)。
如果
$$d=\prod_{i=1}^{k} p_i^{e_i},$$
那么 \(d\) 是 cube-full，当且仅当每个出现的指数都满足 \(e_i\ge 3\)。也就是说，指数 \(1\) 和 \(2\) 都不允许出现。于是一个 cube-full 数完全由两部分决定：
第一，按从小到大排列的不同素因子；第二，每个素因子所选的指数，且该指数属于 \(\{3,4,5,\dots\}\)。
这正是递归搜索所利用的结构。数值 \(1\) 则对应于“一个素数也不选”的空情况，它带来的贡献就是 \(\lfloor N/1\rfloor=N\)。
如果某个素数 \(p\) 出现在 cube-full 因子 \(d\le N\) 中，那么一定有 \(p^3\mid d\)，因此
$$p^3\le d\le N.$$
这立刻推出所有相关素数都必须满足
$$p\le \left\lfloor\sqrt[3]{N}\right\rfloor.$$
这个上界非常小。对于 \(N=10^{18}\)，它只有 \(10^6\)。因此先用普通素数筛生成所有候选素数，代价是完全可以接受的。
从当前乘积 \(d=1\) 开始。每一层递归都只允许从尚未使用过的更后面的素数里选择下一个素数。如果选择的素数是 \(p\)，那么它第一次合法出现时至少要贡献 \(p^3\)。之后只要乘积还不超过 \(N\)，就可以继续乘同一个 \(p\)，从而依次覆盖指数 \(4,5,6,\dots\)。
这种做法保证每个 cube-full 数恰好只会被构造一次。因为如果
$$d=q_1^{a_1}q_2^{a_2}\cdots q_m^{a_m},\qquad q_1<q_2<\cdots<q_m,\qquad a_i\ge 3,$$
那么递归只能按 \(q_1,q_2,\dots,q_m\) 这个顺序到达它。较深层的递归只允许使用更大的素数，所以不存在另一种不同顺序生成同一个 \(d\)；也就不存在重复计数。
设当前 cube-full 乘积为 \(d\)。对于候选下一个素数 \(p\)，它最小可能的新贡献是 \(p^3\)。如果
$$d\,p^3>N,$$
那么这个素数已经无法使用，而任何更大的素数也同样无法使用，因为它们的立方只会更大。于是这一层的素数循环可以立刻停止。正是这个单调性让搜索树保持得很小。
不超过 \(100\) 的 cube-full 数是
$$1,\ 8,\ 16,\ 27,\ 32,\ 64,\ 81.$$
因此
$$S(100)=\left\lfloor\frac{100}{1}\right\rfloor+\left\lfloor\frac{100}{8}\right\rfloor+\left\lfloor\frac{100}{16}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{32}\right\rfloor+\left\lfloor\frac{100}{64}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor.$$
把这些整数部分算出来，就是
$$100+12+6+3+3+1+1=126.$$
这个结果与实现中保留的小规模校验完全一致，因此公式和枚举逻辑彼此吻合。
C++、Python 和 Java 三个实现使用的是同一套算法。第一步都是通过安全的二分搜索求出整数立方根 \(L=\lfloor\sqrt[3]{N}\rfloor\)，然后用筛法生成所有不超过 \(L\) 的素数。
接下来，深度优先递归把“当前已经构造出的 cube-full 因子”记为 \(d\)。一旦得到一个合法的 \(d\)，实现就立刻把 \(\lfloor N/d\rfloor\) 加入总和，因为这正好等于不超过 \(N\) 且能被 \(d\) 整除的整数个数。
从每个递归状态出发，实现会按升序扫描剩余素数。若某个素数被选中，就先从三次幂开始，再不断乘上同一个素数，从而覆盖指数 \(3,4,5,\dots\)。随后递归只会继续考虑更大的素数，这正是“每个 cube-full 数只枚举一次”的保证。
三种语言的差别只体现在底层整数安全上。C++ 在部分立方和乘法判断中使用更宽的整数类型；Java 把一个容易溢出的乘法判断改写成除法不等式；Python 则直接依赖任意精度整数。它们背后的计数思想完全相同。
另外，C++ 实现还保留了几条很小的自检，包括一次在微小范围上的暴力比较，然后才输出 \(N=10^{18}\) 的最终答案。
记 \(L=\lfloor\sqrt[3]{N}\rfloor\)。生成不超过 \(L\) 的素数需要 \(O(L\log\log L)\) 时间和 \(O(L)\) 空间。若用 \(C(N)\) 表示不超过 \(N\) 的 cube-full 整数个数，那么递归部分会恰好访问每一个这样的值一次，因此额外工作量取决于实际生成的搜索树，而不是与 \(N\) 同阶增长。
内存占用也很温和：主要是筛表或素数表、递归栈以及少量整数临时变量。递归深度只等于当前 cube-full 数里不同素因子的个数，所以在实践中非常小。
Для каждого положительного целого \(n\) обозначим через \(s(n)\) число его cube-full делителей. Число
$$d=\prod p_i^{e_i}$$
называется cube-full, если каждый простой множитель, который в нем присутствует, имеет показатель не меньше \(3\). По стандартной договоренности число \(1\) тоже считается cube-full. Нужно вычислить
$$S(N)=\sum_{n=1}^{N}s(n)$$
для огромного значения \(N=10^{18}\). Перебирать и факторизовать все числа до \(N\) нельзя, поэтому подсчет нужно перестроить вокруг самих cube-full делителей.
Главное наблюдение состоит в том, что гораздо проще посчитать, сколько раз фиксированный cube-full делитель встречается среди чисел до \(N\), чем рассматривать каждое \(n\) отдельно.
Для фиксированного \(n\) имеем
$$s(n)=\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
Суммируя это по всем \(1\le n\le N\), получаем
$$S(N)=\sum_{n=1}^{N}\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
После перестановки сумм выходит
$$S(N)=\sum_{\substack{d\le N\\ d\ \text{cube-full}}}\left\lfloor\frac{N}{d}\right\rfloor.$$
Это верно потому, что \(\lfloor N/d\rfloor\) точно равно числу кратных \(d\) в диапазоне от \(1\) до \(N\). Следовательно, задача сводится к перечислению всех cube-full чисел \(d\le N\).
Если
$$d=\prod_{i=1}^{k} p_i^{e_i},$$
то число \(d\) является cube-full тогда и только тогда, когда каждый встречающийся показатель удовлетворяет неравенству \(e_i\ge 3\). Показатели \(1\) и \(2\) недопустимы. Значит, cube-full число полностью задается
списком различных простых множителей в возрастающем порядке и выбранным для каждого из них показателем из множества \(\{3,4,5,\dots\}\).
Именно эту структуру использует рекурсивный перебор. Число \(1\) соответствует пустому набору простых множителей и дает вклад \(\lfloor N/1\rfloor=N\).
Если простой \(p\) входит в cube-full делитель \(d\le N\), то обязательно \(p^3\mid d\). Поэтому
$$p^3\le d\le N,$$
откуда сразу следует ограничение
$$p\le \left\lfloor\sqrt[3]{N}\right\rfloor.$$
Это очень сильное сужение области поиска. Для \(N=10^{18}\) верхняя граница равна всего лишь \(10^6\), так что обычного решета для генерации простых вполне достаточно.
Начинаем с текущего произведения \(d=1\). На каждом уровне рекурсии следующий простой можно выбирать только из позиций после уже использованных простых. Если выбран простой \(p\), то его первый допустимый вклад равен \(p^3\), а затем показатель можно увеличивать до \(4,5,6,\dots\), пока произведение не превысит \(N\).
Это дает единственный путь построения для каждого cube-full числа. Действительно, если
$$d=q_1^{a_1}q_2^{a_2}\cdots q_m^{a_m},\qquad q_1<q_2<\cdots<q_m,\qquad a_i\ge 3,$$
то рекурсия может получить это число только в порядке выбора \(q_1\), затем \(q_2\), затем \(q_3\) и так далее. Более глубокие уровни видят только большие простые, поэтому другой порядок невозможен, а значит, невозможен и повторный учет.
Пусть текущее cube-full произведение равно \(d\). Для кандидата \(p\) наименьший новый множитель равен \(p^3\). Если
$$d\,p^3>N,$$
то этот простой уже нельзя использовать, и тем более нельзя использовать любой больший простой, потому что его куб будет еще больше. Значит, цикл по простым можно немедленно прервать. Именно эта монотонность делает перебор компактным.
Cube-full числа, не превосходящие \(100\), таковы:
$$1,\ 8,\ 16,\ 27,\ 32,\ 64,\ 81.$$
Следовательно,
$$S(100)=\left\lfloor\frac{100}{1}\right\rfloor+\left\lfloor\frac{100}{8}\right\rfloor+\left\lfloor\frac{100}{16}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{32}\right\rfloor+\left\lfloor\frac{100}{64}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor.$$
После вычисления получаем
$$100+12+6+3+3+1+1=126.$$
Это совпадает с малой контрольной проверкой в реализации.
Реализации на C++, Python и Java используют один и тот же алгоритм. Сначала они находят целую кубическую корень \(L=\lfloor\sqrt[3]{N}\rfloor\) при помощи безопасного бинарного поиска. Затем строят список всех простых чисел до \(L\) с помощью решета.
После этого поиск в глубину хранит текущее cube-full значение \(d\). Как только такое \(d\) построено, реализация немедленно прибавляет \(\lfloor N/d\rfloor\) к накопленной сумме, потому что это в точности число целых до \(N\), кратных \(d\).
Из каждого состояния код перебирает оставшиеся простые в возрастающем порядке. Для выбранного простого он начинает с третьей степени, затем продолжает умножать на тот же простой, чтобы покрыть показатели \(3,4,5,\dots\). Следующий рекурсивный вызов разрешает использовать только более поздние простые, и именно это обеспечивает единственность перечисления.
Различия между тремя версиями касаются только защиты от переполнения. В C++ для части проверок используются более широкие целые типы, в Java один потенциально опасный тест произведения заменен делением, а Python опирается на целые произвольной точности. Сам метод подсчета во всех трех языках одинаков.
Кроме того, версия на C++ содержит несколько маленьких проверок здравого смысла, включая одно сравнение с полным перебором на крошечной границе, перед выводом окончательного результата для \(N=10^{18}\).
Пусть \(L=\lfloor\sqrt[3]{N}\rfloor\). Построение списка простых до \(L\) требует \(O(L\log\log L)\) времени и \(O(L)\) памяти. Если обозначить через \(C(N)\) число cube-full целых, не превосходящих \(N\), то рекурсивная часть посещает каждый такой элемент ровно один раз. Поэтому дополнительная работа определяется размером реально построенного дерева поиска, а не самим \(N\).
Память расходуется умеренно: решето или список простых, стек рекурсии и несколько целочисленных переменных. Глубина рекурсии равна лишь числу различных простых в текущем cube-full числе, так что на практике она мала.
لكل عدد صحيح موجب \(n\)، نرمز بـ \(s(n)\) إلى عدد قواسمه من النوع cube-full. ويكون العدد
$$d=\prod p_i^{e_i}$$
cube-full إذا كان كل عامل أولي يظهر فيه بأس لا يقل عن \(3\). وبحسب اصطلاح حاصل الضرب الفارغ، فإن \(1\) يُعد cube-full أيضًا. المطلوب هو حساب
$$S(N)=\sum_{n=1}^{N}s(n)$$
عندما يكون \(N=10^{18}\). وهذا نطاق ضخم جدًا، لذلك لا يمكن تحليل كل عدد حتى \(N\) عاملًا أوليًا واحدًا واحدًا، بل يجب إعادة تنظيم العد حول القواسم cube-full نفسها.
الفكرة الأساسية هي أن عدّ عدد مرات ظهور قاسم cube-full ثابت أسهل بكثير من فحص كل عدد \(n\) على حدة.
بالنسبة إلى \(n\) ثابت، يمكن كتابة
$$s(n)=\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
وعند جمع ذلك على جميع القيم \(1\le n\le N\) نحصل على
$$S(N)=\sum_{n=1}^{N}\sum_{\substack{d\mid n\\ d\ \text{cube-full}}}1.$$
وبعد تبديل ترتيب الجمع يصبح
$$S(N)=\sum_{\substack{d\le N\\ d\ \text{cube-full}}}\left\lfloor\frac{N}{d}\right\rfloor.$$
والسبب هو أن \(\lfloor N/d\rfloor\) يساوي تمامًا عدد مضاعفات \(d\) داخل المجموعة \(\{1,2,\dots,N\}\). وهكذا تختزل المسألة إلى تعداد كل الأعداد cube-full التي لا تتجاوز \(N\).
إذا كان
$$d=\prod_{i=1}^{k} p_i^{e_i},$$
فإن \(d\) يكون cube-full إذا وفقط إذا حقق كل أس ظاهر الشرط \(e_i\ge 3\). أي إن الأسين \(1\) و\(2\) غير مسموح بهما. لذلك فإن العدد cube-full يتحدد تمامًا بواسطة
العوامل الأولية المختلفة مرتبة تصاعديًا، ثم اختيار أس لكل عامل من المجموعة \(\{3,4,5,\dots\}\).
وهذه بالضبط هي البنية التي تستغلها العودية. أما العدد \(1\) فيمثل حالة عدم اختيار أي عامل أولي، ويعطي مساهمة مقدارها \(\lfloor N/1\rfloor=N\).
إذا ظهر أولي \(p\) في قاسم cube-full يحقق \(d\le N\)، فلا بد أن \(p^3\mid d\)، ومن ثم
$$p^3\le d\le N.$$
وعليه فإن كل أولي ذي صلة يجب أن يحقق
$$p\le \left\lfloor\sqrt[3]{N}\right\rfloor.$$
وهذا تقليص كبير جدًا لمساحة البحث. فعندما يكون \(N=10^{18}\) لا نحتاج إلا إلى الأوليات حتى \(10^6\)، ويمكن توليدها بسهولة بمنخل أولي بسيط.
نبدأ من حاصل الضرب الحالي \(d=1\). وفي كل مرحلة عودية لا يجوز اختيار الأولي التالي إلا من المواضع التي تأتي بعد الأوليات المستخدمة سابقًا. وإذا اخترنا أوليًا \(p\)، فأصغر مساهمة قانونية له هي \(p^3\)، ثم يمكن رفع الأس إلى \(4,5,6,\dots\) ما دام حاصل الضرب لا يتجاوز \(N\).
وهذا يعطي مسار بناء وحيدًا لكل عدد cube-full. فإذا كان
$$d=q_1^{a_1}q_2^{a_2}\cdots q_m^{a_m},\qquad q_1<q_2<\cdots<q_m,\qquad a_i\ge 3,$$
فلا يمكن للعودية أن تصل إلى \(d\) إلا باختيار \(q_1\) أولًا ثم \(q_2\) ثم \(q_3\) وهكذا. وبما أن المستويات الأعمق لا يسمح لها إلا بالأوليات الأكبر، فلا توجد طريقة ثانية لبناء العدد نفسه، وبالتالي لا يوجد عدّ مكرر.
لنفترض أن حاصل الضرب cube-full الحالي هو \(d\). وبالنسبة إلى أولي مرشح \(p\)، فإن أصغر عامل جديد ممكن هو \(p^3\). فإذا كان
$$d\,p^3>N,$$
فهذا الأولي لم يعد ممكنًا، وكذلك كل أولي أكبر منه لأن مكعبه سيكون أكبر أيضًا. لذلك يمكن إيقاف الحلقة فورًا عند هذه النقطة. هذه الرتابة هي السبب العملي في بقاء شجرة البحث صغيرة.
الأعداد cube-full التي لا تتجاوز \(100\) هي
$$1,\ 8,\ 16,\ 27,\ 32,\ 64,\ 81.$$
وعليه
$$S(100)=\left\lfloor\frac{100}{1}\right\rfloor+\left\lfloor\frac{100}{8}\right\rfloor+\left\lfloor\frac{100}{16}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{32}\right\rfloor+\left\lfloor\frac{100}{64}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor.$$
وبحساب القيم نحصل على
$$100+12+6+3+3+1+1=126.$$
وهذه القيمة تطابق نقطة التحقق الصغيرة الموجودة في التنفيذ.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. أولًا تحسب الجذر التكعيبي الصحيح \(L=\lfloor\sqrt[3]{N}\rfloor\) باستخدام بحث ثنائي آمن، ثم تولد جميع الأوليات حتى \(L\) بواسطة منخل.
بعد ذلك تمثل عودية بعمق أولي القاسم cube-full الحالي \(d\). وبمجرد بناء قيمة صالحة، يضيف التنفيذ \(\lfloor N/d\rfloor\) إلى المجموع الجاري، لأن هذا هو بالضبط عدد الأعداد التي لا تتجاوز \(N\) والمضاعفة لـ \(d\).
ومن كل حالة عودية يفحص التنفيذ الأوليات المتبقية بترتيب تصاعدي. فإذا اختير أولي ما، يبدأ من القوة الثالثة ثم يواصل الضرب في الأولي نفسه لتغطية الأسس \(3,4,5,\dots\). وبعد ذلك تنتقل النداء العودي إلى أوليات أكبر فقط، وهذا هو ما يضمن التفرد في التعداد.
الاختلاف بين اللغات الثلاث يقتصر على تفاصيل الأمان الحسابي. فنسخة C++ تستخدم أعدادًا صحيحة أوسع في بعض اختبارات المكعبات والضرب، ونسخة Java تعيد صياغة اختبار ضرب قد يفيض على هيئة مقارنة قسمة، أما Python فتعتمد على الأعداد الصحيحة ذات الدقة غير المحدودة. لكن طريقة العد نفسها واحدة في الحالات كلها.
وتحتوي نسخة C++ أيضًا على بضع اختبارات صغيرة للتأكد من الصحة، من بينها مقارنة brute force على حد صغير جدًا، قبل طباعة النتيجة النهائية عند \(N=10^{18}\).
لنكتب \(L=\lfloor\sqrt[3]{N}\rfloor\). إن بناء قائمة الأوليات حتى \(L\) يكلف \(O(L\log\log L)\) زمنًا و\(O(L)\) ذاكرة. وإذا رمزنا بـ \(C(N)\) إلى عدد الأعداد cube-full التي لا تتجاوز \(N\)، فإن الجزء العودي يزور كل قيمة منها مرة واحدة فقط، ولذلك يعتمد العمل الإضافي على حجم شجرة البحث المولدة فعليًا لا على \(N\) نفسه.
أما الذاكرة فتبقى محدودة: المنخل أو قائمة الأوليات حتى \(L\)، ومكدس العودية، وعدد قليل من المتغيرات الصحيحة. وعمق العودية لا يساوي إلا عدد الأوليات المختلفة في العدد cube-full الحالي، لذلك يبقى صغيرًا عمليًا.