Let \(\omega(n)\) denote the number of distinct prime divisors of \(n\). The problem uses the arithmetic function
$$S(n)=\sum_{d\mid n} 2^{\omega(d)}.$$
We must compute
$$F(N)=\sum_{i=2}^{N} S(i!) \pmod{M},\qquad M=1{,}000{,}000{,}087,$$
for the very large value \(N=10^7\). Directly factoring every factorial or enumerating divisors is far too slow, so the key is to update \(S(i!)\) from \(S((i-1)!)\) using only the prime factors of \(i\).
The implementations rely on a multiplicative description of \(S(n)\), then apply it incrementally to the factorial sequence.
Write
$$n=\prod_{p} p^{e_p}.$$
Every divisor of \(n\) has the form
$$d=\prod_{p} p^{a_p},\qquad 0\le a_p\le e_p.$$
The value \(\omega(d)\) counts how many exponents \(a_p\) are positive. Therefore the divisor sum factors prime by prime. For one prime power \(p^e\), the local contribution is
$$1+\underbrace{2+\cdots+2}_{e\text{ times}}=2e+1,$$
because exponent \(0\) contributes \(2^{\omega(1)}=1\), while each exponent \(1,\dots,e\) contributes \(2^{\omega(p^a)}=2\).
Hence
$$S(n)=\prod_{p^{e_p}\parallel n} (2e_p+1).$$
As a quick check, \(6=2^1\cdot 3^1\), so
$$S(6)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9,$$
which matches the divisor sum \(1+2+2+4=9\) over \(d=1,2,3,6\).
For factorials, let
$$E_p(i)=v_p(i!),$$
so that
$$i!=\prod_{p} p^{E_p(i)}.$$
Then the previous identity becomes
$$S(i!)=\prod_{p} \bigl(2E_p(i)+1\bigr).$$
Now compare consecutive factorials:
$$i!=i\cdot (i-1)!.$$
If \(i\) contains prime \(p\) with multiplicity \(c=v_p(i)\), then
$$E_p(i)=E_p(i-1)+c.$$
All primes not dividing \(i\) keep the same exponent. This means only a few local factors change from one step to the next.
Suppose
$$i=\prod_{p^{c_p}\parallel i} p^{c_p}.$$
Each affected prime replaces one factor in the product for \(S((i-1)!)\):
$$2E_p(i-1)+1 \longrightarrow 2\bigl(E_p(i-1)+c_p\bigr)+1.$$
Therefore
$$S(i!)=S((i-1)!)\prod_{p^{c_p}\parallel i}\frac{2\bigl(E_p(i-1)+c_p\bigr)+1}{2E_p(i-1)+1}.$$
This is the central idea of the algorithm. It never recomputes the full product from scratch. It only divides out the old odd factor for each prime in \(i\), multiplies by the new odd factor, and keeps a running value of \(S(i!)\).
Every update uses odd numbers of the form
$$2E_p(i)+1.$$
The largest exponent in a factorial always belongs to prime \(2\), so for every prime \(p\) and every \(i\le N\),
$$E_p(i)\le E_2(N)=v_2(N!).$$
Hence all odd factors that can ever appear are at most
$$B=2v_2(N!)+1.$$
The implementation precomputes modular inverses up to this bound once, then reuses them during every ratio update. That turns each division in the formula above into a constant-time modular multiplication.
Take \(N=5\). The factorial values evolve as follows.
For \(2!=2\), we have \(2^1\), so
$$S(2!)=2\cdot 1+1=3.$$
For \(3!=6=2^1\cdot 3^1\),
$$S(3!)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9.$$
Now move from \(3!\) to \(4!\). Since \(4=2^2\), the exponent of \(2\) rises from \(1\) to \(3\). The local factor for prime \(2\) changes from \(3\) to \(7\), so
$$S(4!)=S(3!)\cdot \frac{7}{3}=9\cdot \frac{7}{3}=21.$$
Next, \(5=5^1\), so prime \(5\) appears with exponent \(1\) for the first time. Its local factor changes from \(1\) to \(3\), giving
$$S(5!)=S(4!)\cdot 3=21\cdot 3=63.$$
Therefore
$$F(5)=S(2!)+S(3!)+S(4!)+S(5!)=3+9+21+63=96.$$
This example shows exactly why an incremental product update is much cheaper than refactoring each factorial independently.
The C++, Python, and Java implementations first build a linear smallest-prime-factor table up to \(N\). That table lets the algorithm factor every integer \(i\) by repeated lookups and divisions, without trial division.
They also maintain an array of current factorial exponents \(E_p(i!)\) for all primes \(p\), together with one running modular value equal to the current \(S(i!)\). Before the main loop starts, the implementations compute the inverse table up to \(2v_2(N!)+1\), which covers every odd factor \(2E_p+1\) that may appear later.
For each \(i\) from \(2\) to \(N\), the factorization of \(i\) yields the multiplicity \(c_p\) of each prime dividing \(i\). The implementation updates the stored exponent of that prime, replaces the old local factor \(2e+1\) by the new factor \(2(e+c_p)+1\) inside the running product, and then adds the updated \(S(i!)\) to the cumulative total. No divisor list and no explicit factorial value is ever constructed.
The linear smallest-prime-factor sieve costs \(O(N)\) time and \(O(N)\) memory. The inverse table also has size \(O(N)\), because \(v_2(N!)<N\).
Factoring every \(i\le N\) through the smallest-prime-factor table takes total time proportional to the total number of prime factors with multiplicity encountered along the way. On average this is \(O(N\log\log N)\), with a coarser upper bound of \(O(N\log N)\). The overall memory usage remains \(O(N)\).
Sei \(\omega(n)\) die Anzahl der verschiedenen Primteiler von \(n\). Verwendet wird die arithmetische Funktion
$$S(n)=\sum_{d\mid n} 2^{\omega(d)}.$$
Gesucht ist
$$F(N)=\sum_{i=2}^{N} S(i!) \pmod{M},\qquad M=1{,}000{,}000{,}087,$$
für den sehr großen Wert \(N=10^7\). Weder das separate Faktorisieren jedes Fakultätswerts noch das Auflisten aller Teiler ist praktikabel, daher muss die Lösung \(S(i!)\) aus \(S((i-1)!)\) nur über die Primfaktoren von \(i\) aktualisieren.
Die Implementierungen benutzen zuerst eine multiplikative Darstellung von \(S(n)\) und wenden sie dann schrittweise auf die Fakultätsfolge an.
Schreibe
$$n=\prod_{p} p^{e_p}.$$
Jeder Teiler von \(n\) hat die Form
$$d=\prod_{p} p^{a_p},\qquad 0\le a_p\le e_p.$$
Der Wert \(\omega(d)\) zählt, bei wie vielen Primzahlen der Exponent \(a_p\) positiv ist. Deshalb faktorisiert die Teilersumme primweise. Für eine einzelne Primzahlpotenz \(p^e\) ist der lokale Beitrag
$$1+\underbrace{2+\cdots+2}_{e\text{ mal}}=2e+1,$$
denn Exponent \(0\) liefert \(2^{\omega(1)}=1\), während die Exponenten \(1,\dots,e\) jeweils \(2^{\omega(p^a)}=2\) liefern.
Also gilt
$$S(n)=\prod_{p^{e_p}\parallel n} (2e_p+1).$$
Zur Kontrolle: \(6=2^1\cdot 3^1\), also
$$S(6)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9,$$
genau wie die Teilersumme \(1+2+2+4=9\) über \(d=1,2,3,6\).
Für Fakultäten setzen wir
$$E_p(i)=v_p(i!),$$
sodass
$$i!=\prod_{p} p^{E_p(i)}.$$
Damit wird die vorige Identität zu
$$S(i!)=\prod_{p} \bigl(2E_p(i)+1\bigr).$$
Vergleicht man aufeinanderfolgende Fakultäten, so gilt
$$i!=i\cdot (i-1)!.$$
Enthält \(i\) eine Primzahl \(p\) mit Vielfachheit \(c=v_p(i)\), dann
$$E_p(i)=E_p(i-1)+c.$$
Alle Primzahlen, die \(i\) nicht teilen, behalten denselben Exponenten. Von einem Schritt zum nächsten ändern sich also nur wenige lokale Faktoren.
Sei
$$i=\prod_{p^{c_p}\parallel i} p^{c_p}.$$
Jede betroffene Primzahl ersetzt genau einen Faktor in der Produktdarstellung von \(S((i-1)!)\):
$$2E_p(i-1)+1 \longrightarrow 2\bigl(E_p(i-1)+c_p\bigr)+1.$$
Daher folgt
$$S(i!)=S((i-1)!)\prod_{p^{c_p}\parallel i}\frac{2\bigl(E_p(i-1)+c_p\bigr)+1}{2E_p(i-1)+1}.$$
Das ist die Kernidee des Verfahrens. Das volle Produkt wird nie neu aufgebaut. Stattdessen entfernt man für jede Primzahl in \(i\) den alten ungeraden Faktor, multipliziert den neuen hinein und hält so einen laufenden Wert von \(S(i!)\) aktuell.
In jedem Update treten ungerade Zahlen der Form
$$2E_p(i)+1$$
auf. Der größte Exponent in einer Fakultät gehört immer zur Primzahl \(2\), also gilt für jede Primzahl \(p\) und jedes \(i\le N\)
$$E_p(i)\le E_2(N)=v_2(N!).$$
Damit sind alle ungeraden Faktoren höchstens
$$B=2v_2(N!)+1.$$
Die Implementierung berechnet modulare Inverse bis zu dieser Schranke einmal vor und verwendet sie dann in jedem Quotienten-Update wieder. So wird jede Division aus der Formel zu einer konstant schnellen modularen Multiplikation.
Nehmen wir \(N=5\). Dann entwickeln sich die Fakultätswerte wie folgt.
Für \(2!=2\) gilt \(2^1\), also
$$S(2!)=2\cdot 1+1=3.$$
Für \(3!=6=2^1\cdot 3^1\) erhält man
$$S(3!)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9.$$
Nun von \(3!\) zu \(4!\): Da \(4=2^2\), steigt der Exponent von \(2\) von \(1\) auf \(3\). Der lokale Faktor für \(2\) wechselt also von \(3\) auf \(7\), somit
$$S(4!)=S(3!)\cdot \frac{7}{3}=9\cdot \frac{7}{3}=21.$$
Als Nächstes ist \(5=5^1\), also tritt die Primzahl \(5\) erstmals mit Exponent \(1\) auf. Ihr lokaler Faktor springt von \(1\) auf \(3\), daher
$$S(5!)=S(4!)\cdot 3=21\cdot 3=63.$$
Damit folgt
$$F(5)=S(2!)+S(3!)+S(4!)+S(5!)=3+9+21+63=96.$$
Genau dieses Beispiel zeigt, warum das inkrementelle Produktupdate viel günstiger ist als eine vollständige Neufaktorisierung jeder Fakultät.
Die C++-, Python- und Java-Implementierungen bauen zunächst bis \(N\) eine lineare Tabelle des kleinsten Primfaktors auf. Damit kann jede Zahl \(i\) durch wiederholtes Nachschlagen und Teilen faktorisiert werden, ohne Probedivision.
Außerdem halten sie ein Feld mit den aktuellen Fakultätsexponenten \(E_p(i!)\) für alle Primzahlen \(p\) sowie einen laufenden modularen Wert für das momentane \(S(i!)\). Vor Beginn der Hauptschleife wird die Inversentabelle bis \(2v_2(N!)+1\) berechnet; das deckt jeden später auftretenden ungeraden Faktor \(2E_p+1\) ab.
Für jedes \(i\) von \(2\) bis \(N\) liefert die Faktorisierung von \(i\) die Vielfachheit \(c_p\) jeder beteiligten Primzahl. Die Implementierung erhöht den gespeicherten Exponenten dieser Primzahl, ersetzt im laufenden Produkt den alten lokalen Faktor \(2e+1\) durch den neuen Faktor \(2(e+c_p)+1\) und addiert anschließend das aktualisierte \(S(i!)\) zur Gesamtsumme. Weder eine Teilerliste noch ein expliziter Fakultätswert wird jemals konstruiert.
Die lineare Tabelle des kleinsten Primfaktors benötigt \(O(N)\) Zeit und \(O(N)\) Speicher. Die Inversentabelle ist ebenfalls \(O(N)\) groß, weil \(v_2(N!)<N\) gilt.
Das Faktorisieren aller \(i\le N\) über diese Tabelle kostet insgesamt Zeit proportional zur gesamten Anzahl auftretender Primfaktoren mit Vielfachheit. Im Durchschnitt ist das \(O(N\log\log N)\), mit einer gröberen oberen Schranke \(O(N\log N)\). Der gesamte Speicherbedarf bleibt \(O(N)\).
\(\omega(n)\), \(n\)'nin farklı asal bölen sayısı olsun. Problemde kullanılan aritmetik fonksiyon
$$S(n)=\sum_{d\mid n} 2^{\omega(d)}$$
şeklindedir. Hesaplanması istenen toplam ise
$$F(N)=\sum_{i=2}^{N} S(i!) \pmod{M},\qquad M=1{,}000{,}000{,}087,$$
burada \(N=10^7\) gibi çok büyük bir değerdir. Her faktöriyeli ayrı ayrı çarpanlara ayırmak ya da tüm bölenleri dolaşmak fazla maliyetli olduğundan, çözüm \(S(i!)\) değerini \(S((i-1)!)\) üzerinden sadece \(i\)'nin asal çarpanlarını kullanarak günceller.
Uygulama önce \(S(n)\)'yi çarpımsal bir forma dönüştürür, sonra bu formu faktöriyel dizisi üzerinde artımlı olarak kullanır.
Şunu yazalım:
$$n=\prod_{p} p^{e_p}.$$
\(n\)'nin her böleni
$$d=\prod_{p} p^{a_p},\qquad 0\le a_p\le e_p$$
biçimindedir. \(\omega(d)\), hangi asalarda \(a_p\) pozitifse onları sayar. Bu nedenle bölen toplamı asal bazında ayrışır. Tek bir asal kuvvet \(p^e\) için yerel katkı
$$1+\underbrace{2+\cdots+2}_{e\text{ kez}}=2e+1$$
olur; çünkü üs \(0\) için katkı \(2^{\omega(1)}=1\), üsler \(1,\dots,e\) için katkı ise \(2^{\omega(p^a)}=2\)'dir.
Dolayısıyla
$$S(n)=\prod_{p^{e_p}\parallel n} (2e_p+1)$$
elde edilir. Hızlı bir kontrol olarak \(6=2^1\cdot 3^1\) için
$$S(6)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9,$$
bu da \(d=1,2,3,6\) bölenleri üzerindeki \(1+2+2+4=9\) toplamıyla aynıdır.
Faktöriyeller için
$$E_p(i)=v_p(i!)$$
tanımını yapalım. Böylece
$$i!=\prod_{p} p^{E_p(i)}$$
olur ve önceki özdeşlik
$$S(i!)=\prod_{p} \bigl(2E_p(i)+1\bigr)$$
şeklini alır. Art arda gelen iki faktöriyel için
$$i!=i\cdot (i-1)!$$
olduğundan, \(i\)'de \(p\) asalının çarpanı \(c=v_p(i)\) ise
$$E_p(i)=E_p(i-1)+c$$
yazılır. \(i\)'yi bölmeyen asalların üsleri ise hiç değişmez. Böylece her adımda yalnızca birkaç yerel çarpan güncellenir.
\(i\)'nin asal çarpanlara ayrılışı
$$i=\prod_{p^{c_p}\parallel i} p^{c_p}$$
olsun. O zaman etkilenen her asal, \(S((i-1)!)\) içindeki tek bir çarpanı değiştirir:
$$2E_p(i-1)+1 \longrightarrow 2\bigl(E_p(i-1)+c_p\bigr)+1.$$
Böylece
$$S(i!)=S((i-1)!)\prod_{p^{c_p}\parallel i}\frac{2\bigl(E_p(i-1)+c_p\bigr)+1}{2E_p(i-1)+1}$$
elde edilir. Algoritmanın özü budur. Tam çarpımı baştan hesaplamak yerine, \(i\)'nin içindeki her asal için eski tek terim çıkarılır, yeni tek terim eklenir ve \(S(i!)\)'nin çalışan değeri korunur.
Her güncellemede kullanılan tek sayılar
$$2E_p(i)+1$$
biçimindedir. Faktöriyelde en büyük üs her zaman \(2\) asalına ait olduğundan, her \(p\) asalı ve her \(i\le N\) için
$$E_p(i)\le E_2(N)=v_2(N!)$$
geçerlidir. Bu yüzden karşılaşılabilecek tüm tek terimler en fazla
$$B=2v_2(N!)+1$$
olur. Uygulama bu sınıra kadar modüler tersleri bir kez önceden hesaplar ve oran güncellemelerinde tekrar kullanır. Böylece formüldeki her bölme sabit maliyetli bir modüler çarpıma dönüşür.
\(N=5\) alalım. Faktöriyel değerleri şu şekilde ilerler.
\(2!=2\) için sayı \(2^1\) olduğundan
$$S(2!)=2\cdot 1+1=3.$$
\(3!=6=2^1\cdot 3^1\) için
$$S(3!)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9.$$
Şimdi \(3!\)'ten \(4!\)'e geçelim. \(4=2^2\) olduğu için \(2\)'nin üssü \(1\)'den \(3\)'e çıkar. Yani \(2\) asalına ait yerel çarpan \(3\)'ten \(7\)'ye döner:
$$S(4!)=S(3!)\cdot \frac{7}{3}=9\cdot \frac{7}{3}=21.$$
Sonra \(5=5^1\) gelir; \(5\) asalı ilk kez üs \(1\) ile ortaya çıkar. Onun yerel çarpanı \(1\)'den \(3\)'e geçtiği için
$$S(5!)=S(4!)\cdot 3=21\cdot 3=63.$$
Dolayısıyla
$$F(5)=S(2!)+S(3!)+S(4!)+S(5!)=3+9+21+63=96.$$
Bu örnek, neden her faktöriyeli yeniden çarpanlara ayırmak yerine artımlı çarpım güncellemesinin kullanıldığını net biçimde gösterir.
C++, Python ve Java uygulamaları önce \(N\)'ye kadar lineer bir en küçük asal bölen tablosu kurar. Böylece her \(i\) sayısı deneme bölmesi yapılmadan, tablo bakışları ve ardışık bölmeler ile çarpanlara ayrılır.
Ayrıca tüm asallar için mevcut faktöriyel üslerini \(E_p(i!)\) tutan bir dizi ve o andaki \(S(i!)\) değerini tutan tek bir modüler çarpım saklanır. Ana döngü başlamadan önce, ileride ortaya çıkabilecek tüm \(2E_p+1\) terimlerini kapsayacak şekilde \(2v_2(N!)+1\)'e kadar ters tablosu hazırlanır.
\(2\)'den \(N\)'ye kadar her \(i\) için, \(i\)'nin çarpanlara ayrılması ilgili asalın çokluğunu \(c_p\) verir. Uygulama o asalın saklanan üssünü artırır, çalışan çarpım içindeki eski yerel terimi \(2e+1\) ile çıkarıp yeni terimi \(2(e+c_p)+1\) ile yer değiştirir ve sonunda güncel \(S(i!)\) değerini toplam cevaba ekler. Hiçbir aşamada bölen listesi ya da açık faktöriyel değeri üretilmez.
Lineer en küçük asal bölen süzgeci \(O(N)\) zaman ve \(O(N)\) bellek gerektirir. Ters tablosu da \(v_2(N!)<N\) olduğu için \(O(N)\) boyutundadır.
Tüm \(i\le N\) değerlerini bu tabloyla çarpanlara ayırmanın toplam maliyeti, yol boyunca görülen asal çarpanların çokluklu toplamıyla orantılıdır. Ortalama durumda bu \(O(N\log\log N)\), daha kaba bir üst sınırla \(O(N\log N)\) olur. Toplam bellek kullanımı \(O(N)\) seviyesinde kalır.
Sea \(\omega(n)\) el número de divisores primos distintos de \(n\). La función aritmética utilizada es
$$S(n)=\sum_{d\mid n} 2^{\omega(d)}.$$
Debemos calcular
$$F(N)=\sum_{i=2}^{N} S(i!) \pmod{M},\qquad M=1{,}000{,}000{,}087,$$
para el valor muy grande \(N=10^7\). Factorizar cada factorial por separado o enumerar todos sus divisores sería demasiado costoso, así que la idea es actualizar \(S(i!)\) a partir de \(S((i-1)!)\) usando solo los factores primos de \(i\).
Las implementaciones primero convierten \(S(n)\) en una expresión multiplicativa y luego la aplican de manera incremental a la sucesión de factoriales.
Escribimos
$$n=\prod_{p} p^{e_p}.$$
Cada divisor de \(n\) tiene la forma
$$d=\prod_{p} p^{a_p},\qquad 0\le a_p\le e_p.$$
El valor \(\omega(d)\) cuenta cuántos exponentes \(a_p\) son positivos. Por eso la suma sobre divisores se separa primo por primo. Para una sola potencia prima \(p^e\), la contribución local es
$$1+\underbrace{2+\cdots+2}_{e\text{ veces}}=2e+1,$$
porque el exponente \(0\) aporta \(2^{\omega(1)}=1\), mientras que los exponentes \(1,\dots,e\) aportan \(2^{\omega(p^a)}=2\).
Así obtenemos
$$S(n)=\prod_{p^{e_p}\parallel n} (2e_p+1).$$
Como comprobación rápida, \(6=2^1\cdot 3^1\), luego
$$S(6)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9,$$
lo cual coincide con la suma \(1+2+2+4=9\) sobre los divisores \(1,2,3,6\).
Para factoriales definimos
$$E_p(i)=v_p(i!).$$
Entonces
$$i!=\prod_{p} p^{E_p(i)}$$
y la identidad anterior pasa a ser
$$S(i!)=\prod_{p} \bigl(2E_p(i)+1\bigr).$$
Ahora comparamos factoriales consecutivos:
$$i!=i\cdot (i-1)!.$$
Si \(i\) contiene al primo \(p\) con multiplicidad \(c=v_p(i)\), entonces
$$E_p(i)=E_p(i-1)+c.$$
Los primos que no dividen a \(i\) conservan el mismo exponente. Por eso, de un paso al siguiente, solo cambian unos pocos factores locales.
Sea
$$i=\prod_{p^{c_p}\parallel i} p^{c_p}.$$
Cada primo afectado reemplaza un único factor en el producto de \(S((i-1)!)\):
$$2E_p(i-1)+1 \longrightarrow 2\bigl(E_p(i-1)+c_p\bigr)+1.$$
Por tanto,
$$S(i!)=S((i-1)!)\prod_{p^{c_p}\parallel i}\frac{2\bigl(E_p(i-1)+c_p\bigr)+1}{2E_p(i-1)+1}.$$
Esa es la idea central del algoritmo. Nunca vuelve a construir el producto completo desde cero. Solo divide por el factor impar antiguo de cada primo que aparece en \(i\), multiplica por el nuevo factor impar y mantiene actualizado un valor acumulado de \(S(i!)\).
Todas las actualizaciones usan números impares de la forma
$$2E_p(i)+1.$$
El mayor exponente en un factorial siempre corresponde al primo \(2\), así que para todo primo \(p\) y todo \(i\le N\),
$$E_p(i)\le E_2(N)=v_2(N!).$$
En consecuencia, todos los factores impares que pueden aparecer están acotados por
$$B=2v_2(N!)+1.$$
La implementación precalcula una vez los inversos modulares hasta ese límite y después los reutiliza en cada actualización por cociente. De ese modo, cada división de la fórmula se convierte en una multiplicación modular de tiempo constante.
Tomemos \(N=5\). La evolución de los factoriales es la siguiente.
Para \(2!=2\), tenemos \(2^1\), así que
$$S(2!)=2\cdot 1+1=3.$$
Para \(3!=6=2^1\cdot 3^1\),
$$S(3!)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9.$$
Ahora pasamos de \(3!\) a \(4!\). Como \(4=2^2\), el exponente de \(2\) sube de \(1\) a \(3\). El factor local del primo \(2\) cambia de \(3\) a \(7\), y por eso
$$S(4!)=S(3!)\cdot \frac{7}{3}=9\cdot \frac{7}{3}=21.$$
Después, \(5=5^1\), así que el primo \(5\) aparece por primera vez con exponente \(1\). Su factor local pasa de \(1\) a \(3\), con lo que
$$S(5!)=S(4!)\cdot 3=21\cdot 3=63.$$
Por lo tanto,
$$F(5)=S(2!)+S(3!)+S(4!)+S(5!)=3+9+21+63=96.$$
Este ejemplo muestra exactamente por qué una actualización incremental del producto es mucho más barata que factorizar cada factorial de forma independiente.
Las implementaciones en C++, Python y Java comienzan construyendo una tabla lineal del menor factor primo hasta \(N\). Esa tabla permite factorizar cada entero \(i\) mediante consultas sucesivas y divisiones repetidas, sin recurrir a división por prueba.
Además, mantienen un arreglo con los exponentes actuales \(E_p(i!)\) de cada primo \(p\), junto con un único valor modular que representa el \(S(i!)\) vigente. Antes de entrar en el bucle principal, las implementaciones precalculan la tabla de inversos hasta \(2v_2(N!)+1\), lo que cubre todos los factores impares \(2E_p+1\) que podrían aparecer.
Para cada \(i\) entre \(2\) y \(N\), la factorización de \(i\) entrega la multiplicidad \(c_p\) de cada primo que lo divide. La implementación actualiza el exponente almacenado de ese primo, reemplaza dentro del producto acumulado el factor antiguo \(2e+1\) por el nuevo factor \(2(e+c_p)+1\), y luego suma el \(S(i!)\) actualizado al total acumulado. En ningún momento se construye una lista de divisores ni el valor explícito del factorial.
La criba lineal del menor factor primo cuesta \(O(N)\) tiempo y \(O(N)\) memoria. La tabla de inversos también tiene tamaño \(O(N)\), ya que \(v_2(N!)<N\).
Factorizar todos los \(i\le N\) mediante esa tabla requiere un tiempo total proporcional al número total de factores primos contados con multiplicidad que aparecen en el proceso. En promedio esto es \(O(N\log\log N)\), con una cota superior más gruesa de \(O(N\log N)\). El uso total de memoria se mantiene en \(O(N)\).
记 \(\omega(n)\) 为 \(n\) 的不同素因子个数。题目中的算术函数是
$$S(n)=\sum_{d\mid n} 2^{\omega(d)}.$$
我们需要计算
$$F(N)=\sum_{i=2}^{N} S(i!) \pmod{M},\qquad M=1{,}000{,}000{,}087,$$
其中 \(N=10^7\) 非常大。无论是把每个阶乘单独分解质因数，还是枚举它的所有因子，代价都过高。因此真正可行的做法，是在从 \((i-1)!\) 走到 \(i!\) 时，只根据 \(i\) 的素因子对 \(S(i!)\) 做增量更新。
实现先把 \(S(n)\) 写成一个完全乘法化的形式，然后把这个形式逐步应用到阶乘序列上。
设
$$n=\prod_{p} p^{e_p}.$$
那么 \(n\) 的任意因子都可以写成
$$d=\prod_{p} p^{a_p},\qquad 0\le a_p\le e_p.$$
\(\omega(d)\) 统计的是其中有多少个 \(a_p\) 为正。因此，求和可以按素数逐个拆开。对单个素数幂 \(p^e\) 来看，局部贡献就是
$$1+\underbrace{2+\cdots+2}_{e\text{ 次}}=2e+1,$$
因为指数为 \(0\) 时贡献 \(2^{\omega(1)}=1\)，而指数为 \(1,\dots,e\) 时对应的因子 \(p^a\) 都恰好有一个不同素因子，所以贡献都是 \(2\)。
于是得到
$$S(n)=\prod_{p^{e_p}\parallel n} (2e_p+1).$$
例如 \(6=2^1\cdot 3^1\)，因此
$$S(6)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9,$$
这与直接按因子 \(1,2,3,6\) 求和得到的 \(1+2+2+4=9\) 完全一致。
对阶乘，定义
$$E_p(i)=v_p(i!),$$
于是
$$i!=\prod_{p} p^{E_p(i)}.$$
代入上面的结论，就有
$$S(i!)=\prod_{p} \bigl(2E_p(i)+1\bigr).$$
接着比较相邻两个阶乘：
$$i!=i\cdot (i-1)!.$$
如果素数 \(p\) 在 \(i\) 中的重数是 \(c=v_p(i)\)，那么
$$E_p(i)=E_p(i-1)+c.$$
不整除 \(i\) 的那些素数，其指数保持不变。所以从 \((i-1)!\) 过渡到 \(i!\) 时，真正变化的只是一小部分局部因子。
设
$$i=\prod_{p^{c_p}\parallel i} p^{c_p}.$$
那么每个受影响的素数，都会把 \(S((i-1)!)\) 乘积中的一个因子替换掉：
$$2E_p(i-1)+1 \longrightarrow 2\bigl(E_p(i-1)+c_p\bigr)+1.$$
因此有
$$S(i!)=S((i-1)!)\prod_{p^{c_p}\parallel i}\frac{2\bigl(E_p(i-1)+c_p\bigr)+1}{2E_p(i-1)+1}.$$
这就是整个算法的核心。它从不重新计算完整乘积，而是只针对 \(i\) 的每个素因子，把旧的奇数因子除掉，再把新的奇数因子乘进去，从而维护一个运行中的 \(S(i!)\) 值。
所有更新里出现的分母和分子，都是形如
$$2E_p(i)+1$$
的奇数。在阶乘中，最大的指数总是来自素数 \(2\)，所以对任意素数 \(p\) 和任意 \(i\le N\)，都有
$$E_p(i)\le E_2(N)=v_2(N!).$$
因此，程序运行过程中可能出现的所有奇数因子都不会超过
$$B=2v_2(N!)+1.$$
实现只需一次性预处理到这个上界的模逆元，之后每次做比例更新时直接查表即可。这样，公式里的“除以旧因子”就变成了常数时间的模乘。
取 \(N=5\)。阶乘项的演化如下。
先看 \(2!=2\)，即 \(2^1\)，所以
$$S(2!)=2\cdot 1+1=3.$$
再看 \(3!=6=2^1\cdot 3^1\)，于是
$$S(3!)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9.$$
从 \(3!\) 到 \(4!\) 时，因为 \(4=2^2\)，素数 \(2\) 的指数从 \(1\) 升到 \(3\)。也就是说，局部因子从 \(3\) 变成 \(7\)，因此
$$S(4!)=S(3!)\cdot \frac{7}{3}=9\cdot \frac{7}{3}=21.$$
再从 \(4!\) 到 \(5!\)，因为 \(5=5^1\)，素数 \(5\) 第一次出现，局部因子从 \(1\) 变成 \(3\)，于是
$$S(5!)=S(4!)\cdot 3=21\cdot 3=63.$$
所以
$$F(5)=S(2!)+S(3!)+S(4!)+S(5!)=3+9+21+63=96.$$
这个例子非常直观地说明了：与其每一步重新分解整个阶乘，不如只维护那些真正发生变化的局部因子。
C++、Python 和 Java 实现都会先构造一个到 \(N\) 为止的线性最小素因子表。这样每个整数 \(i\) 都可以通过不断查表和整除来分解，而不需要试除。
同时，程序维护一个数组来保存当前阶乘中各个素数的指数 \(E_p(i!)\)，再维护一个单独的运行值，表示当前的 \(S(i!)\)。在主循环开始前，还会预处理到 \(2v_2(N!)+1\) 为止的逆元表，因为这已经覆盖了后续所有可能出现的奇数因子 \(2E_p+1\)。
对每个 \(2\le i\le N\)，先用最小素因子表得到 \(i\) 的分解以及每个素数的重数 \(c_p\)。然后更新该素数在当前阶乘中的指数，把运行乘积里的旧因子 \(2e+1\) 替换成新因子 \(2(e+c_p)+1\)，最后把新的 \(S(i!)\) 加入累计答案。整个过程中既不会显式构造阶乘本身，也不会显式枚举任何因子。
线性最小素因子筛的时间复杂度是 \(O(N)\)，空间复杂度也是 \(O(N)\)。逆元表同样是 \(O(N)\) 级别，因为 \(v_2(N!)<N\)。
利用最小素因子表分解所有 \(i\le N\) 的总耗时，与整个过程中遇到的带重数素因子总数成正比。平均情况下这是 \(O(N\log\log N)\)，更粗略的上界可以写成 \(O(N\log N)\)。总空间复杂度保持在 \(O(N)\)。
Пусть \(\omega(n)\) обозначает число различных простых делителей числа \(n\). В задаче используется арифметическая функция
$$S(n)=\sum_{d\mid n} 2^{\omega(d)}.$$
Нужно вычислить
$$F(N)=\sum_{i=2}^{N} S(i!) \pmod{M},\qquad M=1{,}000{,}000{,}087,$$
для очень большого значения \(N=10^7\). Нельзя позволить себе отдельно раскладывать на множители каждый факториал или перечислять все его делители, поэтому алгоритм обновляет \(S(i!)\) из \(S((i-1)!)\), используя только простые множители числа \(i\).
Реализация сначала переводит \(S(n)\) в мультипликативную форму, а затем применяет эту формулу пошагово к последовательности факториалов.
Запишем
$$n=\prod_{p} p^{e_p}.$$
Любой делитель числа \(n\) имеет вид
$$d=\prod_{p} p^{a_p},\qquad 0\le a_p\le e_p.$$
Величина \(\omega(d)\) считает, для скольких простых чисел показатель \(a_p\) положителен. Поэтому сумма по делителям распадается по простым. Для одной простой степени \(p^e\) локальный вклад равен
$$1+\underbrace{2+\cdots+2}_{e\text{ раз}}=2e+1,$$
потому что показатель \(0\) дает \(2^{\omega(1)}=1\), а показатели \(1,\dots,e\) дают \(2^{\omega(p^a)}=2\).
Следовательно,
$$S(n)=\prod_{p^{e_p}\parallel n} (2e_p+1).$$
Проверка: \(6=2^1\cdot 3^1\), значит
$$S(6)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9,$$
что совпадает с суммой \(1+2+2+4=9\) по делителям \(1,2,3,6\).
Для факториалов введем
$$E_p(i)=v_p(i!),$$
тогда
$$i!=\prod_{p} p^{E_p(i)}.$$
Предыдущая формула принимает вид
$$S(i!)=\prod_{p} \bigl(2E_p(i)+1\bigr).$$
Теперь сравним соседние факториалы:
$$i!=i\cdot (i-1)!.$$
Если простое \(p\) входит в \(i\) с кратностью \(c=v_p(i)\), то
$$E_p(i)=E_p(i-1)+c.$$
Для простых, не делящих \(i\), показатель не меняется. Значит, при переходе от \((i-1)!\) к \(i!\) изменяются только немногие локальные множители.
Пусть
$$i=\prod_{p^{c_p}\parallel i} p^{c_p}.$$
Тогда каждое затронутое простое число заменяет ровно один множитель в произведении для \(S((i-1)!)\):
$$2E_p(i-1)+1 \longrightarrow 2\bigl(E_p(i-1)+c_p\bigr)+1.$$
Отсюда следует
$$S(i!)=S((i-1)!)\prod_{p^{c_p}\parallel i}\frac{2\bigl(E_p(i-1)+c_p\bigr)+1}{2E_p(i-1)+1}.$$
Это и есть главное наблюдение. Полное произведение не пересчитывается заново. Для каждого простого из разложения \(i\) алгоритм убирает старый нечетный множитель, домножает на новый и тем самым поддерживает текущее значение \(S(i!)\).
Во всех обновлениях встречаются числа вида
$$2E_p(i)+1.$$
Максимальный показатель в факториале всегда принадлежит простому \(2\), поэтому для любого простого \(p\) и любого \(i\le N\) верно
$$E_p(i)\le E_2(N)=v_2(N!).$$
Значит, все нечетные множители, которые могут понадобиться в ходе вычисления, ограничены сверху числом
$$B=2v_2(N!)+1.$$
Реализация один раз предварительно вычисляет модульные обратные до этой границы, а затем использует их во всех дробных обновлениях. Благодаря этому каждое деление в формуле превращается в константную по времени модульную операцию умножения.
Возьмем \(N=5\). Значения для факториалов развиваются так.
Для \(2!=2\) имеем \(2^1\), значит
$$S(2!)=2\cdot 1+1=3.$$
Для \(3!=6=2^1\cdot 3^1\) получаем
$$S(3!)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9.$$
Переходим от \(3!\) к \(4!\). Так как \(4=2^2\), показатель у простого \(2\) растет с \(1\) до \(3\). Локальный множитель для простого \(2\) меняется с \(3\) на \(7\), поэтому
$$S(4!)=S(3!)\cdot \frac{7}{3}=9\cdot \frac{7}{3}=21.$$
Далее \(5=5^1\), то есть простое \(5\) появляется впервые с показателем \(1\). Его локальный множитель меняется с \(1\) на \(3\), и потому
$$S(5!)=S(4!)\cdot 3=21\cdot 3=63.$$
Следовательно,
$$F(5)=S(2!)+S(3!)+S(4!)+S(5!)=3+9+21+63=96.$$
Этот пример ясно показывает, почему инкрементальное обновление произведения намного выгоднее, чем полное разложение каждого факториала заново.
Реализации на C++, Python и Java сначала строят линейную таблицу наименьшего простого делителя для всех чисел до \(N\). Это позволяет разлагать каждое число \(i\) на множители последовательными обращениями к таблице и делениями, без пробного деления.
Дополнительно поддерживается массив текущих факториальных показателей \(E_p(i!)\) для всех простых \(p\), а также одно текущее модульное значение, равное текущему \(S(i!)\). До начала основного цикла реализации предварительно вычисляют таблицу обратных до \(2v_2(N!)+1\), поскольку этого достаточно для всех возможных нечетных множителей \(2E_p+1\).
Для каждого \(i\) от \(2\) до \(N\) разложение числа \(i\) дает кратность \(c_p\) каждого простого делителя. Затем реализация обновляет сохраненный показатель этого простого, заменяет в текущем произведении старый локальный множитель \(2e+1\) новым множителем \(2(e+c_p)+1\) и после этого прибавляет обновленное \(S(i!)\) к суммарному ответу. Ни список делителей, ни само значение факториала явно не строятся.
Линейная таблица наименьшего простого делителя строится за \(O(N)\) времени и требует \(O(N)\) памяти. Таблица обратных также имеет размер \(O(N)\), поскольку \(v_2(N!)<N\).
Разложение всех \(i\le N\) через эту таблицу требует суммарного времени, пропорционального общему числу простых множителей с кратностями, встреченных по пути. В среднем это \(O(N\log\log N)\), а более грубая верхняя оценка равна \(O(N\log N)\). Общий расход памяти остается \(O(N)\).
لتكن \(\omega(n)\) عدد القواسم الأولية المميزة للعدد \(n\). الدالة الحسابية المستخدمة في المسألة هي
$$S(n)=\sum_{d\mid n} 2^{\omega(d)}.$$
والمطلوب هو حساب
$$F(N)=\sum_{i=2}^{N} S(i!) \pmod{M},\qquad M=1{,}000{,}000{,}087,$$
عند القيمة الكبيرة جدًا \(N=10^7\). لا يمكن تحليل كل مضروب على حدة ولا تعداد جميع قواسمه، لذلك تعتمد الفكرة على تحديث \(S(i!)\) انطلاقًا من \(S((i-1)!)\) باستعمال العوامل الأولية للعدد \(i\) فقط.
تبدأ الخوارزمية بتحويل \(S(n)\) إلى صيغة ضرب multiplicative، ثم تطبق هذه الصيغة تدريجيًا على متتالية المضاريب.
نكتب
$$n=\prod_{p} p^{e_p}.$$
وأي قاسم للعدد \(n\) يمكن كتابته على الصورة
$$d=\prod_{p} p^{a_p},\qquad 0\le a_p\le e_p.$$
القيمة \(\omega(d)\) تعد عدد الأسس \(a_p\) الموجبة. لذلك ينفصل مجموع القواسم حسب كل عدد أولي على حدة. بالنسبة إلى قوة أولية واحدة \(p^e\)، يكون المجموع المحلي
$$1+\underbrace{2+\cdots+2}_{e}=2e+1,$$
لأن الأس \(0\) يعطي \(2^{\omega(1)}=1\)، بينما الأسس \(1,\dots,e\) تعطي جميعها \(2^{\omega(p^a)}=2\).
ومن ثم نحصل على
$$S(n)=\prod_{p^{e_p}\parallel n} (2e_p+1).$$
وعلى سبيل التحقق، لدينا \(6=2^1\cdot 3^1\)، لذا
$$S(6)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9,$$
وهو نفس مجموع \(1+2+2+4=9\) على القواسم \(1,2,3,6\).
بالنسبة إلى المضاريب نعرّف
$$E_p(i)=v_p(i!).$$
وعندئذ
$$i!=\prod_{p} p^{E_p(i)}.$$
فتصبح الصيغة السابقة
$$S(i!)=\prod_{p} \bigl(2E_p(i)+1\bigr).$$
والآن نقارن بين مضروبين متتاليين:
$$i!=i\cdot (i-1)!.$$
إذا كان العدد الأولي \(p\) يظهر في \(i\) بعدد مرات \(c=v_p(i)\)، فإن
$$E_p(i)=E_p(i-1)+c.$$
أما الأعداد الأولية التي لا تقسم \(i\) فلا يتغير أسها. لذلك لا تتبدل من خطوة إلى أخرى إلا عوامل محلية قليلة.
إذا كتبنا
$$i=\prod_{p^{c_p}\parallel i} p^{c_p},$$
فإن كل عدد أولي متأثر يبدل عاملًا واحدًا في حاصل ضرب \(S((i-1)!)\):
$$2E_p(i-1)+1 \longrightarrow 2\bigl(E_p(i-1)+c_p\bigr)+1.$$
ومن هنا نحصل على
$$S(i!)=S((i-1)!)\prod_{p^{c_p}\parallel i}\frac{2\bigl(E_p(i-1)+c_p\bigr)+1}{2E_p(i-1)+1}.$$
هذه هي الفكرة الأساسية في الحل. لا يعاد بناء حاصل الضرب كاملًا، بل تزال لكل عدد أولي في \(i\) القيمة الفردية القديمة ويضرب بالعامل الفردي الجديد، وبذلك نحافظ على قيمة جارية لـ \(S(i!)\).
كل تحديث يستخدم أعدادًا فردية من الصورة
$$2E_p(i)+1.$$
وأكبر أس في المضروب يكون دائمًا للعدد الأولي \(2\)، ولذلك لكل عدد أولي \(p\) ولكل \(i\le N\) لدينا
$$E_p(i)\le E_2(N)=v_2(N!).$$
إذن جميع العوامل الفردية التي قد تظهر أثناء التنفيذ محصورة بـ
$$B=2v_2(N!)+1.$$
ولهذا تقوم الشيفرة بحساب المقلوبات المعيارية حتى هذا الحد مرة واحدة، ثم تعيد استعمالها في جميع عمليات التحديث النسبية. وبهذا تتحول كل قسمة في الصيغة السابقة إلى ضرب معياري بزمن ثابت.
لنأخذ \(N=5\). تتطور قيم المضروب كما يلي.
لدينا \(2!=2\)، أي \(2^1\)، ومن ثم
$$S(2!)=2\cdot 1+1=3.$$
ولأن \(3!=6=2^1\cdot 3^1\)، نحصل على
$$S(3!)=(2\cdot 1+1)(2\cdot 1+1)=3\cdot 3=9.$$
عند الانتقال من \(3!\) إلى \(4!\)، بما أن \(4=2^2\)، يرتفع أس العدد \(2\) من \(1\) إلى \(3\). إذن العامل المحلي للعدد \(2\) يتغير من \(3\) إلى \(7\)، وبالتالي
$$S(4!)=S(3!)\cdot \frac{7}{3}=9\cdot \frac{7}{3}=21.$$
ثم يأتي \(5=5^1\)، فيظهر العدد الأولي \(5\) لأول مرة بالأس \(1\). فيتغير عامله المحلي من \(1\) إلى \(3\)، ومن ثم
$$S(5!)=S(4!)\cdot 3=21\cdot 3=63.$$
وعليه
$$F(5)=S(2!)+S(3!)+S(4!)+S(5!)=3+9+21+63=96.$$
يوضح هذا المثال عمليًا لماذا يكون تحديث حاصل الضرب تدريجيًا أرخص بكثير من إعادة تحليل كل مضروب من الصفر.
تبدأ تطبيقات C++ وPython وJava ببناء جدول خطي لأصغر قاسم أولي حتى \(N\). هذا الجدول يسمح بتحليل كل عدد \(i\) إلى عوامله الأولية عبر عمليات بحث متكررة وقسمة متتالية، من دون الاعتماد على القسمة التجريبية.
كما تحتفظ الشيفرة بمصفوفة لأسس العوامل الأولية الحالية \(E_p(i!)\)، وبقيمة معيارية واحدة تمثل \(S(i!)\) الجاري. وقبل بدء الحلقة الرئيسية، تُحسب أيضًا قيم المقلوبات حتى \(2v_2(N!)+1\)، لأن هذا الحد يكفي لتغطية كل عامل فردي من النوع \(2E_p+1\) قد يظهر لاحقًا.
لكل \(i\) من \(2\) إلى \(N\)، يعطي تحليل \(i\) عدد المرات \(c_p\) لكل عدد أولي يقسمه. بعد ذلك تحدّث الشيفرة الأس المخزن لذلك العدد الأولي، وتستبدل داخل حاصل الضرب الجاري العامل القديم \(2e+1\) بالعامل الجديد \(2(e+c_p)+1\)، ثم تضيف قيمة \(S(i!)\) المحدثة إلى المجموع التراكمي. لا تُنشأ قائمة قواسم، ولا يُبنى المضروب نفسه صراحة في أي مرحلة.
بناء جدول أصغر قاسم أولي خطيًا يحتاج إلى \(O(N)\) زمنًا و\(O(N)\) ذاكرة. أما جدول المقلوبات فحجمه أيضًا \(O(N)\)، لأن \(v_2(N!)<N\).
تحليل جميع الأعداد \(i\le N\) بواسطة هذا الجدول يحتاج زمنًا كليًا متناسبًا مع العدد الإجمالي للعوامل الأولية المحسوبة مع التكرار على امتداد التنفيذ. في المتوسط يكون ذلك \(O(N\log\log N)\)، مع حد أعلى أخشن هو \(O(N\log N)\). ويظل استهلاك الذاكرة الكلي من رتبة \(O(N)\).