Let \(F(n)\) denote the last five non-zero digits of \(n!\). The problem asks for \(F(10^{12})\), so any method that tries to form the factorial directly is hopelessly too large.
The successful approach is to separate the trailing zeros from the rest of the factorial, compute the reduced factorial modulo \(5^5=3125\), observe what happens modulo \(2^5=32\), and then combine the two congruences into the final residue modulo \(10^5\).
Write \(v_p(m)\) for the exponent of the prime \(p\) in \(m\). The whole computation is driven by the fact that trailing zeros come from matching one factor 2 with one factor 5.
The number of trailing zeros in \(n!\) is the number of available factors 5, because factors 2 are more abundant. Therefore
$$e=v_5(n!)=\sum_{k\ge 1}\left\lfloor \frac{n}{5^k}\right\rfloor,$$
and the desired quantity is
$$F(n)\equiv \frac{n!}{10^e}\pmod{100000}.$$
This identity says exactly what must be preserved: remove the \(e\) matched pairs \((2,5)\), keep everything else, and then read the result modulo \(10^5\).
It is convenient to strip out the factors of 5 first and delay the matching factors of 2 until later. Define
$$U(n)=\prod_{m=1}^{n}\frac{m}{5^{v_5(m)}}.$$
Then \(U(n)=n!/5^e\). Split the product into terms not divisible by 5 and terms of the form \(5q\):
$$U(n)=\left(\prod_{\substack{1\le m\le n\\ 5\nmid m}} m\right)\left(\prod_{q=1}^{\lfloor n/5\rfloor}\frac{q}{5^{v_5(q)}}\right).$$
The second factor is exactly \(U(\lfloor n/5\rfloor)\). If we define
$$A(n)=\prod_{\substack{1\le m\le n\\ 5\nmid m}} m \pmod{3125},$$
then the key recurrence becomes
$$U(n)\equiv A(n)\,U\!\left(\left\lfloor\frac{n}{5}\right\rfloor\right)\pmod{3125}.$$
Each recursive step removes one layer of factor 5 from every multiple of 5. Repeating the step until the argument reaches 0 accounts for all powers of 5 in the factorial.
Write \(n=3125q+r\) with \(0\le r<3125\). Inside one full block of length 3125, the numbers not divisible by 5 form a complete reduced residue system modulo \(3125\). For an odd prime power, the product of all units is \(-1\) modulo that power, so
$$A(n)\equiv (-1)^q A(r)\pmod{3125}.$$
This is why the implementations precompute only one prefix table for a single block. Every complete block contributes either \(1\) or \(-1\), depending on whether \(q\) is even or odd, and the leftover part contributes one table lookup.
Since \(U(n)=n!/5^e\), one more adjustment is needed to remove the matching factor \(2^e\):
$$R_{3125}\equiv U(n)\,2^{-e}\pmod{3125}.$$
Because \(2\) is invertible modulo \(3125\) and \(\varphi(3125)=2500\), Euler's theorem allows the exponent of 2 to be reduced modulo 2500 when the inverse power is computed.
At this point \(R_{3125}\) is exactly the reduced factorial modulo \(5^5\).
The modulus \(100000\) factors as
$$100000=32\cdot 3125.$$
We already know the residue modulo 3125. On the modulo 32 side, the surviving power of 2 is
$$v_2(n!)-v_5(n!).$$
For large \(n\), and in particular for \(n=10^{12}\), this quantity is at least 5, so the reduced factorial is divisible by 32. Therefore the final answer is the unique solution of
$$x\equiv R_{3125}\pmod{3125},\qquad x\equiv 0\pmod{32}.$$
The implementations solve this by writing \(x=R_{3125}+3125k\) and choosing the unique \(k\pmod{32}\) that makes the second congruence true. Small values of \(n\) are handled directly so that this large-\(n\) shortcut is used only where it is valid.
Here
$$e=v_5(10!)=\left\lfloor\frac{10}{5}\right\rfloor=2.$$
After removing all factors of 5 from the numbers \(1,2,\dots,10\), the remaining factors are
$$1,2,3,4,1,6,7,8,9,2.$$
So
$$U(10)=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2=145152.$$
Now divide by the matching factor \(2^2\):
$$\frac{U(10)}{2^2}=36288.$$
Thus the last five non-zero digits of \(10!\) are \(36288\), which is the small case used to verify the method.
The C++, Python, and Java implementations begin by building a prefix table of products of positive integers that are not divisible by 5, reduced modulo 3125. Entry \(i\) stores the product of all such integers up to \(i\), so any remainder block can be answered immediately.
The main evaluator repeatedly replaces \(n\) by \(\lfloor n/5\rfloor\). At each level it determines how many complete blocks of length 3125 occur, applies the sign \((-1)^q\), multiplies by the stored prefix product for the leftover block, and then recurses. A separate loop computes \(v_5(n!)\) from Legendre's formula.
After the recursion returns the value of \(U(n)\) modulo 3125, the implementation multiplies by the modular inverse of \(2^e\) to obtain the reduced factorial modulo \(3125\). It then lifts this residue to modulo \(100000\) by enforcing the condition modulo 32. For tiny inputs, the implementations also keep a direct multiplication branch, which doubles as an easy correctness check.
The prefix table has length 3125, so its construction is a fixed one-time cost. The recursive stage divides \(n\) by 5 at each step, giving \(O(\log_5 n)\) levels, and each level performs only constant-time modular arithmetic.
Thus the running time for one query is \(O(\log n)\) after constant-size preprocessing, and the extra memory usage is \(O(\log n)\) for the recursive call stack, or \(O(1)\) extra space if the same recurrence is written iteratively. In concrete terms, the algorithm is fast because it never touches more than a handful of base-5 levels even when \(n=10^{12}\).
Sei \(F(n)\) die Zahl, die aus den letzten fünf von Null verschiedenen Ziffern von \(n!\) besteht. Gesucht ist also \(F(10^{12})\), und damit ist jede direkte Berechnung von \(n!\) völlig ausgeschlossen.
Die Lösung trennt die Endnullen vom restlichen Fakultätswert, berechnet die reduzierte Fakultät modulo \(5^5=3125\), bestimmt den zugehörigen Rest modulo \(2^5=32\) und setzt beide Informationen anschließend per chinesischem Restsatz zu einem Rest modulo \(10^5\) zusammen.
Schreibe \(v_p(m)\) für den Exponenten der Primzahl \(p\) in \(m\). Der Kern der Aufgabe ist, dass jede Endnull aus einem Paar \(2\cdot 5\) entsteht.
Die Anzahl der Endnullen in \(n!\) wird durch die Anzahl der Faktoren 5 bestimmt, weil Faktoren 2 häufiger vorkommen. Also gilt
$$e=v_5(n!)=\sum_{k\ge 1}\left\lfloor \frac{n}{5^k}\right\rfloor,$$
und die gesuchte Größe ist
$$F(n)\equiv \frac{n!}{10^e}\pmod{100000}.$$
Genau diese Formel beschreibt das Ziel: Die \(e\) passenden Paare \((2,5)\) werden entfernt, alle übrigen Faktoren bleiben erhalten, und danach wird nur der Rest modulo \(10^5\) betrachtet.
Zuerst ist es zweckmäßig, nur die Faktoren 5 herauszunehmen und die passenden Zweier später zu behandeln. Definiere
$$U(n)=\prod_{m=1}^{n}\frac{m}{5^{v_5(m)}}.$$
Dann ist \(U(n)=n!/5^e\). Zerlegt man das Produkt in nicht durch 5 teilbare Zahlen und Vielfache von 5, so erhält man
$$U(n)=\left(\prod_{\substack{1\le m\le n\\ 5\nmid m}} m\right)\left(\prod_{q=1}^{\lfloor n/5\rfloor}\frac{q}{5^{v_5(q)}}\right).$$
Der zweite Faktor ist genau \(U(\lfloor n/5\rfloor)\). Mit
$$A(n)=\prod_{\substack{1\le m\le n\\ 5\nmid m}} m \pmod{3125}$$
ergibt sich daher die zentrale Rekursion
$$U(n)\equiv A(n)\,U\!\left(\left\lfloor\frac{n}{5}\right\rfloor\right)\pmod{3125}.$$
Jeder Rekursionsschritt entfernt eine Schicht von Faktoren 5 aus allen Vielfachen von 5. Wiederholt man das, sind sämtliche Potenzen von 5 in der Fakultät erfasst.
Schreibe \(n=3125q+r\) mit \(0\le r<3125\). Innerhalb eines vollständigen Blocks der Länge 3125 bilden die nicht durch 5 teilbaren Zahlen ein vollständiges reduziertes Restsystem modulo \(3125\). Für eine ungerade Primzahlpotenz ist das Produkt aller Einheiten \(-1\) modulo dieser Potenz. Daher gilt
$$A(n)\equiv (-1)^q A(r)\pmod{3125}.$$
Deshalb brauchen die Implementierungen nur eine Präfixtabelle für einen einzigen Block. Jeder volle Block liefert je nach Parität von \(q\) entweder den Faktor \(1\) oder \(-1\), und der Restblock wird direkt aus der Tabelle gelesen.
Da \(U(n)=n!/5^e\) ist, muss noch der zugehörige Faktor \(2^e\) entfernt werden:
$$R_{3125}\equiv U(n)\,2^{-e}\pmod{3125}.$$
Weil \(2\) modulo \(3125\) invertierbar ist und \(\varphi(3125)=2500\) gilt, kann beim Berechnen dieser inversen Zweierpotenz der Exponent modulo 2500 reduziert werden.
Damit ist \(R_{3125}\) genau die reduzierte Fakultät modulo \(5^5\).
Der Modul zerfällt als
$$100000=32\cdot 3125.$$
Den Rest modulo 3125 kennen wir bereits. Modulo 32 bleibt nach dem Entfernen aller Endnullen noch die Zweierpotenz
$$v_2(n!)-v_5(n!).$$
Für große \(n\), insbesondere für \(n=10^{12}\), ist diese Differenz mindestens 5. Also ist die reduzierte Fakultät durch 32 teilbar, und die Endlösung ist der eindeutige Rest von
$$x\equiv R_{3125}\pmod{3125},\qquad x\equiv 0\pmod{32}.$$
Die Implementierungen setzen dazu \(x=R_{3125}+3125k\) und bestimmen das eindeutige \(k\pmod{32}\), das die zweite Kongruenz erfüllt. Für sehr kleine \(n\) wird stattdessen direkt multipliziert, damit diese Groß-\(n\)-Abkürzung nur dort verwendet wird, wo sie tatsächlich gilt.
Hier ist
$$e=v_5(10!)=\left\lfloor\frac{10}{5}\right\rfloor=2.$$
Entfernt man aus den Zahlen \(1,2,\dots,10\) alle Faktoren 5, bleiben
$$1,2,3,4,1,6,7,8,9,2.$$
Daher
$$U(10)=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2=145152.$$
Nun wird noch durch den passenden Faktor \(2^2\) geteilt:
$$\frac{U(10)}{2^2}=36288.$$
Die letzten fünf von Null verschiedenen Ziffern von \(10!\) sind also \(36288\). Dieses kleine Beispiel bestätigt die gesamte Herleitung.
Die C++-, Python- und Java-Implementierungen bauen zuerst eine Präfixtabelle der Produkte aller positiven Zahlen auf, die nicht durch 5 teilbar sind, jeweils reduziert modulo 3125. Damit lässt sich jeder Restblock sofort auslesen.
Der zentrale Auswerter ersetzt \(n\) wiederholt durch \(\lfloor n/5\rfloor\). Auf jeder Ebene bestimmt er die Anzahl voller 3125er-Blöcke, wendet das Vorzeichen \((-1)^q\) an, multipliziert den Tabellenwert des Restblocks hinzu und ruft sich dann mit dem kleineren Argument erneut auf. Parallel dazu wird \(v_5(n!)\) über die Legendre-Summe berechnet.
Nach der Rekursion liegt \(U(n)\) modulo 3125 vor. Danach multipliziert die Implementierung mit der modularen Inversen von \(2^e\), um die reduzierte Fakultät modulo 3125 zu erhalten. Anschließend wird dieser Rest mit der Bedingung modulo 32 zu einem eindeutigen Wert modulo 100000 kombiniert. Für sehr kleine Eingaben gibt es außerdem einen direkten Zweig, der zugleich als einfacher Plausibilitätstest dient.
Die Präfixtabelle hat feste Länge 3125 und verursacht deshalb nur konstante Vorarbeit. Danach halbiert oder viertelt sich das Problem nicht, sondern wird in jeder Rekursion durch Division durch 5 verkleinert. Es gibt also \(O(\log_5 n)\) Ebenen, und jede Ebene benötigt nur konstante modulare Arithmetik.
Damit beträgt die Laufzeit pro Anfrage nach der festen Vorberechnung \(O(\log n)\). Der zusätzliche Speicher ist \(O(\log n)\) für den Rekursionsstapel, beziehungsweise \(O(1)\) Zusatzspeicher bei einer iterativen Form derselben Rekursion. Praktisch ist das Verfahren schnell, weil selbst \(10^{12}\) nur sehr wenige Basis-5-Ebenen erzeugt.
\(F(n)\), \(n!\) sayısının sondaki sıfırlar atıldıktan sonra kalan son beş basamağı olsun. Soruda istenen değer \(F(10^{12})\) olduğundan, faktöriyeli doğrudan üretmeye çalışan her yöntem baştan elenir.
Başarılı çözüm, önce sondaki sıfırları ayırır, sonra indirgenmiş faktöriyeli \(5^5=3125\) modunda hesaplar, \(2^5=32\) modundaki davranışı belirler ve en sonda bu iki kalıntıyı Çin kalan teoremiyle \(10^5\) modunda birleştirir.
\(v_p(m)\), asal \(p\)'nin \(m\) içindeki üssü olsun. Tüm çözüm, her sondaki sıfırın bir \(2\cdot 5\) çiftinden geldiği gözlemine dayanır.
\(n!\) içindeki sondaki sıfır sayısı, 2'ler daha bol olduğu için, 5 çarpanlarının sayısına eşittir. Dolayısıyla
$$e=v_5(n!)=\sum_{k\ge 1}\left\lfloor \frac{n}{5^k}\right\rfloor,$$
ve aradığımız büyüklük
$$F(n)\equiv \frac{n!}{10^e}\pmod{100000}$$
olur. Bu formül, tam olarak neyin korunacağını söyler: eşleşen \(e\) tane \((2,5)\) çifti silinir, diğer tüm çarpanlar bırakılır ve sonuç \(10^5\) modunda okunur.
İlk adımda yalnızca 5 çarpanlarını söküp, eşleşen 2 kuvvetlerini sona bırakmak uygundur. Şöyle tanımlayalım:
$$U(n)=\prod_{m=1}^{n}\frac{m}{5^{v_5(m)}}.$$
Böylece \(U(n)=n!/5^e\) olur. Çarpımı, 5'e bölünmeyen terimler ile \(5q\) biçimindeki terimler diye ayırırsak
$$U(n)=\left(\prod_{\substack{1\le m\le n\\ 5\nmid m}} m\right)\left(\prod_{q=1}^{\lfloor n/5\rfloor}\frac{q}{5^{v_5(q)}}\right)$$
elde edilir. İkinci çarpım tam olarak \(U(\lfloor n/5\rfloor)\)'dir. Eğer
$$A(n)=\prod_{\substack{1\le m\le n\\ 5\nmid m}} m \pmod{3125}$$
dersek, temel özyineleme
$$U(n)\equiv A(n)\,U\!\left(\left\lfloor\frac{n}{5}\right\rfloor\right)\pmod{3125}$$
şeklini alır. Her adım, 5'in katı olan bütün sayılardan bir katman 5 çıkarır. Argüman 0'a düşünceye kadar bunu tekrarlamak, faktöriyeldeki tüm 5 kuvvetlerini hesaba katmış olur.
\(n=3125q+r\) olacak şekilde \(0\le r<3125\) yazalım. Uzunluğu 3125 olan tam bir blok içinde, 5'e bölünmeyen sayılar mod 3125'e göre tam bir indirgenmiş artık sistemi oluşturur. Tek asal kuvvetlerde bütün birimlerin çarpımı o modda \(-1\)'dir. Bu yüzden
$$A(n)\equiv (-1)^q A(r)\pmod{3125}$$
olur. Bu nedenle uygulamalar yalnızca tek bir blok için önek tablo kurar. Her tam blok, \(q\) çiftse \(1\), tekse \(-1\) katkısı yapar; kalan parça ise tek bir tablo erişimiyle gelir.
\(U(n)=n!/5^e\) olduğuna göre, şimdi karşılık gelen \(2^e\) çarpanını da kaldırmalıyız:
$$R_{3125}\equiv U(n)\,2^{-e}\pmod{3125}.$$
\(2\), mod 3125 altında terslenebilir ve \(\varphi(3125)=2500\) olduğundan, Euler teoremi sayesinde ters 2 kuvveti hesaplanırken üs 2500 moduna indirgenebilir.
Bu aşamadan sonra \(R_{3125}\), indirgenmiş faktöriyelimizin tam olarak \(5^5\) modundaki kalıntısıdır.
Modül
$$100000=32\cdot 3125$$
şeklinde ayrılır. Mod 3125 kalıntısını zaten biliyoruz. Mod 32 tarafında, bütün sondaki sıfırlar çıkarıldıktan sonra geriye kalan 2 kuvveti
$$v_2(n!)-v_5(n!)$$
kadardır. Büyük \(n\) için, özellikle \(n=10^{12}\) için, bu fark en az 5'tir. Dolayısıyla indirgenmiş faktöriyel 32'ye tam bölünür ve son cevap şu sistemin tek çözümüdür:
$$x\equiv R_{3125}\pmod{3125},\qquad x\equiv 0\pmod{32}.$$
Uygulamalar bunu \(x=R_{3125}+3125k\) yazarak ve ikinci koşulu sağlayan tek \(k\pmod{32}\) değerini bularak çözer. Çok küçük \(n\) değerleri için ise doğrudan çarpım yapan kısa bir dal tutulur; böylece mod 32'deki bu kısayol yalnızca gerçekten geçerli olduğu yerde kullanılır.
Burada
$$e=v_5(10!)=\left\lfloor\frac{10}{5}\right\rfloor=2.$$
\(1,2,\dots,10\) sayılarından bütün 5 çarpanlarını kaldırınca geriye
$$1,2,3,4,1,6,7,8,9,2$$
kalır. O hâlde
$$U(10)=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2=145152.$$
Şimdi eşleşen \(2^2\) çarpanını çıkaralım:
$$\frac{U(10)}{2^2}=36288.$$
Demek ki \(10!\)'in sondaki sıfırlar atıldıktan sonraki son beş basamağı \(36288\)'dir. Küçük örnek, tüm yöntemin doğru çalıştığını açıkça gösterir.
C++, Python ve Java uygulamaları önce, 5'e bölünmeyen pozitif tamsayıların mod 3125 altındaki kısmi çarpımlarını içeren bir önek tablo kurar. Böylece her kalan blok anında okunabilir.
Ana değerlendirici, \(n\) değerini tekrar tekrar \(\lfloor n/5\rfloor\) ile değiştirir. Her seviyede kaç tane tam 3125 bloğu olduğunu belirler, \((-1)^q\) işaretini uygular, kalan blok için tablodan değeri alır ve sonra daha küçük argümanla devam eder. Ayrı bir döngü de Legendre toplamını kullanarak \(v_5(n!)\) değerini hesaplar.
Özyineleme \(U(n)\) değerini mod 3125 altında döndürdükten sonra, uygulama bunu \(2^e\)'nin modüler tersiyle çarpar ve indirgenmiş faktöriyel kalıntısını elde eder. Daha sonra bu kalıntı, mod 32 koşulu da zorlanarak mod 100000'e kaldırılır. Çok küçük girdiler için tutulan doğrudan çarpım yolu aynı zamanda pratik bir doğruluk kontrolüdür.
Önek tablonun uzunluğu 3125'tir; dolayısıyla kurulumu sabit bir ön maliyettir. Bundan sonra özyineleme her adımda \(n\)'i 5'e böler, yani \(O(\log_5 n)\) seviye vardır ve her seviyede yalnızca sabit sayıda modüler işlem yapılır.
Bu yüzden tek sorgunun çalışma süresi, sabit boyutlu ön işlemeden sonra \(O(\log n)\) olur. Ek bellek kullanımı özyineleme yığını için \(O(\log n)\), aynı bağıntı iteratif yazılırsa \(O(1)\) ek alandır. Pratikte yöntem çok hızlıdır; çünkü \(10^{12}\) gibi bir değer bile yalnızca az sayıda 5 tabanlı seviyeye iner.
Sea \(F(n)\) el número formado por las últimas cinco cifras no nulas de \(n!\). La tarea consiste en hallar \(F(10^{12})\), así que cualquier intento de construir el factorial de forma directa está descartado desde el principio.
La idea correcta es separar los ceros finales del resto del factorial, calcular el factorial reducido módulo \(5^5=3125\), entender qué ocurre módulo \(2^5=32\) y después reconstruir el residuo final módulo \(10^5\) mediante el teorema chino del resto.
Denotemos por \(v_p(m)\) el exponente del primo \(p\) en \(m\). Toda la solución parte de que cada cero final procede de un par \(2\cdot 5\).
El número de ceros finales de \(n!\) coincide con el número de factores 5, porque los factores 2 sobran. Por tanto
$$e=v_5(n!)=\sum_{k\ge 1}\left\lfloor \frac{n}{5^k}\right\rfloor,$$
y la cantidad buscada es
$$F(n)\equiv \frac{n!}{10^e}\pmod{100000}.$$
Esta igualdad expresa exactamente el objetivo: eliminar los \(e\) pares emparejados \((2,5)\), conservar todos los demás factores y leer el resultado módulo \(10^5\).
Conviene quitar primero los factores 5 y dejar para el final los factores 2 que los compensan. Definimos
$$U(n)=\prod_{m=1}^{n}\frac{m}{5^{v_5(m)}}.$$
Entonces \(U(n)=n!/5^e\). Si separamos los términos no divisibles por 5 de los términos de la forma \(5q\), obtenemos
$$U(n)=\left(\prod_{\substack{1\le m\le n\\ 5\nmid m}} m\right)\left(\prod_{q=1}^{\lfloor n/5\rfloor}\frac{q}{5^{v_5(q)}}\right).$$
El segundo producto es exactamente \(U(\lfloor n/5\rfloor)\). Si definimos
$$A(n)=\prod_{\substack{1\le m\le n\\ 5\nmid m}} m \pmod{3125},$$
la recurrencia fundamental pasa a ser
$$U(n)\equiv A(n)\,U\!\left(\left\lfloor\frac{n}{5}\right\rfloor\right)\pmod{3125}.$$
Cada paso recursivo elimina una capa de factores 5 de todos los múltiplos de 5. Repetirlo hasta llegar a 0 contabiliza todas las potencias de 5 presentes en el factorial.
Escribamos \(n=3125q+r\) con \(0\le r<3125\). Dentro de un bloque completo de longitud 3125, los números no divisibles por 5 forman un sistema reducido completo de residuos módulo \(3125\). Para una potencia impar de un primo, el producto de todas las unidades es \(-1\) módulo esa potencia. Por ello
$$A(n)\equiv (-1)^q A(r)\pmod{3125}.$$
De ahí que las implementaciones solo necesiten precalcular una tabla de prefijos para un único bloque. Cada bloque completo aporta \(1\) o \(-1\) según la paridad de \(q\), y la parte sobrante se obtiene con una sola consulta a la tabla.
Como \(U(n)=n!/5^e\), todavía falta eliminar el factor \(2^e\) que corresponde a esos ceros finales:
$$R_{3125}\equiv U(n)\,2^{-e}\pmod{3125}.$$
Dado que \(2\) es una unidad módulo \(3125\) y \(\varphi(3125)=2500\), el teorema de Euler permite reducir el exponente módulo 2500 al calcular esa potencia inversa de 2.
En este punto \(R_{3125}\) ya es exactamente el factorial reducido módulo \(5^5\).
El módulo se descompone como
$$100000=32\cdot 3125.$$
Ya conocemos el residuo módulo 3125. En el lado módulo 32, la potencia de 2 que sobrevive tras eliminar todos los ceros finales es
$$v_2(n!)-v_5(n!).$$
Para \(n\) grande, y en particular para \(n=10^{12}\), esta diferencia es al menos 5, así que el factorial reducido es múltiplo de 32. Por tanto, la respuesta final es la solución única del sistema
$$x\equiv R_{3125}\pmod{3125},\qquad x\equiv 0\pmod{32}.$$
Las implementaciones lo resuelven escribiendo \(x=R_{3125}+3125k\) y escogiendo el único \(k\pmod{32}\) que satisface la segunda congruencia. Para valores muy pequeños de \(n\) se conserva una rama directa, de modo que este atajo para \(n\) grande solo se usa cuando corresponde.
Aquí
$$e=v_5(10!)=\left\lfloor\frac{10}{5}\right\rfloor=2.$$
Si quitamos todos los factores 5 de los números \(1,2,\dots,10\), quedan
$$1,2,3,4,1,6,7,8,9,2.$$
Por tanto
$$U(10)=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2=145152.$$
Ahora dividimos entre el factor emparejado \(2^2\):
$$\frac{U(10)}{2^2}=36288.$$
Así, las últimas cinco cifras no nulas de \(10!\) son \(36288\). Este caso pequeño confirma exactamente la mecánica usada en el problema grande.
Las implementaciones en C++, Python y Java empiezan construyendo una tabla de prefijos con los productos de enteros positivos no divisibles por 5, reducidos módulo 3125. Con ello, cualquier bloque residual se obtiene de inmediato.
El evaluador principal sustituye repetidamente \(n\) por \(\lfloor n/5\rfloor\). En cada nivel calcula cuántos bloques completos de longitud 3125 aparecen, aplica el signo \((-1)^q\), multiplica por el valor de la tabla correspondiente al bloque parcial y continúa con el argumento más pequeño. En paralelo, un bucle independiente calcula \(v_5(n!)\) mediante la suma de Legendre.
Una vez obtenida \(U(n)\) módulo 3125, la implementación la multiplica por la inversa modular de \(2^e\) para conseguir el factorial reducido módulo 3125. Después eleva ese residuo a módulo 100000 imponiendo además la condición módulo 32. Para entradas diminutas, las implementaciones conservan una rama de multiplicación directa que también sirve como comprobación elemental.
La tabla de prefijos tiene longitud 3125, así que su construcción es un coste fijo de una sola vez. A continuación, la recurrencia divide \(n\) por 5 en cada paso, por lo que hay \(O(\log_5 n)\) niveles, y cada nivel solo realiza unas pocas operaciones modulares de tiempo constante.
En consecuencia, el tiempo por consulta es \(O(\log n)\) tras el preproceso de tamaño constante. La memoria adicional es \(O(\log n)\) por la pila recursiva, u \(O(1)\) extra si la misma idea se implementa de forma iterativa. En la práctica el algoritmo es rápido porque incluso \(10^{12}\) solo genera unas pocas capas en base 5.
记 \(F(n)\) 为 \(n!\) 去掉末尾所有 0 之后的最后五位数字。题目要求的是 \(F(10^{12})\)，因此任何先把 \(n!\) 真正算出来再截取尾部的方法都不可能可行。
正确思路是把“末尾的 0”与“剩下的有效数字”分开处理：先在模 \(5^5=3125\) 下求出删去所有 5 因子后的结构，再看模 \(2^5=32\) 的结果，最后用中国剩余定理把这两部分合并成模 \(10^5\) 的唯一答案。
设 \(v_p(m)\) 表示素数 \(p\) 在整数 \(m\) 的分解中出现的次数。整道题的关键是：每一个尾零都来自一对 \(2\cdot 5\)。
\(n!\) 的尾零个数由 5 的个数决定，因为 2 的个数总是更多。因此
$$e=v_5(n!)=\sum_{k\ge 1}\left\lfloor \frac{n}{5^k}\right\rfloor,$$
而我们真正想要的是
$$F(n)\equiv \frac{n!}{10^e}\pmod{100000}.$$
这条公式精确说明了目标对象是什么：把 \(n!\) 中那 \(e\) 对配对成功的 \((2,5)\) 删除，其他所有因子都保留，然后只看模 \(10^5\) 的结果。
先只处理 5 因子会更自然，把对应的 2 留到后面统一消去。定义
$$U(n)=\prod_{m=1}^{n}\frac{m}{5^{v_5(m)}}.$$
于是 \(U(n)=n!/5^e\)。把乘积拆成“不被 5 整除”的部分和“形如 \(5q\)”的部分，有
$$U(n)=\left(\prod_{\substack{1\le m\le n\\ 5\nmid m}} m\right)\left(\prod_{q=1}^{\lfloor n/5\rfloor}\frac{q}{5^{v_5(q)}}\right).$$
第二个乘积恰好就是 \(U(\lfloor n/5\rfloor)\)。如果记
$$A(n)=\prod_{\substack{1\le m\le n\\ 5\nmid m}} m \pmod{3125},$$
那么最核心的递推式就是
$$U(n)\equiv A(n)\,U\!\left(\left\lfloor\frac{n}{5}\right\rfloor\right)\pmod{3125}.$$
这一步的含义很直接：每递归一次，就把所有 5 的倍数里“最外层”的那个 5 剥掉一层。不断重复，直到参数变成 0，阶乘里所有 5 的幂次就都被处理完了。
把 \(n\) 写成 \(n=3125q+r\)，其中 \(0\le r<3125\)。在任意一个完整的 3125 长度区间里，那些不被 5 整除的数在模 3125 意义下正好构成一个完整的既约剩余系。对于奇素数幂模数，所有单位元的乘积等于 \(-1\)。因此
$$A(n)\equiv (-1)^q A(r)\pmod{3125}.$$
这正是实现里只预处理一个前缀表就够用的原因。每个完整块只贡献一个符号 \(1\) 或 \(-1\)，取决于 \(q\) 的奇偶性；剩下那段长度不到 3125 的尾块则由前缀表直接给出。
因为 \(U(n)=n!/5^e\)，所以还需要把与这些 5 匹配的 \(2^e\) 也除掉：
$$R_{3125}\equiv U(n)\,2^{-e}\pmod{3125}.$$
\(2\) 在模 3125 下是可逆元，而且 \(\varphi(3125)=2500\)，所以根据 Euler 定理，求逆幂时可以把指数按 2500 取模来缩减。
做到这一步时，\(R_{3125}\) 就已经是“删掉所有尾零后的阶乘”在模 \(5^5\) 下的准确剩余。
模数分解为
$$100000=32\cdot 3125.$$
模 3125 的部分我们已经算出。至于模 32，删掉所有尾零之后还剩下多少个 2，正好是
$$v_2(n!)-v_5(n!).$$
对于足够大的 \(n\)，特别是本题的 \(10^{12}\)，这个差至少是 5，因此删零后的阶乘一定仍然被 32 整除。于是最终答案就是下面这个同余组在模 \(100000\) 下的唯一解：
$$x\equiv R_{3125}\pmod{3125},\qquad x\equiv 0\pmod{32}.$$
实现时把它写成 \(x=R_{3125}+3125k\)，再求出满足第二个条件的唯一 \(k\pmod{32}\)。而对于非常小的 \(n\)，程序保留了一个直接乘法分支，这样模 32 的这个大数捷径只会在真正适用的范围内使用。
此时
$$e=v_5(10!)=\left\lfloor\frac{10}{5}\right\rfloor=2.$$
把 \(1,2,\dots,10\) 中每个数包含的 5 因子都删掉，剩下的是
$$1,2,3,4,1,6,7,8,9,2.$$
因此
$$U(10)=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2=145152.$$
再除掉匹配的 \(2^2\)：
$$\frac{U(10)}{2^2}=36288.$$
所以 \(10!\) 去掉末尾 0 之后的最后五位正是 \(36288\)。这个小例子和程序中的校验结果完全一致，也把整套推导具体展示出来了。
C++、Python 和 Java 三个实现都会先建立一个前缀表，记录“所有不被 5 整除的正整数”的乘积在模 3125 下的前缀值。这样一来，任何尾块的乘积都可以在 \(O(1)\) 时间内读出。
核心计算不断把 \(n\) 变成 \(\lfloor n/5\rfloor\)。在每一层里，程序先算出有多少个完整的 3125 块，于是得到一个 \((-1)^q\) 的符号；再乘上尾块对应的前缀表值；然后继续处理更小的参数。同时，另一个简单循环按照 Legendre 公式求出 \(v_5(n!)\)。
递归结束后，程序得到了 \(U(n)\) 在模 3125 下的值。接着它乘上 \(2^e\) 的模逆，从而得到真正的删零阶乘在模 3125 下的剩余。最后再结合模 32 的条件，把它提升为模 100000 的唯一结果。对于很小的输入，三个实现还保留了直接计算的分支，这既避免了小范围特判问题，也顺便提供了最直观的正确性检查。
前缀表长度固定为 3125，因此预处理只是一次常数规模的成本。之后递归每一步都把 \(n\) 除以 5，所以只有 \(O(\log_5 n)\) 层，而每层只做常数次模运算。
因此，单次求值在固定规模预处理之后的时间复杂度是 \(O(\log n)\)。额外空间复杂度是递归栈带来的 \(O(\log n)\)；如果把同样的递推改写成迭代形式，则额外空间可以做到 \(O(1)\)。就本题而言，算法之所以高效，是因为即使 \(n=10^{12}\)，真正访问的也只是很少几个 5 进制层次。
Обозначим через \(F(n)\) последние пять ненулевых цифр числа \(n!\). Требуется найти \(F(10^{12})\), поэтому прямое вычисление факториала здесь совершенно непригодно.
Рабочий метод сначала отделяет конечные нули от остальной части факториала, затем вычисляет сокращенный факториал по модулю \(5^5=3125\), выясняет, что происходит по модулю \(2^5=32\), и после этого объединяет обе конгруэнции в единственный остаток по модулю \(10^5\).
Пусть \(v_p(m)\) означает показатель простого числа \(p\) в разложении \(m\). Вся задача основана на том, что каждый конечный нуль возникает из пары \(2\cdot 5\).
Число конечных нулей в \(n!\) равно числу пятерок, потому что двоек в факториале всегда больше. Поэтому
$$e=v_5(n!)=\sum_{k\ge 1}\left\lfloor \frac{n}{5^k}\right\rfloor,$$
а искомая величина задается формулой
$$F(n)\equiv \frac{n!}{10^e}\pmod{100000}.$$
Это и есть точное описание цели: убрать \(e\) согласованных пар \((2,5)\), сохранить все остальные множители и затем взять остаток по модулю \(10^5\).
Сначала удобно убрать только пятерки, а соответствующие двойки сократить позже. Определим
$$U(n)=\prod_{m=1}^{n}\frac{m}{5^{v_5(m)}}.$$
Тогда \(U(n)=n!/5^e\). Разделим произведение на числа, не кратные 5, и числа вида \(5q\):
$$U(n)=\left(\prod_{\substack{1\le m\le n\\ 5\nmid m}} m\right)\left(\prod_{q=1}^{\lfloor n/5\rfloor}\frac{q}{5^{v_5(q)}}\right).$$
Второй множитель в точности равен \(U(\lfloor n/5\rfloor)\). Если теперь положить
$$A(n)=\prod_{\substack{1\le m\le n\\ 5\nmid m}} m \pmod{3125},$$
то получаем ключевую рекуррентную формулу
$$U(n)\equiv A(n)\,U\!\left(\left\lfloor\frac{n}{5}\right\rfloor\right)\pmod{3125}.$$
Каждый рекурсивный шаг снимает один внешний слой пятерок со всех кратных 5 чисел. Повторяя это, мы учитываем все степени 5, входящие в факториал.
Запишем \(n=3125q+r\), где \(0\le r<3125\). Внутри любого полного блока длины 3125 числа, не кратные 5, образуют полную приведенную систему вычетов по модулю 3125. Для нечетной степени простого числа произведение всех единиц равно \(-1\) по этому модулю. Следовательно,
$$A(n)\equiv (-1)^q A(r)\pmod{3125}.$$
Именно поэтому реализациям достаточно одной префиксной таблицы на один блок. Каждый полный блок дает множитель \(1\) или \(-1\) в зависимости от четности \(q\), а хвостовой участок берется одной выборкой из таблицы.
Так как \(U(n)=n!/5^e\), нужно еще сократить соответствующий множитель \(2^e\):
$$R_{3125}\equiv U(n)\,2^{-e}\pmod{3125}.$$
Число 2 обратимо по модулю 3125, а \(\varphi(3125)=2500\), поэтому по теореме Эйлера показатель степени можно уменьшать по модулю 2500 при вычислении обратной степени двойки.
После этого \(R_{3125}\) уже является точным значением сокращенного факториала по модулю \(5^5\).
Модуль раскладывается как
$$100000=32\cdot 3125.$$
Остаток по модулю 3125 нам уже известен. По модулю 32 после удаления всех конечных нулей остается степень двойки
$$v_2(n!)-v_5(n!).$$
Для больших \(n\), и особенно для \(n=10^{12}\), эта разность не меньше 5, так что сокращенный факториал делится на 32. Значит, окончательный ответ есть единственное решение системы
$$x\equiv R_{3125}\pmod{3125},\qquad x\equiv 0\pmod{32}.$$
Реализации ищут его в виде \(x=R_{3125}+3125k\), подбирая единственное \(k\pmod{32}\), при котором выполняется вторая конгруэнция. Для очень малых \(n\) сохраняется прямой вычислительный путь, так что это упрощение для больших \(n\) используется только там, где оно действительно корректно.
Здесь
$$e=v_5(10!)=\left\lfloor\frac{10}{5}\right\rfloor=2.$$
Если удалить все множители 5 из чисел \(1,2,\dots,10\), останутся множители
$$1,2,3,4,1,6,7,8,9,2.$$
Поэтому
$$U(10)=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2=145152.$$
Теперь делим на согласованную степень \(2^2\):
$$\frac{U(10)}{2^2}=36288.$$
Значит, последние пять ненулевых цифр числа \(10!\) равны \(36288\). На этом маленьком примере видно ровно тот же механизм, который используется и для \(10^{12}\).
Реализации на C++, Python и Java сначала строят префиксную таблицу произведений положительных чисел, не делящихся на 5, по модулю 3125. Благодаря этому вклад любого неполного блока можно получить за \(O(1)\).
Основной вычислитель многократно заменяет \(n\) на \(\lfloor n/5\rfloor\). На каждом уровне он считает число полных блоков длины 3125, применяет знак \((-1)^q\), домножает на табличное значение для хвостового блока и продолжает работу с меньшим аргументом. Отдельный цикл по формуле Лежандра вычисляет \(v_5(n!)\).
После завершения рекурсии программа получает \(U(n)\) по модулю 3125. Затем она домножает это значение на модульную обратную к \(2^e\), получая сокращенный факториал по модулю 3125, и поднимает результат до модуля 100000 с учетом условия по модулю 32. Для совсем маленьких входов сохранена и прямая ветка перемножения, которая одновременно служит простой проверкой корректности.
Префиксная таблица имеет фиксированную длину 3125, поэтому ее построение является постоянной предварительной стоимостью. После этого рекурсия на каждом шаге делит \(n\) на 5, то есть имеет \(O(\log_5 n)\) уровней, причем каждый уровень использует лишь константное число модульных операций.
Следовательно, время работы для одного запроса после этой постоянной подготовки равно \(O(\log n)\). Дополнительная память составляет \(O(\log n)\) из-за рекурсивного стека, либо \(O(1)\) сверх таблицы при итеративной записи той же идеи. Практически метод быстр именно потому, что даже для \(10^{12}\) нужно пройти лишь несколько уровней деления по основанию 5.
لنرمز بـ \(F(n)\) إلى آخر خمسة أرقام غير صفرية في \(n!\). المطلوب هو إيجاد \(F(10^{12})\)، ولذلك فكل محاولة لحساب المضروب كاملًا ثم أخذ آخر أرقامه غير عملية تمامًا.
الفكرة الصحيحة هي فصل الأصفار النهائية عن بقية العوامل، ثم حساب المضروب المختزل modulo \(5^5=3125\)، وفهم ما يحدث modulo \(2^5=32\)، ثم دمج النتيجتين في النهاية بواسطة نظرية البواقي الصينية للحصول على الباقي modulo \(10^5\).
ليكن \(v_p(m)\) هو أسّ العدد الأولي \(p\) في تحليل \(m\). جوهر الحل أن كل صفر نهائي يأتي من زوج واحد \(2\cdot 5\).
عدد الأصفار النهائية في \(n!\) يساوي عدد عوامل 5، لأن عوامل 2 أكثر بكثير. لذلك
$$e=v_5(n!)=\sum_{k\ge 1}\left\lfloor \frac{n}{5^k}\right\rfloor,$$
والكمية المطلوبة هي
$$F(n)\equiv \frac{n!}{10^e}\pmod{100000}.$$
هذه الصيغة تقول بدقة ما الذي نحتاج إلى الاحتفاظ به: نحذف الأزواج المتطابقة \((2,5)\) وعددها \(e\)، ونبقي كل شيء آخر، ثم نقرأ الناتج modulo \(10^5\).
من الأنسب أولًا نزع عوامل 5 فقط، ثم إزالة عوامل 2 المطابقة لها في خطوة لاحقة. نعرّف
$$U(n)=\prod_{m=1}^{n}\frac{m}{5^{v_5(m)}}.$$
وعندئذٍ \(U(n)=n!/5^e\). إذا قسمنا حاصل الضرب إلى الأعداد غير القابلة للقسمة على 5، والأعداد من الشكل \(5q\)، نحصل على
$$U(n)=\left(\prod_{\substack{1\le m\le n\\ 5\nmid m}} m\right)\left(\prod_{q=1}^{\lfloor n/5\rfloor}\frac{q}{5^{v_5(q)}}\right).$$
والعامل الثاني هو بالضبط \(U(\lfloor n/5\rfloor)\). وإذا وضعنا
$$A(n)=\prod_{\substack{1\le m\le n\\ 5\nmid m}} m \pmod{3125},$$
فإن العلاقة العودية الأساسية تصبح
$$U(n)\equiv A(n)\,U\!\left(\left\lfloor\frac{n}{5}\right\rfloor\right)\pmod{3125}.$$
كل خطوة عودية تزيل طبقة واحدة من عامل 5 من جميع مضاعفات 5. وعندما نكرر ذلك حتى يصل الوسيط إلى الصفر، نكون قد أحصينا جميع قوى 5 الموجودة في المضروب.
اكتب \(n=3125q+r\) حيث \(0\le r<3125\). داخل أي كتلة كاملة طولها 3125، تشكل الأعداد غير القابلة للقسمة على 5 نظام بواقي مختزلًا كاملًا modulo \(3125\). وبالنسبة لقوة عدد أولي فردي، فإن حاصل ضرب جميع الوحدات يساوي \(-1\) modulo تلك القوة. لذا
$$A(n)\equiv (-1)^q A(r)\pmod{3125}.$$
ولهذا السبب تكتفي التطبيقات بجدول بادئات واحد لكتلة واحدة فقط. كل كتلة كاملة تضيف العامل \(1\) أو \(-1\) حسب زوجية \(q\)، أما الجزء المتبقي فيُؤخذ مباشرة من الجدول.
بما أن \(U(n)=n!/5^e\)، فما زال علينا إزالة العامل \(2^e\) الموافق لهذه الأصفار النهائية:
$$R_{3125}\equiv U(n)\,2^{-e}\pmod{3125}.$$
والعدد 2 عنصر قابل للعكس modulo \(3125\)، كما أن \(\varphi(3125)=2500\)، ولذلك تسمح مبرهنة أويلر باختزال الأس modulo 2500 عند حساب القوة العكسية للعدد 2.
عند هذه المرحلة يصبح \(R_{3125}\) هو بالضبط المضروب المختزل modulo \(5^5\).
يتفكك الموديل إلى
$$100000=32\cdot 3125.$$
نحن نعرف بالفعل الباقي modulo 3125. أما modulo 32 فإن قوة 2 التي تبقى بعد حذف جميع الأصفار النهائية تساوي
$$v_2(n!)-v_5(n!).$$
وبالنسبة إلى \(n\) الكبيرة، ولا سيما \(n=10^{12}\)، تكون هذه الكمية على الأقل 5، ولذلك يكون المضروب المختزل من倍ات 32. ومن ثم فإن الجواب النهائي هو الحل الوحيد للنظام
$$x\equiv R_{3125}\pmod{3125},\qquad x\equiv 0\pmod{32}.$$
وتحل التطبيقات ذلك بكتابة \(x=R_{3125}+3125k\)، ثم اختيار \(k\pmod{32}\) الوحيد الذي يحقق التطابق الثاني. أما القيم الصغيرة جدًا من \(n\) فلها فرع مباشر بالحساب الصريح، حتى لا يُستخدم هذا الاختصار الخاص بالحالات الكبيرة إلا ضمن المجال الصحيح.
لدينا هنا
$$e=v_5(10!)=\left\lfloor\frac{10}{5}\right\rfloor=2.$$
إذا حذفنا جميع عوامل 5 من الأعداد \(1,2,\dots,10\)، فالعوامل الباقية هي
$$1,2,3,4,1,6,7,8,9,2.$$
ومن ثم
$$U(10)=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2=145152.$$
ثم نقسم على عامل \(2^2\) المطابق:
$$\frac{U(10)}{2^2}=36288.$$
إذًا آخر خمسة أرقام غير صفرية في \(10!\) هي \(36288\). هذا المثال الصغير يعرض نفس البنية الحسابية التي تُستخدم للمسألة الأصلية.
تبدأ تطبيقات C++ وPython وJava ببناء جدول بادئات لحواصل ضرب الأعداد الصحيحة الموجبة غير القابلة للقسمة على 5، بعد اختزالها modulo 3125. وبذلك يمكن الحصول على مساهمة أي جزء متبقٍ من الكتلة فورًا.
المقيّم الرئيسي يستبدل \(n\) مرارًا بـ \(\lfloor n/5\rfloor\). في كل مستوى يحسب عدد الكتل الكاملة بطول 3125، ويطبق الإشارة \((-1)^q\)، ثم يضرب بالقيمة المخزنة للجزء المتبقي، وبعد ذلك يتابع مع الوسيط الأصغر. وفي الوقت نفسه تُحسب قيمة \(v_5(n!)\) بحلقة منفصلة تطبق مجموع Legendre.
بعد انتهاء العودية تكون قيمة \(U(n)\) modulo 3125 معروفة. بعدها تضربها الشيفرة في المعكوس الضربي لـ \(2^e\) للحصول على المضروب المختزل modulo 3125، ثم ترفعه إلى modulo 100000 بفرض شرط modulo 32 أيضًا. وبالنسبة للمدخلات الصغيرة جدًا تحتفظ التطبيقات بمسار ضرب مباشر، وهو مفيد كذلك بوصفه فحصًا بسيطًا للصحة.
طول جدول البادئات ثابت ويساوي 3125، لذا فبناؤه كلفة ثابتة تدفع مرة واحدة. بعد ذلك تقسم العودية \(n\) على 5 في كل خطوة، أي إن عدد المستويات هو \(O(\log_5 n)\)، وكل مستوى لا يحتاج إلا إلى عدد ثابت من العمليات المعيارية.
وبالتالي يكون زمن التنفيذ للاستعلام الواحد \(O(\log n)\) بعد هذا التمهيد ثابت الحجم. أما الذاكرة الإضافية فهي \(O(\log n)\) بسبب مكدس العودية، أو \(O(1)\) إضافية إذا كُتبت الفكرة نفسها بصورة تكرارية. ومن الناحية العملية فالخوارزمية سريعة جدًا لأن حتى \(10^{12}\) لا يولد إلا عددًا قليلًا من طبقات القسمة على 5.