For each integer \(n\le N\), let \(t(n)\) denote the number of distinct primes whose squares divide \(n\). In other words, \(t(n)\) counts how many different primes \(p\) satisfy \(p^2\mid n\).
We then define
$$C_k(N)=\left|\left\{n\in\mathbb{Z}_{>0}: n\le N,\ t(n)=k\right\}\right|.$$
The task for Problem 632 is to evaluate, at \(N=10^{16}\), the product of all nonzero values \(C_k(N)\) modulo \(10^9+7\). Since scanning all integers up to \(10^{16}\) is impossible, the solution counts them indirectly by grouping together the squarefree products of the primes whose squares divide each integer.
The key idea is to first count integers by how many chosen squared prime factors they contain, and only afterwards recover the exact buckets \(C_k(N)\).
If an integer \(n\) is divisible by the squares of the distinct primes \(p_1,\dots,p_r\), then the squarefree product
$$d=p_1p_2\cdots p_r$$
satisfies \(d^2\mid n\). Conversely, every squarefree \(d\) with \(d^2\mid n\) identifies a set of distinct squared prime divisors of \(n\). Let \(\omega(d)\) denote the number of distinct prime factors of \(d\), and let \(S_r(N)\) be the set of squarefree integers \(d\) such that \(d^2\le N\) and \(\omega(d)=r\).
For each \(r\ge 0\), define
$$A_r(N)=\sum_{d\in S_r(N)}\left\lfloor\frac{N}{d^2}\right\rfloor.$$
Each term counts the integers \(n\le N\) divisible by \(d^2\). Therefore \(A_r(N)\) is not yet the number of integers with exactly \(r\) squared prime factors. Instead, it is an overcount: an integer is counted once for every squarefree choice of \(r\) squared primes contained in it.
Suppose \(t(n)=t\). Then \(n\) has exactly \(t\) distinct primes whose squares divide it. To contribute to \(A_r(N)\), we may choose any \(r\) of those \(t\) primes, so this single integer contributes exactly
$$\binom{t}{r}$$
times to \(A_r(N)\). Summing over all integers with the same value of \(t\) yields the triangular identity
$$A_r(N)=\sum_{t\ge r}\binom{t}{r}C_t(N).$$
This is the central combinatorial statement used by the implementations.
The previous system is lower triangular with diagonal entries equal to \(1\), so it can be inverted explicitly:
$$C_k(N)=\sum_{r\ge k}(-1)^{r-k}\binom{r}{k}A_r(N).$$
Once the values \(A_r(N)\) are known, each exact bucket \(C_k(N)\) follows from a short alternating sum.
If \(t(n)\ge 9\), then \(n\) must be divisible by the square of the product of the first nine primes:
$$\left(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\right)^2>10^{16}.$$
That is impossible when \(n\le 10^{16}\). Therefore only \(k=0,1,\dots,8\) can occur for the target input. This explains why the implementations only need a very small fixed number of counting buckets.
This small case makes the counting mechanism transparent and matches the checkpoint values used by the implementation.
First, \(A_0(100)=100\), because the only squarefree \(d\) with \(\omega(d)=0\) is \(d=1\).
For \(r=1\), the possible values are \(d=2,3,5,7\), so
$$A_1(100)=\left\lfloor\frac{100}{4}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor\frac{100}{25}\right\rfloor+\left\lfloor\frac{100}{49}\right\rfloor=25+11+4+2=42.$$
For \(r=2\), the only squarefree products with square at most \(100\) are \(d=6\) and \(d=10\), hence
$$A_2(100)=\left\lfloor\frac{100}{36}\right\rfloor+\left\lfloor\frac{100}{100}\right\rfloor=2+1=3.$$
All higher \(A_r(100)\) vanish. Now invert the system:
$$C_2(100)=A_2(100)=3,$$
$$C_1(100)=A_1(100)-2A_2(100)=42-6=36,$$
$$C_0(100)=A_0(100)-A_1(100)+A_2(100)=100-42+3=61.$$
So among the integers up to \(100\), exactly \(61\) have no squared prime factor, \(36\) have exactly one squared prime factor, and \(3\) have exactly two. The total \(61+36+3=100\) is a useful consistency check.
The C++, Python, and Java implementations all begin by setting the limit to \(\lfloor\sqrt{N}\rfloor=10^8\), because every relevant squarefree \(d\) must satisfy \(d^2\le N\). They generate all primes up to that bound and then fill two compact arrays over \(1\le d\le 10^8\): one stores how many distinct prime divisors each \(d\) has, and the other records whether \(d\) is squarefree.
After that preprocessing phase, the implementation scans all \(d\le \sqrt{N}\). Whenever \(d\) is squarefree, it adds \(\left\lfloor N/d^2\right\rfloor\) to the bucket corresponding to \(\omega(d)\). Consecutive values of \(d\) that share the same quotient \(\left\lfloor N/d^2\right\rfloor\) are handled together, so the expensive division work is reused across whole blocks instead of repeated blindly for every bound adjustment.
Once the aggregated buckets \(A_r(N)\) are available, the implementation builds a tiny Pascal triangle of binomial coefficients and applies the inversion formula above to recover the exact values \(C_k(N)\). Finally, it multiplies all positive counts modulo \(10^9+7\). The C++ implementation also verifies several small checkpoints such as \(N=10,100,10^3,\dots,10^8\) and confirms that the recovered buckets sum back to \(N\).
Let \(L=\lfloor\sqrt{N}\rfloor\). The sieve phase and the marking of multiples and square-multiples take \(O(L\log\log L)\) time in the standard sieve model and \(O(L)\) memory. The accumulation pass over \(d\le L\) is \(O(L)\), and the binomial inversion is constant-time because only a fixed number of buckets can be nonzero. For the target input \(N=10^{16}\), this means working up to \(L=10^8\): large, but still feasible for a one-shot optimized computation.
Für jede Zahl \(n\le N\) bezeichne \(t(n)\) die Anzahl verschiedener Primzahlen, deren Quadrat \(n\) teilt. \(t(n)\) zählt also genau die Primzahlen \(p\) mit \(p^2\mid n\).
Dann definieren wir
$$C_k(N)=\left|\left\{n\in\mathbb{Z}_{>0}: n\le N,\ t(n)=k\right\}\right|.$$
Für \(N=10^{16}\) soll das Produkt aller positiven Werte \(C_k(N)\) modulo \(10^9+7\) berechnet werden. Ein direkter Durchlauf bis \(10^{16}\) ist ausgeschlossen, daher zählt die Lösung indirekt über quadratfreie Produkte der Primzahlen, deren Quadrate in einer Zahl vorkommen.
Die Implementierungen zählen zunächst nicht die exakten Klassen \(C_k(N)\), sondern eine Familie von Überzählungen, die sich leicht summieren lassen. Danach werden die exakten Werte per binomialer Inversion zurückgewonnen.
Ist \(n\) durch die Quadrate der verschiedenen Primzahlen \(p_1,\dots,p_r\) teilbar, dann gilt für das quadratfreie Produkt
$$d=p_1p_2\cdots p_r$$
die Beziehung \(d^2\mid n\). Umgekehrt beschreibt jedes quadratfreie \(d\) mit \(d^2\mid n\) eine bestimmte Auswahl verschiedener Primzahlen, deren Quadrate \(n\) teilen. Sei \(\omega(d)\) die Anzahl der verschiedenen Primfaktoren von \(d\), und sei \(S_r(N)\) die Menge aller quadratfreien Zahlen \(d\) mit \(d^2\le N\) und \(\omega(d)=r\).
Für jedes \(r\ge 0\) setzen wir
$$A_r(N)=\sum_{d\in S_r(N)}\left\lfloor\frac{N}{d^2}\right\rfloor.$$
Jeder Summand zählt die Zahlen \(n\le N\), die durch \(d^2\) teilbar sind. \(A_r(N)\) ist daher noch nicht die Anzahl der Zahlen mit genau \(r\) quadratischen Primfaktoren, sondern eine Überzählung: Jede Zahl wird einmal für jede quadratfreie Auswahl von \(r\) solchen Primzahlen mitgezählt.
Angenommen \(t(n)=t\). Dann besitzt \(n\) genau \(t\) verschiedene Primzahlen, deren Quadrate \(n\) teilen. Um zu \(A_r(N)\) beizutragen, können wir aus diesen \(t\) Primzahlen beliebige \(r\) auswählen. Daher trägt die einzelne Zahl \(n\) genau
$$\binom{t}{r}$$
Mal zu \(A_r(N)\) bei. Summiert man über alle Zahlen mit gleichem \(t\), erhält man
$$A_r(N)=\sum_{t\ge r}\binom{t}{r}C_t(N).$$
Diese Dreiecksbeziehung ist die zentrale kombinatorische Identität der Methode.
Das lineare System ist untere Dreiecksgestalt mit Einsen auf der Diagonalen und lässt sich deshalb explizit invertieren:
$$C_k(N)=\sum_{r\ge k}(-1)^{r-k}\binom{r}{k}A_r(N).$$
Sobald die aggregierten Werte \(A_r(N)\) bekannt sind, ergibt sich jeder exakte Zähler \(C_k(N)\) aus einer kurzen alternierenden Summe.
Wäre \(t(n)\ge 9\), dann müsste \(n\) durch das Quadrat des Produkts der ersten neun Primzahlen teilbar sein:
$$\left(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\right)^2>10^{16}.$$
Das ist für \(n\le 10^{16}\) unmöglich. Also können beim Zielwert nur \(k=0,1,\dots,8\) auftreten. Genau deshalb genügen in der Implementierung nur sehr wenige Zählbehälter.
Dieses kleine Beispiel macht die Zählidee sichtbar und stimmt mit den Kontrollwerten der Implementierung überein.
Zuerst gilt \(A_0(100)=100\), denn die einzige quadratfreie Zahl \(d\) mit \(\omega(d)=0\) ist \(d=1\).
Für \(r=1\) kommen nur \(d=2,3,5,7\) in Frage. Damit
$$A_1(100)=\left\lfloor\frac{100}{4}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor\frac{100}{25}\right\rfloor+\left\lfloor\frac{100}{49}\right\rfloor=25+11+4+2=42.$$
Für \(r=2\) sind die einzigen quadratfreien Produkte mit Quadrat höchstens \(100\) die Werte \(d=6\) und \(d=10\). Also
$$A_2(100)=\left\lfloor\frac{100}{36}\right\rfloor+\left\lfloor\frac{100}{100}\right\rfloor=2+1=3.$$
Alle höheren \(A_r(100)\) verschwinden. Nach der Inversion folgt
$$C_2(100)=A_2(100)=3,$$
$$C_1(100)=A_1(100)-2A_2(100)=42-6=36,$$
$$C_0(100)=A_0(100)-A_1(100)+A_2(100)=100-42+3=61.$$
Unter den Zahlen bis \(100\) gibt es also genau \(61\) ohne quadratischen Primfaktor, \(36\) mit genau einem solchen Primfaktor und \(3\) mit genau zwei. Die Summe \(61+36+3=100\) liefert zugleich eine saubere Plausibilitätskontrolle.
Die C++-, Python- und Java-Implementierungen setzen zuerst die Obergrenze \(\lfloor\sqrt{N}\rfloor=10^8\), denn jedes relevante quadratfreie \(d\) muss \(d^2\le N\) erfüllen. Anschließend erzeugen sie alle Primzahlen bis zu dieser Grenze und füllen damit zwei kompakte Arrays für \(1\le d\le 10^8\): eines speichert die Anzahl verschiedener Primteiler von \(d\), das andere markiert, ob \(d\) quadratfrei ist.
Nach dieser Vorverarbeitung wird über alle \(d\le \sqrt{N}\) iteriert. Ist \(d\) quadratfrei, dann wird \(\left\lfloor N/d^2\right\rfloor\) zu dem Behälter addiert, der durch \(\omega(d)\) bestimmt ist. Aufeinanderfolgende \(d\)-Werte mit gleichem Quotienten \(\left\lfloor N/d^2\right\rfloor\) werden blockweise behandelt, damit dieselbe teure Ganzzahldivision über ganze Bereiche wiederverwendet werden kann.
Sind diese aggregierten Behälter \(A_r(N)\) aufgebaut, erzeugt die Implementierung ein kleines Pascalsches Dreieck der Binomialkoeffizienten und wendet die Inversionsformel an, um die exakten Werte \(C_k(N)\) zu erhalten. Zum Schluss wird das Produkt aller positiven Klassen modulo \(10^9+7\) gebildet. Die C++-Implementierung prüft zusätzlich mehrere kleine Kontrollfälle wie \(N=10,100,10^3,\dots,10^8\) und bestätigt, dass die zurückgewonnenen Klassen wieder zu \(N\) aufsummieren.
Sei \(L=\lfloor\sqrt{N}\rfloor\). Das Sieb und das Markieren von Vielfachen sowie Quadrat-Vielfachen benötigen im üblichen Siebmodell \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher. Der anschließende Durchlauf über \(d\le L\) ist \(O(L)\), und die binomiale Inversion ist konstant groß, weil nur endlich viele Klassen ungleich null sein können. Für das Ziel \(N=10^{16}\) bedeutet das Arbeit bis \(L=10^8\): groß, aber für eine optimierte Einmalberechnung realistisch.
Her \(n\le N\) için \(t(n)\), karesi \(n\)'yi bölen farklı asal sayıların sayısı olsun. Yani \(t(n)\), \(p^2\mid n\) koşulunu sağlayan farklı asalların sayısını verir.
Buna göre
$$C_k(N)=\left|\left\{n\in\mathbb{Z}_{>0}: n\le N,\ t(n)=k\right\}\right|$$
tanımlanır. Problem 632'de \(N=10^{16}\) için tüm sıfır olmayan \(C_k(N)\) değerlerinin çarpımı \(10^9+7\) modunda istenir. \(10^{16}\)'ya kadar doğrudan tarama yapılamayacağı için çözüm, sayıları dolaylı biçimde; yani kareleri bölen asalların karefree çarpımları üzerinden sayar.
Ana fikir, önce her sayıyı “seçilmiş kare asal çarpan sayısı” açısından fazla saymak, sonra da bu fazla sayımı binom tersleme ile tam sınıflara dönüştürmektir.
Eğer \(n\), \(p_1,\dots,p_r\) farklı asallarının kareleriyle bölünüyorsa, o zaman
$$d=p_1p_2\cdots p_r$$
karefree sayısı için \(d^2\mid n\) olur. Tersine, \(d^2\mid n\) koşulunu sağlayan her karefree \(d\), \(n\)'yi bölen kare asal çarpanlardan bir altküme seçmiş olur. \(d\)'nin farklı asal çarpan sayısına \(\omega(d)\) diyelim. Ayrıca \(d^2\le N\) ve \(\omega(d)=r\) koşullarını sağlayan karefree \(d\)'lerin kümesine \(S_r(N)\) diyelim.
Her \(r\ge 0\) için
$$A_r(N)=\sum_{d\in S_r(N)}\left\lfloor\frac{N}{d^2}\right\rfloor$$
olsun. Buradaki her terim, \(d^2\) ile bölünebilen \(n\le N\) sayılarını sayar. Dolayısıyla \(A_r(N)\), tam olarak \(r\) tane kare asal çarpanı olan sayıları değil, her sayıyı içindeki uygun \(r\)-li seçim sayısı kadar tekrar sayan bir toplu büyüklüğü temsil eder.
Diyelim ki \(t(n)=t\). O halde \(n\)'yi bölen kare asal çarpan sayısı tam olarak \(t\)'dir. \(A_r(N)\)'ye katkı yapmak için bu \(t\) asal arasından herhangi \(r\) tanesi seçilebilir. Bu yüzden tek bir \(n\) sayısı \(A_r(N)\)'ye tam olarak
$$\binom{t}{r}$$
kez katkı verir. Aynı \(t\) değerine sahip tüm sayıları toplarsak
$$A_r(N)=\sum_{t\ge r}\binom{t}{r}C_t(N)$$
eşitliğini elde ederiz. Yöntemin kalbi bu üçgensel bağıntıdır.
Yukarıdaki sistem alt üçgenseldir ve köşegenindeki katsayılar \(1\)'dir. Bu yüzden açıkça terslenebilir:
$$C_k(N)=\sum_{r\ge k}(-1)^{r-k}\binom{r}{k}A_r(N).$$
Yani \(A_r(N)\) değerleri bilindiğinde, her tam sınıf \(C_k(N)\) kısa bir artı-eksi toplamıyla bulunur.
Eğer \(t(n)\ge 9\) olsaydı, \(n\)'nin ilk dokuz asalın çarpımının karesiyle bölünmesi gerekirdi:
$$\left(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\right)^2>10^{16}.$$
Bu ise \(n\le 10^{16}\) için imkansızdır. Dolayısıyla hedef girdide yalnızca \(k=0,1,\dots,8\) değerleri görülebilir. Uygulamadaki sabit boyutlu sayım dizileri de bu gözleme dayanır.
Bu küçük örnek hem sayım fikrini netleştirir hem de uygulamadaki kontrol değerleriyle birebir örtüşür.
Önce \(A_0(100)=100\) olur; çünkü \(\omega(d)=0\) olan tek karefree sayı \(d=1\)'dir.
\(r=1\) için mümkün değerler yalnızca \(d=2,3,5,7\) olduğundan
$$A_1(100)=\left\lfloor\frac{100}{4}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor\frac{100}{25}\right\rfloor+\left\lfloor\frac{100}{49}\right\rfloor=25+11+4+2=42.$$
\(r=2\) için karesi \(100\)'ü aşmayan tek karefree çarpımlar \(d=6\) ve \(d=10\)'dur. Bu nedenle
$$A_2(100)=\left\lfloor\frac{100}{36}\right\rfloor+\left\lfloor\frac{100}{100}\right\rfloor=2+1=3.$$
Daha büyük tüm \(A_r(100)\) değerleri sıfırdır. Tersleme uygulandığında
$$C_2(100)=A_2(100)=3,$$
$$C_1(100)=A_1(100)-2A_2(100)=42-6=36,$$
$$C_0(100)=A_0(100)-A_1(100)+A_2(100)=100-42+3=61$$
çıkar. Yani \(100\)'e kadar olan sayılar içinde \(61\) tanesinde hiç kare asal yoktur, \(36\) tanesinde tam bir tane vardır, \(3\) tanesinde ise tam iki tane vardır. Toplamın tekrar \(100\) etmesi de doğru bir iç kontrol sağlar.
C++, Python ve Java uygulamaları önce üst sınırı \(\lfloor\sqrt{N}\rfloor=10^8\) olarak belirler; çünkü ilgili her karefree \(d\) için \(d^2\le N\) olmalıdır. Sonra bu sınıra kadar tüm asallar üretilir ve \(1\le d\le 10^8\) aralığı için iki sıkı dizi doldurulur: biri her \(d\)'nin kaç farklı asal çarpanı olduğunu, diğeri de \(d\)'nin karefree olup olmadığını tutar.
Bu ön işlem tamamlandıktan sonra tüm \(d\le \sqrt{N}\) değerleri taranır. \(d\) karefree ise \(\left\lfloor N/d^2\right\rfloor\) değeri, \(\omega(d)\) ile belirlenen kovaya eklenir. Ayrıca \(\left\lfloor N/d^2\right\rfloor\) bölümü aynı kalan ardışık \(d\) değerleri bloklar halinde işlendiği için pahalı bölüm işlemleri geniş aralıklarda yeniden kullanılmış olur.
Toplu sayım kovaları \(A_r(N)\) elde edilince küçük bir Pascal üçgeni kurulur ve yukarıdaki tersleme formülü uygulanarak tam sayımlar \(C_k(N)\) hesaplanır. Son adımda tüm pozitif sınıflar \(10^9+7\) modunda çarpılır. C++ uygulaması ayrıca \(N=10,100,10^3,\dots,10^8\) gibi küçük kontrol noktalarını doğrular ve elde edilen kovaların toplamının tekrar \(N\) ettiğini de sınar.
\(L=\lfloor\sqrt{N}\rfloor\) olsun. Elek ve asal katları ile asal kare katlarını işaretleme aşaması, klasik elek modelinde \(O(L\log\log L)\) zaman ve \(O(L)\) bellek kullanır. Ardından \(d\le L\) üzerinden yapılan biriktirme geçişi \(O(L)\) maliyetlidir. Binom tersleme ise yalnızca sabit sayıda kova bulunduğu için sabit boyutlu bir işlemdir. Hedef girdi \(N=10^{16}\) için \(L=10^8\) elde edilir; bu da tek seferlik optimize bir hesap için büyük ama uygulanabilir bir ölçektir.
Para cada entero \(n\le N\), sea \(t(n)\) el número de primos distintos cuyo cuadrado divide a \(n\). Es decir, \(t(n)\) cuenta cuántos primos diferentes \(p\) satisfacen \(p^2\mid n\).
Definimos entonces
$$C_k(N)=\left|\left\{n\in\mathbb{Z}_{>0}: n\le N,\ t(n)=k\right\}\right|.$$
En el Problema 632, para \(N=10^{16}\), se pide el producto de todos los valores no nulos \(C_k(N)\) módulo \(10^9+7\). Como recorrer directamente todos los enteros hasta \(10^{16}\) es imposible, la solución cuenta de forma indirecta usando los productos libres de cuadrados formados por los primos cuyos cuadrados dividen a cada número.
La idea central es contar primero por “conjuntos elegidos” de primos cuadrados, lo que produce sobrecuentas manejables, y después recuperar los conteos exactos mediante inversión binomial.
Si \(n\) es divisible por los cuadrados de los primos distintos \(p_1,\dots,p_r\), entonces el producto libre de cuadrados
$$d=p_1p_2\cdots p_r$$
cumple \(d^2\mid n\). A la inversa, todo \(d\) libre de cuadrados con \(d^2\mid n\) representa una elección concreta de primos distintos cuyos cuadrados dividen a \(n\). Denotemos por \(\omega(d)\) el número de factores primos distintos de \(d\), y llamemos \(S_r(N)\) al conjunto de enteros libres de cuadrados \(d\) tales que \(d^2\le N\) y \(\omega(d)=r\).
Para cada \(r\ge 0\), definimos
$$A_r(N)=\sum_{d\in S_r(N)}\left\lfloor\frac{N}{d^2}\right\rfloor.$$
Cada término cuenta los enteros \(n\le N\) divisibles por \(d^2\). Por tanto, \(A_r(N)\) todavía no es el número de enteros con exactamente \(r\) primos cuadrados, sino una sobrecuenta: cada entero se cuenta una vez por cada elección libre de cuadrados de \(r\) primos cuadrados contenida en él.
Supongamos que \(t(n)=t\). Entonces \(n\) tiene exactamente \(t\) primos distintos cuyos cuadrados lo dividen. Para contribuir a \(A_r(N)\), podemos elegir cualesquiera \(r\) de esos \(t\) primos. En consecuencia, el entero \(n\) contribuye exactamente
$$\binom{t}{r}$$
veces a \(A_r(N)\). Sumando sobre todos los enteros con el mismo valor de \(t\), obtenemos
$$A_r(N)=\sum_{t\ge r}\binom{t}{r}C_t(N).$$
Esta es la identidad combinatoria fundamental de todo el método.
El sistema anterior es triangular inferior con unos en la diagonal, así que puede invertirse de forma explícita:
$$C_k(N)=\sum_{r\ge k}(-1)^{r-k}\binom{r}{k}A_r(N).$$
Una vez conocidos los valores agregados \(A_r(N)\), cada clase exacta \(C_k(N)\) se obtiene con una suma alternante corta.
Si \(t(n)\ge 9\), entonces \(n\) tendría que ser divisible por el cuadrado del producto de los primeros nueve primos:
$$\left(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\right)^2>10^{16}.$$
Eso es imposible para \(n\le 10^{16}\). Por ello, en la entrada objetivo solo pueden aparecer \(k=0,1,\dots,8\). Esta cota explica por qué basta con un número fijo y muy pequeño de cubetas.
Este caso pequeño hace visible la mecánica del conteo y coincide con los valores de comprobación usados por la implementación.
Primero, \(A_0(100)=100\), porque el único \(d\) libre de cuadrados con \(\omega(d)=0\) es \(d=1\).
Para \(r=1\), los únicos valores posibles son \(d=2,3,5,7\), así que
$$A_1(100)=\left\lfloor\frac{100}{4}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor\frac{100}{25}\right\rfloor+\left\lfloor\frac{100}{49}\right\rfloor=25+11+4+2=42.$$
Para \(r=2\), los únicos productos libres de cuadrados cuyo cuadrado no supera \(100\) son \(d=6\) y \(d=10\). Entonces
$$A_2(100)=\left\lfloor\frac{100}{36}\right\rfloor+\left\lfloor\frac{100}{100}\right\rfloor=2+1=3.$$
Todos los \(A_r(100)\) con \(r\ge 3\) son cero. Al invertir:
$$C_2(100)=A_2(100)=3,$$
$$C_1(100)=A_1(100)-2A_2(100)=42-6=36,$$
$$C_0(100)=A_0(100)-A_1(100)+A_2(100)=100-42+3=61.$$
Así, entre los enteros hasta \(100\), exactamente \(61\) no tienen ningún primo cuadrado, \(36\) tienen exactamente uno y \(3\) tienen exactamente dos. La suma \(61+36+3=100\) confirma que la partición es correcta.
Las implementaciones en C++, Python y Java empiezan fijando el límite \(\lfloor\sqrt{N}\rfloor=10^8\), porque todo \(d\) libre de cuadrados relevante debe cumplir \(d^2\le N\). Después generan todos los primos hasta ese límite y rellenan dos arreglos compactos en \(1\le d\le 10^8\): uno almacena cuántos divisores primos distintos tiene cada \(d\), y el otro indica si \(d\) es libre de cuadrados.
Tras esa fase de preprocesamiento, la implementación recorre todos los \(d\le \sqrt{N}\). Cuando \(d\) es libre de cuadrados, añade \(\left\lfloor N/d^2\right\rfloor\) a la cubeta indicada por \(\omega(d)\). Además, los valores consecutivos de \(d\) que comparten el mismo cociente \(\left\lfloor N/d^2\right\rfloor\) se procesan en bloque, de modo que el trabajo costoso de divisiones enteras se reutiliza sobre intervalos completos.
Una vez obtenidas las cubetas agregadas \(A_r(N)\), la implementación construye un pequeño triángulo de Pascal y aplica la fórmula de inversión para recuperar los conteos exactos \(C_k(N)\). El paso final es multiplicar todas las clases positivas módulo \(10^9+7\). La versión en C++ también verifica varios casos pequeños, como \(N=10,100,10^3,\dots,10^8\), y comprueba que la suma de las clases recuperadas vuelve a ser exactamente \(N\).
Sea \(L=\lfloor\sqrt{N}\rfloor\). La criba y el marcado de múltiplos y múltiplos cuadrados cuestan \(O(L\log\log L)\) tiempo en el modelo habitual de cribas y \(O(L)\) memoria. El recorrido de acumulación sobre \(d\le L\) es \(O(L)\), y la inversión binomial tiene coste constante porque solo puede haber un número fijo de cubetas no nulas. Para la entrada objetivo \(N=10^{16}\), esto significa trabajar hasta \(L=10^8\): un tamaño grande, pero razonable para un cálculo optimizado de una sola ejecución.
对每个 \(n\le N\)，定义 \(t(n)\) 为满足 \(p^2\mid n\) 的不同素数 \(p\) 的个数。也就是说，\(t(n)\) 统计的是“有多少个不同的素数，其平方整除 \(n\)”。
接着定义
$$C_k(N)=\left|\left\{n\in\mathbb{Z}_{>0}: n\le N,\ t(n)=k\right\}\right|.$$
Problem 632 要求在 \(N=10^{16}\) 时，计算所有非零 \(C_k(N)\) 的乘积，并对 \(10^9+7\) 取模。显然，不可能直接枚举到 \(10^{16}\)。真正可行的做法，是把“某些素数的平方是否整除 \(n\)”重新编码成平方自由数的平方整除条件，再通过组合反演恢复精确计数。
核心思路分成两层。第一层先做一个容易求和的“聚合计数”；第二层再把这个聚合计数反演回精确的 \(C_k(N)\)。这正是三个实现共享的数学框架。
如果某个整数 \(n\) 被不同素数 \(p_1,\dots,p_r\) 的平方同时整除，那么它一定满足
$$d^2\mid n,\qquad d=p_1p_2\cdots p_r.$$
这里的 \(d\) 一定是平方自由数，因为每个素数只出现一次。反过来，只要一个平方自由数 \(d\) 满足 \(d^2\mid n\)，就等价于说 \(n\) 至少含有 \(d\) 的所有素因子的平方。记 \(\omega(d)\) 为 \(d\) 的不同素因子个数，并记 \(S_r(N)\) 为所有满足 \(d^2\le N\)、\(d\) 平方自由且 \(\omega(d)=r\) 的整数 \(d\) 的集合。
对每个 \(r\ge 0\)，定义
$$A_r(N)=\sum_{d\in S_r(N)}\left\lfloor\frac{N}{d^2}\right\rfloor.$$
原因很直接：对固定的平方自由数 \(d\)，满足 \(d^2\mid n\) 且 \(n\le N\) 的整数个数正好是 \(\left\lfloor N/d^2\right\rfloor\)。所以 \(A_r(N)\) 把所有“含有某个 \(r\) 元平方素因子集合”的整数都累加起来了。
但要注意，\(A_r(N)\) 不是“恰好有 \(r\) 个平方素因子”的计数。它会重复计数。一个整数如果有很多个平方素因子，那么它会因为不同的选择方式被多次计入同一个 \(A_r(N)\)。
设某个整数 \(n\) 满足 \(t(n)=t\)。这表示恰好有 \(t\) 个不同素数的平方整除 \(n\)。若要把它计入 \(A_r(N)\)，只需从这 \(t\) 个素数中选出任意 \(r\) 个。这样的选择数正是
$$\binom{t}{r}.$$
因此，每个满足 \(t(n)=t\) 的整数会对 \(A_r(N)\) 贡献 \(\binom{t}{r}\) 次。把所有同类整数合并起来，就得到
$$A_r(N)=\sum_{t\ge r}\binom{t}{r}C_t(N).$$
这条公式非常关键，因为它把“容易算的聚合量” \(A_r(N)\) 和“真正想要的精确量” \(C_t(N)\) 联系了起来。
上面的关系是一个下三角线性系统，而且对角线系数全是 \(1\)，因此可以直接反演：
$$C_k(N)=\sum_{r\ge k}(-1)^{r-k}\binom{r}{k}A_r(N).$$
也就是说，只要先把所有 \(A_r(N)\) 求出来，后面恢复 \(C_k(N)\) 就只是一个很短的交错求和过程。这正是实现中最后一步所做的事情。
在 \(N=10^{16}\) 的目标规模下，不可能出现无限多种 \(k\)。如果 \(t(n)\ge 9\)，那么 \(n\) 至少要被前九个素数的平方乘积整除，也就是必须满足
$$\left(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\right)^2\le n.$$
但左边实际上已经大于 \(10^{16}\)，因此对所有 \(n\le 10^{16}\) 都不可能发生。于是只有 \(k=0,1,\dots,8\) 这些桶可能非零。这也是实现里只维护很小固定数组的数学理由。
这个小例子既容易手算，也和实现中的检查值完全一致。
首先，\(A_0(100)=100\)。因为 \(\omega(d)=0\) 的平方自由数只有 \(d=1\)，而所有 \(1\le n\le 100\) 都满足 \(1^2\mid n\)。
接着看 \(r=1\)。满足 \(d^2\le 100\) 的平方自由单素数乘积只有 \(d=2,3,5,7\)，所以
$$A_1(100)=\left\lfloor\frac{100}{4}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor\frac{100}{25}\right\rfloor+\left\lfloor\frac{100}{49}\right\rfloor=25+11+4+2=42.$$
再看 \(r=2\)。平方不超过 \(100\) 的平方自由双素数乘积只有 \(d=6\) 和 \(d=10\)，因此
$$A_2(100)=\left\lfloor\frac{100}{36}\right\rfloor+\left\lfloor\frac{100}{100}\right\rfloor=2+1=3.$$
更大的 \(r\) 都不可能，所以 \(A_r(100)=0\)（\(r\ge 3\)）。现在开始反演：
$$C_2(100)=A_2(100)=3,$$
$$C_1(100)=A_1(100)-2A_2(100)=42-6=36,$$
$$C_0(100)=A_0(100)-A_1(100)+A_2(100)=100-42+3=61.$$
所以在 \(1\) 到 \(100\) 之间，恰好有 \(61\) 个数没有任何平方素因子，\(36\) 个数恰好有一个，\(3\) 个数恰好有两个。总和 \(61+36+3=100\)，说明分类完全正确。
C++、Python 和 Java 实现的流程是一致的。首先把上界设为 \(\lfloor\sqrt{N}\rfloor=10^8\)，因为所有有用的平方自由数 \(d\) 都必须满足 \(d^2\le N\)。接下来，程序筛出这个范围内的全部素数，并据此构造两个紧凑数组：一个记录每个 \(d\) 有多少个不同素因子，另一个记录 \(d\) 是否为平方自由数。
完成预处理后，程序遍历全部 \(1\le d\le \sqrt{N}\)。如果 \(d\) 是平方自由数，就把 \(\left\lfloor N/d^2\right\rfloor\) 加到编号为 \(\omega(d)\) 的聚合桶里，也就是把它计入对应的 \(A_r(N)\)。此外，实现还把具有相同 \(\left\lfloor N/d^2\right\rfloor\) 的连续 \(d\) 合并成区间处理，从而复用整数除法结果，减少重复的边界计算。
所有聚合桶得到之后，程序再构造一个很小的 Pascal 三角形，读取需要的二项式系数，并按上面的反演公式恢复精确计数 \(C_k(N)\)。最后一步就是把所有正的 \(C_k(N)\) 在模 \(10^9+7\) 下相乘。C++ 实现还额外核对了一系列小规模样例，例如 \(N=10,100,10^3,\dots,10^8\)，并验证最终各桶之和重新等于 \(N\)。
记 \(L=\lfloor\sqrt{N}\rfloor\)。筛法以及对素数倍数、素数平方倍数的标记，在通常的筛法模型下需要 \(O(L\log\log L)\) 时间和 \(O(L)\) 空间。随后对全部 \(d\le L\) 的累加扫描是 \(O(L)\)。二项反演只作用于一个固定大小的桶数组，因此额外代价是常数级。对目标输入 \(N=10^{16}\) 而言，这意味着主要工作规模是 \(L=10^8\)：虽然不小，但对一次性的优化计算仍然是可承受的。
Для каждого \(n\le N\) обозначим через \(t(n)\) количество различных простых чисел, квадраты которых делят \(n\). Иными словами, \(t(n)\) считает, сколько различных простых \(p\) удовлетворяют условию \(p^2\mid n\).
Далее вводится величина
$$C_k(N)=\left|\left\{n\in\mathbb{Z}_{>0}: n\le N,\ t(n)=k\right\}\right|.$$
В задаче требуется для \(N=10^{16}\) найти произведение всех ненулевых значений \(C_k(N)\) по модулю \(10^9+7\). Перебор всех чисел до \(10^{16}\) невозможен, поэтому решение идет обходным путем: оно кодирует наборы квадратов простых через квадратсвободные числа и затем восстанавливает точные количества при помощи комбинаторной инверсии.
Главная идея состоит в том, чтобы сначала посчитать удобные агрегированные величины с повторным учетом, а уже потом перейти от них к точным классам \(C_k(N)\).
Если число \(n\) делится на квадраты различных простых \(p_1,\dots,p_r\), то квадратсвободное произведение
$$d=p_1p_2\cdots p_r$$
удовлетворяет условию \(d^2\mid n\). Обратное тоже верно: любое квадратсвободное \(d\) с \(d^2\mid n\) задает некоторый набор различных простых, квадраты которых делят \(n\). Пусть \(\omega(d)\) обозначает число различных простых делителей \(d\), а \(S_r(N)\) — множество всех квадратсвободных чисел \(d\), для которых \(d^2\le N\) и \(\omega(d)=r\).
Для каждого \(r\ge 0\) определим
$$A_r(N)=\sum_{d\in S_r(N)}\left\lfloor\frac{N}{d^2}\right\rfloor.$$
Каждое слагаемое равно количеству чисел \(n\le N\), кратных \(d^2\). Поэтому \(A_r(N)\) еще не является числом целых с ровно \(r\) квадратными простыми делителями. Это агрегированный счетчик с повторениями: одно и то же число учитывается столько раз, сколько разных квадратсвободных выборов из \(r\) подходящих простых оно содержит.
Пусть \(t(n)=t\). Тогда у числа \(n\) ровно \(t\) различных простых, квадраты которых его делят. Чтобы попасть в \(A_r(N)\), нужно выбрать любые \(r\) из этих \(t\) простых. Число таких выборов равно
$$\binom{t}{r}.$$
Значит, каждое число с \(t(n)=t\) вносит в \(A_r(N)\) вклад \(\binom{t}{r}\). Суммируя по всем классам, получаем
$$A_r(N)=\sum_{t\ge r}\binom{t}{r}C_t(N).$$
Это основная комбинаторная формула, на которой строится весь метод.
Полученная система имеет нижнетреугольный вид и единицы на диагонали, поэтому ее можно явно обратить:
$$C_k(N)=\sum_{r\ge k}(-1)^{r-k}\binom{r}{k}A_r(N).$$
Таким образом, после вычисления агрегированных величин \(A_r(N)\) точные счетчики \(C_k(N)\) находятся короткими знакопеременными суммами.
Если бы \(t(n)\ge 9\), то число \(n\) было бы обязано делиться на квадрат произведения первых девяти простых:
$$\left(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\right)^2>10^{16}.$$
Но это невозможно при \(n\le 10^{16}\). Значит, в целевой задаче ненулевыми могут быть только классы \(k=0,1,\dots,8\). Этим объясняется использование очень маленького фиксированного числа корзин в реализации.
Этот малый пример прозрачно показывает механику счета и совпадает с контрольными значениями из реализации.
Во-первых, \(A_0(100)=100\), потому что единственное квадратсвободное число \(d\) с \(\omega(d)=0\) — это \(d=1\).
Для \(r=1\) возможны только \(d=2,3,5,7\). Поэтому
$$A_1(100)=\left\lfloor\frac{100}{4}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor\frac{100}{25}\right\rfloor+\left\lfloor\frac{100}{49}\right\rfloor=25+11+4+2=42.$$
Для \(r=2\) квадрат числа \(d\) не должен превосходить \(100\), и тогда подходят только \(d=6\) и \(d=10\). Следовательно,
$$A_2(100)=\left\lfloor\frac{100}{36}\right\rfloor+\left\lfloor\frac{100}{100}\right\rfloor=2+1=3.$$
Все \(A_r(100)\) при \(r\ge 3\) равны нулю. После инверсии получаем
$$C_2(100)=A_2(100)=3,$$
$$C_1(100)=A_1(100)-2A_2(100)=42-6=36,$$
$$C_0(100)=A_0(100)-A_1(100)+A_2(100)=100-42+3=61.$$
Итак, среди чисел от \(1\) до \(100\) ровно \(61\) не имеют квадратных простых делителей, \(36\) имеют ровно один такой делитель и \(3\) имеют ровно два. Сумма \(61+36+3=100\) служит дополнительной проверкой корректности.
Реализации на C++, Python и Java устроены одинаково. Сначала они берут предел \(\lfloor\sqrt{N}\rfloor=10^8\), поскольку любое полезное квадратсвободное \(d\) должно удовлетворять \(d^2\le N\). Затем строится список простых до этого предела и заполняются два компактных массива на диапазоне \(1\le d\le 10^8\): первый хранит число различных простых делителей каждого \(d\), второй отмечает, является ли \(d\) квадратсвободным.
После такой подготовки программа проходит по всем \(d\le \sqrt{N}\). Если \(d\) квадратсвободно, то величина \(\left\lfloor N/d^2\right\rfloor\) прибавляется к корзине, соответствующей значению \(\omega(d)\). Кроме того, соседние значения \(d\), для которых частное \(\left\lfloor N/d^2\right\rfloor\) одинаково, обрабатываются блоками, так что дорогие целочисленные деления переиспользуются на целых промежутках.
Когда агрегированные корзины \(A_r(N)\) накоплены, реализация строит маленький треугольник Паскаля, берет нужные биномиальные коэффициенты и применяет формулу инверсии для получения точных значений \(C_k(N)\). Затем все положительные корзины перемножаются по модулю \(10^9+7\). В реализации на C++ дополнительно проверяются несколько малых случаев \(N=10,100,10^3,\dots,10^8\), а также подтверждается, что сумма всех восстановленных корзин снова равна \(N\).
Пусть \(L=\lfloor\sqrt{N}\rfloor\). Построение решета и отметка кратных простым и квадратам простых требуют \(O(L\log\log L)\) времени в стандартной модели решета и \(O(L)\) памяти. Проход накопления по всем \(d\le L\) занимает \(O(L)\), а биномиальная инверсия имеет постоянный размер, поскольку ненулевых корзин может быть только конечное малое число. Для целевого случая \(N=10^{16}\) это означает работу до \(L=10^8\): масштаб большой, но приемлемый для оптимизированного однократного вычисления.
لكل عدد صحيح \(n\le N\)، نرمز بـ \(t(n)\) إلى عدد الأعداد الأولية المختلفة التي يقسم مربعها العدد \(n\). أي إن \(t(n)\) يحسب عدد الأوليات المختلفة \(p\) التي تحقق \(p^2\mid n\).
ثم نعرّف
$$C_k(N)=\left|\left\{n\in\mathbb{Z}_{>0}: n\le N,\ t(n)=k\right\}\right|.$$
في هذه المسألة نريد، عند \(N=10^{16}\)، حساب حاصل ضرب جميع القيم غير الصفرية \(C_k(N)\) بترديد \(10^9+7\). وبما أن استعراض جميع الأعداد حتى \(10^{16}\) غير ممكن عمليًا، فالحل يعتمد على إعادة ترميز العوامل الأولية التي تقسم مربعاتها العدد، ثم العد بطريقة غير مباشرة باستخدام الأعداد الخالية من المربعات.
الفكرة الأساسية هي أن نحسب أولًا كميات مجمعة يسهل التعامل معها، حتى لو كانت تعدّ بعض الأعداد أكثر من مرة، ثم نسترجع منها القيم الدقيقة \(C_k(N)\) بواسطة الانعكاس الثنائي.
إذا كان \(n\) قابلًا للقسمة على مربعات الأوليات المختلفة \(p_1,\dots,p_r\)، فإن حاصل الضرب الخالي من المربعات
$$d=p_1p_2\cdots p_r$$
يحقق الشرط \(d^2\mid n\). وبالعكس، كل عدد خال من المربعات \(d\) يحقق \(d^2\mid n\) يحدد مجموعة من الأوليات المختلفة التي تقسم مربعاتها العدد \(n\). لنكتب \(\omega(d)\) لعدد العوامل الأولية المختلفة للعدد \(d\)، ولنرمز بـ \(S_r(N)\) إلى مجموعة الأعداد الخالية من المربعات \(d\) التي تحقق \(d^2\le N\) و \(\omega(d)=r\).
لكل \(r\ge 0\) نعرّف
$$A_r(N)=\sum_{d\in S_r(N)}\left\lfloor\frac{N}{d^2}\right\rfloor.$$
كل حد في هذا المجموع يعدّ الأعداد \(n\le N\) التي تقبل القسمة على \(d^2\). لذلك فالقيمة \(A_r(N)\) لا تمثل بعدُ عدد الأعداد التي تملك بالضبط \(r\) عوامل أولية مربعة، بل تمثل عدًا مجمعًا فيه تكرار: فالعدد الواحد قد يُحسب أكثر من مرة بحسب عدد الطرق التي يمكن بها اختيار \(r\) من أولياته المربعة.
افترض أن \(t(n)=t\). هذا يعني أن هناك بالضبط \(t\) أوليات مختلفة تقسم مربعاتها العدد \(n\). ولكي يُحتسب هذا العدد ضمن \(A_r(N)\)، نختار أي \(r\) أوليات من هذه الأوليات \(t\). عدد هذه الاختيارات يساوي
$$\binom{t}{r}.$$
إذن يساهم كل عدد يحقق \(t(n)=t\) في \(A_r(N)\) بعدد \(\binom{t}{r}\) من المرات. وبجمع المساهمات على جميع القيم الممكنة لـ \(t\) نحصل على العلاقة
$$A_r(N)=\sum_{t\ge r}\binom{t}{r}C_t(N).$$
وهذه هي الهوية التوافقية الأساسية التي يعتمد عليها الحل كله.
النظام السابق مثلثي سفلي، وعناصر قطره تساوي \(1\)، ولذلك يمكن قلبه صراحةً:
$$C_k(N)=\sum_{r\ge k}(-1)^{r-k}\binom{r}{k}A_r(N).$$
بمجرد معرفة القيم المجمعة \(A_r(N)\)، تصبح كل فئة دقيقة \(C_k(N)\) مجرد مجموع متناوب قصير.
لو كان \(t(n)\ge 9\)، لكان \(n\) مضاعفًا لمربع حاصل ضرب أول تسعة أعداد أولية:
$$\left(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\right)^2>10^{16}.$$
وهذا مستحيل عندما يكون \(n\le 10^{16}\). لذا لا يمكن أن تظهر في الإدخال الهدف إلا القيم \(k=0,1,\dots,8\). وهذا يبرر رياضيًا لماذا تحتفظ التطبيقات بعدد صغير وثابت من الحاويات فقط.
هذا المثال الصغير يوضح الآلية كاملة، كما أنه يطابق قيم التحقق الموجودة في التنفيذ.
أولًا، \(A_0(100)=100\)، لأن العدد الخالي من المربعات الوحيد الذي يحقق \(\omega(d)=0\) هو \(d=1\).
بالنسبة إلى \(r=1\)، القيم الممكنة الوحيدة هي \(d=2,3,5,7\)، ومن ثم
$$A_1(100)=\left\lfloor\frac{100}{4}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor\frac{100}{25}\right\rfloor+\left\lfloor\frac{100}{49}\right\rfloor=25+11+4+2=42.$$
أما عندما \(r=2\)، فإن حاصلَي الضرب الخاليين من المربعات اللذين لا يتجاوز مربعهما \(100\) هما \(d=6\) و\(d=10\)، ولذلك
$$A_2(100)=\left\lfloor\frac{100}{36}\right\rfloor+\left\lfloor\frac{100}{100}\right\rfloor=2+1=3.$$
وتختفي جميع القيم \(A_r(100)\) عندما \(r\ge 3\). الآن نطبّق الانعكاس:
$$C_2(100)=A_2(100)=3,$$
$$C_1(100)=A_1(100)-2A_2(100)=42-6=36,$$
$$C_0(100)=A_0(100)-A_1(100)+A_2(100)=100-42+3=61.$$
إذن بين الأعداد من \(1\) إلى \(100\)، هناك \(61\) عددًا بلا أي عامل أولي مربع، و\(36\) عددًا لها عامل أولي مربع واحد بالضبط، و\(3\) أعداد لها عاملان من هذا النوع. كما أن \(61+36+3=100\)، وهذا فحص اتساق مهم.
تتبع تطبيقات C++ وPython وJava المسار نفسه. فهي تبدأ بتحديد الحد \(\lfloor\sqrt{N}\rfloor=10^8\)، لأن كل عدد خال من المربعات \(d\) نحتاج إليه يجب أن يحقق \(d^2\le N\). بعد ذلك تُولَّد جميع الأعداد الأولية حتى هذا الحد، ثم تُملأ مصفوفتان مضغوطتان على المجال \(1\le d\le 10^8\): إحداهما تخزن عدد العوامل الأولية المختلفة لكل \(d\)، والأخرى تحدد هل \(d\) خالٍ من المربعات أم لا.
بعد مرحلة التمهيد هذه، تمر الشيفرة على جميع القيم \(d\le \sqrt{N}\). فإذا كان \(d\) خاليًا من المربعات، أضافت القيمة \(\left\lfloor N/d^2\right\rfloor\) إلى الحاوية التي يحددها \(\omega(d)\). كما أن القيم المتتالية لـ \(d\) التي تعطي نفس خارج القسمة \(\left\lfloor N/d^2\right\rfloor\) تُعالج على شكل كتل، بحيث يعاد استخدام حسابات القسمة الصحيحة على مقاطع كاملة بدل تكرارها بلا داع.
وبعد تكوين الحاويات المجمعة \(A_r(N)\)، تبني الشيفرة مثلث باسكال صغيرًا للحصول على معاملات ثنائية الحد اللازمة، ثم تطبق صيغة الانعكاس لاسترجاع القيم الدقيقة \(C_k(N)\). وأخيرًا يُحسب حاصل ضرب جميع الحاويات الموجبة بترديد \(10^9+7\). تنفيذ C++ يضيف أيضًا مجموعة من اختبارات التحقق الصغيرة مثل \(N=10,100,10^3,\dots,10^8\)، ويتأكد كذلك من أن مجموع الحاويات المسترجعة يساوي \(N\) من جديد.
لنضع \(L=\lfloor\sqrt{N}\rfloor\). مرحلة المنخل ووضع العلامات على مضاعفات الأوليات وعلى مضاعفات مربعاتها تحتاج إلى زمن \(O(L\log\log L)\) في نموذج المناخل المعتاد، وإلى ذاكرة \(O(L)\). أما المرور التجميعي على جميع \(d\le L\) فهو \(O(L)\)، في حين أن الانعكاس الثنائي كلفته ثابتة لأن عدد الحاويات غير الصفرية محدود مسبقًا. وعند \(N=10^{16}\) نحصل على \(L=10^8\)، وهو حجم كبير لكنه يظل عمليًا لحساب وحيد محسّن بعناية.