Write the factorial as
$$n!=\prod_{p\le n}p^{a_p},\qquad a_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
The quantity to compute is the signed divisor sum
$$S(n;L,H)=\sum_{\substack{d\mid n!\\L\le d\le H}}\lambda(d)\,d,\qquad \lambda(d)=(-1)^{\Omega(d)},$$
reduced modulo \(10^9+7\). The interval \([L,H]\) is enormous in the target case, so the solution cannot enumerate divisors naively; it must exploit the multiplicative structure of \(n!\) and the fact that only divisors up to \(H\) can matter.
The main idea is to represent each divisor by its prime exponents, split those primes into two independent groups, and turn the interval condition into two prefix queries.
For every prime \(p\le n\), Legendre's formula gives the exponent \(a_p\) of \(p\) in \(n!\). Therefore every divisor of \(n!\) has a unique form
$$d=\prod_{p\le n}p^{e_p},\qquad 0\le e_p\le a_p.$$
So the problem is equivalent to iterating over all allowable exponent vectors \((e_p)\), but doing so intelligently enough that the upper bound \(H\) removes most impossible branches before they are fully built.
If \(d=\prod p^{e_p}\), then
$$\lambda(d)\,d=(-1)^{\Omega(d)}\prod p^{e_p}=\prod (-p)^{e_p}.$$
Without the interval restriction, the total signed sum over all divisors would factor as
$$\sum_{d\mid n!}\lambda(d)\,d=\prod_{p\le n}\left(\sum_{e=0}^{a_p}(-p)^e\right).$$
The interval \(L\le d\le H\) destroys that simple product formula, because different primes now interact through the size of the full divisor. That is exactly why the implementation switches to a meet-in-the-middle strategy.
Partition the prime powers of \(n!\) into two disjoint groups. For the first group define partial states
$$u=\prod_{p\in A}p^{e_p},\qquad \alpha=\prod_{p\in A}(-p)^{e_p},$$
and for the second group define
$$v=\prod_{p\in B}p^{e_p},\qquad \beta=\prod_{p\in B}(-p)^{e_p}.$$
Because the groups use disjoint primes, every divisor corresponds to exactly one pair of partial states, with
$$d=u\,v,\qquad \lambda(d)\,d=\alpha\beta.$$
This reduces one very large search over all prime exponents to a merge of two precomputed lists.
During recursion, if the current partial product already exceeds \(H\), or if multiplying by one more copy of the current prime would exceed \(H\), then no continuation can ever contribute to a divisor in \([L,H]\) or to a prefix sum up to \(H\). Every extra prime power only makes the divisor larger.
So each side generates only feasible pairs \((u,\alpha)\) or \((v,\beta)\) with numeric value at most \(H\). The sign is carried through the factor \(-p\), while the divisor magnitude itself is stored exactly for later ordering and comparison.
Define the bounded prefix function
$$P(X)=\sum_{\substack{d\mid n!\\d\le X}}\lambda(d)\,d.$$
After splitting, this becomes
$$P(X)=\sum_{(u,\alpha)}\alpha\left(\sum_{\substack{(v,\beta)\\v\le X/u}}\beta\right).$$
If the second list is sorted by \(v\) and its signed weights are accumulated into prefix sums, then the inner quantity is available immediately once we know how far the threshold \(X/u\) reaches. Sorting the first list as well allows a monotone sweep: as \(u\) grows, the allowed bound \(X/u\) shrinks, so one pointer moves only in one direction.
The target interval sum is just the difference of two prefixes:
$$S(n;L,H)=P(H)-P(L-1)\pmod{10^9+7}.$$
That identity is the final reduction. The algorithm therefore computes two threshold queries, one at \(H\) and one at \(L-1\), and subtracts them modulo \(10^9+7\).
Here
$$5!=2^3\cdot 3\cdot 5.$$
Split the prime factors into \(A=\{2^3,3\}\) and \(B=\{5\}\). The first side produces the sorted partial states
$$\{(1,1),(2,-2),(3,-3),(4,4),(6,6),(8,-8),(12,-12),(24,24)\}.$$
The second side produces
$$\{(1,1),(5,-5)\},$$
whose prefix sums of weights are \(1\) and \(-4\).
For \(P(30)\), the bound \(30/u\) is at least \(5\) when \(u=1,2,3,4,6\), so the inner sum is \(-4\). For \(u=8,12,24\), only the state \(v=1\) is allowed, so the inner sum is \(1\). Thus
$$P(30)=-4+8+12-16-24-8-12+24=-20.$$
For \(P(5)\), only \(u=1,2,3,4\) contribute, giving
$$P(5)=-4-2-3+4=-5.$$
Therefore
$$S(5;6,30)=P(30)-P(5)=-15\equiv 10^9+7-15 \pmod{10^9+7}.$$
This small example is exactly the same merge logic used in the full computation.
The C++, Python, and Java implementations first generate all primes up to \(n\) and compute their exponents in \(n!\) by repeated division. They then split the resulting prime-factor list after the first five primes, which keeps both recursive enumerations manageable for the target instance.
Each side recursively enumerates every partial divisor whose exact value does not exceed \(H\). Alongside the exact divisor value, the implementation carries the signed multiplicative weight modulo \(10^9+7\). The divisor values themselves use exact wide integers: 256-bit arithmetic in C++ and arbitrary-precision integers in Python and Java, so comparisons against \(10^{60}\) remain exact.
After sorting both partial-state lists by divisor value, the implementation builds prefix sums of the signed weights on the second list. A linear sweep over the first list then evaluates \(P(H)\) and \(P(L-1)\). If \(L\le 1\), the lower prefix is zero; otherwise the algorithm evaluates the second threshold normally and subtracts the two results modulo \(10^9+7\).
Generating primes up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory. Computing the exponents \(a_p\) by repeated division contributes \(O(\pi(n)\log n)\), which is small here. If the two recursive enumerations produce \(A\) and \(B\) feasible partial states after pruning, then enumeration costs \(O(A+B)\), sorting costs \(O(A\log A+B\log B)\), and each threshold sweep costs \(O(A+B)\) because the pointer over the second list moves monotonically. The memory usage is \(O(A+B)\).
Schreibe die Fakultät als
$$n!=\prod_{p\le n}p^{a_p},\qquad a_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
Gesucht ist die vorzeichenbehaftete Teilersumme
$$S(n;L,H)=\sum_{\substack{d\mid n!\\L\le d\le H}}\lambda(d)\,d,\qquad \lambda(d)=(-1)^{\Omega(d)},$$
modulo \(10^9+7\). Im Zielbeispiel ist das Intervall \([L,H]\) riesig, daher ist direkte Teilerenumeration unbrauchbar. Man muss die multiplikative Struktur von \(n!\) und die Schranke \(H\) systematisch ausnutzen.
Die zentrale Idee ist, jeden Teiler über seine Primexponenten darzustellen, die Primzahlen in zwei unabhängige Gruppen zu zerlegen und die Intervallbedingung auf zwei Präfixabfragen zurückzuführen.
Für jedes \(p\le n\) liefert die Legendre-Formel den Exponenten \(a_p\) von \(p\) in \(n!\). Jeder Teiler von \(n!\) hat also eindeutig die Form
$$d=\prod_{p\le n}p^{e_p},\qquad 0\le e_p\le a_p.$$
Das Problem ist damit ein Durchlauf über alle zulässigen Exponentenvektoren \((e_p)\), allerdings mit früher Abschneidung aller Zweige, die wegen der Obergrenze \(H\) niemals relevant werden können.
Für \(d=\prod p^{e_p}\) gilt
$$\lambda(d)\,d=(-1)^{\Omega(d)}\prod p^{e_p}=\prod (-p)^{e_p}.$$
Ohne Intervallbedingung würde die gesamte signierte Teilersumme direkt faktorisiert werden:
$$\sum_{d\mid n!}\lambda(d)\,d=\prod_{p\le n}\left(\sum_{e=0}^{a_p}(-p)^e\right).$$
Die Schranke \(L\le d\le H\) zerstört diese einfache Produktform, weil die verschiedenen Primzahlen nun über die Größe des Gesamtprodukts gekoppelt sind. Genau deshalb ist Meet-in-the-middle hier passend.
Teile die Primzahlpotenzen von \(n!\) in zwei disjunkte Gruppen. Für die erste Gruppe definieren wir partielle Zustände
$$u=\prod_{p\in A}p^{e_p},\qquad \alpha=\prod_{p\in A}(-p)^{e_p},$$
und für die zweite Gruppe
$$v=\prod_{p\in B}p^{e_p},\qquad \beta=\prod_{p\in B}(-p)^{e_p}.$$
Da die Gruppen disjunkte Primzahlen benutzen, gehört zu jedem vollständigen Teiler genau ein Paar partieller Zustände, nämlich
$$d=u\,v,\qquad \lambda(d)\,d=\alpha\beta.$$
Aus einer großen Gesamtsuche wird so ein Zusammenführen zweier vorberechneter Listen.
Wenn das aktuelle partielle Produkt bereits größer als \(H\) ist oder die nächste Multiplikation mit derselben Primzahl \(H\) überschreiten würde, dann kann keine Fortsetzung jemals zu einem Teiler in \([L,H]\) oder zu einer Präfixsumme bis \(H\) beitragen. Weitere Primzahlpotenzen machen den Teiler nur größer.
Daher erzeugt jede Rekursion nur zulässige Paare \((u,\alpha)\) beziehungsweise \((v,\beta)\) mit Zahlenwert höchstens \(H\). Das Vorzeichen läuft über den Faktor \(-p\), der Zahlenwert des Teilers wird dagegen exakt gespeichert, damit spätere Vergleiche und Sortierungen korrekt bleiben.
Definiere die Präfixfunktion
$$P(X)=\sum_{\substack{d\mid n!\\d\le X}}\lambda(d)\,d.$$
Nach der Aufspaltung gilt dann
$$P(X)=\sum_{(u,\alpha)}\alpha\left(\sum_{\substack{(v,\beta)\\v\le X/u}}\beta\right).$$
Wird die zweite Liste nach \(v\) sortiert und werden ihre Gewichte als Präfixsummen gespeichert, dann ist die innere Summe sofort verfügbar, sobald die Grenze \(X/u\) bekannt ist. Sortiert man auch die erste Liste, genügt ein monotones Sweep-Verfahren: Mit wachsendem \(u\) wird die zulässige Grenze \(X/u\) nur kleiner, also bewegt sich der Zeiger nur in eine Richtung.
Die eigentliche Antwort ist nur die Differenz zweier Präfixwerte:
$$S(n;L,H)=P(H)-P(L-1)\pmod{10^9+7}.$$
Damit ist das Problem vollständig reduziert. Der Algorithmus berechnet also genau zwei Schwellenabfragen, bei \(H\) und bei \(L-1\), und subtrahiert sie modulo \(10^9+7\).
Hier gilt
$$5!=2^3\cdot 3\cdot 5.$$
Wir zerlegen in \(A=\{2^3,3\}\) und \(B=\{5\}\). Die erste Seite liefert die sortierten partiellen Zustände
$$\{(1,1),(2,-2),(3,-3),(4,4),(6,6),(8,-8),(12,-12),(24,24)\}.$$
Die zweite Seite liefert
$$\{(1,1),(5,-5)\},$$
mit Präfixsummen \(1\) und \(-4\).
Für \(P(30)\) ist die Grenze \(30/u\) bei \(u=1,2,3,4,6\) mindestens \(5\), also ist die innere Summe jeweils \(-4\). Für \(u=8,12,24\) ist nur \(v=1\) erlaubt, also ist die innere Summe \(1\). Daher
$$P(30)=-4+8+12-16-24-8-12+24=-20.$$
Für \(P(5)\) tragen nur \(u=1,2,3,4\) bei, also
$$P(5)=-4-2-3+4=-5.$$
Somit
$$S(n;L,H)=S(5;6,30)=P(30)-P(5)=-15\equiv 10^9+7-15 \pmod{10^9+7}.$$
Dieses kleine Beispiel benutzt exakt dieselbe Merge-Logik wie die vollständige Rechnung.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst alle Primzahlen bis \(n\) und berechnen ihre Exponenten in \(n!\) durch wiederholtes Teilen. Danach wird die Primfaktorliste nach den ersten fünf Primzahlen geteilt; für die Zielinstanz bleiben dadurch beide rekursiven Aufzählungen beherrschbar.
Auf jeder Seite werden alle partiellen Teiler rekursiv erzeugt, deren exakter Zahlenwert \(H\) nicht überschreitet. Neben diesem exakten Zahlenwert wird das signierte Gewicht modulo \(10^9+7\) mitgeführt. Die Teilerwerte selbst werden als exakte große Ganzzahlen gespeichert: in C++ mit 256-Bit-Arithmetik, in Python und Java mit beliebiger Präzision, sodass Vergleiche mit \(10^{60}\) exakt bleiben.
Nach dem Sortieren beider Listen nach dem Teilerwert baut die Implementierung Präfixsummen der Gewichte für die zweite Liste. Ein linearer Sweep über die erste Liste berechnet dann \(P(H)\) und \(P(L-1)\). Falls \(L\le 1\), ist der untere Präfixwert gleich null; sonst wird auch diese zweite Schwelle normal ausgewertet und anschließend modulo \(10^9+7\) subtrahiert.
Das Primzahlsieb bis \(n\) benötigt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Das Berechnen der Exponenten \(a_p\) per wiederholter Division trägt \(O(\pi(n)\log n)\) bei und ist hier klein. Wenn die beiden Rekursionen nach dem Abschneiden \(A\) und \(B\) zulässige partielle Zustände erzeugen, dann kostet die Enumeration \(O(A+B)\), das Sortieren \(O(A\log A+B\log B)\) und jede Schwellenabfrage \(O(A+B)\), weil der Zeiger über der zweiten Liste nur monoton wandert. Der Speicherverbrauch beträgt \(O(A+B)\).
Faktöriyeli şu şekilde yazalım:
$$n!=\prod_{p\le n}p^{a_p},\qquad a_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
Hesaplanması gereken ifade işaretli bölen toplamıdır:
$$S(n;L,H)=\sum_{\substack{d\mid n!\\L\le d\le H}}\lambda(d)\,d,\qquad \lambda(d)=(-1)^{\Omega(d)},$$
ve sonuç \(10^9+7\) modunda alınır. Hedef örnekte \([L,H]\) aralığı çok büyük olduğu için tüm bölenleri körlemesine üretmek mümkün değildir; çözüm, hem \(n!\)'in çarpımsal yapısını hem de yalnızca \(H\)'ye kadar olan bölenlerin önemli olmasını kullanır.
Ana fikir, her böleni asal üsleriyle temsil etmek, bu asalları iki bağımsız gruba ayırmak ve aralık koşulunu iki prefix sorgusuna dönüştürmektir.
Her \(p\le n\) asalı için Legendre formülü, \(p\)'nin \(n!\) içindeki üssünü verir. Böylece \(n!\)'in her böleni tekil olarak
$$d=\prod_{p\le n}p^{e_p},\qquad 0\le e_p\le a_p$$
şeklinde yazılır. Problem, izinli tüm üs vektörlerini \((e_p)\) incelemek demektir; fakat \(H\) sınırı yüzünden daha oluşurken elenebilecek dalları erkenden kesmek gerekir.
Eğer \(d=\prod p^{e_p}\) ise
$$\lambda(d)\,d=(-1)^{\Omega(d)}\prod p^{e_p}=\prod (-p)^{e_p}.$$
Aralık kısıtı olmasaydı, tüm işaretli bölen toplamı doğrudan şu çarpıma ayrılırdı:
$$\sum_{d\mid n!}\lambda(d)\,d=\prod_{p\le n}\left(\sum_{e=0}^{a_p}(-p)^e\right).$$
Fakat \(L\le d\le H\) koşulu geldiğinde bu basit çarpım bozulur; çünkü artık farklı asallar, oluşan toplam bölenin büyüklüğü üzerinden birbirine bağlanır. Meet-in-the-middle yaklaşımının nedeni tam olarak budur.
\(n!\)'in asal kuvvetlerini iki ayrık kümeye böl. İlk küme için kısmi durumları
$$u=\prod_{p\in A}p^{e_p},\qquad \alpha=\prod_{p\in A}(-p)^{e_p}$$
diye tanımlayalım; ikinci küme için de
$$v=\prod_{p\in B}p^{e_p},\qquad \beta=\prod_{p\in B}(-p)^{e_p}.$$
Kümeler ayrık asallar kullandığı için her tam bölen tam olarak bir \((u,\alpha)\) ve bir \((v,\beta)\) çiftine karşılık gelir; dolayısıyla
$$d=u\,v,\qquad \lambda(d)\,d=\alpha\beta.$$
Böylece tek dev arama yerine, önceden üretilmiş iki listenin birleştirilmesi problemi kalır.
Özyineleme sırasında mevcut kısmi çarpım zaten \(H\)'yi aşmışsa ya da aynı asalla bir kez daha çarpıldığında \(H\) aşılacaksa, bu dalın devamı hiçbir zaman \([L,H]\) içinde bir bölen üretemez. Daha fazla asal kuvvet eklemek sayıyı sadece büyütür.
Bu yüzden her iki tarafta da yalnızca sayısal değeri \(H\)'yi aşmayan \((u,\alpha)\) ve \((v,\beta)\) çiftleri saklanır. İşaret \(-p\) çarpanları üzerinden taşınır; bölen büyüklüğü ise daha sonra sıralama ve karşılaştırma yapılacağı için tam olarak tutulur.
Şu prefix fonksiyonunu tanımlayalım:
$$P(X)=\sum_{\substack{d\mid n!\\d\le X}}\lambda(d)\,d.$$
Bölme sonrası bu ifade
$$P(X)=\sum_{(u,\alpha)}\alpha\left(\sum_{\substack{(v,\beta)\\v\le X/u}}\beta\right)$$
şeklini alır. İkinci liste \(v\)'ye göre sıralanıp ağırlıkları prefix toplamına dönüştürülürse, içteki değer \(X/u\) sınırı bilindiği anda hazır olur. İlk liste de sıralanınca tek yönlü bir işaretçi yeterlidir: \(u\) arttıkça \(X/u\) küçülür, dolayısıyla işaretçi sadece bir yöne hareket eder.
Asıl aralık toplamı iki prefix farkıdır:
$$S(n;L,H)=P(H)-P(L-1)\pmod{10^9+7}.$$
Yani algoritma gerçekte yalnızca iki eşik sorgusu yapar: biri \(H\), diğeri \(L-1\) için. Son adım bunların farkını mod altında almaktır.
Bu durumda
$$5!=2^3\cdot 3\cdot 5.$$
Ayrımı \(A=\{2^3,3\}\) ve \(B=\{5\}\) olarak yapalım. İlk tarafın sıralı kısmi durumları
$$\{(1,1),(2,-2),(3,-3),(4,4),(6,6),(8,-8),(12,-12),(24,24)\}$$
olur. İkinci taraf ise
$$\{(1,1),(5,-5)\}$$
üretir ve bunun prefix toplamları \(1\) ile \(-4\)'tür.
\(P(30)\) için \(u=1,2,3,4,6\) değerlerinde \(30/u\ge 5\) olduğundan iç toplam \(-4\) olur. \(u=8,12,24\) için yalnızca \(v=1\) izinlidir, dolayısıyla iç toplam \(1\)'dir. Buradan
$$P(30)=-4+8+12-16-24-8-12+24=-20$$
çıkar.
\(P(5)\) için sadece \(u=1,2,3,4\) katkı verir:
$$P(5)=-4-2-3+4=-5.$$
Sonuç olarak
$$S(5;6,30)=P(30)-P(5)=-15\equiv 10^9+7-15 \pmod{10^9+7}.$$
Bu küçük örnek, tam çözümdeki birleştirme mantığını birebir gösterir.
C++, Python ve Java implementasyonları önce \(n\)'ye kadar olan tüm asalları üretir, sonra tekrar tekrar bölerek her asalın \(n!\) içindeki üssünü bulur. Ardından asal çarpan listesi ilk beş asal sonrasında iki parçaya ayrılır; hedef örnekte bu seçim iki özyinelemeli üretimi de yönetilebilir boyutta tutar.
Her iki tarafta da, tam değeri \(H\)'yi geçmeyen tüm kısmi bölenler özyinelemeli olarak üretilir. Tam bölen değeri ayrı, işaretli ağırlık ise \(10^9+7\) modunda ayrı taşınır. Bölen büyüklükleri tam hassasiyetle saklanır: C++ tarafında 256 bit, Python ve Java tarafında ise keyfi hassasiyet kullanılır; böylece \(10^{60}\) ile karşılaştırmalar hatasız olur.
Her iki liste değere göre sıralandıktan sonra, ikinci listenin işaretli ağırlıkları üzerinde prefix toplamı kurulur. İlk liste üzerinde yapılan doğrusal tarama ile \(P(H)\) ve \(P(L-1)\) hesaplanır. Eğer \(L\le 1\) ise alt sınır prefix'i sıfır kabul edilir; değilse ikinci eşik de normal hesaplanır ve iki sonuç mod \(10^9+7\) altında çıkarılır.
\(n\)'ye kadar asal üretimi \(O(n\log\log n)\) zaman ve \(O(n)\) bellek ister. \(a_p\) üslerini tekrar bölerek bulmak \(O(\pi(n)\log n)\) ek iş yükü getirir ve burada küçüktür. Kırpma sonrasında iki tarafta oluşan durum sayıları \(A\) ve \(B\) ise, üretim maliyeti \(O(A+B)\), sıralama maliyeti \(O(A\log A+B\log B)\) ve her eşik sorgusu \(O(A+B)\) olur; çünkü ikinci listedeki işaretçi tek yönde ilerler. Toplam bellek kullanımı \(O(A+B)\)'dir.
Escribimos el factorial como
$$n!=\prod_{p\le n}p^{a_p},\qquad a_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
La cantidad pedida es la suma de divisores con signo
$$S(n;L,H)=\sum_{\substack{d\mid n!\\L\le d\le H}}\lambda(d)\,d,\qquad \lambda(d)=(-1)^{\Omega(d)},$$
tomada módulo \(10^9+7\). En la instancia objetivo el intervalo \([L,H]\) es enorme, así que no se pueden enumerar todos los divisores uno por uno; hay que aprovechar la estructura multiplicativa de \(n!\) y el hecho de que solo importan los divisores de valor a lo sumo \(H\).
La idea central consiste en representar cada divisor por sus exponentes primos, dividir esos primos en dos grupos independientes y convertir la restricción de intervalo en dos consultas de prefijo.
Para cada primo \(p\le n\), la fórmula de Legendre da el exponente \(a_p\) de \(p\) dentro de \(n!\). Por tanto, cualquier divisor de \(n!\) se escribe de forma única como
$$d=\prod_{p\le n}p^{e_p},\qquad 0\le e_p\le a_p.$$
Así, el problema equivale a recorrer todos los vectores de exponentes \((e_p)\), pero descartando de inmediato los ramales cuyo producto parcial ya no puede contribuir por culpa de la cota superior \(H\).
Si \(d=\prod p^{e_p}\), entonces
$$\lambda(d)\,d=(-1)^{\Omega(d)}\prod p^{e_p}=\prod (-p)^{e_p}.$$
Sin la restricción del intervalo, la suma total sobre todos los divisores se factorizaría como
$$\sum_{d\mid n!}\lambda(d)\,d=\prod_{p\le n}\left(\sum_{e=0}^{a_p}(-p)^e\right).$$
La condición \(L\le d\le H\) rompe esa factorización sencilla, porque ahora los distintos primos interactúan a través del tamaño del producto total. Ese es precisamente el motivo para usar meet-in-the-middle.
Partimos las potencias primas de \(n!\) en dos grupos disjuntos. Para el primer grupo definimos estados parciales
$$u=\prod_{p\in A}p^{e_p},\qquad \alpha=\prod_{p\in A}(-p)^{e_p},$$
y para el segundo grupo
$$v=\prod_{p\in B}p^{e_p},\qquad \beta=\prod_{p\in B}(-p)^{e_p}.$$
Como los grupos usan primos disjuntos, cada divisor completo corresponde a un único par de estados parciales, con
$$d=u\,v,\qquad \lambda(d)\,d=\alpha\beta.$$
La búsqueda global se reduce así a combinar dos listas ya construidas.
Durante la recursión, si el producto parcial actual ya es mayor que \(H\), o si una multiplicación adicional por el primo actual haría que se superase \(H\), entonces ninguna continuación de ese ramal podrá contribuir a un divisor dentro de \([L,H]\) ni a una suma de prefijo hasta \(H\). Añadir más potencias primas solo hace crecer el divisor.
Por eso cada lado genera únicamente pares \((u,\alpha)\) o \((v,\beta)\) cuyo valor numérico es como mucho \(H\). El signo se transporta mediante el factor \(-p\), mientras que la magnitud del divisor se conserva de forma exacta para ordenar y comparar después.
Definimos la función prefijo
$$P(X)=\sum_{\substack{d\mid n!\\d\le X}}\lambda(d)\,d.$$
Tras la división en dos listas, queda
$$P(X)=\sum_{(u,\alpha)}\alpha\left(\sum_{\substack{(v,\beta)\\v\le X/u}}\beta\right).$$
Si la segunda lista se ordena por \(v\) y se guardan sus pesos en una tabla de prefijos, la suma interior se obtiene en cuanto conocemos el límite \(X/u\). Si también ordenamos la primera lista, el proceso se hace con un barrido monótono: al crecer \(u\), el límite \(X/u\) solo puede disminuir, así que el puntero avanza en una sola dirección.
La respuesta final es la diferencia entre dos prefijos:
$$S(n;L,H)=P(H)-P(L-1)\pmod{10^9+7}.$$
Esa identidad es la reducción final. El algoritmo evalúa exactamente dos umbrales, \(H\) y \(L-1\), y luego resta ambos valores módulo \(10^9+7\).
En este caso
$$5!=2^3\cdot 3\cdot 5.$$
Tomemos \(A=\{2^3,3\}\) y \(B=\{5\}\). El primer lado genera los estados parciales ordenados
$$\{(1,1),(2,-2),(3,-3),(4,4),(6,6),(8,-8),(12,-12),(24,24)\}.$$
El segundo lado genera
$$\{(1,1),(5,-5)\},$$
cuyas sumas de prefijo son \(1\) y \(-4\).
Para \(P(30)\), se tiene \(30/u\ge 5\) cuando \(u=1,2,3,4,6\), de modo que la suma interior vale \(-4\). Para \(u=8,12,24\), solo se permite \(v=1\), así que la suma interior vale \(1\). Por tanto
$$P(30)=-4+8+12-16-24-8-12+24=-20.$$
Para \(P(5)\), solo contribuyen \(u=1,2,3,4\), y obtenemos
$$P(5)=-4-2-3+4=-5.$$
En consecuencia,
$$S(5;6,30)=P(30)-P(5)=-15\equiv 10^9+7-15 \pmod{10^9+7}.$$
Este ejemplo pequeño usa exactamente la misma lógica de mezcla que la resolución completa.
Las implementaciones en C++, Python y Java primero generan todos los primos hasta \(n\) y calculan sus exponentes en \(n!\) mediante divisiones sucesivas. Después dividen la lista de factores primos tras los primeros cinco primos, lo que deja ambas enumeraciones recursivas en un tamaño manejable para la instancia objetivo.
Cada lado enumera recursivamente todos los divisores parciales cuyo valor exacto no supera \(H\). Junto al valor exacto del divisor se mantiene el peso con signo módulo \(10^9+7\). Los valores de los divisores se guardan como enteros exactos de gran tamaño: aritmética de 256 bits en C++ y enteros de precisión arbitraria en Python y Java, para que las comparaciones contra \(10^{60}\) sean exactas.
Una vez ordenadas ambas listas por valor del divisor, la implementación construye sumas de prefijo sobre los pesos de la segunda lista. Un barrido lineal sobre la primera lista permite evaluar \(P(H)\) y \(P(L-1)\). Si \(L\le 1\), el prefijo inferior vale cero; en caso contrario se calcula el segundo umbral de la forma habitual y luego se resta todo módulo \(10^9+7\).
Generar los primos hasta \(n\) cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. Calcular los exponentes \(a_p\) por divisiones repetidas añade \(O(\pi(n)\log n)\), que aquí es pequeño. Si las dos enumeraciones producen \(A\) y \(B\) estados parciales factibles tras la poda, la generación cuesta \(O(A+B)\), la ordenación cuesta \(O(A\log A+B\log B)\) y cada barrido para un umbral cuesta \(O(A+B)\), ya que el puntero de la segunda lista solo se mueve en una dirección. La memoria total es \(O(A+B)\).
先把阶乘写成素因子幂的形式：
$$n!=\prod_{p\le n}p^{a_p},\qquad a_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
要求计算的量是带符号的因子和
$$S(n;L,H)=\sum_{\substack{d\mid n!\\L\le d\le H}}\lambda(d)\,d,\qquad \lambda(d)=(-1)^{\Omega(d)},$$
最后对 \(10^9+7\) 取模。目标实例中的区间 \([L,H]\) 极大，因此不可能把所有因子逐个枚举出来再筛选；必须同时利用 \(n!\) 的乘法结构和“只有不超过 \(H\) 的因子才可能有贡献”这一事实。
核心思路是：把每个因子写成素数指数向量，把所有素数拆成两组独立部分，再把区间求和转化成两个前缀求和问题。
对每个 \(p\le n\)，Legendre 公式给出 \(p\) 在 \(n!\) 中的指数 \(a_p\)。因此 \(n!\) 的任意因子都能唯一写成
$$d=\prod_{p\le n}p^{e_p},\qquad 0\le e_p\le a_p.$$
从这个角度看，问题就是在所有合法的指数向量 \((e_p)\) 中做搜索。但如果某个部分乘积已经超过 \(H\)，那么这个分支继续乘下去只会更大，不可能重新回到有效范围，因此可以立刻剪枝。
若 \(d=\prod p^{e_p}\)，则
$$\lambda(d)\,d=(-1)^{\Omega(d)}\prod p^{e_p}=\prod (-p)^{e_p}.$$
如果没有区间限制，那么对全部因子的总和会直接分解成
$$\sum_{d\mid n!}\lambda(d)\,d=\prod_{p\le n}\left(\sum_{e=0}^{a_p}(-p)^e\right).$$
但一旦加入 \(L\le d\le H\) 这个条件，事情就不再是单纯的独立乘积了，因为不同素数对最终因子大小的贡献会彼此耦合。这正是需要 meet-in-the-middle 的根本原因。
把 \(n!\) 的素数幂拆成两个互不相交的组。对于第一组，定义部分状态
$$u=\prod_{p\in A}p^{e_p},\qquad \alpha=\prod_{p\in A}(-p)^{e_p},$$
对于第二组，定义
$$v=\prod_{p\in B}p^{e_p},\qquad \beta=\prod_{p\in B}(-p)^{e_p}.$$
由于两组使用的是互不重叠的素数，每个完整因子都唯一对应于一对部分状态，并且有
$$d=u\,v,\qquad \lambda(d)\,d=\alpha\beta.$$
这样，原本一次性处理所有素数的巨大搜索，就变成了两个预生成列表之间的合并问题。
递归生成时，如果当前部分乘积已经大于 \(H\)，或者再乘一次当前素数就会超过 \(H\)，那么这个分支之后无论怎么补充其他素数幂，都不可能落入 \([L,H]\)，也不可能对任何不超过 \(H\) 的前缀和有贡献。因为继续乘只会让数更大。
因此，两边递归都只保留数值不超过 \(H\) 的状态 \((u,\alpha)\) 或 \((v,\beta)\)。权重中的符号通过 \(-p\) 带过去，而因子的实际大小则必须精确保留，用于后续排序、比较以及阈值判断。
定义前缀函数
$$P(X)=\sum_{\substack{d\mid n!\\d\le X}}\lambda(d)\,d.$$
拆分后可写成
$$P(X)=\sum_{(u,\alpha)}\alpha\left(\sum_{\substack{(v,\beta)\\v\le X/u}}\beta\right).$$
如果第二个列表按 \(v\) 从小到大排序，并预先做好权重前缀和，那么只要知道阈值 \(X/u\)，内层和就能立即得到。再把第一个列表也按 \(u\) 排序，就可以用单调指针线性扫描：随着 \(u\) 变大，允许的上界 \(X/u\) 只会变小，所以指针只需要单向移动。
最终要求的区间和就是两个前缀值之差：
$$S(n;L,H)=P(H)-P(L-1)\pmod{10^9+7}.$$
这就是整个推导的最后一步。也就是说，算法只需要处理两个阈值查询，一个是 \(H\)，一个是 \(L-1\)，然后在模 \(10^9+7\) 下相减即可。
此时
$$5!=2^3\cdot 3\cdot 5.$$
把素因子分成 \(A=\{2^3,3\}\) 和 \(B=\{5\}\)。第一部分生成的有序状态为
$$\{(1,1),(2,-2),(3,-3),(4,4),(6,6),(8,-8),(12,-12),(24,24)\}.$$
第二部分生成
$$\{(1,1),(5,-5)\},$$
它的权重前缀和依次为 \(1\) 和 \(-4\)。
计算 \(P(30)\) 时，当 \(u=1,2,3,4,6\) 时都有 \(30/u\ge 5\)，所以第二部分两个状态都可以取到，内层和是 \(-4\)。当 \(u=8,12,24\) 时，只允许 \(v=1\)，内层和变成 \(1\)。因此
$$P(30)=-4+8+12-16-24-8-12+24=-20.$$
再看 \(P(5)\)，只有 \(u=1,2,3,4\) 会贡献，所以
$$P(5)=-4-2-3+4=-5.$$
于是
$$S(5;6,30)=P(30)-P(5)=-15\equiv 10^9+7-15 \pmod{10^9+7}.$$
这个小例子和完整程序使用的是完全相同的合并逻辑，只是规模更小、可以手算出来。
C++、Python 和 Java 的实现都会先生成不超过 \(n\) 的所有素数，再用不断整除的方式求出每个素数在 \(n!\) 中的指数。之后，素因子列表在前五个素数之后切成两段；对目标实例来说，这样的固定切分已经能把两边的递归枚举控制在可接受的范围内。
两边递归都会枚举所有数值不超过 \(H\) 的部分因子状态。一方面保存因子的精确数值，另一方面保存对应的带符号权重并对 \(10^9+7\) 取模。因子数值必须保持精确：C++ 使用 256 位整数，Python 和 Java 使用任意精度整数，因此与 \(10^{60}\) 的比较不会出现精度问题。
接下来，两份状态表按因子大小排序，第二份表建立权重前缀和。随后对第一份表做一次线性扫描，就能分别得到 \(P(H)\) 和 \(P(L-1)\)。如果 \(L\le 1\)，下界前缀直接视为零；否则正常计算第二个阈值，最后将两者在模 \(10^9+7\) 下相减。
生成不超过 \(n\) 的素数需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间。通过重复整除求各个 \(a_p\) 还要加上 \(O(\pi(n)\log n)\) 的代价，但这里这部分很小。若剪枝后两边分别得到 \(A\) 和 \(B\) 个可行状态，则生成成本是 \(O(A+B)\)，排序成本是 \(O(A\log A+B\log B)\)，每个阈值扫描的成本是 \(O(A+B)\)，因为第二个列表上的指针只会单调移动。总空间复杂度为 \(O(A+B)\)。
Представим факториал в виде
$$n!=\prod_{p\le n}p^{a_p},\qquad a_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
Требуется вычислить знакопеременную сумму делителей
$$S(n;L,H)=\sum_{\substack{d\mid n!\\L\le d\le H}}\lambda(d)\,d,\qquad \lambda(d)=(-1)^{\Omega(d)},$$
по модулю \(10^9+7\). В целевом случае интервал \([L,H]\) огромен, поэтому прямой перебор делителей невозможен. Нужно использовать и мультипликативную структуру \(n!\), и тот факт, что важны только делители, не превосходящие \(H\).
Ключевая идея состоит в том, чтобы описать каждый делитель через вектор простых показателей, разделить все простые на две независимые группы и заменить задачу на две префиксные суммы.
Для каждого простого \(p\le n\) формула Лежандра дает показатель \(a_p\) числа \(p\) в разложении \(n!\). Поэтому любой делитель \(n!\) единственным образом записывается как
$$d=\prod_{p\le n}p^{e_p},\qquad 0\le e_p\le a_p.$$
Иными словами, задача сводится к перебору допустимых векторов \((e_p)\), но с ранним отсечением всех ветвей, которые уже не могут дать вклад из-за верхней границы \(H\).
Если \(d=\prod p^{e_p}\), то
$$\lambda(d)\,d=(-1)^{\Omega(d)}\prod p^{e_p}=\prod (-p)^{e_p}.$$
Без ограничения по интервалу полная сумма по всем делителям раскладывалась бы в простой продукт:
$$\sum_{d\mid n!}\lambda(d)\,d=\prod_{p\le n}\left(\sum_{e=0}^{a_p}(-p)^e\right).$$
Но условие \(L\le d\le H\) ломает эту независимую факторизацию, потому что разные простые начинают взаимодействовать через размер итогового произведения. Именно поэтому здесь естественен подход meet-in-the-middle.
Разобьем простые степени в \(n!\) на две непересекающиеся группы. Для первой группы введем частичные состояния
$$u=\prod_{p\in A}p^{e_p},\qquad \alpha=\prod_{p\in A}(-p)^{e_p},$$
а для второй группы
$$v=\prod_{p\in B}p^{e_p},\qquad \beta=\prod_{p\in B}(-p)^{e_p}.$$
Так как группы используют разные простые, каждый полный делитель соответствует ровно одной паре таких состояний, причем
$$d=u\,v,\qquad \lambda(d)\,d=\alpha\beta.$$
Одна очень большая задача перечисления превращается в объединение двух заранее построенных списков.
Если на каком-то шаге рекурсии текущее частичное произведение уже больше \(H\), или следующая дополнительная степень текущего простого сразу переведет его за \(H\), то никакое продолжение этой ветви уже не даст вклад ни в интервал \([L,H]\), ни в префиксную сумму до \(H\). Дополнительные простые степени могут только увеличивать делитель.
Поэтому на каждом боку сохраняются лишь те пары \((u,\alpha)\) и \((v,\beta)\), чей точный числовой размер не превосходит \(H\). Знак переносится через множитель \(-p\), а численное значение делителя хранится точно, чтобы сортировка и сравнения были корректными.
Определим префиксную функцию
$$P(X)=\sum_{\substack{d\mid n!\\d\le X}}\lambda(d)\,d.$$
После разбиения она принимает вид
$$P(X)=\sum_{(u,\alpha)}\alpha\left(\sum_{\substack{(v,\beta)\\v\le X/u}}\beta\right).$$
Если второй список отсортировать по \(v\) и заранее накопить его веса в массиве префиксных сумм, то внутренняя сумма получается сразу после того, как известна граница \(X/u\). Если также отсортировать первый список, то можно сделать линейный монотонный проход: при росте \(u\) величина \(X/u\) только уменьшается, значит указатель по второму списку движется лишь в одну сторону.
Искомая сумма по интервалу равна разности двух префиксов:
$$S(n;L,H)=P(H)-P(L-1)\pmod{10^9+7}.$$
Это и есть окончательное сведение задачи. Алгоритм считает два пороговых значения, при \(H\) и при \(L-1\), после чего вычитает их по модулю \(10^9+7\).
Здесь
$$5!=2^3\cdot 3\cdot 5.$$
Разобьем множители как \(A=\{2^3,3\}\) и \(B=\{5\}\). Первый список частичных состояний имеет вид
$$\{(1,1),(2,-2),(3,-3),(4,4),(6,6),(8,-8),(12,-12),(24,24)\}.$$
Второй список равен
$$\{(1,1),(5,-5)\},$$
а его префиксные суммы равны \(1\) и \(-4\).
Для \(P(30)\) при \(u=1,2,3,4,6\) выполняется \(30/u\ge 5\), поэтому внутренняя сумма равна \(-4\). Для \(u=8,12,24\) разрешено только \(v=1\), значит внутренняя сумма равна \(1\). Следовательно,
$$P(30)=-4+8+12-16-24-8-12+24=-20.$$
Для \(P(5)\) вклад дают только \(u=1,2,3,4\), откуда
$$P(5)=-4-2-3+4=-5.$$
Значит,
$$S(5;6,30)=P(30)-P(5)=-15\equiv 10^9+7-15 \pmod{10^9+7}.$$
Это маленькое ручное вычисление использует ровно ту же схему слияния, что и полная программа.
Реализации на C++, Python и Java сначала строят список простых чисел до \(n\), а затем находят показатели этих простых в \(n!\) последовательным делением. После этого список простых множителей разрезается после первых пяти простых; для целевого входа этого достаточно, чтобы обе рекурсивные генерации оставались управляемыми.
С каждой стороны рекурсивно перечисляются все частичные делители, чей точный размер не превосходит \(H\). Одновременно хранятся точное значение делителя и его знаковый вес по модулю \(10^9+7\). Числовые значения делителей должны оставаться точными: в C++ используется 256-битная арифметика, а в Python и Java применяются целые произвольной длины, поэтому сравнения с \(10^{60}\) выполняются без потери точности.
Затем оба списка сортируются по значению делителя, для второго списка строятся префиксные суммы весов, и линейный проход по первому списку вычисляет \(P(H)\) и \(P(L-1)\). Если \(L\le 1\), нижний префикс считается равным нулю; в противном случае второй порог вычисляется обычным образом, а разность берется по модулю \(10^9+7\).
Построение списка простых до \(n\) требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Вычисление показателей \(a_p\) повторным делением добавляет \(O(\pi(n)\log n)\), что здесь мало. Если после отсечения получаются \(A\) и \(B\) допустимых частичных состояний, то генерация стоит \(O(A+B)\), сортировка стоит \(O(A\log A+B\log B)\), а каждый пороговый проход стоит \(O(A+B)\), поскольку указатель по второму списку двигается монотонно. Память имеет порядок \(O(A+B)\).
نكتب العامل \(n!\) على الصورة
$$n!=\prod_{p\le n}p^{a_p},\qquad a_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
والكمية المطلوبة هي مجموع القواسم ذي الإشارة
$$S(n;L,H)=\sum_{\substack{d\mid n!\\L\le d\le H}}\lambda(d)\,d,\qquad \lambda(d)=(-1)^{\Omega(d)},$$
ثم يؤخذ الناتج بترديد \(10^9+7\). في الحالة المستهدفة يكون المجال \([L,H]\) هائلًا جدًا، لذلك لا يمكن توليد جميع القواسم مباشرة. الحل يعتمد على البنية الضربية لـ \(n!\) وعلى أن القواسم الأكبر من \(H\) لا يمكن أن تساهم أصلًا.
الفكرة الأساسية هي تمثيل كل قاسم بمتجه أسس أولية، ثم تقسيم هذه الأعداد الأولية إلى مجموعتين مستقلتين، وتحويل شرط المجال إلى استعلامين من نوع المجموع التراكمي.
لكل عدد أولي \(p\le n\)، تعطي صيغة ليجاندر الأس \(a_p\) للعدد \(p\) داخل \(n!\). لذلك فإن كل قاسم لـ \(n!\) يكتب بشكل وحيد على الصورة
$$d=\prod_{p\le n}p^{e_p},\qquad 0\le e_p\le a_p.$$
إذن المسألة تعادل المرور على جميع متجهات الأسس المسموح بها \((e_p)\)، لكن مع قطع الفروع مبكرًا إذا كان حاصل الضرب الجزئي قد تجاوز \(H\)، لأن متابعة الضرب لن تعيده أبدًا إلى المجال المطلوب.
إذا كان \(d=\prod p^{e_p}\)، فإن
$$\lambda(d)\,d=(-1)^{\Omega(d)}\prod p^{e_p}=\prod (-p)^{e_p}.$$
ولو لم يكن هناك تقييد بالمجال، لتفكك مجموع جميع القواسم مباشرة إلى
$$\sum_{d\mid n!}\lambda(d)\,d=\prod_{p\le n}\left(\sum_{e=0}^{a_p}(-p)^e\right).$$
لكن الشرط \(L\le d\le H\) يكسر هذا التفكيك البسيط، لأن مساهمات الأعداد الأولية المختلفة تصبح مرتبطة بحجم القاسم الكامل. ومن هنا تظهر الحاجة إلى أسلوب meet-in-the-middle.
نقسم القوى الأولية في \(n!\) إلى مجموعتين منفصلتين. للمجموعة الأولى نعرّف الحالات الجزئية
$$u=\prod_{p\in A}p^{e_p},\qquad \alpha=\prod_{p\in A}(-p)^{e_p},$$
وللمجموعة الثانية نعرّف
$$v=\prod_{p\in B}p^{e_p},\qquad \beta=\prod_{p\in B}(-p)^{e_p}.$$
وبما أن المجموعتين تستخدمان أعدادًا أولية متمايزة، فإن كل قاسم كامل يقابل زوجًا وحيدًا من الحالتين الجزئيتين، بحيث
$$d=u\,v,\qquad \lambda(d)\,d=\alpha\beta.$$
وهكذا تتحول عملية التعداد الكبيرة الواحدة إلى دمج قائمتين جاهزتين مسبقًا.
إذا تجاوز حاصل الضرب الجزئي الحالي \(H\)، أو إذا كانت الضربة التالية بنفس العدد الأولي ستجعله يتجاوز \(H\)، فلا يوجد أي امتداد لذلك الفرع يمكن أن ينتج قاسمًا داخل \([L,H]\) أو حتى يساهم في مجموع تراكمي حتى \(H\). فإضافة مزيد من القوى الأولية لا تفعل إلا زيادة القيمة.
لهذا السبب تحتفظ كل جهة فقط بالأزواج \((u,\alpha)\) أو \((v,\beta)\) التي لا يتجاوز مقدارها العددي \(H\). الإشارة تنتقل عبر العامل \(-p\)، أما قيمة القاسم نفسها فتُحفظ بدقة كاملة حتى تبقى المقارنات والترتيب صحيحة.
لنعرّف دالة المجموع التراكمي
$$P(X)=\sum_{\substack{d\mid n!\\d\le X}}\lambda(d)\,d.$$
بعد التقسيم نحصل على
$$P(X)=\sum_{(u,\alpha)}\alpha\left(\sum_{\substack{(v,\beta)\\v\le X/u}}\beta\right).$$
إذا رُتبت القائمة الثانية بحسب \(v\) وحُسبت مجاميعها التراكمية، فإن المجموع الداخلي يصبح متاحًا فور معرفة الحد \(X/u\). وإذا رتّبنا القائمة الأولى أيضًا، أمكن تنفيذ مسح أحادي الاتجاه: عندما تكبر \(u\) فإن الحد \(X/u\) لا يمكن إلا أن يصغر، لذلك يتحرك المؤشر في اتجاه واحد فقط.
الجواب النهائي هو فرق مجموعين تراكميين:
$$S(n;L,H)=P(H)-P(L-1)\pmod{10^9+7}.$$
هذه هي الخطوة الختامية في الاختزال الرياضي. لذلك فالتنفيذ يحسب قيمتين حدّيتين فقط، عند \(H\) وعند \(L-1\)، ثم يأخذ الفرق بترديد \(10^9+7\).
لدينا هنا
$$5!=2^3\cdot 3\cdot 5.$$
لنأخذ التقسيم \(A=\{2^3,3\}\) و\(B=\{5\}\). تنتج الجهة الأولى الحالات الجزئية المرتبة
$$\{(1,1),(2,-2),(3,-3),(4,4),(6,6),(8,-8),(12,-12),(24,24)\}.$$
أما الجهة الثانية فتنتج
$$\{(1,1),(5,-5)\},$$
ومجاميعها التراكمية هي \(1\) ثم \(-4\).
عند حساب \(P(30)\)، يكون \(30/u\ge 5\) عندما \(u=1,2,3,4,6\)، لذلك يكون المجموع الداخلي مساويًا لـ \(-4\). أما عندما \(u=8,12,24\)، فلا يسمح إلا بالقيمة \(v=1\)، فيصبح المجموع الداخلي \(1\). إذن
$$P(30)=-4+8+12-16-24-8-12+24=-20.$$
ولحساب \(P(5)\) لا يساهم إلا \(u=1,2,3,4\)، فنحصل على
$$P(5)=-4-2-3+4=-5.$$
وبالتالي
$$S(5;6,30)=P(30)-P(5)=-15\equiv 10^9+7-15 \pmod{10^9+7}.$$
هذا المثال الصغير يطابق تمامًا آلية الدمج نفسها المستخدمة في الحساب الكامل، لكنه صغير بما يكفي ليتحقق يدويًا.
تبدأ تطبيقات C++ وPython وJava بتوليد جميع الأعداد الأولية حتى \(n\)، ثم تحسب أس كل عدد أولي في \(n!\) بواسطة القسمة المتكررة. بعد ذلك تُقسم قائمة العوامل الأولية بعد أول خمسة أعداد أولية، وهذا التقسيم الثابت يكفي لجعل التعدادين العوديَّين قابلين للإدارة في الحالة المستهدفة.
كل جهة تعدّ عوديًا جميع القواسم الجزئية التي لا تتجاوز قيمتها الدقيقة \(H\). وبالتوازي مع القيمة الدقيقة للقاسم يُحمل الوزن ذو الإشارة بترديد \(10^9+7\). قيم القواسم نفسها يجب أن تبقى دقيقة تمامًا: يستخدم C++ أعدادًا بعرض 256 بت، بينما تعتمد Python وJava على أعداد صحيحة ذات دقة غير محدودة، لذلك تبقى المقارنات مع \(10^{60}\) دقيقة.
بعد ترتيب القائمتين بحسب قيمة القاسم، يبني التنفيذ مجاميع تراكمية لأوزان القائمة الثانية. ثم يؤدي مسح خطي على القائمة الأولى إلى حساب \(P(H)\) و\(P(L-1)\). وإذا كان \(L\le 1\) فإن الحد الأدنى التراكمي يساوي صفرًا، وإلا تُحسب القيمة الثانية بالطريقة العادية ثم يُؤخذ الفرق بترديد \(10^9+7\).
توليد الأعداد الأولية حتى \(n\) يكلف \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة. أما حساب الأسس \(a_p\) بالقسمة المتكررة فيضيف \(O(\pi(n)\log n)\)، وهو جزء صغير هنا. إذا أنتج التعداد بعد القص \(A\) و\(B\) حالة جزئية صالحة، فالكلفة هي \(O(A+B)\) للتوليد، و\(O(A\log A+B\log B)\) للترتيب، و\(O(A+B)\) لكل مسح حدّي، لأن مؤشر القائمة الثانية يتحرك بشكل رتيب فقط. أما الذاكرة فهي \(O(A+B)\).