The problem defines an integer \(S(n)\) by summing over all \(t=1,2,\dots,n\). The term indexed by \(t\) contributes only when the divisibility condition \((n-t)! \mid t^{\,n-t}\) holds, and then its value is
$$(-1)^{n-t}\frac{t^{\,n-t}}{(n-t)!}.$$
The goal is not to compute one isolated \(S(n)\), but the enormous prefix sum
$$A(N)=\sum_{n=1}^{N} S(n)$$
for \(N=10^{18}\), modulo \(10^9+7\). A direct evaluation is hopeless, because even checking the divisibility condition term by term would already be far too slow. The successful approach turns that divisibility test into a simple description of which \(t\)-values are allowed, then reduces everything to a short sum of power sums.
The implementations revolve around one re-indexing step, one valuation argument, and one fast method for evaluating \(\sum_{k=1}^{x} k^m\) at huge \(x\).
Write
$$m=n-t,\qquad t=n-m.$$
Then \(m\) ranges from \(0\) to \(n-1\), and the defining sum becomes
$$S(n)=\sum_{m=0}^{n-1}\mathbf{1}_{\,m!\mid (n-m)^m}\,(-1)^m\frac{(n-m)^m}{m!}.$$
For the prefix sum, it is better to regard \(m\) as the outer variable and \(t\) as the free value. Since \(n=t+m\), we obtain
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{\substack{t\ge 1\\ t+m\le N\\ m!\mid t^m}} t^m.$$
Now the whole problem is: for each fixed \(m\), characterize the integers \(t\) for which \(m!\) divides \(t^m\).
Define
$$P_m=\prod_{\substack{p\le m\\ p\text{ prime}}} p,$$
with the empty product interpreted as \(1\), so \(P_0=P_1=1\). This is the primorial up to \(m\).
The crucial fact used by all three implementations is
$$m!\mid t^m \quad\Longleftrightarrow\quad P_m\mid t.$$
Why is this true? For every prime \(p\le m\), the factorial \(m!\) contains at least one factor \(p\). So if \(p\nmid t\), then \(v_p(t^m)=0\lt v_p(m!)\), and divisibility fails immediately. Therefore every prime \(p\le m\) must divide \(t\), which means \(P_m\mid t\).
Conversely, suppose \(P_m\mid t\). Then every prime \(p\le m\) divides \(t\), so \(v_p(t)\ge 1\) and hence \(v_p(t^m)\ge m\). On the other hand, Legendre's formula gives
$$v_p(m!)=\sum_{j\ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor \le m,$$
so \(v_p(t^m)\ge v_p(m!)\) for every prime \(p\le m\). No larger prime matters, because it does not divide \(m!\). Thus \(m!\mid t^m\).
This is the decisive simplification: the complicated-looking factorial divisibility test collapses to the simple statement that \(t\) is a multiple of one explicit primorial.
Once we know that the admissible values are exactly \(t=kP_m\), the inner sum becomes static:
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{kP_m+m\le N}(kP_m)^m.$$
Pull \(P_m^m\) out of the inner sum:
$$A(N)=\sum_{m\ge 0}(-1)^m\frac{P_m^m}{m!}\sum_{k=1}^{\left\lfloor\frac{N-m}{P_m}\right\rfloor} k^m.$$
So for each \(m\) we only need the power sum
$$F_m(x)=\sum_{k=1}^{x} k^m,\qquad x=\left\lfloor\frac{N-m}{P_m}\right\rfloor.$$
The outer loop is short because primorials grow very fast. As soon as \(P_m>N-m\), the floor becomes \(0\), and no later \(m\) can contribute.
This small case shows how the primorial filter really selects the surviving terms. Here
$$S(10)=\sum_{t=1}^{10}\mathbf{1}_{(10-t)!\mid t^{\,10-t}}(-1)^{10-t}\frac{t^{\,10-t}}{(10-t)!}.$$
Write \(m=10-t\).
For \(m=4\), we have \(P_4=2\cdot 3=6\). Then \(t=6\) is a multiple of \(6\), so the term survives and contributes
$$(-1)^4\frac{6^4}{4!}=\frac{1296}{24}=54.$$
For \(m=3\), we have \(P_3=6\), but now \(t=7\) is not a multiple of \(6\), so the term vanishes. For \(m=2\), \(P_2=2\) and \(t=8\) is allowed, giving
$$(-1)^2\frac{8^2}{2!}=32.$$
The terms with \(m=1\) and \(m=0\) always survive, contributing \(-9\) and \(1\). All larger \(m\) fail the divisibility test. Therefore
$$S(10)=54+32-9+1=78.$$
This example captures the full logic of the large computation: each \(m\) contributes through multiples of \(P_m\), and nothing else matters.
For fixed \(m\), the power sum \(F_m(x)\) is a polynomial in \(x\) of degree \(m+1\) by Faulhaber's theorem. Therefore it is completely determined by the \(m+2\) values
$$F_m(0),F_m(1),\dots,F_m(m+1).$$
If we set \(d=m+2\) and \(y_i=F_m(i)\), then for any \(x\)
$$F_m(x)=\sum_{i=0}^{d-1} y_i \prod_{\substack{0\le j\le d-1\\ j\ne i}}\frac{x-j}{i-j}.$$
Because the interpolation nodes are consecutive integers, the denominator simplifies to
$$\prod_{\substack{0\le j\le d-1\\ j\ne i}}(i-j)=(-1)^{d-1-i} i!(d-1-i)!.$$
The implementations therefore precompute factorials and inverse factorials modulo \(10^9+7\), then use prefix and suffix products of \((x-j)\) to evaluate the numerator of every Lagrange basis term in linear time.
This is especially efficient here because the contributing \(m\)-values are tiny compared with the modulus. For the target \(N=10^{18}\), only \(m=0,1,\dots,52\) contribute, so the interpolation tables never exceed \(d=54\) entries.
Each implementation contains a small exact routine that evaluates \(S(n)\) directly with arbitrary-precision integers. That exact routine is used only for validation: it confirms \(S(1)=1\), \(S(3)=-1\), the prefix \(\sum_{n=1}^{10}S(n)=43\), and then compares several larger prefixes against the fast method. This guards the derivation before the large-\(N\) computation is trusted.
The optimized solver walks upward through \(m\), maintaining three quantities: the actual primorial \(P_m\) for the stopping test, its residue modulo \(10^9+7\), and \(m!\) modulo \(10^9+7\). For each \(m\), it computes
$$(-1)^m P_m^m (m!)^{-1}\pmod{10^9+7}$$
and multiplies it by the modular value of \(F_m\!\left(\left\lfloor\frac{N-m}{P_m}\right\rfloor\right)\).
The power sum is not expanded symbolically. Instead, the code first tabulates the prefix values \(F_m(0),F_m(1),\dots,F_m(m+1)\), then performs one Lagrange evaluation modulo the prime modulus. The C++, Python, and Java implementations all follow this same mathematical pipeline; they only differ in language-specific integer types.
The outer summation is extremely short. For \(N=10^{18}\), the primorial up to \(53\) already exceeds \(N-53\), so only \(53\) values of \(m\) contribute: \(m=0\) through \(m=52\).
For each fixed \(m\), building the sample table \(F_m(0),\dots,F_m(m+1)\), the factorial tables, and the prefix/suffix products all costs \(O(m)\) modular operations. Summing over all contributing \(m\), the total work is therefore \(O(m_{\max}^2)\) with \(m_{\max}=52\), and the memory usage is \(O(m_{\max})\). In concrete terms, the problem becomes small because the hard part is not the size of \(N\), but the very slow growth of the set of relevant exponents \(m\).
Die Aufgabe definiert eine ganze Zahl \(S(n)\) als Summe über alle \(t=1,2,\dots,n\). Der zum Wert \(t\) gehörende Summand bleibt genau dann erhalten, wenn die Teilbarkeitsbedingung \((n-t)! \mid t^{\,n-t}\) erfüllt ist; in diesem Fall lautet sein Beitrag
$$(-1)^{n-t}\frac{t^{\,n-t}}{(n-t)!}.$$
Gesucht ist nicht nur ein einzelnes \(S(n)\), sondern die riesige Präfixsumme
$$A(N)=\sum_{n=1}^{N} S(n)$$
für \(N=10^{18}\) modulo \(10^9+7\). Eine direkte Auswertung wäre aussichtslos. Der entscheidende Durchbruch besteht darin, die Fakultäts-Teilbarkeit exakt zu charakterisieren und anschließend auf Potenzsummen zu reduzieren.
Die drei Implementierungen beruhen auf derselben Herleitung: Umindizieren, die zulässigen \(t\)-Werte über Primoriale beschreiben und die verbleibenden Potenzsummen per Interpolation auswerten.
Setze
$$m=n-t,\qquad t=n-m.$$
Dann gilt
$$S(n)=\sum_{m=0}^{n-1}\mathbf{1}_{\,m!\mid (n-m)^m}\,(-1)^m\frac{(n-m)^m}{m!}.$$
Für die Präfixsumme ist es günstiger, zuerst über \(m\) zu summieren. Da \(n=t+m\), erhält man
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{\substack{t\ge 1\\ t+m\le N\\ m!\mid t^m}} t^m.$$
Damit hängt alles von einer einzigen Frage ab: Für welche \(t\) gilt bei festem \(m\) die Teilbarkeit \(m!\mid t^m\)?
Definiere
$$P_m=\prod_{\substack{p\le m\\ p\text{ prime}}} p,$$
wobei das leere Produkt \(1\) ist, also \(P_0=P_1=1\).
Der Schlüsselsatz lautet
$$m!\mid t^m \quad\Longleftrightarrow\quad P_m\mid t.$$
Die Richtung nach links ist sofort klar: Wenn ein Prim \(p\le m\) nicht in \(t\) vorkommt, dann ist \(v_p(t^m)=0\), während \(v_p(m!)\ge 1\) gilt. Also kann \(m!\) unmöglich \(t^m\) teilen. Folglich muss jedes Prim \(p\le m\) den Wert \(t\) teilen, also auch ihr Produkt \(P_m\).
Umgekehrt nehme man \(P_m\mid t\) an. Dann gilt für jedes Prim \(p\le m\): \(v_p(t)\ge 1\) und damit \(v_p(t^m)\ge m\). Mit der Formel von Legendre folgt
$$v_p(m!)=\sum_{j\ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor \le m,$$
also \(v_p(t^m)\ge v_p(m!)\). Größere Primzahlen spielen keine Rolle, weil sie in \(m!\) gar nicht vorkommen. Daher ist \(m!\mid t^m\) tatsächlich erfüllt.
So wird die komplizierte Bedingung \((n-t)! \mid t^{\,n-t}\) auf einen einfachen Multiplikationstest reduziert: \(t\) muss ein Vielfaches eines expliziten Primorials sein.
Setzt man \(t=kP_m\), dann wird die Präfixsumme zu
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{kP_m+m\le N}(kP_m)^m$$
und somit
$$A(N)=\sum_{m\ge 0}(-1)^m\frac{P_m^m}{m!}\sum_{k=1}^{\left\lfloor\frac{N-m}{P_m}\right\rfloor} k^m.$$
Für jedes \(m\) bleibt also nur die klassische Potenzsumme
$$F_m(x)=\sum_{k=1}^{x} k^m,\qquad x=\left\lfloor\frac{N-m}{P_m}\right\rfloor.$$
Die äußere Summe endet sehr schnell, weil Primoriale rasant wachsen. Sobald \(P_m>N-m\) ist, gibt es keine zulässigen \(k\) mehr.
Hier sieht man die Filterwirkung konkret. Es gilt
$$S(10)=\sum_{t=1}^{10}\mathbf{1}_{(10-t)!\mid t^{\,10-t}}(-1)^{10-t}\frac{t^{\,10-t}}{(10-t)!}.$$
Mit \(m=10-t\) betrachten wir die einzelnen Fälle:
Für \(m=4\) ist \(P_4=6\), und \(t=6\) ist zulässig. Der Beitrag lautet
$$\frac{6^4}{4!}=54.$$
Für \(m=3\) ist \(P_3=6\), aber \(t=7\) ist kein Vielfaches von \(6\); dieser Summand verschwindet. Für \(m=2\) ist \(P_2=2\), also ist \(t=8\) erlaubt und liefert
$$\frac{8^2}{2!}=32.$$
Die Fälle \(m=1\) und \(m=0\) tragen \(-9\) bzw. \(1\) bei. Alle größeren \(m\) fallen weg. Damit ergibt sich
$$S(10)=54+32-9+1=78.$$
Genau dieselbe Logik skaliert anschließend auf die große Präfixsumme.
Für festes \(m\) ist \(F_m(x)\) nach dem Satz von Faulhaber ein Polynom vom Grad \(m+1\). Es genügt also, die Werte
$$F_m(0),F_m(1),\dots,F_m(m+1)$$
zu kennen. Mit \(d=m+2\) und \(y_i=F_m(i)\) erhält man
$$F_m(x)=\sum_{i=0}^{d-1} y_i \prod_{\substack{0\le j\le d-1\\ j\ne i}}\frac{x-j}{i-j}.$$
Da die Stützstellen aufeinanderfolgende ganze Zahlen sind, vereinfacht sich der Nenner zu
$$(-1)^{d-1-i} i!(d-1-i)!.$$
Deshalb berechnet die Implementierung Fakultäten und inverse Fakultäten modulo \(10^9+7\) und verwendet Präfix- und Suffix-Produkte der Faktoren \((x-j)\). Für das Ziel \(N=10^{18}\) tragen nur \(m=0,\dots,52\) bei; die größte Interpolation verwendet also nur \(54\) Stützstellen.
Jede Sprachversion enthält zunächst eine exakte Auswertung von \(S(n)\) mit Ganzzahlarithmetik beliebiger Größe. Diese wird nur für Prüfungen verwendet: kontrolliert werden \(S(1)=1\), \(S(3)=-1\), die Präfixsumme bis \(10\) mit Wert \(43\) sowie mehrere größere Grenzwerte im Vergleich zwischen direkter und schneller Rechnung.
Danach folgt die eigentliche Lösung. Beim Durchlauf über \(m\) werden das Primorial \(P_m\), sein Rest modulo \(10^9+7\) und \(m!\) modulo \(10^9+7\) fortlaufend aktualisiert. Zu jedem \(m\) wird der Koeffizient
$$(-1)^m P_m^m (m!)^{-1}\pmod{10^9+7}$$
berechnet und mit dem interpolierten Wert von \(F_m\!\left(\left\lfloor\frac{N-m}{P_m}\right\rfloor\right)\) multipliziert. C++, Python und Java verwenden dabei dieselbe Mathematik; verschieden sind nur die konkreten Datentypen für große Zwischenwerte.
Die äußere Summe ist sehr kurz. Für \(N=10^{18}\) ist das Primorial bis \(53\) bereits größer als \(N-53\), daher tragen nur \(m=0\) bis \(m=52\) bei.
Für ein festes \(m\) kostet die Erzeugung der Stützwerte, Fakultäten, inversen Fakultäten sowie Präfix-/Suffix-Produkte jeweils \(O(m)\). Insgesamt ergibt sich daher \(O(m_{\max}^2)\) mit \(m_{\max}=52\); der Speicherbedarf ist \(O(m_{\max})\). Die enorme Größe von \(N\) ist also nicht das Problem, weil nur sehr wenige \(m\)-Werte überhaupt relevant sind.
Problem, \(S(n)\) adlı bir tam sayıyı \(t=1,2,\dots,n\) üzerinden tanımlı bir toplamla veriyor. \(t\) terimi yalnızca \((n-t)! \mid t^{\,n-t}\) koşulu sağlanırsa katkı yapıyor; o durumda katkı değeri
$$(-1)^{n-t}\frac{t^{\,n-t}}{(n-t)!}$$
oluyor. Asıl hedef tek bir \(S(n)\) değil,
$$A(N)=\sum_{n=1}^{N} S(n)$$
ön-toplamını \(N=10^{18}\) için \(10^9+7\) modunda bulmak. Doğrudan hesaplama pratik değildir; çözüm, faktöriyel bölünebilirlik koşulunu tam olarak hangi \(t\)-lerin sağladığını belirleyip problemi kısa bir üs toplamları dizisine indirger.
Üç uygulamanın ortak omurgası şudur: önce yeniden indeksleme yapılır, sonra \(m!\mid t^m\) koşulu bir primorial koşuluna dönüştürülür, son olarak da büyük üs toplamları interpolasyonla hesaplanır.
Şunu yazalım:
$$m=n-t,\qquad t=n-m.$$
Böylece
$$S(n)=\sum_{m=0}^{n-1}\mathbf{1}_{\,m!\mid (n-m)^m}\,(-1)^m\frac{(n-m)^m}{m!}$$
olur. Ön-toplam için \(m\)'yi dış değişken yapmak daha doğrudur. Çünkü \(n=t+m\) olduğundan
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{\substack{t\ge 1\\ t+m\le N\\ m!\mid t^m}} t^m$$
elde edilir. Yani tüm mesele, sabit bir \(m\) için hangi \(t\)-lerin \(m!\mid t^m\) koşulunu sağladığını anlamaktır.
Şu çarpımı tanımlayalım:
$$P_m=\prod_{\substack{p\le m\\ p\text{ prime}}} p,$$
boş çarpım \(1\) kabul edildiği için \(P_0=P_1=1\).
Çözümün kilit eşdeğerliği şudur:
$$m!\mid t^m \quad\Longleftrightarrow\quad P_m\mid t.$$
Neden? Eğer \(p\le m\) olan bir asal \(t\)'yi bölmüyorsa, \(v_p(t^m)=0\) olur ama \(p\), \(m!\)'in içinde bulunduğu için \(v_p(m!)\ge 1\) olur. Dolayısıyla bölünebilirlik mümkün değildir. Demek ki \(m\)'den küçük ya da eşit her asal, \(t\)'yi bölmek zorundadır; yani \(P_m\mid t\).
Tersi yönde, \(P_m\mid t\) ise her \(p\le m\) asalı için \(v_p(t)\ge 1\) ve dolayısıyla \(v_p(t^m)\ge m\) olur. Legendre formülü
$$v_p(m!)=\sum_{j\ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor \le m$$
verdiğinden \(v_p(t^m)\ge v_p(m!)\) sağlanır. \(m!\)'de \(m\)'den büyük asal olmadığı için başka kontrol gerekmiyor. Böylece \(m!\mid t^m\) tamamlanır.
Sonuç çok güçlüdür: zor görünen faktöriyel koşulu, yalnızca “\(t\), \(m\)'e kadar olan asalların çarpımının katı mı?” sorusuna iner.
Artık \(t=kP_m\) yazabiliriz. O zaman
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{kP_m+m\le N}(kP_m)^m$$
ve buradan
$$A(N)=\sum_{m\ge 0}(-1)^m\frac{P_m^m}{m!}\sum_{k=1}^{\left\lfloor\frac{N-m}{P_m}\right\rfloor} k^m$$
çıkar. Yani her \(m\) için ihtiyaç duyulan tek şey
$$F_m(x)=\sum_{k=1}^{x} k^m,\qquad x=\left\lfloor\frac{N-m}{P_m}\right\rfloor$$
değeridir. Primorial çok hızlı büyüdüğü için dış toplam kısa kalır; \(P_m>N-m\) olduğu anda katkı biter.
Küçük bir örnek seçelim:
$$S(10)=\sum_{t=1}^{10}\mathbf{1}_{(10-t)!\mid t^{\,10-t}}(-1)^{10-t}\frac{t^{\,10-t}}{(10-t)!}.$$
\(m=10-t\) yazınca filtre net biçimde görülür.
\(m=4\) için \(P_4=6\) ve \(t=6\) bunun katıdır; katkı
$$\frac{6^4}{4!}=54$$
olur. \(m=3\) için \(P_3=6\) ama \(t=7\) bunun katı değildir, dolayısıyla terim yoktur. \(m=2\) için \(P_2=2\) ve \(t=8\) uygundur; katkı
$$\frac{8^2}{2!}=32$$
olur. \(m=1\) ve \(m=0\) durumları sırasıyla \(-9\) ve \(1\) verir. Daha büyük \(m\)-ler elenir. Sonuç:
$$S(10)=54+32-9+1=78.$$
Büyük hesaplamada yapılan şey tam olarak budur; sadece bunu bütün uygun \(m\)-ler için ön-toplama yayarız.
Sabit \(m\) için \(F_m(x)\), Faulhaber teoremine göre derece \(m+1\) olan bir polinomdur. Bu yüzden
$$F_m(0),F_m(1),\dots,F_m(m+1)$$
değerleri polinomu tamamen belirler. \(d=m+2\) ve \(y_i=F_m(i)\) dersek
$$F_m(x)=\sum_{i=0}^{d-1} y_i \prod_{\substack{0\le j\le d-1\\ j\ne i}}\frac{x-j}{i-j}$$
olur. Düğümler ardışık tamsayılar olduğundan payda
$$(-1)^{d-1-i} i!(d-1-i)!$$
şeklinde sadeleşir. Bu yüzden uygulamalar, mod altında faktöriyel ve ters faktöriyel tabloları ile \((x-j)\) terimlerinin prefix/suffix çarpımlarını kullanır. \(N=10^{18}\) hedefinde sadece \(m=0\) ile \(52\) arası katkı yaptığı için en büyük tablo boyutu \(54\)'tür.
Her dilde önce küçük \(n\) değerleri için \(S(n)\)'i doğrudan hesaplayan bir kesin kontrol bölümü vardır. Bu bölüm yalnızca doğrulama içindir: \(S(1)=1\), \(S(3)=-1\), \(\sum_{n=1}^{10}S(n)=43\) gibi kontroller yapılır; sonra birkaç daha büyük sınır için hızlı yöntem ile doğrudan toplam karşılaştırılır.
Asıl çözücü \(m\) üzerinde ilerlerken gerçek primorial \(P_m\)'yi, onun \(10^9+7\) modundaki değerini ve \(m!\)'in modüler değerini birlikte günceller. Her adımda
$$(-1)^m P_m^m (m!)^{-1}\pmod{10^9+7}$$
katsayısı hesaplanır ve \(\left\lfloor\frac{N-m}{P_m}\right\rfloor\) noktasındaki \(F_m\) değeriyle çarpılır. C++, Python ve Java sürümleri aynı matematiksel akışı uygular; farklı olan sadece büyük ara değerleri temsil etme biçimidir.
Dış toplam şaşırtıcı derecede kısadır. \(N=10^{18}\) için 53'e kadarki asalların çarpımı \(N-53\)'ten büyük olduğu anda süreç durur; dolayısıyla yalnızca \(m=0,\dots,52\) katkı verir.
Sabit bir \(m\) için örnek değer tablosu, faktöriyel tabloları ve prefix/suffix çarpımları \(O(m)\) zamanda hazırlanır. Toplam maliyet bu nedenle \(m_{\max}=52\) için \(O(m_{\max}^2)\), bellek ise \(O(m_{\max})\) olur. Zorlu görünen \(10^{18}\) büyüklüğü pratikte sorun yaratmaz; asıl önemli nokta, katkı veren \(m\) sayısının çok küçük olmasıdır.
El problema define un entero \(S(n)\) mediante una suma sobre \(t=1,2,\dots,n\). El término correspondiente a \(t\) solo sobrevive cuando se cumple la divisibilidad \((n-t)! \mid t^{\,n-t}\), y entonces aporta
$$(-1)^{n-t}\frac{t^{\,n-t}}{(n-t)!}.$$
Lo que se pide no es un valor aislado, sino la suma prefijo gigantesca
$$A(N)=\sum_{n=1}^{N} S(n)$$
para \(N=10^{18}\), tomada módulo \(10^9+7\). Un cálculo directo sería inviable. La solución eficaz consiste en describir exactamente qué valores de \(t\) pasan el test factorial y, una vez hecho eso, reducir todo a unas pocas sumas de potencias.
Las implementaciones siguen la misma idea: reindexar con \(m=n-t\), convertir la condición \(m!\mid t^m\) en una condición de primorial y evaluar las sumas de potencias mediante interpolación.
Escribimos
$$m=n-t,\qquad t=n-m.$$
Entonces
$$S(n)=\sum_{m=0}^{n-1}\mathbf{1}_{\,m!\mid (n-m)^m}\,(-1)^m\frac{(n-m)^m}{m!}.$$
Para la suma prefijo conviene fijar primero \(m\). Como \(n=t+m\), obtenemos
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{\substack{t\ge 1\\ t+m\le N\\ m!\mid t^m}} t^m.$$
Todo el problema queda concentrado en la pregunta: para un \(m\) fijo, ¿qué enteros \(t\) satisfacen \(m!\mid t^m\)?
Definimos
$$P_m=\prod_{\substack{p\le m\\ p\text{ prime}}} p,$$
con el producto vacío igual a \(1\), de modo que \(P_0=P_1=1\).
El hecho central es
$$m!\mid t^m \quad\Longleftrightarrow\quad P_m\mid t.$$
Si un primo \(p\le m\) no divide a \(t\), entonces \(v_p(t^m)=0\), mientras que \(v_p(m!)\ge 1\), así que la divisibilidad fracasa. Por tanto, todos los primos \(\le m\) deben dividir a \(t\), lo cual implica \(P_m\mid t\).
Recíprocamente, si \(P_m\mid t\), entonces cada primo \(p\le m\) aparece al menos una vez en \(t\), así que \(v_p(t^m)\ge m\). Además, por la fórmula de Legendre,
$$v_p(m!)=\sum_{j\ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor \le m.$$
Por ello \(v_p(t^m)\ge v_p(m!)\) para todos los primos relevantes, y en consecuencia \(m!\mid t^m\).
Esta equivalencia elimina por completo la parte difícil del filtro: ya no hay que inspeccionar un factorial, solo comprobar si \(t\) es múltiplo de un primorial concreto.
Si \(t=kP_m\), entonces
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{kP_m+m\le N}(kP_m)^m,$$
y por tanto
$$A(N)=\sum_{m\ge 0}(-1)^m\frac{P_m^m}{m!}\sum_{k=1}^{\left\lfloor\frac{N-m}{P_m}\right\rfloor} k^m.$$
Para cada \(m\) solo queda evaluar
$$F_m(x)=\sum_{k=1}^{x} k^m,\qquad x=\left\lfloor\frac{N-m}{P_m}\right\rfloor.$$
El bucle exterior es corto porque los primoriales crecen muy deprisa. En cuanto \(P_m>N-m\), el término deja de contribuir.
En este caso
$$S(10)=\sum_{t=1}^{10}\mathbf{1}_{(10-t)!\mid t^{\,10-t}}(-1)^{10-t}\frac{t^{\,10-t}}{(10-t)!}.$$
Tomamos \(m=10-t\).
Para \(m=4\), el primorial es \(P_4=6\) y \(t=6\) sí es múltiplo de \(6\), así que el término aporta
$$\frac{6^4}{4!}=54.$$
Para \(m=3\), también tenemos \(P_3=6\), pero ahora \(t=7\) no es múltiplo de \(6\), así que el término desaparece. Para \(m=2\), \(P_2=2\) y \(t=8\) sí es admisible; su contribución es
$$\frac{8^2}{2!}=32.$$
Los casos \(m=1\) y \(m=0\) aportan \(-9\) y \(1\). Los demás fallan el criterio. Por tanto,
$$S(10)=54+32-9+1=78.$$
Este ejemplo pequeño es exactamente el mismo mecanismo que luego se usa dentro del prefijo enorme.
Para \(m\) fijo, \(F_m(x)\) es un polinomio de grado \(m+1\) por el teorema de Faulhaber. Por eso queda determinado por
$$F_m(0),F_m(1),\dots,F_m(m+1).$$
Si ponemos \(d=m+2\) y \(y_i=F_m(i)\), entonces
$$F_m(x)=\sum_{i=0}^{d-1} y_i \prod_{\substack{0\le j\le d-1\\ j\ne i}}\frac{x-j}{i-j}.$$
Como los nodos son enteros consecutivos, el denominador se simplifica a
$$(-1)^{d-1-i} i!(d-1-i)!.$$
Por eso la implementación construye factoriales e inversos factoriales módulo \(10^9+7\), y usa productos prefijo y sufijo de \((x-j)\) para evaluar rápidamente todos los numeradores. Para el objetivo \(N=10^{18}\), solo aparecen \(m=0,\dots,52\), así que las tablas de interpolación nunca superan \(54\) valores.
Las tres versiones incluyen una rutina exacta, con enteros de precisión arbitraria, para calcular \(S(n)\) directamente en casos pequeños. Esa rutina se usa como verificación: comprueba \(S(1)=1\), \(S(3)=-1\), la suma prefijo hasta \(10\) igual a \(43\), y varios límites más grandes comparando el método rápido con la suma directa.
El solucionador principal recorre los valores de \(m\), manteniendo el primorial real \(P_m\), su residuo módulo \(10^9+7\) y el valor modular de \(m!\). En cada paso calcula
$$(-1)^m P_m^m (m!)^{-1}\pmod{10^9+7}$$
y lo multiplica por el valor interpolado de \(F_m\!\left(\left\lfloor\frac{N-m}{P_m}\right\rfloor\right)\). Las implementaciones en C++, Python y Java siguen exactamente esta misma tubería matemática.
La suma exterior es muy corta. Para \(N=10^{18}\), el primorial hasta \(53\) ya supera \(N-53\), de modo que solo contribuyen \(m=0,1,\dots,52\).
Para cada \(m\), construir la tabla de muestras, las factoriales, las inversas factoriales y los productos prefijo/sufijo cuesta \(O(m)\). En total, el coste es \(O(m_{\max}^2)\) con \(m_{\max}=52\), y la memoria es \(O(m_{\max})\). En otras palabras, el tamaño gigantesco de \(N\) no domina la ejecución porque el número de exponentes relevantes es muy pequeño.
题目把整数 \(S(n)\) 定义为对 \(t=1,2,\dots,n\) 的求和。只有当 \((n-t)! \mid t^{\,n-t}\) 成立时，编号为 \(t\) 的那一项才会保留下来；此时它的贡献是
$$(-1)^{n-t}\frac{t^{\,n-t}}{(n-t)!}.$$
真正要求的不是某一个单独的 \(S(n)\)，而是巨大的前缀和
$$A(N)=\sum_{n=1}^{N} S(n)$$
在 \(N=10^{18}\) 时对 \(10^9+7\) 取模的结果。逐项暴力检查完全不可行。有效做法是先把这个看起来很难的阶乘整除条件彻底改写成“\(t\) 是否为某个 primorial 的倍数”，然后把剩下的计算压缩成很短的一串幂和。
三份实现都基于同一条推导链：先把 \(m=n-t\) 固定下来，再用 \(p\)-进赋值证明可行的 \(t\) 恰好是 primorial 的倍数，最后用插值计算 \(\sum_{k=1}^{x}k^m\)。
令
$$m=n-t,\qquad t=n-m.$$
于是定义式可以改写为
$$S(n)=\sum_{m=0}^{n-1}\mathbf{1}_{\,m!\mid (n-m)^m}\,(-1)^m\frac{(n-m)^m}{m!}.$$
接着把前缀和按 \(m\) 分组，因为 \(n=t+m\)，所以
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{\substack{t\ge 1\\ t+m\le N\\ m!\mid t^m}} t^m.$$
这样一来，核心问题就变成：在固定 \(m\) 的情况下，哪些 \(t\) 会满足 \(m!\mid t^m\)？
定义
$$P_m=\prod_{\substack{p\le m\\ p\text{ prime}}} p,$$
空乘积取 \(1\)，所以 \(P_0=P_1=1\)。这就是不超过 \(m\) 的所有素数的乘积。
实现真正利用的关键等价式是
$$m!\mid t^m \quad\Longleftrightarrow\quad P_m\mid t.$$
先看必要性。如果某个素数 \(p\le m\) 不整除 \(t\)，那么 \(v_p(t^m)=0\)。但由于 \(p\) 出现在 \(m!\) 里，必有 \(v_p(m!)\ge 1\)。于是 \(m!\) 不可能整除 \(t^m\)。因此所有不超过 \(m\) 的素数都必须整除 \(t\)，也就是 \(P_m\mid t\)。
再看充分性。若 \(P_m\mid t\)，则每个 \(p\le m\) 都至少在 \(t\) 中出现一次，所以 \(v_p(t^m)\ge m\)。另一方面，Legendre 公式给出
$$v_p(m!)=\sum_{j\ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor \le m.$$
因此对每个相关素数都有 \(v_p(t^m)\ge v_p(m!)\)。而大于 \(m\) 的素数根本不会出现在 \(m!\) 中，所以不需要再检查。由此得到 \(m!\mid t^m\)。
这一步把原本困难的条件彻底压缩成一个简单的筛选规则：\(t\) 只需要是 \(P_m\) 的倍数。
既然 \(t\) 必须写成 \(t=kP_m\)，那么
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{kP_m+m\le N}(kP_m)^m,$$
从而
$$A(N)=\sum_{m\ge 0}(-1)^m\frac{P_m^m}{m!}\sum_{k=1}^{\left\lfloor\frac{N-m}{P_m}\right\rfloor} k^m.$$
所以每个 \(m\) 只剩下一个标准对象：
$$F_m(x)=\sum_{k=1}^{x} k^m,\qquad x=\left\lfloor\frac{N-m}{P_m}\right\rfloor.$$
由于 primorial 增长极快，外层求和很快就会停止。一旦 \(P_m>N-m\)，对应项就不再有任何贡献。
这个小例子可以直观看到 primorial 过滤器如何工作：
$$S(10)=\sum_{t=1}^{10}\mathbf{1}_{(10-t)!\mid t^{\,10-t}}(-1)^{10-t}\frac{t^{\,10-t}}{(10-t)!}.$$
令 \(m=10-t\)。
当 \(m=4\) 时，\(P_4=2\cdot 3=6\)，而此时 \(t=6\) 正好是 \(6\) 的倍数，所以该项保留，贡献为
$$\frac{6^4}{4!}=54.$$
当 \(m=3\) 时，\(P_3=6\)，但这时 \(t=7\) 不是 \(6\) 的倍数，所以这一项直接消失。对于 \(m=2\)，有 \(P_2=2\)，而 \(t=8\) 合法，贡献
$$\frac{8^2}{2!}=32.$$
\(m=1\) 和 \(m=0\) 总是保留，分别贡献 \(-9\) 与 \(1\)。其余更大的 \(m\) 都无法通过整除条件。因此
$$S(10)=54+32-9+1=78.$$
大规模前缀和只是把同样的逻辑系统化并重复到所有相关的 \(m\) 上。
对固定的 \(m\)，根据 Faulhaber 定理，\(F_m(x)\) 是一个次数为 \(m+1\) 的多项式。因此只要知道
$$F_m(0),F_m(1),\dots,F_m(m+1)$$
就能恢复整个多项式。设 \(d=m+2\)，并记 \(y_i=F_m(i)\)，则
$$F_m(x)=\sum_{i=0}^{d-1} y_i \prod_{\substack{0\le j\le d-1\\ j\ne i}}\frac{x-j}{i-j}.$$
由于插值节点是连续整数，分母可以化简成
$$(-1)^{d-1-i} i!(d-1-i)!.$$
因此实现会预先建立阶乘和逆阶乘表，再用 \((x-j)\) 的前缀积与后缀积在线性时间内求出每个基函数的分子。对于目标 \(N=10^{18}\)，只有 \(m=0,1,\dots,52\) 需要处理，所以最大的插值表大小只有 \(54\)。
三种语言的实现都先保留了一段精确计算小规模 \(S(n)\) 的逻辑，使用任意精度整数来避免误差。这部分只用于校验推导是否正确：它验证 \(S(1)=1\)、\(S(3)=-1\)、\(\sum_{n=1}^{10}S(n)=43\)，并把若干更大的前缀和与快速算法逐一对比。
真正的求解器按 \(m\) 递增扫描，同时维护真实的 \(P_m\)、它在模 \(10^9+7\) 下的值，以及 \(m!\) 的模值。对每个 \(m\)，程序形成系数
$$(-1)^m P_m^m (m!)^{-1}\pmod{10^9+7}$$
再乘上 \(F_m\!\left(\left\lfloor\frac{N-m}{P_m}\right\rfloor\right)\) 的模值。C++、Python 和 Java 版本走的是同一条数学路线，只是底层大整数表示方式不同。
外层求和非常短。对 \(N=10^{18}\) 而言，不超过 \(53\) 的素数乘积已经大于 \(N-53\)，所以真正有贡献的只有 \(m=0\) 到 \(52\)。
固定一个 \(m\) 后，样本表、阶乘表、逆阶乘表以及前缀/后缀积都只需要 \(O(m)\) 时间，因此总复杂度是 \(O(m_{\max}^2)\)，其中 \(m_{\max}=52\)，空间复杂度是 \(O(m_{\max})\)。换句话说，虽然 \(N\) 大到 \(10^{18}\)，但程序实际处理的有效指数范围非常小，所以整体计算量并不大。
Задача определяет целое число \(S(n)\) как сумму по всем \(t=1,2,\dots,n\). Слагаемое с данным \(t\) остается только тогда, когда выполнено условие делимости \((n-t)! \mid t^{\,n-t}\); в этом случае его вклад равен
$$(-1)^{n-t}\frac{t^{\,n-t}}{(n-t)!}.$$
Нужно найти не одно отдельное значение, а огромную префиксную сумму
$$A(N)=\sum_{n=1}^{N} S(n)$$
при \(N=10^{18}\) по модулю \(10^9+7\). Прямой перебор невозможен. Рабочее решение сводит факториальную делимость к простому описанию допустимых \(t\), а затем превращает всю задачу в короткую сумму степенных сумм.
Во всех трех реализациях используется одна и та же схема: сначала вводится параметр \(m=n-t\), затем условие \(m!\mid t^m\) доказывается эквивалентным делимости на primorial, и после этого остаются только суммы вида \(\sum_{k=1}^{x}k^m\).
Положим
$$m=n-t,\qquad t=n-m.$$
Тогда
$$S(n)=\sum_{m=0}^{n-1}\mathbf{1}_{\,m!\mid (n-m)^m}\,(-1)^m\frac{(n-m)^m}{m!}.$$
Для префиксной суммы выгоднее сначала фиксировать \(m\). Поскольку \(n=t+m\), получаем
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{\substack{t\ge 1\\ t+m\le N\\ m!\mid t^m}} t^m.$$
Значит, центральный вопрос таков: какие значения \(t\) при фиксированном \(m\) удовлетворяют условию \(m!\mid t^m\)?
Введем
$$P_m=\prod_{\substack{p\le m\\ p\text{ prime}}} p,$$
причем пустое произведение равно \(1\), так что \(P_0=P_1=1\).
Ключевой факт:
$$m!\mid t^m \quad\Longleftrightarrow\quad P_m\mid t.$$
Если некоторый простой \(p\le m\) не делит \(t\), то \(v_p(t^m)=0\), тогда как \(v_p(m!)\ge 1\). Следовательно, делимость невозможна. Значит, каждый простой \(p\le m\) обязан делить \(t\), а значит, \(t\) делится на их произведение \(P_m\).
Обратно, если \(P_m\mid t\), то для каждого простого \(p\le m\) имеем \(v_p(t)\ge 1\), следовательно \(v_p(t^m)\ge m\). По формуле Лежандра
$$v_p(m!)=\sum_{j\ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor \le m,$$
поэтому \(v_p(t^m)\ge v_p(m!)\) для всех нужных простых. Простые больше \(m\) в \(m!\) не входят. Значит, \(m!\mid t^m\).
Именно этот шаг радикально упрощает задачу: вместо проверки факториала достаточно проверить, является ли \(t\) кратным конкретному primorial.
Подставляя \(t=kP_m\), получаем
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{kP_m+m\le N}(kP_m)^m,$$
то есть
$$A(N)=\sum_{m\ge 0}(-1)^m\frac{P_m^m}{m!}\sum_{k=1}^{\left\lfloor\frac{N-m}{P_m}\right\rfloor} k^m.$$
Для каждого \(m\) остается вычислить стандартную сумму
$$F_m(x)=\sum_{k=1}^{x} k^m,\qquad x=\left\lfloor\frac{N-m}{P_m}\right\rfloor.$$
Внешний цикл очень короткий, потому что primorial растет стремительно. Как только \(P_m>N-m\), соответствующий член обнуляется.
Маленький пример хорошо показывает действие фильтра:
$$S(10)=\sum_{t=1}^{10}\mathbf{1}_{(10-t)!\mid t^{\,10-t}}(-1)^{10-t}\frac{t^{\,10-t}}{(10-t)!}.$$
Пусть \(m=10-t\).
При \(m=4\) имеем \(P_4=6\), а \(t=6\) делится на \(6\), поэтому вклад равен
$$\frac{6^4}{4!}=54.$$
При \(m=3\) также \(P_3=6\), но \(t=7\) уже не кратно \(6\), значит этот член отсутствует. При \(m=2\) имеем \(P_2=2\), и \(t=8\) допустимо, что дает
$$\frac{8^2}{2!}=32.$$
Случаи \(m=1\) и \(m=0\) дают \(-9\) и \(1\). Остальные значения \(m\) не проходят условие делимости. Поэтому
$$S(10)=54+32-9+1=78.$$
Именно так и работает полное решение, только затем эта логика суммируется по всем релевантным \(m\).
Для фиксированного \(m\) функция \(F_m(x)\) по формуле Фаульхабера является многочленом степени \(m+1\). Значит, ее полностью определяют значения
$$F_m(0),F_m(1),\dots,F_m(m+1).$$
Если положить \(d=m+2\) и \(y_i=F_m(i)\), то
$$F_m(x)=\sum_{i=0}^{d-1} y_i \prod_{\substack{0\le j\le d-1\\ j\ne i}}\frac{x-j}{i-j}.$$
Поскольку узлы интерполяции идут подряд, знаменатель упрощается до
$$(-1)^{d-1-i} i!(d-1-i)!.$$
Поэтому реализации заранее строят таблицы факториалов и обратных факториалов по модулю \(10^9+7\), а числители всех базисных множителей получают через префиксные и суффиксные произведения \((x-j)\). Для цели \(N=10^{18}\) реально нужны только \(m=0,\dots,52\), так что максимальная таблица содержит всего \(54\) значения.
Во всех версиях есть небольшой точный вычислитель \(S(n)\) на малых \(n\), использующий целые произвольной длины. Он нужен не для финального ответа, а для проверки вывода: подтверждаются равенства \(S(1)=1\), \(S(3)=-1\), \(\sum_{n=1}^{10}S(n)=43\), а также сравниваются несколько более длинных префиксов между медленным и быстрым методами.
Основной алгоритм проходит по значениям \(m\), поддерживая реальный primorial \(P_m\), его остаток по модулю \(10^9+7\) и значение \(m!\) по тому же модулю. Для каждого \(m\) формируется коэффициент
$$(-1)^m P_m^m (m!)^{-1}\pmod{10^9+7}$$
и умножается на интерполированное значение \(F_m\!\left(\left\lfloor\frac{N-m}{P_m}\right\rfloor\right)\). Реализации на C++, Python и Java делают одну и ту же математику; различаются только языковые детали представления больших чисел.
Внешняя сумма очень коротка. При \(N=10^{18}\) произведение всех простых до \(53\) уже больше, чем \(N-53\), поэтому вклад дают только \(m=0,1,\dots,52\).
Для каждого фиксированного \(m\) построение таблицы значений, факториалов, обратных факториалов и префиксно-суффиксных произведений требует \(O(m)\) модульных операций. Итого получаем \(O(m_{\max}^2)\) при \(m_{\max}=52\) и память \(O(m_{\max})\). Огромное значение \(N\) не приводит к огромной работе, потому что число существенных значений \(m\) остается очень маленьким.
تعرّف المسألة عددًا صحيحًا \(S(n)\) على أنه مجموع على جميع القيم \(t=1,2,\dots,n\). الحد الموافق لـ \(t\) لا يبقى إلا إذا تحققت القابلية للقسمة \((n-t)! \mid t^{\,n-t}\)، وعندها تكون مساهمته
$$(-1)^{n-t}\frac{t^{\,n-t}}{(n-t)!}.$$
المطلوب ليس قيمة منفردة لـ \(S(n)\)، بل المجموع التراكمي الضخم
$$A(N)=\sum_{n=1}^{N} S(n)$$
عند \(N=10^{18}\) modulo \(10^9+7\). الحساب المباشر مستحيل عمليًا. الفكرة الفعالة هي تحويل شرط القسمة الذي يحتوي على عاملي إلى وصف بسيط للقيم المسموح بها من \(t\)، ثم اختزال المسألة كلها إلى عدد صغير من مجاميع القوى.
تعتمد النسخ الثلاث على السلسلة نفسها من الأفكار: نثبّت أولًا \(m=n-t\)، ثم نبرهن أن الشرط \(m!\mid t^m\) مكافئ تمامًا لكون \(t\) من مضاعفات primorial مناسب، وبعد ذلك نحسب مجاميع القوى بالاستيفاء.
لنكتب
$$m=n-t,\qquad t=n-m.$$
عندئذ تصبح الصيغة
$$S(n)=\sum_{m=0}^{n-1}\mathbf{1}_{\,m!\mid (n-m)^m}\,(-1)^m\frac{(n-m)^m}{m!}.$$
ولحساب المجموع التراكمي من الأنسب أن نجعل \(m\) هو الفهرس الخارجي. بما أن \(n=t+m\)، نحصل على
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{\substack{t\ge 1\\ t+m\le N\\ m!\mid t^m}} t^m.$$
إذًا جوهر المسألة هو: لأي قيم من \(t\)، ومع \(m\) ثابت، يتحقق الشرط \(m!\mid t^m\)؟
نعرّف
$$P_m=\prod_{\substack{p\le m\\ p\text{ prime}}} p,$$
ومع اعتبار الجداء الخالي مساويًا لـ \(1\)، يكون \(P_0=P_1=1\).
الحقيقة الحاسمة هي
$$m!\mid t^m \quad\Longleftrightarrow\quad P_m\mid t.$$
إذا كان هناك عدد أولي \(p\le m\) لا يقسم \(t\)، فإن \(v_p(t^m)=0\)، بينما \(v_p(m!)\ge 1\) لأن \(p\) يظهر داخل \(m!\). عندئذ تفشل القابلية للقسمة فورًا. لذلك يجب أن يقسم كل عدد أولي لا يتجاوز \(m\) العدد \(t\)، وهذا يعني أن \(P_m\mid t\).
أما في الاتجاه العكسي، فإذا كان \(P_m\mid t\)، فكل عدد أولي \(p\le m\) يظهر مرة واحدة على الأقل في \(t\)، ومن ثم \(v_p(t^m)\ge m\). ومن صيغة ليجاندر
$$v_p(m!)=\sum_{j\ge 1}\left\lfloor \frac{m}{p^j}\right\rfloor \le m$$
نستنتج أن \(v_p(t^m)\ge v_p(m!)\) لكل عدد أولي ذي صلة. ولا توجد أعداد أولية أكبر من \(m\) داخل \(m!\). إذن يتحقق \(m!\mid t^m\).
هذه هي النقلة الأساسية في الحل: بدل فحص عاملي كامل، يكفي أن نعرف هل \(t\) من مضاعفات جداء الأعداد الأولية حتى \(m\) أم لا.
بما أن \(t\) يجب أن يكتب على صورة \(t=kP_m\)، فإن
$$A(N)=\sum_{m\ge 0}\frac{(-1)^m}{m!}\sum_{kP_m+m\le N}(kP_m)^m,$$
ومن ثم
$$A(N)=\sum_{m\ge 0}(-1)^m\frac{P_m^m}{m!}\sum_{k=1}^{\left\lfloor\frac{N-m}{P_m}\right\rfloor} k^m.$$
لكل \(m\) لم يعد مطلوبًا إلا حساب
$$F_m(x)=\sum_{k=1}^{x} k^m,\qquad x=\left\lfloor\frac{N-m}{P_m}\right\rfloor.$$
ويظل هذا المجموع الخارجي قصيرًا لأن الـ primorial ينمو بسرعة كبيرة. بمجرد أن يصبح \(P_m>N-m\)، ينعدم الإسهام نهائيًا.
يوضح هذا المثال الصغير كيف يعمل المرشح فعليًا:
$$S(10)=\sum_{t=1}^{10}\mathbf{1}_{(10-t)!\mid t^{\,10-t}}(-1)^{10-t}\frac{t^{\,10-t}}{(10-t)!}.$$
نضع \(m=10-t\).
عندما \(m=4\)، يكون \(P_4=2\cdot 3=6\)، وفي هذه الحالة \(t=6\) من مضاعفات \(6\)، لذا يبقى الحد ويعطي
$$\frac{6^4}{4!}=54.$$
وعندما \(m=3\)، يبقى \(P_3=6\) لكن \(t=7\) ليس من مضاعفات \(6\)، لذلك يختفي هذا الحد. أما عند \(m=2\)، فلدينا \(P_2=2\) و\(t=8\) مقبول، ومساهمته
$$\frac{8^2}{2!}=32.$$
الحالتان \(m=1\) و\(m=0\) تعطيان \(-9\) و\(1\). أما القيم الأكبر من \(m\) فلا تحقق شرط القسمة. إذن
$$S(10)=54+32-9+1=78.$$
والحساب الكامل يفعل الشيء نفسه تمامًا، لكنه يجمع هذه المساهمات عبر جميع القيم المهمة لـ \(m\).
عند تثبيت \(m\)، تكون \(F_m(x)\) كثيرة حدود من الدرجة \(m+1\) وفق صيغة Faulhaber. لذا فهي تتحدد بالكامل بواسطة القيم
$$F_m(0),F_m(1),\dots,F_m(m+1).$$
إذا وضعنا \(d=m+2\) و\(y_i=F_m(i)\)، فإن
$$F_m(x)=\sum_{i=0}^{d-1} y_i \prod_{\substack{0\le j\le d-1\\ j\ne i}}\frac{x-j}{i-j}.$$
وبما أن نقاط الاستيفاء أعداد صحيحة متتالية، فإن المقام يتبسط إلى
$$(-1)^{d-1-i} i!(d-1-i)!.$$
لهذا تبني التطبيقات جداول للعوامل والعوامل العكسية modulo \(10^9+7\)، ثم تستخدم جداءات prefix وsuffix لعوامل \((x-j)\) للحصول على البسوط بسرعة خطية. وعند \(N=10^{18}\)، لا تظهر إلا القيم \(m=0,\dots,52\)، لذلك لا يتجاوز أكبر جدول استيفاء \(54\) عنصرًا.
تحتوي كل نسخة على جزء صغير يحسب \(S(n)\) مباشرة باستعمال أعداد صحيحة ذات دقة غير محدودة. هذا الجزء مخصص للتحقق فقط: فهو يثبت أن \(S(1)=1\)، و\(S(3)=-1\)، وأن \(\sum_{n=1}^{10}S(n)=43\)، ثم يقارن عدة مجاميع أصغر بين الطريقة المباشرة والطريقة السريعة.
بعد ذلك يمر الحل السريع على قيم \(m\) تصاعديًا، مع تحديث الـ primorial الحقيقي \(P_m\)، وباقيه modulo \(10^9+7\)، وقيمة \(m!\) modulo \(10^9+7\). في كل خطوة يُحسب المعامل
$$(-1)^m P_m^m (m!)^{-1}\pmod{10^9+7}$$
ثم يضرب في القيمة المستوفاة لـ \(F_m\!\left(\left\lfloor\frac{N-m}{P_m}\right\rfloor\right)\). وتنفذ تطبيقات C++ وPython وJava هذا الخط الرياضي نفسه دون تغيير في الفكرة.
المجموع الخارجي قصير جدًا. عند \(N=10^{18}\)، يكون حاصل ضرب جميع الأعداد الأولية حتى \(53\) أكبر من \(N-53\)، لذا لا تسهم إلا القيم \(m=0\) حتى \(m=52\).
لكل \(m\) ثابت، يتطلب بناء جدول القيم والعوامل والعوامل العكسية وجدائي prefix وsuffix زمنًا مقداره \(O(m)\). لذلك يكون التعقيد الكلي \(O(m_{\max}^2)\) مع \(m_{\max}=52\)، واستهلاك الذاكرة \(O(m_{\max})\). وبالتالي فإن ضخامة \(N\) لا تتحول إلى ضخامة في زمن التنفيذ، لأن عدد الأسس المؤثرة صغير جدًا.