For each \(n\), define
$$B_n=\prod_{k=0}^{n}\binom{n}{k},\qquad D_n=\sigma(B_n),\qquad S(N)=\sum_{n=1}^{N} D_n \pmod{10^9+7}.$$
The task is to compute \(S(20000)\). The number \(B_n\) grows far too quickly to build directly, so the useful object is not \(B_n\) itself but its prime factorization. Once the exponent of every prime in \(B_n\) is known, the divisor-sum function \(\sigma\) becomes a clean multiplicative product.
The C++, Python, and Java implementations all follow the same strategy: rewrite \(B_n\) in factorial form, describe each prime exponent exactly, derive an update rule from \(n-1\) to \(n\), and then convert the resulting factorization into \(D_n\).
Each factor satisfies
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
Multiplying over all \(k=0,1,\dots,n\) gives
$$B_n=\prod_{k=0}^{n}\binom{n}{k}=\frac{(n!)^{n+1}}{\left(\prod_{j=0}^{n} j!\right)^2}.$$
The numerator contributes \(n+1\) copies of \(n!\). The denominator contains one copy of every \(k!\) and one copy of every \((n-k)!\), which is the same list reversed, so the whole denominator becomes the square of \(\prod_{j=0}^{n} j!\).
Fix a prime \(p\). Let
$$A_{n,p}=v_p(n!),\qquad T_{n,p}=\sum_{j=0}^{n} A_{j,p},$$
where \(v_p(m)\) is the exponent of \(p\) in \(m\). Equivalently, \(A_{n,p}\) is the quantity described by Legendre's formula.
If \(e_{n,p}=v_p(B_n)\), then the factorial identity above yields
$$e_{n,p}=(n+1)A_{n,p}-2T_{n,p}.$$
So the entire problem reduces to keeping track of these exponents for all primes \(p\le n\).
The implementations do not recompute \(e_{n,p}\) from scratch. Instead they update it incrementally. Since
$$A_{n,p}=A_{n-1,p}+v_p(n),\qquad T_{n,p}=T_{n-1,p}+A_{n,p},$$
we get
$$\begin{aligned} e_{n,p}-e_{n-1,p} &= (n+1)A_{n,p}-2T_{n,p}-\left(nA_{n-1,p}-2T_{n-1,p}\right) \\ &= (n-1)v_p(n)-A_{n-1,p}. \end{aligned}$$
This formula is the heart of the solution. Every prime receives the subtractive term \(-A_{n-1,p}\), and only primes dividing \(n\) receive the additive correction \((n-1)v_p(n)\).
Once
$$B_n=\prod_{p\le n} p^{e_{n,p}}$$
is known, multiplicativity of the divisor-sum function gives
$$D_n=\sigma(B_n)=\prod_{p\le n}\sigma\!\left(p^{e_{n,p}}\right)=\prod_{p\le n}\frac{p^{e_{n,p}+1}-1}{p-1} \pmod{10^9+7}.$$
That is why the implementations maintain \(p^{e_{n,p}+1}\) modulo \(10^9+7\) rather than the bare exponent itself. Because the modulus is prime and much larger than every prime used here, both \(p\) and \(p-1\) have modular inverses.
From the product definition,
$$B_5=\binom{5}{0}\binom{5}{1}\binom{5}{2}\binom{5}{3}\binom{5}{4}\binom{5}{5}=1\cdot 5\cdot 10\cdot 10\cdot 5\cdot 1=2500.$$
The valuation formula recovers the same factorization. For the relevant primes,
$$\begin{aligned} A_{5,2}&=v_2(5!)=3, & T_{5,2}&=0+0+1+1+3+3=8, & e_{5,2}&=6\cdot 3-2\cdot 8=2, \\ A_{5,3}&=v_3(5!)=1, & T_{5,3}&=0+0+0+1+1+1=3, & e_{5,3}&=6\cdot 1-2\cdot 3=0, \\ A_{5,5}&=v_5(5!)=1, & T_{5,5}&=0+0+0+0+0+1=1, & e_{5,5}&=6\cdot 1-2\cdot 1=4. \end{aligned}$$
So
$$B_5=2^2\cdot 5^4,$$
and therefore
$$D_5=\frac{2^3-1}{2-1}\cdot\frac{5^5-1}{5-1}=7\cdot 781=5467.$$
The earlier values are \(D_1=1\), \(D_2=3\), \(D_3=13\), and \(D_4=252\), so
$$S(5)=1+3+13+252+5467=5736,$$
which matches the checkpoint used by the implementations.
The implementations begin with a smallest-prime-factor sieve up to \(N\). This provides the full prime list and allows each new integer \(n\) to be factorized quickly.
For every prime, the implementation stores two modular states. One state represents the inverse of the prime power already accumulated in the current factorial valuation, and the other represents the current value of \(p^{e_{n,p}+1}\). At the start of the transition from \(n-1\) to \(n\), every stored prime-power term is multiplied by the inverse factorial contribution corresponding to \(-A_{n-1,p}\).
Then the current integer \(n\) is factorized. If \(p^v\) divides \(n\), the stored value for that prime is multiplied by \(p^{(n-1)v}\), and the stored inverse factorial contribution is extended by another factor of \(p^{-v}\). After these updates, the maintained prime-power term is exactly \(p^{e_{n,p}+1}\).
Finally, the implementation evaluates
$$D_n=\prod_{p}\frac{p^{e_{n,p}+1}-1}{p-1}\pmod{10^9+7}$$
across the prime list and adds the result to the running total. Primes larger than the current \(n\) still have exponent \(0\), so their factor is \(1\) and they do not affect the answer.
The smallest-prime-factor sieve is built in \(O(N)\) time and uses \(O(N)\) memory. Factoring each \(n\) through that sieve costs \(O(\Omega(n))\) in the straightforward bound, with total average-order work \(O(N\log\log N)\). In these implementations the dominant term is the full prime scan performed for each \(n\): once to apply the common recurrence factor and once to assemble \(D_n\). Therefore the overall running time is \(O(N\pi(N)+N\log\log N)\), usually summarized as \(O(N\pi(N))\), and the extra memory beyond the sieve is \(O(\pi(N))\).
Für jedes \(n\) definieren wir
$$B_n=\prod_{k=0}^{n}\binom{n}{k},\qquad D_n=\sigma(B_n),\qquad S(N)=\sum_{n=1}^{N} D_n \pmod{10^9+7}.$$
Gesucht ist \(S(20000)\). Die Zahl \(B_n\) wird extrem schnell riesig, daher darf man sie nicht direkt aufbauen. Stattdessen betrachtet die Lösung nur die Primfaktorzerlegung von \(B_n\). Kennt man alle Primexponenten, folgt \(\sigma(B_n)\) sofort aus einer multiplikativen Formel.
Die C++-, Python- und Java-Implementierungen verwenden denselben Plan: Zuerst wird \(B_n\) in eine Fakultätsform gebracht, dann werden die Primexponenten exakt beschrieben, daraus eine Übergangsformel von \(n-1\) nach \(n\) abgeleitet und schließlich \(D_n\) aus diesen Exponenten zusammengesetzt.
Jeder Faktor erfüllt
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
Multipliziert man über alle \(k=0,1,\dots,n\), so erhält man
$$B_n=\prod_{k=0}^{n}\binom{n}{k}=\frac{(n!)^{n+1}}{\left(\prod_{j=0}^{n} j!\right)^2}.$$
Im Zähler stehen \(n+1\) Kopien von \(n!\). Im Nenner erscheint einmal jede Fakultät \(k!\) und einmal jede Fakultät \((n-k)!\); das ist dieselbe Liste nur in umgekehrter Reihenfolge, also das Quadrat von \(\prod_{j=0}^{n} j!\).
Fixiere eine Primzahl \(p\). Setze
$$A_{n,p}=v_p(n!),\qquad T_{n,p}=\sum_{j=0}^{n} A_{j,p},$$
wobei \(v_p(m)\) den Exponenten von \(p\) in \(m\) bezeichnet. \(A_{n,p}\) ist also genau die Größe aus der Legendre-Formel.
Mit \(e_{n,p}=v_p(B_n)\) folgt aus der obigen Identität
$$e_{n,p}=(n+1)A_{n,p}-2T_{n,p}.$$
Damit ist das Problem darauf reduziert, diese Exponenten für alle Primzahlen \(p\le n\) effizient fortzuschreiben.
Die Implementierungen berechnen \(e_{n,p}\) nicht jedes Mal neu. Stattdessen wird inkrementell aktualisiert. Aus
$$A_{n,p}=A_{n-1,p}+v_p(n),\qquad T_{n,p}=T_{n-1,p}+A_{n,p}$$
ergibt sich
$$\begin{aligned} e_{n,p}-e_{n-1,p} &= (n+1)A_{n,p}-2T_{n,p}-\left(nA_{n-1,p}-2T_{n-1,p}\right) \\ &= (n-1)v_p(n)-A_{n-1,p}. \end{aligned}$$
Genau diese Formel treibt die Lösung an. Jede Primzahl erhält den negativen Anteil \(-A_{n-1,p}\), und nur Primzahlen, die \(n\) teilen, erhalten zusätzlich den positiven Anteil \((n-1)v_p(n)\).
Sobald
$$B_n=\prod_{p\le n} p^{e_{n,p}}$$
bekannt ist, liefert die Multiplikativität der Teilerfunktion
$$D_n=\sigma(B_n)=\prod_{p\le n}\sigma\!\left(p^{e_{n,p}}\right)=\prod_{p\le n}\frac{p^{e_{n,p}+1}-1}{p-1} \pmod{10^9+7}.$$
Darum speichern die Implementierungen \(p^{e_{n,p}+1}\) modulo \(10^9+7\) statt des nackten Exponenten. Da der Modulus prim und deutlich größer als jede hier vorkommende Primzahl ist, besitzen sowohl \(p\) als auch \(p-1\) modulare Inversen.
Direkt aus der Definition folgt
$$B_5=\binom{5}{0}\binom{5}{1}\binom{5}{2}\binom{5}{3}\binom{5}{4}\binom{5}{5}=1\cdot 5\cdot 10\cdot 10\cdot 5\cdot 1=2500.$$
Die Bewertungsformel liefert dieselbe Zerlegung. Für die relevanten Primzahlen gilt
$$\begin{aligned} A_{5,2}&=v_2(5!)=3, & T_{5,2}&=0+0+1+1+3+3=8, & e_{5,2}&=6\cdot 3-2\cdot 8=2, \\ A_{5,3}&=v_3(5!)=1, & T_{5,3}&=0+0+0+1+1+1=3, & e_{5,3}&=6\cdot 1-2\cdot 3=0, \\ A_{5,5}&=v_5(5!)=1, & T_{5,5}&=0+0+0+0+0+1=1, & e_{5,5}&=6\cdot 1-2\cdot 1=4. \end{aligned}$$
Also
$$B_5=2^2\cdot 5^4,$$
und damit
$$D_5=\frac{2^3-1}{2-1}\cdot\frac{5^5-1}{5-1}=7\cdot 781=5467.$$
Die früheren Werte sind \(D_1=1\), \(D_2=3\), \(D_3=13\) und \(D_4=252\), also
$$S(5)=1+3+13+252+5467=5736,$$
genau der Kontrollwert aus den Implementierungen.
Am Anfang steht ein SPF-Sieb bis \(N\) (smallest prime factor). Damit erhält man die Primzahlliste und kann jede neue Zahl \(n\) schnell faktorisieren.
Für jede Primzahl werden zwei modulare Zustände gehalten. Einer repräsentiert die inverse Primzahlpotenz, die bereits in der aktuellen Fakultätsbewertung enthalten ist, der andere repräsentiert den aktuellen Wert von \(p^{e_{n,p}+1}\). Beim Übergang von \(n-1\) zu \(n\) wird zunächst jeder gespeicherte Primzahlterm mit dem inversen Fakultätsbeitrag multipliziert, der den Anteil \(-A_{n-1,p}\) realisiert.
Danach wird die aktuelle Zahl \(n\) faktorisiert. Falls \(p^v\) in \(n\) enthalten ist, wird der gespeicherte Term für diese Primzahl mit \(p^{(n-1)v}\) multipliziert und der inverse Fakultätszustand um einen weiteren Faktor \(p^{-v}\) ergänzt. Nach diesen Aktualisierungen ist der gespeicherte Primzahlterm exakt \(p^{e_{n,p}+1}\).
Zum Schluss berechnet die Implementierung
$$D_n=\prod_{p}\frac{p^{e_{n,p}+1}-1}{p-1}\pmod{10^9+7}$$
über die Primzahlliste und addiert den Wert zur laufenden Summe. Primzahlen größer als das aktuelle \(n\) haben weiterhin Exponent \(0\), ihr Faktor ist also \(1\).
Das SPF-Sieb wird in \(O(N)\) Zeit aufgebaut und benötigt \(O(N)\) Speicher. Die Faktorisierung jedes \(n\) über dieses Sieb kostet in der einfachen Schranke \(O(\Omega(n))\), insgesamt also im Durchschnitt \(O(N\log\log N)\). Dominant ist hier der vollständige Primzahldurchlauf pro Schritt: einmal für den gemeinsamen Rekurrenzfaktor und einmal zum Zusammensetzen von \(D_n\). Daher beträgt die Gesamtlaufzeit \(O(N\pi(N)+N\log\log N)\), meist kurz als \(O(N\pi(N))\) notiert, und der zusätzliche Speicher jenseits des Siebs ist \(O(\pi(N))\).
Her \(n\) için
$$B_n=\prod_{k=0}^{n}\binom{n}{k},\qquad D_n=\sigma(B_n),\qquad S(N)=\sum_{n=1}^{N} D_n \pmod{10^9+7}$$
tanımlanır. Amaç \(S(20000)\) değerini bulmaktır. \(B_n\) doğrudan hesaplanamayacak kadar hızlı büyüdüğü için çözüm, sayının kendisini değil asal çarpan üslerini izler. Her asalın üssü bilindiğinde \(\sigma(B_n)\) çarpımsal bir formülle hemen elde edilir.
C++, Python ve Java implementasyonları aynı planı izler: önce \(B_n\) ifadesini faktöriyel cinsinden yeniden yazar, sonra asal üsleri açık bir formülle ifade eder, \(n-1\)'den \(n\)'ye geçen bir güncelleme bağıntısı çıkarır ve son olarak bu çarpanlaşmayı \(D_n\)'ye dönüştürür.
Her terim için
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$
olduğundan, tüm \(k=0,1,\dots,n\) için çarpınca
$$B_n=\prod_{k=0}^{n}\binom{n}{k}=\frac{(n!)^{n+1}}{\left(\prod_{j=0}^{n} j!\right)^2}$$
elde edilir. Pay kısmında \(n!\) tam \(n+1\) kez bulunur. Paydada ise bir kez tüm \(k!\) listesi, bir kez de ters sırayla aynı liste olan \((n-k)!\) bulunur; bu yüzden payda \(\prod_{j=0}^{n} j!\) ifadesinin karesidir.
Sabit bir asal \(p\) için
$$A_{n,p}=v_p(n!),\qquad T_{n,p}=\sum_{j=0}^{n} A_{j,p}$$
tanımını yapalım. Burada \(v_p(m)\), \(m\) sayısının içindeki \(p\) üssüdür. Yani \(A_{n,p}\), Legendre formülünün verdiği faktöriyel asal üssüdür.
\(e_{n,p}=v_p(B_n)\) dersek, yukarıdaki faktöriyel kimlikten
$$e_{n,p}=(n+1)A_{n,p}-2T_{n,p}$$
çıkar. Böylece problem, tüm \(p\le n\) asalları için bu üsleri verimli biçimde güncellemeye indirgenir.
İmplementasyonlar \(e_{n,p}\)'yi her seferinde sıfırdan hesaplamaz. Bunun yerine artımlı güncelleme kullanır. Çünkü
$$A_{n,p}=A_{n-1,p}+v_p(n),\qquad T_{n,p}=T_{n-1,p}+A_{n,p}$$
olduğundan
$$\begin{aligned} e_{n,p}-e_{n-1,p} &= (n+1)A_{n,p}-2T_{n,p}-\left(nA_{n-1,p}-2T_{n-1,p}\right) \\ &= (n-1)v_p(n)-A_{n-1,p}. \end{aligned}$$
Çözümün kilit noktası budur. Her asal için ortak bir \(-A_{n-1,p}\) azaltması vardır; yalnızca \(n\)'yi bölen asallar ise buna ek olarak \((n-1)v_p(n)\) kadar pozitif katkı alır.
Eğer
$$B_n=\prod_{p\le n} p^{e_{n,p}}$$
ise, bölen toplam fonksiyonunun çarpımsallığından
$$D_n=\sigma(B_n)=\prod_{p\le n}\sigma\!\left(p^{e_{n,p}}\right)=\prod_{p\le n}\frac{p^{e_{n,p}+1}-1}{p-1} \pmod{10^9+7}$$
olur. Bu yüzden implementasyonlar çıplak üssü değil, doğrudan \(p^{e_{n,p}+1}\) değerini mod \(10^9+7\) altında tutar. Modül asal olduğu ve kullanılan tüm \(p\) değerlerinden büyük olduğu için hem \(p\)'nin hem de \(p-1\)'in modüler tersi vardır.
Tanımdan doğrudan
$$B_5=\binom{5}{0}\binom{5}{1}\binom{5}{2}\binom{5}{3}\binom{5}{4}\binom{5}{5}=1\cdot 5\cdot 10\cdot 10\cdot 5\cdot 1=2500$$
bulunur. Üs formülü aynı çarpanlaşmayı verir. Gerekli asallar için
$$\begin{aligned} A_{5,2}&=v_2(5!)=3, & T_{5,2}&=0+0+1+1+3+3=8, & e_{5,2}&=6\cdot 3-2\cdot 8=2, \\ A_{5,3}&=v_3(5!)=1, & T_{5,3}&=0+0+0+1+1+1=3, & e_{5,3}&=6\cdot 1-2\cdot 3=0, \\ A_{5,5}&=v_5(5!)=1, & T_{5,5}&=0+0+0+0+0+1=1, & e_{5,5}&=6\cdot 1-2\cdot 1=4. \end{aligned}$$
Dolayısıyla
$$B_5=2^2\cdot 5^4,$$
ve buradan
$$D_5=\frac{2^3-1}{2-1}\cdot\frac{5^5-1}{5-1}=7\cdot 781=5467$$
çıkar. Önceki değerler \(D_1=1\), \(D_2=3\), \(D_3=13\) ve \(D_4=252\) olduğundan
$$S(5)=1+3+13+252+5467=5736,$$
ki bu, implementasyonların kullandığı doğrulama değeridir.
İlk adım, \(N\)'e kadar bir en küçük asal bölen eleği kurmaktır. Böylece asal listesi elde edilir ve her yeni \(n\) değeri hızlıca asal çarpanlarına ayrılabilir.
Her asal için iki modüler durum tutulur. Birincisi, mevcut faktöriyel asal üssünün tersini temsil eden birikimli çarpandır. İkincisi, o anki \(p^{e_{n,p}+1}\) değeridir. Döngü \(n-1\)'den \(n\)'ye ilerlerken önce her asal için saklanan üs terimi, \(-A_{n-1,p}\) katkısını uygulayan ortak ters çarpanla güncellenir.
Ardından güncel \(n\) sayısı çarpanlarına ayrılır. Eğer \(p^v\) sayısı \(n\)'yi bölüyorsa, ilgili saklanan terim \(p^{(n-1)v}\) ile çarpılır ve ters faktöriyel durumu bir ek \(p^{-v}\) faktörüyle genişletilir. Bu işlemler tamamlandığında elde tutulan asal-kuvvet terimi tam olarak \(p^{e_{n,p}+1}\) olur.
Son olarak implementasyon
$$D_n=\prod_{p}\frac{p^{e_{n,p}+1}-1}{p-1}\pmod{10^9+7}$$
ifadesini asal listesi üzerinde hesaplar ve sonucu toplam cevaba ekler. Güncel \(n\)'den büyük asalların üssü hâlâ \(0\) olduğu için katkıları \(1\)'dir.
En küçük asal bölen eleği \(O(N)\) zamanda kurulur ve \(O(N)\) bellek kullanır. Her \(n\)'in bu elek üzerinden çarpanlara ayrılması, temel üst sınırda \(O(\Omega(n))\) maliyetlidir; toplam ortalama düzen \(O(N\log\log N)\) olur. Bu implementasyonlarda baskın terim, her \(n\) adımında tüm asal listesinin taranmasıdır: bir kez ortak bağıntı çarpanını uygulamak, bir kez de \(D_n\)'yi oluşturmak için. Bu yüzden toplam süre \(O(N\pi(N)+N\log\log N)\), pratikte kısaca \(O(N\pi(N))\), ek bellek ise elek dışında \(O(\pi(N))\) düzeyindedir.
Para cada \(n\) se define
$$B_n=\prod_{k=0}^{n}\binom{n}{k},\qquad D_n=\sigma(B_n),\qquad S(N)=\sum_{n=1}^{N} D_n \pmod{10^9+7}.$$
Hay que calcular \(S(20000)\). El valor de \(B_n\) crece demasiado deprisa como para construirse de manera directa, así que la clave es trabajar con su factorización prima. Una vez conocidos los exponentes primos de \(B_n\), la función suma de divisores \(\sigma\) se obtiene mediante un producto multiplicativo muy manejable.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea: reescribir \(B_n\) en términos de factoriales, describir sus exponentes primos, deducir una recurrencia al pasar de \(n-1\) a \(n\) y convertir esa información en \(D_n\).
Cada factor cumple
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
Al multiplicar para \(k=0,1,\dots,n\), resulta
$$B_n=\prod_{k=0}^{n}\binom{n}{k}=\frac{(n!)^{n+1}}{\left(\prod_{j=0}^{n} j!\right)^2}.$$
En el numerador aparecen \(n+1\) copias de \(n!\). En el denominador aparece una vez cada \(k!\) y una vez cada \((n-k)!\); ambas listas son la misma recorrida en sentidos opuestos, por eso el denominador es el cuadrado de \(\prod_{j=0}^{n} j!\).
Fijemos un primo \(p\). Definimos
$$A_{n,p}=v_p(n!),\qquad T_{n,p}=\sum_{j=0}^{n} A_{j,p},$$
donde \(v_p(m)\) es el exponente de \(p\) en \(m\). Dicho de otro modo, \(A_{n,p}\) es exactamente la cantidad descrita por la fórmula de Legendre.
Si llamamos \(e_{n,p}=v_p(B_n)\), la identidad factorial anterior da
$$e_{n,p}=(n+1)A_{n,p}-2T_{n,p}.$$
Así, el problema se reduce a mantener estos exponentes para todos los primos \(p\le n\).
Las implementaciones no recalculan \(e_{n,p}\) desde cero en cada paso. Usan una actualización incremental. Como
$$A_{n,p}=A_{n-1,p}+v_p(n),\qquad T_{n,p}=T_{n-1,p}+A_{n,p},$$
se obtiene
$$\begin{aligned} e_{n,p}-e_{n-1,p} &= (n+1)A_{n,p}-2T_{n,p}-\left(nA_{n-1,p}-2T_{n-1,p}\right) \\ &= (n-1)v_p(n)-A_{n-1,p}. \end{aligned}$$
Esta identidad es el núcleo del método. Cada primo recibe el término negativo \(-A_{n-1,p}\), y solo los primos que dividen a \(n\) reciben además la corrección positiva \((n-1)v_p(n)\).
Una vez que
$$B_n=\prod_{p\le n} p^{e_{n,p}}$$
está determinado, la multiplicatividad de \(\sigma\) da
$$D_n=\sigma(B_n)=\prod_{p\le n}\sigma\!\left(p^{e_{n,p}}\right)=\prod_{p\le n}\frac{p^{e_{n,p}+1}-1}{p-1} \pmod{10^9+7}.$$
Por eso las implementaciones mantienen \(p^{e_{n,p}+1}\) módulo \(10^9+7\) en lugar del exponente desnudo. Como el módulo es primo y mucho mayor que cualquiera de los primos usados aquí, tanto \(p\) como \(p-1\) son invertibles módulo \(10^9+7\).
Desde la definición,
$$B_5=\binom{5}{0}\binom{5}{1}\binom{5}{2}\binom{5}{3}\binom{5}{4}\binom{5}{5}=1\cdot 5\cdot 10\cdot 10\cdot 5\cdot 1=2500.$$
La fórmula de valuaciones recupera la misma factorización. Para los primos relevantes,
$$\begin{aligned} A_{5,2}&=v_2(5!)=3, & T_{5,2}&=0+0+1+1+3+3=8, & e_{5,2}&=6\cdot 3-2\cdot 8=2, \\ A_{5,3}&=v_3(5!)=1, & T_{5,3}&=0+0+0+1+1+1=3, & e_{5,3}&=6\cdot 1-2\cdot 3=0, \\ A_{5,5}&=v_5(5!)=1, & T_{5,5}&=0+0+0+0+0+1=1, & e_{5,5}&=6\cdot 1-2\cdot 1=4. \end{aligned}$$
Por lo tanto,
$$B_5=2^2\cdot 5^4,$$
y en consecuencia
$$D_5=\frac{2^3-1}{2-1}\cdot\frac{5^5-1}{5-1}=7\cdot 781=5467.$$
Los valores anteriores son \(D_1=1\), \(D_2=3\), \(D_3=13\) y \(D_4=252\), así que
$$S(5)=1+3+13+252+5467=5736,$$
exactamente el punto de control que usan las implementaciones.
Primero se construye una criba de menor factor primo hasta \(N\). Eso proporciona la lista de primos y permite factorizar rápidamente cada nuevo valor de \(n\).
Para cada primo se mantienen dos estados modulares. Uno representa la inversa de la potencia prima ya acumulada dentro de la valuación factorial actual, y el otro representa el valor actual de \(p^{e_{n,p}+1}\). Cuando el bucle avanza de \(n-1\) a \(n\), cada término primo almacenado se multiplica primero por la contribución inversa que implementa el término \(-A_{n-1,p}\).
Después se factoriza el entero \(n\). Si \(p^v\) divide a \(n\), el valor almacenado para ese primo se multiplica por \(p^{(n-1)v}\), y el estado que guarda la parte factorial inversa se amplía con otro factor \(p^{-v}\). Tras estas actualizaciones, el término mantenido coincide exactamente con \(p^{e_{n,p}+1}\).
Finalmente, la implementación evalúa
$$D_n=\prod_{p}\frac{p^{e_{n,p}+1}-1}{p-1}\pmod{10^9+7}$$
sobre la lista de primos y suma el resultado al acumulado total. Los primos mayores que el \(n\) actual siguen teniendo exponente \(0\), de modo que su contribución es \(1\).
La criba de menor factor primo se construye en \(O(N)\) tiempo y usa \(O(N)\) memoria. Factorizar cada \(n\) con esa criba cuesta \(O(\Omega(n))\) en la cota elemental, y el trabajo total de esa parte es de orden medio \(O(N\log\log N)\). En estas implementaciones domina el recorrido completo de la lista de primos para cada \(n\): una vez para aplicar el factor común de la recurrencia y otra vez para formar \(D_n\). Por ello, el tiempo total es \(O(N\pi(N)+N\log\log N)\), normalmente resumido como \(O(N\pi(N))\), y la memoria adicional aparte de la criba es \(O(\pi(N))\).
对每个 \(n\)，定义
$$B_n=\prod_{k=0}^{n}\binom{n}{k},\qquad D_n=\sigma(B_n),\qquad S(N)=\sum_{n=1}^{N} D_n \pmod{10^9+7}.$$
目标是计算 \(S(20000)\)。由于 \(B_n\) 增长极快，直接把它构造出来既不现实也没有必要。真正有用的是 \(B_n\) 的素因子分解：只要知道每个素数在 \(B_n\) 中的指数，就可以利用约数和函数 \(\sigma\) 的乘法性把 \(D_n\) 写成一个清晰的乘积。
C++、Python 和 Java 的实现采用完全相同的思路：先把 \(B_n\) 改写成阶乘形式，再精确描述每个素数的指数，接着推导从 \(n-1\) 过渡到 \(n\) 时的递推式，最后把这些指数还原成 \(D_n\)。
对每个 \(k\) 都有
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
因此对 \(k=0,1,\dots,n\) 全部相乘可得
$$B_n=\prod_{k=0}^{n}\binom{n}{k}=\frac{(n!)^{n+1}}{\left(\prod_{j=0}^{n} j!\right)^2}.$$
原因很直接：分子中出现了 \(n+1\) 份 \(n!\)；分母中一份来自所有的 \(k!\)，另一份来自所有的 \((n-k)!\)，而这第二份只是同一列阶乘按相反顺序写了一遍，所以整个分母正好是 \(\prod_{j=0}^{n} j!\) 的平方。
固定一个素数 \(p\)。定义
$$A_{n,p}=v_p(n!),\qquad T_{n,p}=\sum_{j=0}^{n} A_{j,p},$$
其中 \(v_p(m)\) 表示 \(p\) 在 \(m\) 的素因子分解中的指数。换句话说，\(A_{n,p}\) 就是 Legendre 公式所给出的阶乘中 \(p\) 的指数。
若记 \(e_{n,p}=v_p(B_n)\)，那么由上面的阶乘恒等式立刻得到
$$e_{n,p}=(n+1)A_{n,p}-2T_{n,p}.$$
于是整个问题就转化为：怎样对所有 \(p\le n\) 高效维护这些指数。
实现并不会在每一步都从头计算 \(e_{n,p}\)。它们使用增量更新。因为
$$A_{n,p}=A_{n-1,p}+v_p(n),\qquad T_{n,p}=T_{n-1,p}+A_{n,p},$$
所以
$$\begin{aligned} e_{n,p}-e_{n-1,p} &= (n+1)A_{n,p}-2T_{n,p}-\left(nA_{n-1,p}-2T_{n-1,p}\right) \\ &= (n-1)v_p(n)-A_{n-1,p}. \end{aligned}$$
这就是整个算法最核心的公式。每个素数都会统一收到一个负项 \(-A_{n-1,p}\)，而只有真正整除 \(n\) 的素数才会额外获得正项 \((n-1)v_p(n)\)。因此更新只需要知道当前 \(n\) 的素因子分解，而不必重新展开所有阶乘。
一旦写成
$$B_n=\prod_{p\le n} p^{e_{n,p}},$$
就可以利用 \(\sigma\) 的乘法性得到
$$D_n=\sigma(B_n)=\prod_{p\le n}\sigma\!\left(p^{e_{n,p}}\right)=\prod_{p\le n}\frac{p^{e_{n,p}+1}-1}{p-1} \pmod{10^9+7}.$$
这解释了为什么实现里维护的是 \(p^{e_{n,p}+1}\) 的模值，而不是单独存放指数本身。由于模数 \(10^9+7\) 是素数，而且远大于这里涉及的所有素数，所以 \(p\) 和 \(p-1\) 都存在模逆元。
直接从定义出发，
$$B_5=\binom{5}{0}\binom{5}{1}\binom{5}{2}\binom{5}{3}\binom{5}{4}\binom{5}{5}=1\cdot 5\cdot 10\cdot 10\cdot 5\cdot 1=2500.$$
赋值公式会给出同样的分解。对相关素数有
$$\begin{aligned} A_{5,2}&=v_2(5!)=3, & T_{5,2}&=0+0+1+1+3+3=8, & e_{5,2}&=6\cdot 3-2\cdot 8=2, \\ A_{5,3}&=v_3(5!)=1, & T_{5,3}&=0+0+0+1+1+1=3, & e_{5,3}&=6\cdot 1-2\cdot 3=0, \\ A_{5,5}&=v_5(5!)=1, & T_{5,5}&=0+0+0+0+0+1=1, & e_{5,5}&=6\cdot 1-2\cdot 1=4. \end{aligned}$$
因此
$$B_5=2^2\cdot 5^4,$$
于是
$$D_5=\frac{2^3-1}{2-1}\cdot\frac{5^5-1}{5-1}=7\cdot 781=5467.$$
再结合前面的 \(D_1=1\)、\(D_2=3\)、\(D_3=13\)、\(D_4=252\)，可得
$$S(5)=1+3+13+252+5467=5736,$$
这正是实现中使用的检验值。
实现首先建立一个到 \(N\) 为止的最小素因子筛。这样既能拿到完整的素数表，也能快速分解每一个新的 \(n\)。
对每个素数，程序维护两个模状态。第一个状态表示当前阶乘素数指数所对应的逆向素数幂积，第二个状态表示当前的 \(p^{e_{n,p}+1}\)。当循环从 \(n-1\) 进入 \(n\) 时，所有素数的第二个状态都会先乘上一个公共的逆向因子，这一步正对应递推式中的 \(-A_{n-1,p}\)。
接着对当前整数 \(n\) 做素因子分解。若 \(p^v\) 整除 \(n\)，那么该素数对应的幂状态还要再乘上 \(p^{(n-1)v}\)，同时第一个状态再额外乘上一个 \(p^{-v}\)。完成这些更新后，维护的值就恰好变成了 \(p^{e_{n,p}+1}\)。
最后，程序计算
$$D_n=\prod_{p}\frac{p^{e_{n,p}+1}-1}{p-1}\pmod{10^9+7}$$
并把它累加到总和中。当前 \(n\) 还没有用到的较大素数，其指数仍然是 \(0\)，所以贡献自然是 \(1\)。
最小素因子筛的建立时间是 \(O(N)\)，空间也是 \(O(N)\)。利用该筛分解每个 \(n\) 的代价，在直接意义下是 \(O(\Omega(n))\)，累计平均量级为 \(O(N\log\log N)\)。而这些实现的主导成本其实是对整张素数表的扫描：每个 \(n\) 都要扫描一次以施加公共递推因子，再扫描一次以组装 \(D_n\)。因此总时间复杂度为 \(O(N\pi(N)+N\log\log N)\)，通常简写为 \(O(N\pi(N))\)；除筛本身外，还需要 \(O(\pi(N))\) 的额外空间。
Для каждого \(n\) задаются
$$B_n=\prod_{k=0}^{n}\binom{n}{k},\qquad D_n=\sigma(B_n),\qquad S(N)=\sum_{n=1}^{N} D_n \pmod{10^9+7}.$$
Нужно вычислить \(S(20000)\). Число \(B_n\) растет слишком быстро, чтобы строить его напрямую, поэтому полезно работать не с самим \(B_n\), а с его разложением по простым. Как только известны показатели всех простых в \(B_n\), функция суммы делителей \(\sigma\) превращается в удобное мультипликативное произведение.
Реализации на C++, Python и Java используют один и тот же план: сначала переписывают \(B_n\) через факториалы, затем точно описывают показатели простых, выводят формулу перехода от \(n-1\) к \(n\), а после этого превращают полученные показатели в \(D_n\).
Для каждого \(k\)
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
Если перемножить это по всем \(k=0,1,\dots,n\), получим
$$B_n=\prod_{k=0}^{n}\binom{n}{k}=\frac{(n!)^{n+1}}{\left(\prod_{j=0}^{n} j!\right)^2}.$$
В числителе стоит \(n+1\) копий \(n!\). В знаменателе один раз появляется список всех \(k!\) и еще один раз список всех \((n-k)!\), который отличается только обратным порядком. Поэтому весь знаменатель равен квадрату \(\prod_{j=0}^{n} j!\).
Зафиксируем простое \(p\). Обозначим
$$A_{n,p}=v_p(n!),\qquad T_{n,p}=\sum_{j=0}^{n} A_{j,p},$$
где \(v_p(m)\) означает показатель простого \(p\) в разложении числа \(m\). Иными словами, \(A_{n,p}\) совпадает с величиной из формулы Лежандра.
Если \(e_{n,p}=v_p(B_n)\), то из факториальной формы сразу следует
$$e_{n,p}=(n+1)A_{n,p}-2T_{n,p}.$$
Тем самым задача сводится к эффективному поддержанию этих показателей для всех простых \(p\le n\).
Реализации не пересчитывают \(e_{n,p}\) заново на каждом шаге. Используется инкрементное обновление. Поскольку
$$A_{n,p}=A_{n-1,p}+v_p(n),\qquad T_{n,p}=T_{n-1,p}+A_{n,p},$$
получаем
$$\begin{aligned} e_{n,p}-e_{n-1,p} &= (n+1)A_{n,p}-2T_{n,p}-\left(nA_{n-1,p}-2T_{n-1,p}\right) \\ &= (n-1)v_p(n)-A_{n-1,p}. \end{aligned}$$
Именно эта формула определяет весь алгоритм. Для каждого простого есть общий отрицательный вклад \(-A_{n-1,p}\), а дополнительный положительный вклад \((n-1)v_p(n)\) появляется только у тех простых, которые делят \(n\).
Когда известно, что
$$B_n=\prod_{p\le n} p^{e_{n,p}},$$
мультипликативность \(\sigma\) дает
$$D_n=\sigma(B_n)=\prod_{p\le n}\sigma\!\left(p^{e_{n,p}}\right)=\prod_{p\le n}\frac{p^{e_{n,p}+1}-1}{p-1} \pmod{10^9+7}.$$
Поэтому в реализации хранится не сам показатель, а значение \(p^{e_{n,p}+1}\) по модулю \(10^9+7\). Поскольку модуль прост и намного больше всех простых, участвующих в вычислении, и \(p\), и \(p-1\) обратимы по модулю.
Непосредственно из определения имеем
$$B_5=\binom{5}{0}\binom{5}{1}\binom{5}{2}\binom{5}{3}\binom{5}{4}\binom{5}{5}=1\cdot 5\cdot 10\cdot 10\cdot 5\cdot 1=2500.$$
Формула показателей дает то же разложение. Для существенных простых:
$$\begin{aligned} A_{5,2}&=v_2(5!)=3, & T_{5,2}&=0+0+1+1+3+3=8, & e_{5,2}&=6\cdot 3-2\cdot 8=2, \\ A_{5,3}&=v_3(5!)=1, & T_{5,3}&=0+0+0+1+1+1=3, & e_{5,3}&=6\cdot 1-2\cdot 3=0, \\ A_{5,5}&=v_5(5!)=1, & T_{5,5}&=0+0+0+0+0+1=1, & e_{5,5}&=6\cdot 1-2\cdot 1=4. \end{aligned}$$
Следовательно,
$$B_5=2^2\cdot 5^4,$$
и потому
$$D_5=\frac{2^3-1}{2-1}\cdot\frac{5^5-1}{5-1}=7\cdot 781=5467.$$
Ранее получаются значения \(D_1=1\), \(D_2=3\), \(D_3=13\) и \(D_4=252\), так что
$$S(5)=1+3+13+252+5467=5736,$$
что в точности совпадает с контрольным значением в реализациях.
Сначала строится решето минимального простого делителя до \(N\). Оно дает список простых чисел и позволяет быстро факторизовать каждое новое \(n\).
Для каждого простого поддерживаются два модульных состояния. Одно состояние хранит обратную простую степень, уже накопленную в текущей факториальной оценке, а другое хранит текущее значение \(p^{e_{n,p}+1}\). Когда цикл переходит от \(n-1\) к \(n\), каждый сохраненный простой множитель сначала умножается на общий обратный фактор, реализующий слагаемое \(-A_{n-1,p}\).
Затем факторизуется само число \(n\). Если \(p^v\) делит \(n\), то сохраненное значение для этого простого умножается на \(p^{(n-1)v}\), а состояние, отвечающее за обратную факториальную часть, дополняется еще одним множителем \(p^{-v}\). После этого обновления поддерживаемый множитель становится ровно \(p^{e_{n,p}+1}\).
В конце вычисляется
$$D_n=\prod_{p}\frac{p^{e_{n,p}+1}-1}{p-1}\pmod{10^9+7}$$
по всему списку простых и добавляется к общей сумме. Простые, большие текущего \(n\), по-прежнему имеют показатель \(0\), поэтому их вклад равен \(1\).
Решето минимального простого делителя строится за \(O(N)\) времени и требует \(O(N)\) памяти. Факторизация каждого \(n\) через это решето занимает \(O(\Omega(n))\) в прямой оценке, а суммарно дает средний порядок \(O(N\log\log N)\). В данных реализациях доминирует полный проход по списку простых для каждого \(n\): один раз для применения общего рекуррентного множителя и еще один раз для сборки \(D_n\). Поэтому полное время работы равно \(O(N\pi(N)+N\log\log N)\), что обычно сокращают до \(O(N\pi(N))\), а дополнительная память сверх решета составляет \(O(\pi(N))\).
لكل \(n\) نعرّف
$$B_n=\prod_{k=0}^{n}\binom{n}{k},\qquad D_n=\sigma(B_n),\qquad S(N)=\sum_{n=1}^{N} D_n \pmod{10^9+7}.$$
المطلوب هو حساب \(S(20000)\). العدد \(B_n\) يكبر بسرعة هائلة، لذلك لا يفيد بناؤه مباشرة. الفكرة الصحيحة هي تتبّع التحليل إلى عوامل أولية: إذا عرفنا أس كل عدد أولي داخل \(B_n\)، فإن دالة مجموع القواسم \(\sigma\) تتحول إلى حاصل ضرب مضاعفي واضح وسهل التحديث.
تسير تطبيقات C++ وPython وJava وفق الخطة نفسها: إعادة كتابة \(B_n\) بصيغة تعتمد على المضاريب، ثم وصف أسس الأعداد الأولية بدقة، ثم اشتقاق علاقة انتقال من \(n-1\) إلى \(n\)، وأخيرًا تحويل هذه الأسس إلى \(D_n\).
لكل \(k\) لدينا
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
وبضرب هذه العلاقة لجميع \(k=0,1,\dots,n\) نحصل على
$$B_n=\prod_{k=0}^{n}\binom{n}{k}=\frac{(n!)^{n+1}}{\left(\prod_{j=0}^{n} j!\right)^2}.$$
يوجد في البسط \(n+1\) نسخة من \(n!\). أما المقام ففيه مرة جميع \(k!\) ومرة جميع \((n-k)!\)، والقائمتان متماثلتان لكن بترتيب معكوس، لذلك يصبح المقام مربع \(\prod_{j=0}^{n} j!\).
لنثبّت عددًا أوليًا \(p\). نعرّف
$$A_{n,p}=v_p(n!),\qquad T_{n,p}=\sum_{j=0}^{n} A_{j,p},$$
حيث \(v_p(m)\) هو أس \(p\) في تحليل \(m\) إلى عوامل أولية. وبالتالي فإن \(A_{n,p}\) هو بالضبط المقدار الذي تصفه صيغة ليجاندر.
إذا كتبنا \(e_{n,p}=v_p(B_n)\)، فإن الصيغة السابقة تعطي
$$e_{n,p}=(n+1)A_{n,p}-2T_{n,p}.$$
وبذلك تصبح المسألة هي كيفية صيانة هذه الأسس بكفاءة لكل الأعداد الأولية \(p\le n\).
لا تعيد التطبيقات حساب \(e_{n,p}\) من الصفر في كل مرة، بل تستخدم تحديثًا تزايديًا. لأن
$$A_{n,p}=A_{n-1,p}+v_p(n),\qquad T_{n,p}=T_{n-1,p}+A_{n,p},$$
فإننا نحصل على
$$\begin{aligned} e_{n,p}-e_{n-1,p} &= (n+1)A_{n,p}-2T_{n,p}-\left(nA_{n-1,p}-2T_{n-1,p}\right) \\ &= (n-1)v_p(n)-A_{n-1,p}. \end{aligned}$$
هذه هي العلاقة الجوهرية في الحل. كل عدد أولي يتلقى الحد السالب \(-A_{n-1,p}\)، بينما لا يتلقى الحد الموجب \((n-1)v_p(n)\) إلا إذا كان هذا الأولي يقسم \(n\).
إذا صار لدينا
$$B_n=\prod_{p\le n} p^{e_{n,p}},$$
فإن خاصية الضرب في \(\sigma\) تعطي
$$D_n=\sigma(B_n)=\prod_{p\le n}\sigma\!\left(p^{e_{n,p}}\right)=\prod_{p\le n}\frac{p^{e_{n,p}+1}-1}{p-1} \pmod{10^9+7}.$$
ولهذا السبب تحتفظ التطبيقات بالقيمة \(p^{e_{n,p}+1}\) بترديد \(10^9+7\) بدل الاحتفاظ بالأس وحده. وبما أن هذا الترديد أولي وأكبر بكثير من كل \(p\) المستخدم هنا، فإن \(p\) و\(p-1\) كلاهما يملك معكوسًا ضربيًا.
من التعريف مباشرةً نجد
$$B_5=\binom{5}{0}\binom{5}{1}\binom{5}{2}\binom{5}{3}\binom{5}{4}\binom{5}{5}=1\cdot 5\cdot 10\cdot 10\cdot 5\cdot 1=2500.$$
وصيغة الأسس تعطي التحليل نفسه. بالنسبة إلى الأعداد الأولية المهمة:
$$\begin{aligned} A_{5,2}&=v_2(5!)=3, & T_{5,2}&=0+0+1+1+3+3=8, & e_{5,2}&=6\cdot 3-2\cdot 8=2, \\ A_{5,3}&=v_3(5!)=1, & T_{5,3}&=0+0+0+1+1+1=3, & e_{5,3}&=6\cdot 1-2\cdot 3=0, \\ A_{5,5}&=v_5(5!)=1, & T_{5,5}&=0+0+0+0+0+1=1, & e_{5,5}&=6\cdot 1-2\cdot 1=4. \end{aligned}$$
إذًا
$$B_5=2^2\cdot 5^4,$$
ومن ثم
$$D_5=\frac{2^3-1}{2-1}\cdot\frac{5^5-1}{5-1}=7\cdot 781=5467.$$
أما القيم السابقة فهي \(D_1=1\) و\(D_2=3\) و\(D_3=13\) و\(D_4=252\)، ولذلك
$$S(5)=1+3+13+252+5467=5736,$$
وهذا يطابق قيمة التحقق المستخدمة في التطبيقات.
تبدأ التطبيقات ببناء غربال لأصغر عامل أولي حتى \(N\). بهذه الطريقة نحصل على قائمة الأعداد الأولية، ويمكن تحليل كل قيمة جديدة لـ \(n\) بسرعة.
لكل عدد أولي تحفظ الشيفرة حالتين بترديد المودولو. الحالة الأولى تمثل معكوس قوة أولية تراكمت بالفعل داخل تقييم المضروب الحالي، والحالة الثانية تمثل القيمة الحالية لـ \(p^{e_{n,p}+1}\). عندما تنتقل الحلقة من \(n-1\) إلى \(n\)، يُضرب حد كل عدد أولي أولًا في العامل العكسي المشترك الذي يطبق الجزء \(-A_{n-1,p}\) من علاقة التحديث.
بعد ذلك تُحلَّل القيمة الحالية \(n\) إلى عواملها الأولية. إذا كان \(p^v\) يقسم \(n\)، فإن الحد المخزّن لذلك الأولي يُضرب في \(p^{(n-1)v}\)، كما تُمدَّد الحالة الخاصة بالجزء العكسي من المضروب بعامل إضافي \(p^{-v}\). وبعد هذه الخطوات يصبح الحد المحفوظ مساويًا تمامًا لـ \(p^{e_{n,p}+1}\).
أخيرًا تحسب الشيفرة
$$D_n=\prod_{p}\frac{p^{e_{n,p}+1}-1}{p-1}\pmod{10^9+7}$$
على جميع الأعداد الأولية في القائمة، ثم تضيف النتيجة إلى المجموع التراكمي. أما الأعداد الأولية الأكبر من \(n\) الحالي فتبقى أسسها صفرًا، ولذلك يكون تأثيرها مساويًا لـ \(1\).
يُبنى غربال أصغر عامل أولي في زمن \(O(N)\) ويستخدم ذاكرة \(O(N)\). أما تحليل كل \(n\) عبر هذا الغربال فتكلفته \(O(\Omega(n))\) في التقدير المباشر، ويكون مجموع هذه الكلفة من رتبة متوسطة \(O(N\log\log N)\). لكن الكلفة المسيطرة في هذه التطبيقات هي المرور الكامل على قائمة الأعداد الأولية عند كل \(n\): مرة لتطبيق العامل المشترك في علاقة التحديث، ومرة أخرى لتجميع \(D_n\). لذلك يصبح الزمن الكلي \(O(N\pi(N)+N\log\log N)\)، ويُختصر غالبًا إلى \(O(N\pi(N))\)، بينما تكون الذاكرة الإضافية بعد الغربال \(O(\pi(N))\).