For an integer \(x\) and a smoothness bound \(b\), define the largest \(b\)-smooth divisor by
$$S_b(x)=\prod_{p^\alpha \parallel x,\ p \le b} p^\alpha.$$
Only prime powers whose prime base is at most \(b\) are kept. For example, \(2100=2^2\cdot 3\cdot 5^2\cdot 7\), so \(S_4(2100)=2^2\cdot 3=12\).
Problem 468 asks for
$$F(n)=\sum_{r=0}^{n}\sum_{b=1}^{n} S_b\!\left(\binom{n}{r}\right) \pmod{M},\qquad M=1{,}000{,}000{,}993.$$
A naive approach would refactor every binomial coefficient for every value of \(b\). The successful method instead derives a closed form for one fixed coefficient and then updates that value incrementally as \(r\) moves across the row.
The solution has two layers. First, for one fixed integer \(x\), it converts \(\sum_b S_b(x)\) into a weighted sum of prime-prefix products. Second, it exploits the recurrence between consecutive binomial coefficients so that only a few prime exponents change from one step to the next.
For each \(r\), write
$$x_r=\binom{n}{r},\qquad T_r=\sum_{b=1}^{n} S_b(x_r).$$
Then the required answer is simply
$$F(n)=\sum_{r=0}^{n} T_r \pmod{M}.$$
Every prime divisor of \(\binom{n}{r}\) is at most \(n\), so it is enough to consider the primes up to \(n\).
Let the primes up to \(n\) be
$$2=p_1<p_2<\cdots<p_t\le n,$$
and introduce the sentinel
$$p_{t+1}=n+1.$$
Write the factorization of the current binomial coefficient as
$$x_r=\prod_{i=1}^{t} p_i^{\alpha_i(r)},$$
where some exponents may be zero. If \(p_i \le b < p_{i+1}\), then the allowed primes are exactly \(p_1,\dots,p_i\), so
$$S_b(x_r)=\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
Therefore \(S_b(x_r)\) is constant on every interval between consecutive primes, and
$$T_r=1+\sum_{i=1}^{t}(p_{i+1}-p_i)\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
The coefficient \(p_{i+1}-p_i\) is the number of integers \(b\) for which the smooth divisor has exactly that prime-prefix product. This is why prime gaps become the natural weights in the implementation.
Consecutive coefficients satisfy the standard ratio
$$\binom{n}{r+1}=\binom{n}{r}\cdot \frac{n-r}{r+1}.$$
So the exponent vector \((\alpha_i(r))\) does not need to be recomputed from scratch. It changes only by the prime powers appearing in \(n-r\) and \(r+1\).
For each integer \(m\le n\), the implementation precomputes a decomposition
$$m=p^{e}u,\qquad p \nmid u,$$
where \(p\) is the smallest prime dividing \(m\). One lookup then reveals four useful pieces of information: which prime is involved, the prime-power block \(p^e\), its modular inverse, and the remaining cofactor \(u\). Repeating this stripping process factors any number into distinct prime-power blocks in a small number of table lookups.
Because \(M\) is prime and all relevant primes satisfy \(p\le n<M\), each block \(p^e\) is invertible modulo \(M\), so division by the denominator is handled as multiplication by modular inverses.
For each prime \(p_i\), define the current local factor
$$A_i(r)=p_i^{\alpha_i(r)},\qquad w_i=p_{i+1}-p_i.$$
A leaf stores the pair
$$A_i(r),\qquad w_iA_i(r).$$
For an interval \([L,R]\), store
$$P_{L,R}=\prod_{k=L}^{R} A_k(r),$$
$$Q_{L,R}=\sum_{i=L}^{R} w_i\prod_{k=L}^{i} A_k(r).$$
If the interval is split into left and right halves, the merge rule is
$$P=P_{\text{left}}P_{\text{right}},\qquad Q=Q_{\text{left}}+P_{\text{left}}Q_{\text{right}}.$$
At the root this gives
$$Q_{1,t}=\sum_{i=1}^{t} w_i\prod_{j=1}^{i} A_j(r),$$
hence
$$T_r=1+Q_{1,t}\pmod{M}.$$
Only the leaves belonging to primes dividing \(n-r\) or \(r+1\) change from one row to the next, so each transition touches only a small part of the tree.
Since
$$\binom{n}{r}=\binom{n}{n-r},$$
we also have \(T_r=T_{n-r}\). Therefore it is enough to sum from \(r=0\) to \(\lfloor n/2\rfloor\), doubling every non-central term. When \(n\) is even, the middle coefficient is added only once.
Here
$$x_4=\binom{11}{4}=330=2\cdot 3\cdot 5\cdot 11.$$
The primes up to \(11\) are \(2,3,5,7,11\), and the sentinel is \(12\). Because the exponent of \(7\) is zero, the prime-prefix products are
$$2,\quad 2\cdot 3=6,\quad 2\cdot 3\cdot 5=30,\quad 30,\quad 30\cdot 11=330.$$
Thus
$$T_4=1+(3-2)\cdot 2+(5-3)\cdot 6+(7-5)\cdot 30+(11-7)\cdot 30+(12-11)\cdot 330=525.$$
Directly listing the smooth divisors for \(b=1,\dots,11\) gives
$$1,\,2,\,6,\,6,\,30,\,30,\,30,\,30,\,30,\,30,\,330,$$
whose sum is again \(525\).
The next coefficient is
$$\binom{11}{5}=\binom{11}{4}\cdot \frac{7}{5}=462,$$
so only the prime-power contributions attached to \(5\) and \(7\) change. This illustrates why the row-to-row update is cheap. Summing the whole row symmetrically yields the checkpoint
$$F(11)=3132.$$
The C++, Python, and Java implementations follow the same numerical strategy. They first generate all primes up to \(n\), record the gap from each prime to the next one, and precompute for every integer up to \(n\) how to peel off one smallest-prime-power block together with the modular factors needed to apply or remove that block.
The main loop starts from \(\binom{n}{0}=1\), where every local factor is \(1\). For the current \(r\), the implementation reads the segment-tree root, adds \(1\), and obtains \(T_r\). It then adds that value to the running total, using binomial symmetry to double non-central terms.
To advance from \(r\) to \(r+1\), the implementation factors \(n-r\) and \(r+1\) through the precomputed stripping tables, combines all multiplicative changes prime by prime, and updates only the affected leaves. The C++ and Java versions contain the full sieve-and-tree algorithm directly, while the Python implementation delegates to the same compiled computation path.
Let \(\pi(n)\) be the number of primes up to \(n\). The preprocessing tables for the sieve and the stripped factorizations require \(O(n)\) memory, and the segment tree needs \(O(\pi(n))\) more.
Across all integers up to \(n\), the total amount of prime-stripping work is \(O(n\log\log n)\). Each distinct prime touched during a row transition causes one segment-tree update, and each such update costs \(O(\log \pi(n))\). So the overall running time is about
$$O\!\bigl(n\log\log n\log \pi(n)\bigr),$$
which in practice behaves like a near-\(O(n\log n)\) method. The memory usage is
$$O(n+\pi(n)).$$
Für eine ganze Zahl \(x\) und eine Glattheitsschranke \(b\) sei der größte \(b\)-glatte Teiler definiert durch
$$S_b(x)=\prod_{p^\alpha \parallel x,\ p \le b} p^\alpha.$$
Man behält also genau die Primzahlpotenzen, deren Primzahlbasis höchstens \(b\) ist. Zum Beispiel gilt \(2100=2^2\cdot 3\cdot 5^2\cdot 7\), also \(S_4(2100)=2^2\cdot 3=12\).
In Problem 468 ist gesucht
$$F(n)=\sum_{r=0}^{n}\sum_{b=1}^{n} S_b\!\left(\binom{n}{r}\right) \pmod{M},\qquad M=1{,}000{,}000{,}993.$$
Eine naive Methode würde für jedes \(b\) und jedes \(\binom{n}{r}\) neu faktorisieren. Die tatsächliche Lösung ersetzt diese Doppelschleife durch eine geschlossene Formel für einen festen Binomialkoeffizienten und durch schnelle inkrementelle Updates von Zeile zu Zeile.
Die Idee besteht aus zwei Teilen. Zuerst wird \(\sum_b S_b(x)\) für ein festes \(x\) in eine gewichtete Summe von Primpräfixprodukten umgeschrieben. Danach wird ausgenutzt, dass sich aufeinanderfolgende Binomialkoeffizienten nur durch den Faktor \((n-r)/(r+1)\) unterscheiden.
Für jedes \(r\) setzen wir
$$x_r=\binom{n}{r},\qquad T_r=\sum_{b=1}^{n} S_b(x_r).$$
Dann ist die gesuchte Größe
$$F(n)=\sum_{r=0}^{n} T_r \pmod{M}.$$
Jeder Primteiler von \(\binom{n}{r}\) ist höchstens \(n\). Deshalb genügt es, nur die Primzahlen bis \(n\) zu betrachten.
Seien die Primzahlen bis \(n\)
$$2=p_1<p_2<\cdots<p_t\le n,$$
und setze als Wächter
$$p_{t+1}=n+1.$$
Schreibe den aktuellen Binomialkoeffizienten als
$$x_r=\prod_{i=1}^{t} p_i^{\alpha_i(r)},$$
wobei einzelne Exponenten auch null sein dürfen. Gilt \(p_i \le b < p_{i+1}\), dann sind genau die Primzahlen \(p_1,\dots,p_i\) zugelassen, also
$$S_b(x_r)=\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
Zwischen zwei aufeinanderfolgenden Primzahlen bleibt \(S_b(x_r)\) also konstant, und damit folgt
$$T_r=1+\sum_{i=1}^{t}(p_{i+1}-p_i)\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
Der Faktor \(p_{i+1}-p_i\) zählt genau, für wie viele Werte \(b\) derselbe Primpräfixwert gilt. Darum verwendet die Implementierung diese Primzahllücken als Gewichte.
Aufeinanderfolgende Binomialkoeffizienten erfüllen
$$\binom{n}{r+1}=\binom{n}{r}\cdot \frac{n-r}{r+1}.$$
Die Exponenten \(\alpha_i(r)\) müssen daher nicht jedes Mal neu berechnet werden. Es ändern sich nur die Primzahlpotenzen aus \(n-r\) und \(r+1\).
Für jede Zahl \(m\le n\) wird vorab eine Zerlegung
$$m=p^{e}u,\qquad p \nmid u,$$
gespeichert, wobei \(p\) der kleinste Primteiler von \(m\) ist. Ein Tabellenzugriff liefert dann den betroffenen Primindex, den Block \(p^e\), sein modulares Inverses und den Restfaktor \(u\). Wiederholt man diesen Schritt, erhält man die Faktorisierung in wenigen Zugriffen als Folge verschiedener Primzahlpotenzen.
Da \(M\) prim ist und alle relevanten Primzahlen \(p\le n<M\) erfüllen, ist jeder Block \(p^e\) modulo \(M\) invertierbar. Divisionen durch den Nenner werden also als Multiplikation mit modularen Inversen ausgeführt.
Für jede Primzahl \(p_i\) definieren wir den aktuellen lokalen Faktor
$$A_i(r)=p_i^{\alpha_i(r)},\qquad w_i=p_{i+1}-p_i.$$
Ein Blatt speichert das Paar
$$A_i(r),\qquad w_iA_i(r).$$
Für ein Intervall \([L,R]\) werden gespeichert
$$P_{L,R}=\prod_{k=L}^{R} A_k(r),$$
$$Q_{L,R}=\sum_{i=L}^{R} w_i\prod_{k=L}^{i} A_k(r).$$
Beim Zusammenführen zweier Hälften gilt
$$P=P_{\text{links}}P_{\text{rechts}},\qquad Q=Q_{\text{links}}+P_{\text{links}}Q_{\text{rechts}}.$$
An der Wurzel erhält man damit
$$Q_{1,t}=\sum_{i=1}^{t} w_i\prod_{j=1}^{i} A_j(r),$$
also
$$T_r=1+Q_{1,t}\pmod{M}.$$
Von einer Zeile zur nächsten ändern sich nur die Blätter zu Primzahlen, die \(n-r\) oder \(r+1\) teilen. Deshalb wird pro Schritt nur ein kleiner Teil des Baums aktualisiert.
Wegen
$$\binom{n}{r}=\binom{n}{n-r}$$
gilt auch \(T_r=T_{n-r}\). Daher genügt es, von \(r=0\) bis \(\lfloor n/2\rfloor\) zu summieren und alle nichtzentralen Terme zu verdoppeln. Ist \(n\) gerade, wird der mittlere Term genau einmal addiert.
Hier ist
$$x_4=\binom{11}{4}=330=2\cdot 3\cdot 5\cdot 11.$$
Die Primzahlen bis \(11\) sind \(2,3,5,7,11\), der Wächter ist \(12\). Weil der Exponent von \(7\) null ist, lauten die Primpräfixprodukte
$$2,\quad 2\cdot 3=6,\quad 2\cdot 3\cdot 5=30,\quad 30,\quad 30\cdot 11=330.$$
Damit ergibt sich
$$T_4=1+(3-2)\cdot 2+(5-3)\cdot 6+(7-5)\cdot 30+(11-7)\cdot 30+(12-11)\cdot 330=525.$$
Die direkte Liste der Werte \(S_b(x_4)\) für \(b=1,\dots,11\) ist
$$1,\,2,\,6,\,6,\,30,\,30,\,30,\,30,\,30,\,30,\,330,$$
also ebenfalls mit Summe \(525\).
Der nächste Koeffizient ist
$$\binom{11}{5}=\binom{11}{4}\cdot \frac{7}{5}=462,$$
deshalb ändern sich nur die Beiträge der Primzahlen \(5\) und \(7\). Genau das macht die inkrementelle Aktualisierung so billig. Summiert man die ganze Zeile mit Symmetrie, erhält man den Kontrollwert
$$F(11)=3132.$$
Die C++, Python- und Java-Implementierungen folgen derselben numerischen Strategie. Zuerst werden alle Primzahlen bis \(n\) erzeugt, die Lücke zur jeweils nächsten Primzahl gespeichert und für jede Zahl bis \(n\) Vorberechnungen angelegt, mit denen sich ein Block aus kleinster Primzahlpotenz samt modularem Faktor in einem Schritt abtrennen oder wieder hinzufügen lässt.
Die Hauptschleife startet bei \(\binom{n}{0}=1\), also mit lokalen Faktoren gleich \(1\). Für das aktuelle \(r\) liest die Implementierung den Wurzelwert des Segmentbaums aus, addiert \(1\) und erhält so \(T_r\). Dieser Beitrag wird zur Gesamtsumme addiert, wobei die Binomialsymmetrie nichtzentrale Terme verdoppelt.
Für den Übergang von \(r\) nach \(r+1\) werden \(n-r\) und \(r+1\) über die vorberechneten Tabellen zerlegt, alle Änderungen primweise zusammengefasst und nur die betroffenen Blätter multipliziert. Die vollständige Sieb-und-Baum-Methode ist direkt in C++ und Java umgesetzt; die Python-Implementierung delegiert auf denselben kompilierten Rechenweg.
Mit \(\pi(n)\) als Anzahl der Primzahlen bis \(n\) benötigen die Vorberechnungstabellen für Sieb und Strip-Zerlegungen \(O(n)\) Speicher, der Segmentbaum zusätzlich \(O(\pi(n))\).
Über alle Zahlen bis \(n\) hinweg beträgt der gesamte Aufwand für das schrittweise Abstreifen von Primzahlpotenzen \(O(n\log\log n)\). Jede in einem Zeilenübergang berührte Primzahl verursacht genau ein Update im Segmentbaum, und jedes solche Update kostet \(O(\log \pi(n))\). Insgesamt liegt die Laufzeit also bei ungefähr
$$O\!\bigl(n\log\log n\log \pi(n)\bigr),$$
was sich in der Praxis wie eine nahezu \(O(n\log n)\)-Methode verhält. Der Speicherverbrauch ist
$$O(n+\pi(n)).$$
Bir \(x\) tamsayısı ve bir \(b\) düzgünlük sınırı için en büyük \(b\)-smooth bölen
$$S_b(x)=\prod_{p^\alpha \parallel x,\ p \le b} p^\alpha$$
şeklinde tanımlanır. Yani sadece tabanı \(b\)'yi aşmayan asal kuvvetler korunur. Örneğin \(2100=2^2\cdot 3\cdot 5^2\cdot 7\) olduğundan \(S_4(2100)=2^2\cdot 3=12\).
Problem 468’de istenen büyüklük
$$F(n)=\sum_{r=0}^{n}\sum_{b=1}^{n} S_b\!\left(\binom{n}{r}\right) \pmod{M},\qquad M=1{,}000{,}000{,}993.$$
Doğrudan yöntem, her \(b\) ve her \(\binom{n}{r}\) için yeniden çarpanlara ayırma yapardı. Etkin çözüm ise önce sabit bir sayı için \(\sum_b S_b(x)\) ifadesini kapalı bir forma dönüştürür, sonra \(r\) bir arttığında değeri çok az değişen asal üslerini günceller.
Yöntemin iki ana parçası vardır. İlk parça, sabit bir \(x\) için \(\sum_b S_b(x)\) toplamını asal ön-ek çarpımlarının ağırlıklı toplamı haline getirir. İkinci parça ise ardışık binom katsayıları arasındaki oranı kullanarak bir satırdan sonrakine ucuz geçiş yapar.
Her \(r\) için
$$x_r=\binom{n}{r},\qquad T_r=\sum_{b=1}^{n} S_b(x_r)$$
tanımlarını yapalım. O zaman aranan cevap
$$F(n)=\sum_{r=0}^{n} T_r \pmod{M}$$
olur. \(\binom{n}{r}\)'nin her asal böleni en fazla \(n\) olabilir; dolayısıyla sadece \(n\)'ye kadar olan asallar önemlidir.
\(n\)'ye kadar olan asallar
$$2=p_1<p_2<\cdots<p_t\le n$$
olsun ve koruma amaçlı son terim olarak
$$p_{t+1}=n+1$$
ekleyelim. Mevcut binom katsayısını
$$x_r=\prod_{i=1}^{t} p_i^{\alpha_i(r)}$$
şeklinde yazalım; bazı üsler sıfır olabilir. Eğer \(p_i \le b < p_{i+1}\) ise, izin verilen asallar tam olarak \(p_1,\dots,p_i\) olur ve
$$S_b(x_r)=\prod_{j=1}^{i} p_j^{\alpha_j(r)}$$
elde edilir. Yani \(S_b(x_r)\) ardışık asal sayılar arasında sabittir. Bu yüzden
$$T_r=1+\sum_{i=1}^{t}(p_{i+1}-p_i)\prod_{j=1}^{i} p_j^{\alpha_j(r)}$$
olur. Buradaki \(p_{i+1}-p_i\) katsayısı, aynı ön-ek çarpımının kaç farklı \(b\) değeri için geçerli olduğunu sayar.
Standart oran bağıntısı
$$\binom{n}{r+1}=\binom{n}{r}\cdot \frac{n-r}{r+1}$$
şunu söyler: \((\alpha_i(r))\) vektörünü baştan hesaplamak gerekmez. Yalnızca \(n-r\) ve \(r+1\) içindeki asal kuvvetler eklenir ya da çıkarılır.
Her \(m\le n\) için önceden
$$m=p^e u,\qquad p \nmid u$$
biçiminde bir ayrışım tutulur; burada \(p\), \(m\)'yi bölen en küçük asaldır. Tek bir tablo erişimi, hangi asalın etkilendiğini, \(p^e\) bloğunu, bu bloğun modüler tersini ve kalan çarpan \(u\)'yu verir. Bu işlem tekrarlandığında sayı, farklı asal kuvvet bloklarına çok az adımda ayrılır.
\(M\) asal olduğundan ve ilgili tüm asallar \(p\le n<M\) koşulunu sağladığından, her \(p^e\) bloğu mod \(M\) altında terslenebilir. Böylece paydadaki bölme, modüler tersle çarpma olarak uygulanır.
Her asal \(p_i\) için güncel yerel çarpanı
$$A_i(r)=p_i^{\alpha_i(r)},\qquad w_i=p_{i+1}-p_i$$
olarak tanımlayalım. Bir yaprakta
$$A_i(r),\qquad w_iA_i(r)$$
çifti tutulur. \([L,R]\) aralığı için
$$P_{L,R}=\prod_{k=L}^{R} A_k(r),$$
$$Q_{L,R}=\sum_{i=L}^{R} w_i\prod_{k=L}^{i} A_k(r)$$
saklanır. İki yarım aralık birleştirilirken
$$P=P_{\text{sol}}P_{\text{sağ}},\qquad Q=Q_{\text{sol}}+P_{\text{sol}}Q_{\text{sağ}}$$
kuralı kullanılır. Kök düğümde
$$Q_{1,t}=\sum_{i=1}^{t} w_i\prod_{j=1}^{i} A_j(r)$$
elde edildiği için
$$T_r=1+Q_{1,t}\pmod{M}$$
olur. Bir satırdan sonrakine geçerken sadece \(n-r\) veya \(r+1\)'i bölen asallara ait yapraklar değişir.
Şu özdeşlikten dolayı
$$\binom{n}{r}=\binom{n}{n-r},$$
\(T_r=T_{n-r}\) olur. Bu yüzden \(r=0\) ile \(\lfloor n/2\rfloor\) aralığını toplamak yeterlidir; orta terim hariç her katkı ikiyle çarpılır. \(n\) çiftse merkez terim yalnızca bir kez eklenir.
Bu durumda
$$x_4=\binom{11}{4}=330=2\cdot 3\cdot 5\cdot 11.$$
\(11\)'e kadar olan asallar \(2,3,5,7,11\), koruma terimi ise \(12\)'dir. \(7\)'nin üssü sıfır olduğundan asal ön-ek çarpımları
$$2,\quad 2\cdot 3=6,\quad 2\cdot 3\cdot 5=30,\quad 30,\quad 30\cdot 11=330$$
şeklindedir. Dolayısıyla
$$T_4=1+(3-2)\cdot 2+(5-3)\cdot 6+(7-5)\cdot 30+(11-7)\cdot 30+(12-11)\cdot 330=525.$$
\(b=1,\dots,11\) için doğrudan liste
$$1,\,2,\,6,\,6,\,30,\,30,\,30,\,30,\,30,\,30,\,330$$
olur ve toplam yine \(525\) çıkar.
Bir sonraki katsayı
$$\binom{11}{5}=\binom{11}{4}\cdot \frac{7}{5}=462$$
olduğundan sadece \(5\) ve \(7\) ile ilgili asal kuvvet blokları değişir. Artımlı güncellemenin ucuz olmasının nedeni budur. Tüm satır simetrik toplandığında kontrol değeri
$$F(11)=3132$$
elde edilir.
C++, Python ve Java implementasyonları aynı sayısal planı izler. Önce \(n\)'ye kadar olan asallar üretilir, her asal ile bir sonraki asal arasındaki fark kaydedilir ve \(n\)'ye kadar her sayı için en küçük asal kuvvet bloğunu ayırmayı sağlayan ön hesaplar hazırlanır.
Ana döngü \(\binom{n}{0}=1\) noktasından başlar; bu anda tüm yerel çarpanlar \(1\)'dir. Mevcut \(r\) için segment tree kökünden ağırlıklı ön-ek toplamı okunur, üzerine \(1\) eklenerek \(T_r\) bulunur ve binom simetrisi kullanılarak toplam cevaba eklenir.
\(r\)'den \(r+1\)'e geçmek için uygulama \(n-r\) ve \(r+1\) sayılarını önceden hazırlanmış ayrıştırma tablolarıyla parçalar, aynı asala ait değişimleri birleştirir ve sadece etkilenen yaprakları günceller. Tam algoritma C++ ve Java sürümlerinde doğrudan bulunur; Python sürümü ise aynı derlenmiş hesaplama yolunu çağırır.
\(\pi(n)\), \(n\)'ye kadar olan asal sayısı olsun. Elek ve ön işleme tabloları \(O(n)\) bellek, segment tree ise ek olarak \(O(\pi(n))\) bellek kullanır.
\(n\)'ye kadar tüm sayılar üzerinde yapılan asal blok sıyırma işlemlerinin toplam maliyeti \(O(n\log\log n)\) olur. Bir satır geçişinde dokunulan her farklı asal, segment tree üzerinde bir güncelleme üretir ve her güncelleme \(O(\log \pi(n))\) sürer. Bu nedenle toplam çalışma süresi yaklaşık
$$O\!\bigl(n\log\log n\log \pi(n)\bigr)$$
seviyesindedir; pratikte bu, near-\(O(n\log n)\) davranışı verir. Toplam bellek kullanımı
$$O(n+\pi(n))$$
şeklindedir.
Para un entero \(x\) y una cota de suavidad \(b\), el mayor divisor \(b\)-suave se define por
$$S_b(x)=\prod_{p^\alpha \parallel x,\ p \le b} p^\alpha.$$
Se conservan exactamente las potencias primas cuya base prima no supera \(b\). Por ejemplo, \(2100=2^2\cdot 3\cdot 5^2\cdot 7\), así que \(S_4(2100)=2^2\cdot 3=12\).
En el problema 468 se pide calcular
$$F(n)=\sum_{r=0}^{n}\sum_{b=1}^{n} S_b\!\left(\binom{n}{r}\right) \pmod{M},\qquad M=1{,}000{,}000{,}993.$$
Un enfoque ingenuo volvería a factorizar cada coeficiente binomial para cada valor de \(b\). La solución eficiente evita eso: deduce una fórmula cerrada para un coeficiente fijo y luego la actualiza de forma incremental cuando \(r\) avanza por la fila.
El método tiene dos capas. Primero, convierte \(\sum_b S_b(x)\) para un entero fijo \(x\) en una suma ponderada de productos prefijo de primos. Después aprovecha la relación entre coeficientes binomiales consecutivos para modificar solo unas pocas exponentes primas en cada paso.
Para cada \(r\), definimos
$$x_r=\binom{n}{r},\qquad T_r=\sum_{b=1}^{n} S_b(x_r).$$
Entonces la cantidad buscada es
$$F(n)=\sum_{r=0}^{n} T_r \pmod{M}.$$
Todo primo que divide a \(\binom{n}{r}\) es a lo sumo \(n\), así que basta considerar los primos hasta \(n\).
Sean los primos hasta \(n\)
$$2=p_1<p_2<\cdots<p_t\le n,$$
y añadamos el centinela
$$p_{t+1}=n+1.$$
Escribimos el coeficiente binomial actual como
$$x_r=\prod_{i=1}^{t} p_i^{\alpha_i(r)},$$
permitiendo exponentes nulos. Si \(p_i \le b < p_{i+1}\), los primos admitidos son exactamente \(p_1,\dots,p_i\), y por tanto
$$S_b(x_r)=\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
Eso muestra que \(S_b(x_r)\) es constante entre dos primos consecutivos, y de ahí se obtiene
$$T_r=1+\sum_{i=1}^{t}(p_{i+1}-p_i)\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
El factor \(p_{i+1}-p_i\) cuenta cuántos valores de \(b\) producen exactamente el mismo producto prefijo. Por eso los huecos entre primos aparecen como pesos naturales.
Los coeficientes binomiales consecutivos satisfacen
$$\binom{n}{r+1}=\binom{n}{r}\cdot \frac{n-r}{r+1}.$$
Así, el vector de exponentes \((\alpha_i(r))\) no se recalcula desde cero. Solo cambian las potencias primas contenidas en \(n-r\) y en \(r+1\).
Para cada entero \(m\le n\), la implementación precomputa una descomposición
$$m=p^e u,\qquad p \nmid u,$$
donde \(p\) es el menor primo divisor de \(m\). Una sola consulta de tabla entrega qué primo interviene, el bloque \(p^e\), su inverso modular y el cofator restante \(u\). Repitiendo el proceso se descompone cualquier número en bloques de potencias primas distintas con muy pocas consultas.
Como \(M\) es primo y todos los primos relevantes cumplen \(p\le n<M\), cada bloque \(p^e\) tiene inverso módulo \(M\). Por eso la división por el denominador se implementa como multiplicación por inversos modulares.
Para cada primo \(p_i\), definimos
$$A_i(r)=p_i^{\alpha_i(r)},\qquad w_i=p_{i+1}-p_i.$$
En cada hoja se guarda el par
$$A_i(r),\qquad w_iA_i(r).$$
Para un intervalo \([L,R]\) se almacenan
$$P_{L,R}=\prod_{k=L}^{R} A_k(r),$$
$$Q_{L,R}=\sum_{i=L}^{R} w_i\prod_{k=L}^{i} A_k(r).$$
Al combinar dos mitades adyacentes se usa
$$P=P_{\text{izq}}P_{\text{der}},\qquad Q=Q_{\text{izq}}+P_{\text{izq}}Q_{\text{der}}.$$
En la raíz aparece
$$Q_{1,t}=\sum_{i=1}^{t} w_i\prod_{j=1}^{i} A_j(r),$$
y por tanto
$$T_r=1+Q_{1,t}\pmod{M}.$$
Al pasar de una fila a la siguiente solo cambian las hojas correspondientes a los primos que dividen \(n-r\) o \(r+1\).
Puesto que
$$\binom{n}{r}=\binom{n}{n-r},$$
también se cumple \(T_r=T_{n-r}\). Por ello basta sumar desde \(r=0\) hasta \(\lfloor n/2\rfloor\) y duplicar cada término no central. Si \(n\) es par, el término del centro se añade una sola vez.
En este caso
$$x_4=\binom{11}{4}=330=2\cdot 3\cdot 5\cdot 11.$$
Los primos hasta \(11\) son \(2,3,5,7,11\), con centinela \(12\). Como el exponente de \(7\) es cero, los productos prefijo son
$$2,\quad 2\cdot 3=6,\quad 2\cdot 3\cdot 5=30,\quad 30,\quad 30\cdot 11=330.$$
Así,
$$T_4=1+(3-2)\cdot 2+(5-3)\cdot 6+(7-5)\cdot 30+(11-7)\cdot 30+(12-11)\cdot 330=525.$$
Si se listan directamente los valores \(S_b(x_4)\) para \(b=1,\dots,11\), se obtiene
$$1,\,2,\,6,\,6,\,30,\,30,\,30,\,30,\,30,\,30,\,330,$$
cuya suma vuelve a ser \(525\).
El siguiente coeficiente es
$$\binom{11}{5}=\binom{11}{4}\cdot \frac{7}{5}=462,$$
así que solo cambian los bloques ligados a los primos \(5\) y \(7\). Eso muestra por qué la actualización incremental es barata. Al sumar toda la fila usando simetría se obtiene el valor de control
$$F(11)=3132.$$
Las implementaciones en C++, Python y Java siguen el mismo plan numérico. Primero generan todos los primos hasta \(n\), registran el hueco entre cada primo y el siguiente, y precomputan para cada entero hasta \(n\) cómo separar un bloque de potencia del menor primo, junto con los factores modulares necesarios para añadirlo o retirarlo.
El bucle principal empieza en \(\binom{n}{0}=1\), donde todos los factores locales valen \(1\). Para el \(r\) actual, la implementación lee la raíz del árbol de segmentos, suma \(1\) y así obtiene \(T_r\). Después incorpora ese valor al total, duplicando los términos no centrales por la simetría binomial.
Para avanzar de \(r\) a \(r+1\), la implementación factoriza \(n-r\) y \(r+1\) usando las tablas precomputadas, combina los cambios primo por primo y actualiza solo las hojas afectadas. Las versiones de C++ y Java contienen el algoritmo completo de criba y árbol; la implementación en Python delega en la misma ruta de cálculo compilada.
Si \(\pi(n)\) denota el número de primos hasta \(n\), las tablas de preprocesamiento de la criba y de las descomposiciones usan \(O(n)\) memoria, y el árbol de segmentos añade \(O(\pi(n))\) memoria adicional.
Sobre todos los enteros hasta \(n\), el trabajo total de ir retirando bloques de potencias primas es \(O(n\log\log n)\). Cada primo distinto tocado en una transición de fila produce una actualización del árbol, y cada actualización cuesta \(O(\log \pi(n))\). Por tanto, el tiempo total es aproximadamente
$$O\!\bigl(n\log\log n\log \pi(n)\bigr),$$
que en la práctica se comporta como un método cercano a \(O(n\log n)\). El uso total de memoria es
$$O(n+\pi(n)).$$
对整数 \(x\) 和平滑度上界 \(b\)，定义 \(x\) 的最大 \(b\)-smooth 因子为
$$S_b(x)=\prod_{p^\alpha \parallel x,\ p \le b} p^\alpha.$$
也就是说，只保留底数不超过 \(b\) 的那些素数幂。比如 \(2100=2^2\cdot 3\cdot 5^2\cdot 7\)，所以 \(S_4(2100)=2^2\cdot 3=12\)。
第 468 题要求计算
$$F(n)=\sum_{r=0}^{n}\sum_{b=1}^{n} S_b\!\left(\binom{n}{r}\right) \pmod{M},\qquad M=1{,}000{,}000{,}993.$$
如果直接对每个 \(b\) 和每个二项式系数都重新做质因数分解，规模会完全失控。可行做法是先把固定整数 \(x\) 的 \(\sum_b S_b(x)\) 写成封闭公式，再利用相邻二项式系数之间的递推关系做增量更新。
整个方法分成两层。第一层针对固定的 \(x\)，把 \(\sum_b S_b(x)\) 改写成一串“带权素数前缀乘积”的和。第二层利用相邻二项式系数只差一个比值这一事实，使得从 \(r\) 走到 \(r+1\) 时只需要调整很少几个素数指数。
对每个 \(r\)，记
$$x_r=\binom{n}{r},\qquad T_r=\sum_{b=1}^{n} S_b(x_r).$$
那么题目要求的就是
$$F(n)=\sum_{r=0}^{n} T_r \pmod{M}.$$
\(\binom{n}{r}\) 的任何素因子都不会超过 \(n\)，因此整个问题只需要关心不大于 \(n\) 的素数。
设不超过 \(n\) 的素数为
$$2=p_1<p_2<\cdots<p_t\le n,$$
再补一个哨兵值
$$p_{t+1}=n+1.$$
把当前的二项式系数写成
$$x_r=\prod_{i=1}^{t} p_i^{\alpha_i(r)},$$
其中允许某些 \(\alpha_i(r)\) 为 \(0\)。当 \(p_i \le b < p_{i+1}\) 时，可用的素数恰好是 \(p_1,\dots,p_i\)，因此
$$S_b(x_r)=\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
这说明 \(S_b(x_r)\) 只会在 \(b\) 越过某个素数时发生变化，在相邻素数之间保持常数。于是
$$T_r=1+\sum_{i=1}^{t}(p_{i+1}-p_i)\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
其中 \(p_{i+1}-p_i\) 正好表示有多少个整数 \(b\) 会得到同一个前缀乘积，所以“素数间隔”自然成为权重。
相邻二项式系数满足
$$\binom{n}{r+1}=\binom{n}{r}\cdot \frac{n-r}{r+1}.$$
这意味着指数向量 \((\alpha_i(r))\) 不必每次从头重算。它只会因为分子 \(n-r\) 中的素数幂而增加，并因为分母 \(r+1\) 中的素数幂而减少。
实现中会对每个 \(m\le n\) 预先保存一种分解
$$m=p^e u,\qquad p \nmid u,$$
其中 \(p\) 是 \(m\) 的最小素因子。一次表查询就能得到四件事：受影响的是哪个素数、对应的素数幂块 \(p^e\)、该块在模 \(M\) 下的逆元，以及去掉这个块以后剩下的 \(u\)。不断重复这个过程，就能把任意整数拆成若干个不同素数对应的幂块，而且查询次数很少。
由于 \(M\) 是素数，并且所有相关素数都满足 \(p\le n<M\)，所以每个 \(p^e\) 在模 \(M\) 下都有逆元。因此实现里对分母的“除法”实际上是乘上预先准备好的模逆。
对每个素数 \(p_i\)，定义当前局部因子
$$A_i(r)=p_i^{\alpha_i(r)},\qquad w_i=p_{i+1}-p_i.$$
叶子节点保存
$$A_i(r),\qquad w_iA_i(r)$$
这一对信息。对任意区间 \([L,R]\)，维护
$$P_{L,R}=\prod_{k=L}^{R} A_k(r),$$
$$Q_{L,R}=\sum_{i=L}^{R} w_i\prod_{k=L}^{i} A_k(r).$$
如果把区间分成左右两半，则合并公式是
$$P=P_{\text{left}}P_{\text{right}},\qquad Q=Q_{\text{left}}+P_{\text{left}}Q_{\text{right}}.$$
在根节点上便得到
$$Q_{1,t}=\sum_{i=1}^{t} w_i\prod_{j=1}^{i} A_j(r),$$
因此
$$T_r=1+Q_{1,t}\pmod{M}.$$
从一行走到下一行时，只会改动那些整除 \(n-r\) 或 \(r+1\) 的素数对应的叶子，所以每一步只需要更新树中的很小一部分。
因为
$$\binom{n}{r}=\binom{n}{n-r},$$
所以 \(T_r=T_{n-r}\)。这意味着只需要计算到 \(\lfloor n/2\rfloor\)，非中心项乘以 \(2\) 即可。如果 \(n\) 为偶数，中间那一项只加一次。
此时
$$x_4=\binom{11}{4}=330=2\cdot 3\cdot 5\cdot 11.$$
不超过 \(11\) 的素数是 \(2,3,5,7,11\)，哨兵是 \(12\)。由于 \(7\) 的指数为 \(0\)，对应的素数前缀乘积依次是
$$2,\quad 2\cdot 3=6,\quad 2\cdot 3\cdot 5=30,\quad 30,\quad 30\cdot 11=330.$$
所以
$$T_4=1+(3-2)\cdot 2+(5-3)\cdot 6+(7-5)\cdot 30+(11-7)\cdot 30+(12-11)\cdot 330=525.$$
如果直接列出 \(b=1,\dots,11\) 时的最大平滑因子，就得到
$$1,\,2,\,6,\,6,\,30,\,30,\,30,\,30,\,30,\,30,\,330,$$
它们的和同样是 \(525\)。
下一项为
$$\binom{11}{5}=\binom{11}{4}\cdot \frac{7}{5}=462,$$
因此只需要修改与素数 \(5\) 和 \(7\) 相关的局部因子。这正是增量更新非常高效的原因。把整行按对称方式累加后，会得到校验值
$$F(11)=3132.$$
C++、Python 和 Java 实现遵循同一套数值流程。首先筛出所有不超过 \(n\) 的素数，记录每个素数到下一个素数的间隔，并为每个不超过 \(n\) 的整数预计算一种“剥掉最小素数幂块”的表示，同时保存添加或撤销该块所需的模乘因子。
主循环从 \(\binom{n}{0}=1\) 开始，此时所有局部因子都等于 \(1\)。对当前 \(r\)，实现读取线段树根节点中的带权前缀和，加上 \(1\) 就得到 \(T_r\)，然后利用二项式对称性把它并入总答案。
当 \(r\) 递增到 \(r+1\) 时，实现会通过预处理表分解 \(n-r\) 和 \(r+1\)，按素数把所有变化合并，再只更新受影响的叶子。完整的筛法加线段树算法直接写在 C++ 和 Java 版本中，而 Python 版本调用的是同一条已编译的计算路径。
记 \(\pi(n)\) 为不超过 \(n\) 的素数个数。筛法和剥离表一共需要 \(O(n)\) 空间，线段树再额外需要 \(O(\pi(n))\) 空间。
对所有不超过 \(n\) 的整数而言，反复剥离素数幂块的总工作量是 \(O(n\log\log n)\)。每次行转移中，每个被触及的不同素数会引起一次线段树更新，而每次更新的代价是 \(O(\log \pi(n))\)。因此总时间大约是
$$O\!\bigl(n\log\log n\log \pi(n)\bigr),$$
实际表现接近一个 near-\(O(n\log n)\) 的方法。总空间复杂度是
$$O(n+\pi(n)).$$
Для целого числа \(x\) и границы гладкости \(b\) определим наибольший \(b\)-гладкий делитель:
$$S_b(x)=\prod_{p^\alpha \parallel x,\ p \le b} p^\alpha.$$
То есть сохраняются только те простые степени, у которых простое основание не превосходит \(b\). Например, \(2100=2^2\cdot 3\cdot 5^2\cdot 7\), поэтому \(S_4(2100)=2^2\cdot 3=12\).
В задаче 468 требуется вычислить
$$F(n)=\sum_{r=0}^{n}\sum_{b=1}^{n} S_b\!\left(\binom{n}{r}\right) \pmod{M},\qquad M=1{,}000{,}000{,}993.$$
Наивный подход заново раскладывал бы каждый биномиальный коэффициент на простые множители для каждого значения \(b\). Эффективное решение сначала выводит замкнутую формулу для фиксированного коэффициента, а затем быстро обновляет её при переходе от \(r\) к \(r+1\).
Метод состоит из двух частей. Сначала сумма \(\sum_b S_b(x)\) для фиксированного \(x\) переписывается как взвешенная сумма префиксных произведений простых. Затем используется рекуррентное соотношение для соседних биномиальных коэффициентов, благодаря чему на каждом шаге меняются только несколько простых показателей.
Для каждого \(r\) обозначим
$$x_r=\binom{n}{r},\qquad T_r=\sum_{b=1}^{n} S_b(x_r).$$
Тогда искомая величина равна
$$F(n)=\sum_{r=0}^{n} T_r \pmod{M}.$$
Любой простой делитель числа \(\binom{n}{r}\) не превосходит \(n\), поэтому достаточно рассматривать только простые до \(n\).
Пусть простые числа до \(n\) таковы:
$$2=p_1<p_2<\cdots<p_t\le n,$$
а в качестве фиктивной правой границы введём
$$p_{t+1}=n+1.$$
Разложим текущий биномиальный коэффициент в виде
$$x_r=\prod_{i=1}^{t} p_i^{\alpha_i(r)},$$
где некоторые показатели могут быть нулевыми. Если \(p_i \le b < p_{i+1}\), то разрешены ровно простые \(p_1,\dots,p_i\), и потому
$$S_b(x_r)=\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
Следовательно, \(S_b(x_r)\) постоянно на каждом промежутке между соседними простыми, и
$$T_r=1+\sum_{i=1}^{t}(p_{i+1}-p_i)\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
Коэффициент \(p_{i+1}-p_i\) просто считает, для скольких значений \(b\) сохраняется один и тот же префиксный множитель. Именно поэтому веса в реализации равны промежуткам между соседними простыми.
Для соседних биномиальных коэффициентов выполняется
$$\binom{n}{r+1}=\binom{n}{r}\cdot \frac{n-r}{r+1}.$$
Значит, вектор показателей \((\alpha_i(r))\) не нужно каждый раз вычислять заново. Он меняется только за счёт простых степеней, входящих в \(n-r\) и \(r+1\).
Для каждого числа \(m\le n\) реализация заранее хранит представление
$$m=p^e u,\qquad p \nmid u,$$
где \(p\) — минимальный простой делитель числа \(m\). Один просмотр таблицы даёт четыре нужных факта: какой простой затронут, какой блок \(p^e\) нужно применить, каков его обратный элемент по модулю, и какой кофактор \(u\) остаётся. Повторяя процедуру, можно быстро разложить число на блоки по различным простым.
Поскольку \(M\) простое и все релевантные простые удовлетворяют \(p\le n<M\), любой блок \(p^e\) обратим по модулю \(M\). Поэтому деление на знаменатель выполняется как умножение на заранее вычисленные модульные обратные.
Для каждого простого \(p_i\) введём текущий локальный множитель
$$A_i(r)=p_i^{\alpha_i(r)},\qquad w_i=p_{i+1}-p_i.$$
В листе хранятся величины
$$A_i(r),\qquad w_iA_i(r).$$
Для интервала \([L,R]\) поддерживаются
$$P_{L,R}=\prod_{k=L}^{R} A_k(r),$$
$$Q_{L,R}=\sum_{i=L}^{R} w_i\prod_{k=L}^{i} A_k(r).$$
Если интервал разбит на левую и правую части, то правило слияния имеет вид
$$P=P_{\text{лев}}P_{\text{прав}},\qquad Q=Q_{\text{лев}}+P_{\text{лев}}Q_{\text{прав}}.$$
В корне дерева получается
$$Q_{1,t}=\sum_{i=1}^{t} w_i\prod_{j=1}^{i} A_j(r),$$
а значит
$$T_r=1+Q_{1,t}\pmod{M}.$$
При переходе к следующему \(r\) меняются только те листья, чьи простые делят \(n-r\) или \(r+1\), так что обновляется лишь малая часть дерева.
Из равенства
$$\binom{n}{r}=\binom{n}{n-r}$$
следует \(T_r=T_{n-r}\). Поэтому достаточно просуммировать значения от \(r=0\) до \(\lfloor n/2\rfloor\), удваивая все нецентральные вклады. Если \(n\) чётно, средний член добавляется только один раз.
Здесь
$$x_4=\binom{11}{4}=330=2\cdot 3\cdot 5\cdot 11.$$
Простые до \(11\): \(2,3,5,7,11\), а фиктивная граница равна \(12\). Поскольку показатель у \(7\) равен нулю, префиксные произведения равны
$$2,\quad 2\cdot 3=6,\quad 2\cdot 3\cdot 5=30,\quad 30,\quad 30\cdot 11=330.$$
Следовательно,
$$T_4=1+(3-2)\cdot 2+(5-3)\cdot 6+(7-5)\cdot 30+(11-7)\cdot 30+(12-11)\cdot 330=525.$$
Если выписать значения \(S_b(x_4)\) при \(b=1,\dots,11\), получим
$$1,\,2,\,6,\,6,\,30,\,30,\,30,\,30,\,30,\,30,\,330,$$
и их сумма снова равна \(525\).
Следующий коэффициент равен
$$\binom{11}{5}=\binom{11}{4}\cdot \frac{7}{5}=462,$$
поэтому обновлять нужно только блоки, связанные с простыми \(5\) и \(7\). Это хорошо показывает, почему переход по строке дешёв. Полная симметричная сумма по строке даёт контрольное значение
$$F(11)=3132.$$
Реализации на C++, Python и Java следуют одному и тому же вычислительному плану. Сначала они строят список всех простых до \(n\), сохраняют расстояние до следующего простого и подготавливают для каждого числа до \(n\) таблицы, позволяющие одним шагом снять блок минимальной простой степени и одновременно получить нужные множители по модулю.
Основной цикл стартует с \(\binom{n}{0}=1\), когда все локальные множители равны \(1\). Для текущего \(r\) реализация считывает значение в корне сегментного дерева, прибавляет \(1\) и получает \(T_r\). Затем этот вклад добавляется в ответ с учётом симметрии биномиальной строки.
Чтобы перейти от \(r\) к \(r+1\), реализация раскладывает \(n-r\) и \(r+1\) через заранее подготовленные таблицы, объединяет изменения по каждому простому и обновляет только затронутые листья. Полный алгоритм с решетом и деревом реализован непосредственно в C++ и Java; Python-версия делегирует вычисление тому же скомпилированному пути.
Если \(\pi(n)\) — число простых, не превосходящих \(n\), то таблицы предварительной обработки для решета и разложений требуют \(O(n)\) памяти, а сегментное дерево — ещё \(O(\pi(n))\).
Совокупная стоимость последовательного снятия простых блоков для всех чисел до \(n\) равна \(O(n\log\log n)\). Каждый различный простой, затронутый при переходе между двумя соседними значениями \(r\), вызывает одно обновление дерева, а каждое обновление стоит \(O(\log \pi(n))\). Значит, полное время работы составляет примерно
$$O\!\bigl(n\log\log n\log \pi(n)\bigr),$$
что на практике ведёт себя как почти \(O(n\log n)\). Используемая память равна
$$O(n+\pi(n)).$$
لعدد صحيح \(x\) وحدّ نعومة \(b\)، نعرّف أكبر قاسم \(b\)-smooth بالصيغة
$$S_b(x)=\prod_{p^\alpha \parallel x,\ p \le b} p^\alpha.$$
أي إننا نحتفظ فقط بقوى الأعداد الأولية التي لا يتجاوز أساسها الأولي القيمة \(b\). على سبيل المثال
$$2100=2^2\cdot 3\cdot 5^2\cdot 7,$$
ولذلك
$$S_4(2100)=2^2\cdot 3=12.$$
في المسألة 468 نريد حساب
$$F(n)=\sum_{r=0}^{n}\sum_{b=1}^{n} S_b\!\left(\binom{n}{r}\right) \pmod{M},\qquad M=1{,}000{,}000{,}993.$$
الطريقة الساذجة ستعيد تحليل كل معامل ثنائي حد إلى عوامله الأولية لكل قيمة من قيم \(b\)، وهذا غير عملي تمامًا. الحل الفعلي يحول \(\sum_b S_b(x)\) لعدد ثابت إلى صيغة مغلقة، ثم يحدثها تدريجيًا عند الانتقال من \(\binom{n}{r}\) إلى \(\binom{n}{r+1}\).
الفكرة لها طبقتان. أولًا نحول \(\sum_b S_b(x)\) لعدد ثابت \(x\) إلى مجموع موزون لجداءات بادئية على الأعداد الأولية. ثم نستغل العلاقة بين معاملات ثنائية الحد المتتالية بحيث لا تتغير إلا أسس أولية قليلة جدًا في كل خطوة.
لكل \(r\) نكتب
$$x_r=\binom{n}{r},\qquad T_r=\sum_{b=1}^{n} S_b(x_r).$$
وعندئذ تصبح الكمية المطلوبة
$$F(n)=\sum_{r=0}^{n} T_r \pmod{M}.$$
كل عدد أولي يقسم \(\binom{n}{r}\) لا بد أن يكون أصغر من أو يساوي \(n\)، لذلك يكفي التعامل مع الأعداد الأولية حتى \(n\) فقط.
لتكن الأعداد الأولية حتى \(n\) هي
$$2=p_1<p_2<\cdots<p_t\le n,$$
ونضيف حدًا حارسًا
$$p_{t+1}=n+1.$$
نكتب معامل ثنائي الحد الحالي على الصورة
$$x_r=\prod_{i=1}^{t} p_i^{\alpha_i(r)},$$
مع السماح لبعض الأسس أن تكون صفرًا. إذا كان
$$p_i \le b < p_{i+1},$$
فإن الأوليات المسموح بها هي بالضبط \(p_1,\dots,p_i\)، ومن ثم
$$S_b(x_r)=\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
وهذا يعني أن \(S_b(x_r)\) ثابت على كل مجال يقع بين عددين أوليين متتاليين، وبالتالي
$$T_r=1+\sum_{i=1}^{t}(p_{i+1}-p_i)\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$$
المعامل \(p_{i+1}-p_i\) يحصي عدد قيم \(b\) التي تعطي الجداء البادئ نفسه، ولهذا تظهر فروق الأعداد الأولية كأوزان طبيعية في التنفيذ.
العلاقة القياسية بين معاملين متتاليين هي
$$\binom{n}{r+1}=\binom{n}{r}\cdot \frac{n-r}{r+1}.$$
إذًا لا حاجة إلى إعادة بناء متجه الأسس \((\alpha_i(r))\) من الصفر في كل مرة. ما يتغير فقط هو قوى الأوليات الموجودة في \(n-r\) وفي \(r+1\).
لكل عدد \(m\le n\) يحضر التنفيذ مسبقًا تفكيكًا من الشكل
$$m=p^e u,\qquad p \nmid u,$$
حيث \(p\) هو أصغر أولي يقسم \(m\). ومن خلال قراءة واحدة من الجداول نحصل على أربع معلومات: أي أولي يتأثر، وما هي الكتلة \(p^e\)، وما هو معكوسها الضربي بترديد \(M\)، وما هو العامل الباقي \(u\). بتكرار هذه العملية يمكن تحليل أي عدد إلى كتل من قوى أولية مميزة بعدد صغير من الخطوات.
ولأن \(M\) عدد أولي، ولأن جميع الأوليات المستخدمة تحقق \(p\le n<M\)، فإن كل كتلة \(p^e\) قابلة للعكس بترديد \(M\). لذلك تمثل القسمة على المقام على شكل ضرب في المعكوسات المعيارية.
لكل أولي \(p_i\) نعرف العامل المحلي الحالي
$$A_i(r)=p_i^{\alpha_i(r)},\qquad w_i=p_{i+1}-p_i.$$
وتحفظ الورقة الزوج
$$A_i(r),\qquad w_iA_i(r).$$
أما على مجال \([L,R]\) فنحفظ
$$P_{L,R}=\prod_{k=L}^{R} A_k(r),$$
$$Q_{L,R}=\sum_{i=L}^{R} w_i\prod_{k=L}^{i} A_k(r).$$
وعند دمج النصفين الأيسر والأيمن نستعمل
$$P=P_{\text{left}}P_{\text{right}},\qquad Q=Q_{\text{left}}+P_{\text{left}}Q_{\text{right}}.$$
وعند الجذر نحصل على
$$Q_{1,t}=\sum_{i=1}^{t} w_i\prod_{j=1}^{i} A_j(r),$$
ومن ثم
$$T_r=1+Q_{1,t}\pmod{M}.$$
عند الانتقال من صف إلى الصف الذي يليه لا تتغير إلا الأوراق التابعة للأعداد الأولية التي تقسم \(n-r\) أو \(r+1\)، ولذلك يكون التحديث محليًا وسريعًا.
بما أن
$$\binom{n}{r}=\binom{n}{n-r},$$
فإن \(T_r=T_{n-r}\) أيضًا. لذا يكفي الجمع من \(r=0\) حتى \(\lfloor n/2\rfloor\)، مع مضاعفة كل حد غير مركزي. وإذا كان \(n\) زوجيًا فإن الحد الأوسط يضاف مرة واحدة فقط.
لدينا هنا
$$x_4=\binom{11}{4}=330=2\cdot 3\cdot 5\cdot 11.$$
الأوليات حتى \(11\) هي \(2,3,5,7,11\)، والحد الحارس هو \(12\). وبما أن أس \(7\) يساوي صفرًا، فإن الجداءات البادئية تصبح
$$2,\quad 2\cdot 3=6,\quad 2\cdot 3\cdot 5=30,\quad 30,\quad 30\cdot 11=330.$$
إذًا
$$T_4=1+(3-2)\cdot 2+(5-3)\cdot 6+(7-5)\cdot 30+(11-7)\cdot 30+(12-11)\cdot 330=525.$$
ولو كتبنا قيم \(S_b(x_4)\) مباشرة عندما \(b=1,\dots,11\) لوجدنا
$$1,\,2,\,6,\,6,\,30,\,30,\,30,\,30,\,30,\,30,\,330,$$
ومجموعها مرة أخرى هو \(525\).
المعامل التالي هو
$$\binom{11}{5}=\binom{11}{4}\cdot \frac{7}{5}=462,$$
ولذلك لا تتغير إلا الكتل المرتبطة بالأوليين \(5\) و\(7\). هذا يوضح عمليًا لماذا يكون التحديث بين صفين متتاليين رخيصًا. وبجمع الصف كله مع استغلال التناظر نحصل على قيمة التحقق
$$F(11)=3132.$$
تتبع تنفيذات C++ وPython وJava الخطة العددية نفسها. أولًا تُولَّد جميع الأعداد الأولية حتى \(n\)، وتُسجَّل الفجوة بين كل أولي والذي يليه، ثم تُحضَّر جداول لكل عدد حتى \(n\) تتيح نزع كتلة من أصغر قوة أولية فيه مع معرفة عوامل الضرب المعيارية اللازمة لإضافتها أو حذفها.
تبدأ الحلقة الرئيسية من \(\binom{n}{0}=1\)، حيث تكون جميع العوامل المحلية مساوية لـ \(1\). عند كل قيمة لـ \(r\)، تقرأ الشيفرة قيمة الجذر في شجرة المقاطع، وتضيف \(1\) لتحصل على \(T_r\)، ثم تضم هذه القيمة إلى الناتج الكلي مع مضاعفة الحدود غير المركزية بفضل تناظر معاملات ثنائية الحد.
للانتقال من \(r\) إلى \(r+1\)، تقوم الشيفرة بتحليل \(n-r\) و\(r+1\) عبر الجداول المسبقة، وتدمج التغييرات حسب كل أولي، ثم تحدث الأوراق المتأثرة فقط. النسختان في C++ وJava تحتويان الخوارزمية الكاملة مباشرة، أما تنفيذ Python فيفوّض الحساب إلى المسار المترجم نفسه.
إذا رمزنا بعدد الأوليات حتى \(n\) بالرمز \(\pi(n)\)، فإن جداول الغربلة والتحضير المسبق تحتاج إلى ذاكرة من رتبة \(O(n)\)، بينما تحتاج شجرة المقاطع إلى \(O(\pi(n))\) إضافية.
إجمالي العمل اللازم لنزع كتل القوى الأولية عبر جميع الأعداد حتى \(n\) هو \(O(n\log\log n)\). وكل أولي مختلف يُلمس أثناء الانتقال بين قيمتين متتاليتين لـ \(r\) يولد تحديثًا واحدًا في شجرة المقاطع، وكل تحديث تكلفته \(O(\log \pi(n))\). لذلك يكون الزمن الكلي تقريبًا
$$O\!\bigl(n\log\log n\log \pi(n)\bigr),$$
وهو في التطبيق العملي قريب من سلوك طريقة من رتبة \(O(n\log n)\). أما الذاكرة الكلية فهي
$$O(n+\pi(n)).$$