Let \(f(N)\) be the last 12 hexadecimal digits that remain after deleting all trailing hexadecimal zeroes from \(N!\). The problem asks for \(f(20!)\).
A direct attack on \((20!)!\) is hopeless. The quantity is far too large to build explicitly, so the solution keeps only the information that survives after removing factors of \(16\) and reducing to 12 hexadecimal digits, namely arithmetic modulo \(16^{12}=2^{48}\).
The key observation is that hexadecimal trailing zeroes depend only on powers of \(2\), because \(16=2^4\). Everything else belongs to the odd part of the factorial and can be handled modulo \(2^{48}\).
For any positive integer \(m\), write
$$m=2^{\nu_2(m)}\operatorname{odd}(m),$$
where \(\nu_2(m)\) is the exponent of \(2\) in \(m\), and \(\operatorname{odd}(m)\) is the odd part of \(m\).
Applied to \(N!\), this gives
$$N!=2^{\nu_2(N!)}\operatorname{odd}(N!).$$
Each trailing hexadecimal zero removes one factor \(16=2^4\), so after deleting all hexadecimal zeroes the remaining factor of \(2\) is only
$$2^{\nu_2(N!) \bmod 4}.$$
Therefore
$$f(N)\equiv \operatorname{odd}(N!)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
The exponent \(\nu_2(N!)\) is computed by Legendre's formula:
$$\nu_2(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{2^k}\right\rfloor.$$
Define
$$O(N)=\operatorname{odd}(N!),\qquad P(N)=\prod_{\substack{1\le m\le N\\ m\text{ odd}}} m.$$
Split the factors of \(N!\) into odd numbers and even numbers. If a factor is \(2t\), then its odd part is just the odd part of \(t\). Hence
$$O(N)=P(N)\,O\!\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
Iterating this identity yields
$$O(N)=\prod_{j\ge 0} P\!\left(\left\lfloor\frac{N}{2^j}\right\rfloor\right),$$
where the product stops once the floor becomes \(0\). So the hard part is reduced to evaluating the odd prefix product \(P(n)\) quickly for several values of \(n\).
To compute \(P(n)\) modulo \(2^{48}\), choose the block size
$$S=2^{16}.$$
Write
$$n=qS+u,\qquad 0\le u<S.$$
For each odd residue \(r\in\{1,3,5,\dots,S-1\}\), the odd numbers up to \(n\) in that class are
$$r,\ r+S,\ r+2S,\ \dots,\ r+(q-1)S,$$
and there is one additional term \(r+qS\) exactly when \(r\le u\).
So \(P(n)\) factors into a product of full class products and possibly one extra factor from each residue class:
$$P(n)=\prod_{\substack{1\le r<S\\ r\text{ odd}}}\left(\prod_{j=0}^{q-1}(r+jS)\right)\cdot \prod_{\substack{1\le r\le u\\ r\text{ odd}}}(r+qS).$$
Fix one odd residue \(r\), and define the full class product
$$C_r(q)=\prod_{j=0}^{q-1}(r+jS).$$
Because \(r\) is odd, it is invertible modulo \(2^{48}\). In the ring \(\mathbb{Z}/2^{48}\mathbb{Z}\), we can write
$$C_r(q)=r^q\prod_{j=0}^{q-1}\left(1+j\,a\right),\qquad a=S\,r^{-1}.$$
Now \(S=2^{16}\), so every factor \(a\) contains a factor \(2^{16}\). Any term of degree \(3\) or higher in the expansion of \(\prod(1+j\,a)\) contains \(a^3\), hence a factor \(2^{48}\), and therefore vanishes modulo \(2^{48}\).
Only the first two elementary symmetric sums survive:
$$\prod_{j=0}^{q-1}(1+j\,a)\equiv 1+a\,e_1+a^2e_2\pmod{2^{48}},$$
where
$$e_1=\sum_{j=0}^{q-1}j=\frac{q(q-1)}{2},$$
$$e_2=\sum_{0\le i<j<q}ij=\frac{q(q-1)(q-2)(3q-1)}{24}.$$
This replaces a long product by one modular power, one modular inverse, and a short polynomial evaluation.
For each level \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\), compute the corresponding prefix product \(P(\cdot)\) using the residue-class formula above, and multiply all those values together. That gives \(O(N)=\operatorname{odd}(N!)\) modulo \(2^{48}\).
Finally restore the leftover factor of \(2\):
$$f(N)\equiv O(N)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
Since the target is \(N=20!\), the implementations first compute \(20!\), then apply this fast routine to that value.
The statement provides \(f(20)\) as a checkpoint, and it is a good small example of the method.
First,
$$\nu_2(20!)=\left\lfloor\frac{20}{2}\right\rfloor+\left\lfloor\frac{20}{4}\right\rfloor+\left\lfloor\frac{20}{8}\right\rfloor+\left\lfloor\frac{20}{16}\right\rfloor=10+5+2+1=18.$$
So after removing all hexadecimal zeroes, the remaining power of \(2\) is
$$2^{18\bmod 4}=2^2=4.$$
Next, the recursive identity gives
$$O(20)=P(20)\,P(10)\,P(5)\,P(2)\,P(1).$$
These small prefix products are
$$P(20)=1\cdot 3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13\cdot 15\cdot 17\cdot 19=654729075,$$
$$P(10)=1\cdot 3\cdot 5\cdot 7\cdot 9=945,\qquad P(5)=1\cdot 3\cdot 5=15,\qquad P(2)=P(1)=1.$$
Therefore
$$O(20)=654729075\cdot 945\cdot 15=9280784638125.$$
Reducing modulo \(2^{48}\) gives
$$O(20)\equiv \texttt{0870D9DF20AD}_{16}\pmod{2^{48}}.$$
Multiplying by the remaining factor \(4\) yields
$$f(20)\equiv \texttt{21C3677C82B4}_{16},$$
which matches the known checkpoint exactly.
The C++, Python, and Java implementations all follow the same mathematics. They work entirely modulo \(2^{48}\), precompute modular inverses for every odd residue modulo \(2^{16}\), and use Newton iteration because odd numbers are invertible modulo powers of \(2\).
For the required input, they first build the integer \(20!\). Then they generate the sequence
$$N,\ \left\lfloor\frac{N}{2}\right\rfloor,\ \left\lfloor\frac{N}{4}\right\rfloor,\ \dots$$
until it reaches \(0\). For each level they compute the odd prefix product by scanning all odd residue classes modulo \(2^{16}\), using the closed form for the full blocks and multiplying one extra factor when the partial block reaches that residue.
Those level products are multiplied together to obtain the odd part of \(N!\). Separately, the exponent \(\nu_2(N!)\) is found by repeated halving. The final result restores the leftover factor \(2^{\nu_2(N!)\bmod 4}\) and formats the answer as a 12-digit uppercase hexadecimal string. The C++ implementation parallelizes the independent level computations, while the Python and Java implementations perform the same steps serially.
The dominant work is evaluating the odd prefix product for the values \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\), so there are \(O(\log N)\) levels. Each level scans the \(2^{15}\) odd residue classes modulo \(2^{16}\). Inside one class there is a modular exponentiation and a constant amount of fixed-width modular arithmetic; because the modulus is always \(2^{48}\) and the implementations operate on fixed-width integers, that inner cost stays small in practice.
In practical terms, the method behaves like a small constant times \(2^{15}\log N\), with \(O(2^{15})\) memory for the inverse table. The point is that the algorithm never builds \(N!\) itself; it only computes the residue information that can affect the final 12 hexadecimal digits.
Sei \(f(N)\) die Folge der letzten 12 Hexadezimalziffern, die nach dem Entfernen aller nachgestellten Hex-Nullen von \(N!\) übrig bleibt. Gesucht ist \(f(20!)\).
Ein direkter Zugriff auf \((20!)!\) ist unmöglich. Die Zahl ist viel zu groß, also hält die Lösung nur die Information fest, die nach dem Entfernen aller Faktoren \(16\) und nach Reduktion auf 12 Hexziffern überhaupt noch sichtbar ist, also Arithmetik modulo \(16^{12}=2^{48}\).
Der zentrale Punkt ist, dass Endnullen im Hexadezimalsystem nur von Zweierpotenzen abhängen, weil \(16=2^4\). Alles andere steckt im ungeraden Anteil der Fakultät und kann modulo \(2^{48}\) behandelt werden.
Für jede positive ganze Zahl \(m\) schreiben wir
$$m=2^{\nu_2(m)}\operatorname{odd}(m),$$
wobei \(\nu_2(m)\) die Zweierbewertung und \(\operatorname{odd}(m)\) der ungerade Anteil ist.
Für \(N!\) gilt damit
$$N!=2^{\nu_2(N!)}\operatorname{odd}(N!).$$
Jede Hex-Endnull entspricht einem Faktor \(16=2^4\). Nach dem Entfernen aller Hex-Endnullen bleibt daher nur
$$2^{\nu_2(N!) \bmod 4}$$
als restliche Zweierpotenz stehen. Also
$$f(N)\equiv \operatorname{odd}(N!)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
Die Bewertung \(\nu_2(N!)\) liefert die Legendre-Formel:
$$\nu_2(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{2^k}\right\rfloor.$$
Definieren wir
$$O(N)=\operatorname{odd}(N!),\qquad P(N)=\prod_{\substack{1\le m\le N\\ m\text{ ungerade}}} m.$$
Teilt man die Faktoren von \(N!\) in ungerade und gerade auf, dann hat ein gerader Faktor \(2t\) denselben ungeraden Anteil wie \(t\). Deshalb gilt
$$O(N)=P(N)\,O\!\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
Durch Iteration folgt
$$O(N)=\prod_{j\ge 0} P\!\left(\left\lfloor\frac{N}{2^j}\right\rfloor\right),$$
wobei das Produkt endet, sobald der Quotient \(0\) wird. Damit reduziert sich die Aufgabe auf schnelle Berechnung mehrerer ungerader Präfixprodukte \(P(n)\).
Zur Berechnung von \(P(n)\) modulo \(2^{48}\) wählen wir die Blockgröße
$$S=2^{16}.$$
Schreibe
$$n=qS+u,\qquad 0\le u<S.$$
Für jede ungerade Restklasse \(r\in\{1,3,5,\dots,S-1\}\) liegen die ungeraden Zahlen bis \(n\) in dieser Klasse bei
$$r,\ r+S,\ r+2S,\ \dots,\ r+(q-1)S,$$
und genau dann kommt noch ein zusätzlicher Faktor \(r+qS\) dazu, wenn \(r\le u\) ist.
Somit zerfällt \(P(n)\) in volle Klassenprodukte und eventuell einen Zusatzfaktor pro Klasse:
$$P(n)=\prod_{\substack{1\le r<S\\ r\text{ ungerade}}}\left(\prod_{j=0}^{q-1}(r+jS)\right)\cdot \prod_{\substack{1\le r\le u\\ r\text{ ungerade}}}(r+qS).$$
Fixiere eine ungerade Restklasse \(r\) und definiere
$$C_r(q)=\prod_{j=0}^{q-1}(r+jS).$$
Weil \(r\) ungerade ist, besitzt es modulo \(2^{48}\) ein Inverses. Im Ring \(\mathbb{Z}/2^{48}\mathbb{Z}\) kann man schreiben
$$C_r(q)=r^q\prod_{j=0}^{q-1}\left(1+j\,a\right),\qquad a=S\,r^{-1}.$$
Da \(S=2^{16}\) ist, trägt jedes \(a\) bereits einen Faktor \(2^{16}\). Jeder Term vom Grad \(3\) oder höher in der Entwicklung von \(\prod(1+j\,a)\) enthält also \(a^3\), damit einen Faktor \(2^{48}\), und verschwindet modulo \(2^{48}\).
Übrig bleiben nur die ersten beiden elementarsymmetrischen Summen:
$$\prod_{j=0}^{q-1}(1+j\,a)\equiv 1+a\,e_1+a^2e_2\pmod{2^{48}},$$
wobei
$$e_1=\sum_{j=0}^{q-1}j=\frac{q(q-1)}{2},$$
$$e_2=\sum_{0\le i<j<q}ij=\frac{q(q-1)(q-2)(3q-1)}{24}.$$
Dadurch wird ein langes Produkt durch eine modulare Potenz, ein modulares Inverses und die Auswertung eines kurzen Polynoms ersetzt.
Für jede Stufe \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\) wird das entsprechende Präfixprodukt \(P(\cdot)\) mit der Restklassenformel berechnet und anschließend alles multipliziert. So erhält man \(O(N)=\operatorname{odd}(N!)\) modulo \(2^{48}\).
Zum Schluss wird der restliche Zweierfaktor wieder eingesetzt:
$$f(N)\equiv O(N)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
Da hier \(N=20!\) ist, berechnen die Implementierungen zunächst \(20!\) und wenden dann genau diese schnelle Routine auf diesen Wert an.
Die Aufgabenstellung liefert \(f(20)\) als Kontrollwert; das ist ein gutes kleines Beispiel für die Methode.
Zuerst gilt
$$\nu_2(20!)=\left\lfloor\frac{20}{2}\right\rfloor+\left\lfloor\frac{20}{4}\right\rfloor+\left\lfloor\frac{20}{8}\right\rfloor+\left\lfloor\frac{20}{16}\right\rfloor=10+5+2+1=18.$$
Nach dem Entfernen aller Hex-Endnullen bleibt also
$$2^{18\bmod 4}=2^2=4$$
als Zweierfaktor übrig. Weiter liefert die Rekursion
$$O(20)=P(20)\,P(10)\,P(5)\,P(2)\,P(1).$$
Die kleinen Präfixprodukte sind
$$P(20)=1\cdot 3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13\cdot 15\cdot 17\cdot 19=654729075,$$
$$P(10)=1\cdot 3\cdot 5\cdot 7\cdot 9=945,\qquad P(5)=1\cdot 3\cdot 5=15,\qquad P(2)=P(1)=1.$$
Damit folgt
$$O(20)=654729075\cdot 945\cdot 15=9280784638125.$$
Modulo \(2^{48}\) ist das
$$O(20)\equiv \texttt{0870D9DF20AD}_{16}\pmod{2^{48}}.$$
Nach Multiplikation mit dem verbleibenden Faktor \(4\) erhält man
$$f(20)\equiv \texttt{21C3677C82B4}_{16},$$
genau den bekannten Kontrollwert.
Die C++-, Python- und Java-Implementierungen folgen alle derselben Mathematik. Sie arbeiten vollständig modulo \(2^{48}\), berechnen modulare Inverse für alle ungeraden Restklassen modulo \(2^{16}\) vorab und verwenden Newton-Iteration, weil ungerade Zahlen modulo Zweierpotenzen invertierbar sind.
Für die eigentliche Aufgabe wird zunächst die Zahl \(20!\) aufgebaut. Danach erzeugen die Programme die Folge
$$N,\ \left\lfloor\frac{N}{2}\right\rfloor,\ \left\lfloor\frac{N}{4}\right\rfloor,\ \dots$$
bis \(0\). Für jede Stufe wird das ungerade Präfixprodukt berechnet, indem alle ungeraden Restklassen modulo \(2^{16}\) durchlaufen werden. Für die vollen Blöcke wird die geschlossene Formel benutzt, und wenn der letzte Block nur teilweise gefüllt ist, wird ein zusätzlicher Faktor ergänzt.
Das Produkt über alle Stufen ergibt den ungeraden Anteil von \(N!\). Separat wird \(\nu_2(N!)\) durch wiederholtes Halbieren bestimmt. Am Ende wird der Faktor \(2^{\nu_2(N!)\bmod 4}\) zurückmultipliziert und das Ergebnis als 12-stellige hexadezimale Großschreibung ausgegeben. Die C++-Version parallelisiert die voneinander unabhängigen Stufenberechnungen, während Python und Java dieselbe Logik seriell ausführen.
Die Hauptarbeit besteht darin, das ungerade Präfixprodukt für die Werte \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\) auszuwerten, also für \(O(\log N)\) Stufen. Auf jeder Stufe werden die \(2^{15}\) ungeraden Restklassen modulo \(2^{16}\) durchlaufen. Innerhalb einer Klasse fallen eine modulare Potenzierung und eine konstante Anzahl fester modularer Operationen an; da der Modulus stets \(2^{48}\) ist und mit Festbreitenzahlen gearbeitet wird, bleibt dieser Aufwand in der Praxis klein.
Praktisch verhält sich das Verfahren daher wie eine kleine Konstante mal \(2^{15}\log N\), bei \(O(2^{15})\) Speicher für die Inversentabelle. Entscheidend ist, dass niemals \(N!\) selbst aufgebaut wird; es wird nur diejenige Restinformation berechnet, die die letzten 12 Hexziffern beeinflussen kann.
\(f(N)\), \(N!\) sayısının onaltılık gösterimindeki sondaki tüm sıfırlar atıldıktan sonra geriye kalan son 12 hexadecimal basamağı ifade eder. İstenen değer \(f(20!)\)'dir.
\((20!)!\) sayısını doğrudan üretmek mümkün değildir. Bu yüzden çözüm, yalnızca sondaki hexadecimal sıfırlar silindikten sonra hâlâ sonucu etkileyen bilgiyi tutar; bu da \(16^{12}=2^{48}\) modundaki artık sınıfıdır.
Ana gözlem şudur: hexadecimal sondaki sıfırlar yalnızca \(2\) kuvvetlerinden gelir, çünkü \(16=2^4\). Geriye kalan her şey faktöriyel içindeki tek kısma aittir ve \(2^{48}\) modunda izlenebilir.
Her pozitif tam sayı \(m\) için
$$m=2^{\nu_2(m)}\operatorname{odd}(m)$$
yazalım. Burada \(\nu_2(m)\), \(m\) içindeki \(2\) üssünü; \(\operatorname{odd}(m)\) ise tek kısmı gösterir.
Bunu \(N!\)'e uygularsak
$$N!=2^{\nu_2(N!)}\operatorname{odd}(N!)$$
elde edilir. Bir hexadecimal son sıfır bir adet \(16=2^4\) demektir. Dolayısıyla tüm hexadecimal son sıfırlar silindikten sonra elde kalan \(2\) kuvveti sadece
$$2^{\nu_2(N!) \bmod 4}$$
olur. Böylece
$$f(N)\equiv \operatorname{odd}(N!)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
\(\nu_2(N!)\) değeri Legendre formülüyle bulunur:
$$\nu_2(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{2^k}\right\rfloor.$$
Şu tanımları yapalım:
$$O(N)=\operatorname{odd}(N!),\qquad P(N)=\prod_{\substack{1\le m\le N\\ m\text{ tek}}} m.$$
\(N!\)'in çarpanlarını tekler ve çiftler diye ayırırsak, çift bir çarpan olan \(2t\)'nin tek kısmı doğrudan \(t\)'nin tek kısmıdır. Bu yüzden
$$O(N)=P(N)\,O\!\left(\left\lfloor\frac{N}{2}\right\rfloor\right)$$
olur. Bu özdeşlik tekrarlanırsa
$$O(N)=\prod_{j\ge 0} P\!\left(\left\lfloor\frac{N}{2^j}\right\rfloor\right)$$
elde edilir; bölüm \(0\) olduğunda çarpım durur. Yani asıl zor iş, birkaç farklı \(n\) için tek önek çarpımı \(P(n)\)'yi hızlı hesaplamaktır.
\(P(n)\)'yi \(2^{48}\) modunda hesaplamak için blok büyüklüğü olarak
$$S=2^{16}$$
seçilir. Ardından
$$n=qS+u,\qquad 0\le u<S$$
yazılır. Her tek kalan \(r\in\{1,3,5,\dots,S-1\}\) için bu sınıftaki tek sayılar
$$r,\ r+S,\ r+2S,\ \dots,\ r+(q-1)S$$
şeklindedir; ayrıca ancak \(r\le u\) ise bir adet ek terim \(r+qS\) gelir.
Bu nedenle \(P(n)\), tam sınıf çarpımları ve gerekiyorsa sınıf başına bir ek terim olarak ayrılır:
$$P(n)=\prod_{\substack{1\le r<S\\ r\text{ tek}}}\left(\prod_{j=0}^{q-1}(r+jS)\right)\cdot \prod_{\substack{1\le r\le u\\ r\text{ tek}}}(r+qS).$$
Sabit bir tek kalan \(r\) için tam sınıf çarpımını
$$C_r(q)=\prod_{j=0}^{q-1}(r+jS)$$
olarak tanımlayalım. \(r\) tek olduğu için \(2^{48}\) modunda tersi vardır. \(\mathbb{Z}/2^{48}\mathbb{Z}\) halkasında
$$C_r(q)=r^q\prod_{j=0}^{q-1}(1+j\,a),\qquad a=S\,r^{-1}$$
yazılabilir. Burada \(S=2^{16}\) olduğundan \(a\) en az bir adet \(2^{16}\) çarpanı taşır. \(\prod(1+j\,a)\) açılımındaki üçüncü dereceden ve daha yüksek her terim \(a^3\) içerir; dolayısıyla \(2^{48}\) ile bölünür ve mod \(2^{48}\)'de sıfır olur.
Geriye sadece ilk iki simetrik toplam kalır:
$$\prod_{j=0}^{q-1}(1+j\,a)\equiv 1+a\,e_1+a^2e_2\pmod{2^{48}},$$
burada
$$e_1=\sum_{j=0}^{q-1}j=\frac{q(q-1)}{2},$$
$$e_2=\sum_{0\le i<j<q}ij=\frac{q(q-1)(q-2)(3q-1)}{24}.$$
Böylece çok uzun bir çarpım, tek bir modüler üs alma, tek bir modüler ters ve kısa bir polinom hesabına indirgenir.
\(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\) seviyelerinin her biri için yukarıdaki sınıf formülüyle ilgili \(P(\cdot)\) değeri hesaplanır ve hepsi çarpılır. Sonuç \(O(N)=\operatorname{odd}(N!)\) değeridir; hepsi mod \(2^{48}\) izlenir.
Son aşamada elde kalan \(2\) kuvveti geri eklenir:
$$f(N)\equiv O(N)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
Buradaki hedef \(N=20!\) olduğu için, uygulamalar önce \(20!\)'yi hesaplar, sonra bu hızlı yöntemi o girdiye uygular.
Soruda verilen kontrol değeri \(f(20)\), yöntemin küçük bir örneği olarak idealdir.
Önce
$$\nu_2(20!)=\left\lfloor\frac{20}{2}\right\rfloor+\left\lfloor\frac{20}{4}\right\rfloor+\left\lfloor\frac{20}{8}\right\rfloor+\left\lfloor\frac{20}{16}\right\rfloor=10+5+2+1=18$$
bulunur. Tüm hexadecimal son sıfırlar çıkarılınca geriye kalan \(2\) kuvveti
$$2^{18\bmod 4}=2^2=4$$
olur. Ayrıca özyineleme
$$O(20)=P(20)\,P(10)\,P(5)\,P(2)\,P(1)$$
verir. Küçük önek çarpımları şunlardır:
$$P(20)=1\cdot 3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13\cdot 15\cdot 17\cdot 19=654729075,$$
$$P(10)=1\cdot 3\cdot 5\cdot 7\cdot 9=945,\qquad P(5)=1\cdot 3\cdot 5=15,\qquad P(2)=P(1)=1.$$
Dolayısıyla
$$O(20)=654729075\cdot 945\cdot 15=9280784638125$$
olur. Bu değer mod \(2^{48}\)'de
$$O(20)\equiv \texttt{0870D9DF20AD}_{16}\pmod{2^{48}}$$
şeklindedir. Kalan \(4\) ile çarpınca
$$f(20)\equiv \texttt{21C3677C82B4}_{16}$$
elde edilir; bu da bilinen kontrol değeriyle tam uyumludur.
C++, Python ve Java uygulamaları aynı matematiksel iskeleti kullanır. Hepsi \(2^{48}\) modunda çalışır, \(2^{16}\) modundaki tüm tek kalanların terslerini önceden hesaplar ve tek sayıların iki kuvvetleri modundaki terslenebilirliğinden yararlanarak Newton iterasyonunu kullanır.
Gerekli girdi için önce \(20!\) sayısı oluşturulur. Sonra
$$N,\ \left\lfloor\frac{N}{2}\right\rfloor,\ \left\lfloor\frac{N}{4}\right\rfloor,\ \dots$$
dizisi üretilir. Her seviye için, \(2^{16}\) modundaki tüm tek kalan sınıfları taranır; tam bloklar kapalı formülle işlenir, son blok kısmi ise uygun tek ek çarpan da eklenir.
Bu seviye sonuçlarının çarpımı \(N!\)'in tek kısmını verir. Ayrı olarak \(\nu_2(N!)\) değeri ardışık ikiye bölmelerle hesaplanır. Son adımda \(2^{\nu_2(N!)\bmod 4}\) geri çarpılır ve sonuç 12 basamaklı büyük harf hexadecimal dizge olarak yazdırılır. C++ uygulaması birbirinden bağımsız seviye hesaplarını paralelleştirir; Python ve Java aynı mantığı seri olarak uygular.
Ana maliyet, \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\) değerleri için tek önek çarpımını hesaplamaktır; yani toplam \(O(\log N)\) seviye vardır. Her seviyede mod \(2^{16}\) altındaki \(2^{15}\) tek kalan sınıfı gezilir. Bir sınıf içinde bir modüler üs alma ve sabit sayıda sabit-genişlikli modüler işlem yapılır; modül her zaman \(2^{48}\) olduğundan bu iç maliyet pratikte küçüktür.
Bu yüzden yöntem pratikte küçük bir sabit çarpan ile \(2^{15}\log N\) gibi davranır ve ters tablosu için \(O(2^{15})\) bellek kullanır. En önemli nokta, algoritmanın \(N!\)'i asla doğrudan kurmaması; yalnızca son 12 hexadecimal basamağı etkileyebilecek artık bilgisini hesaplamasıdır.
Sea \(f(N)\) la secuencia formada por los últimos 12 dígitos hexadecimales que quedan después de eliminar todos los ceros hexadecimales finales de \(N!\). El problema pide \(f(20!)\).
Atacar \((20!)!\) de forma directa es imposible. La idea es conservar solo la información que sobrevive tras quitar factores de \(16\) y reducir a 12 dígitos hexadecimales, es decir, trabajar módulo \(16^{12}=2^{48}\).
La observación principal es que los ceros finales en base hexadecimal dependen únicamente de las potencias de \(2\), porque \(16=2^4\). Todo lo demás pertenece a la parte impar del factorial y se puede seguir módulo \(2^{48}\).
Para cualquier entero positivo \(m\), escribimos
$$m=2^{\nu_2(m)}\operatorname{odd}(m),$$
donde \(\nu_2(m)\) es el exponente de \(2\) en \(m\) y \(\operatorname{odd}(m)\) es su parte impar.
Aplicado a \(N!\), obtenemos
$$N!=2^{\nu_2(N!)}\operatorname{odd}(N!).$$
Cada cero hexadecimal final consume un factor \(16=2^4\), así que después de eliminar todos los ceros finales solo queda
$$2^{\nu_2(N!) \bmod 4}.$$
Por tanto,
$$f(N)\equiv \operatorname{odd}(N!)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
El valor \(\nu_2(N!)\) se calcula con la fórmula de Legendre:
$$\nu_2(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{2^k}\right\rfloor.$$
Definimos
$$O(N)=\operatorname{odd}(N!),\qquad P(N)=\prod_{\substack{1\le m\le N\\ m\text{ impar}}} m.$$
Si se separan los factores de \(N!\) en impares y pares, un factor par \(2t\) tiene la misma parte impar que \(t\). De ahí sale la identidad
$$O(N)=P(N)\,O\!\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
Iterándola, queda
$$O(N)=\prod_{j\ge 0} P\!\left(\left\lfloor\frac{N}{2^j}\right\rfloor\right),$$
y el producto termina cuando el cociente ya es \(0\). Así, el problema se reduce a calcular rápidamente varios productos prefijo de impares \(P(n)\).
Para calcular \(P(n)\) módulo \(2^{48}\), se toma el tamaño de bloque
$$S=2^{16}.$$
Escribimos
$$n=qS+u,\qquad 0\le u<S.$$
Para cada residuo impar \(r\in\{1,3,5,\dots,S-1\}\), los impares hasta \(n\) en esa clase son
$$r,\ r+S,\ r+2S,\ \dots,\ r+(q-1)S,$$
y aparece un término adicional \(r+qS\) exactamente cuando \(r\le u\).
Por ello, \(P(n)\) se descompone en productos de clases completas y, si hace falta, un factor extra por clase:
$$P(n)=\prod_{\substack{1\le r<S\\ r\text{ impar}}}\left(\prod_{j=0}^{q-1}(r+jS)\right)\cdot \prod_{\substack{1\le r\le u\\ r\text{ impar}}}(r+qS).$$
Fijemos un residuo impar \(r\) y definamos
$$C_r(q)=\prod_{j=0}^{q-1}(r+jS).$$
Como \(r\) es impar, es invertible módulo \(2^{48}\). En \(\mathbb{Z}/2^{48}\mathbb{Z}\) podemos escribir
$$C_r(q)=r^q\prod_{j=0}^{q-1}(1+j\,a),\qquad a=S\,r^{-1}.$$
Aquí \(S=2^{16}\), así que cada \(a\) contiene un factor \(2^{16}\). Cualquier término de grado \(3\) o superior en la expansión de \(\prod(1+j\,a)\) incluye \(a^3\), por lo que contiene un factor \(2^{48}\) y desaparece módulo \(2^{48}\).
Solo sobreviven las dos primeras sumas simétricas:
$$\prod_{j=0}^{q-1}(1+j\,a)\equiv 1+a\,e_1+a^2e_2\pmod{2^{48}},$$
donde
$$e_1=\sum_{j=0}^{q-1}j=\frac{q(q-1)}{2},$$
$$e_2=\sum_{0\le i<j<q}ij=\frac{q(q-1)(q-2)(3q-1)}{24}.$$
Así, un producto largo queda sustituido por una potencia modular, una inversa modular y la evaluación de un polinomio corto.
Para cada nivel \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\), se calcula el producto prefijo correspondiente \(P(\cdot)\) con la fórmula por clases de residuos y luego se multiplican todos esos niveles. El resultado es \(O(N)=\operatorname{odd}(N!)\) módulo \(2^{48}\).
Al final se restaura la potencia residual de \(2\):
$$f(N)\equiv O(N)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
Como aquí el objetivo es \(N=20!\), las implementaciones primero calculan \(20!\) y luego aplican esta rutina rápida a ese valor.
El enunciado da \(f(20)\) como punto de comprobación, y es un ejemplo pequeño muy útil.
Primero,
$$\nu_2(20!)=\left\lfloor\frac{20}{2}\right\rfloor+\left\lfloor\frac{20}{4}\right\rfloor+\left\lfloor\frac{20}{8}\right\rfloor+\left\lfloor\frac{20}{16}\right\rfloor=10+5+2+1=18.$$
Después de eliminar todos los ceros hexadecimales finales, la potencia de \(2\) que queda es
$$2^{18\bmod 4}=2^2=4.$$
Además, la identidad recursiva da
$$O(20)=P(20)\,P(10)\,P(5)\,P(2)\,P(1).$$
Estos productos pequeños valen
$$P(20)=1\cdot 3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13\cdot 15\cdot 17\cdot 19=654729075,$$
$$P(10)=1\cdot 3\cdot 5\cdot 7\cdot 9=945,\qquad P(5)=1\cdot 3\cdot 5=15,\qquad P(2)=P(1)=1.$$
Por tanto,
$$O(20)=654729075\cdot 945\cdot 15=9280784638125.$$
Reducido módulo \(2^{48}\), esto es
$$O(20)\equiv \texttt{0870D9DF20AD}_{16}\pmod{2^{48}}.$$
Al multiplicar por el factor restante \(4\), se obtiene
$$f(20)\equiv \texttt{21C3677C82B4}_{16},$$
que coincide exactamente con el valor de control conocido.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea matemática. Todas trabajan módulo \(2^{48}\), precalculan las inversas modulares de todos los residuos impares módulo \(2^{16}\) y usan iteración de Newton porque los números impares son invertibles módulo potencias de \(2\).
Para la entrada requerida, primero construyen el entero \(20!\). Después generan la sucesión
$$N,\ \left\lfloor\frac{N}{2}\right\rfloor,\ \left\lfloor\frac{N}{4}\right\rfloor,\ \dots$$
hasta llegar a \(0\). En cada nivel calculan el producto prefijo de impares recorriendo todas las clases impares módulo \(2^{16}\), aplicando la fórmula cerrada a los bloques completos y multiplicando un factor extra cuando el último bloque parcial alcanza ese residuo.
El producto de todos los niveles da la parte impar de \(N!\). Por separado, \(\nu_2(N!)\) se obtiene con divisiones sucesivas por \(2\). Finalmente se restaura el factor \(2^{\nu_2(N!)\bmod 4}\) y se formatea la respuesta como una cadena hexadecimal de 12 dígitos en mayúsculas. La versión en C++ paraleliza los niveles independientes; las versiones en Python y Java hacen la misma secuencia en serie.
El trabajo dominante es evaluar el producto prefijo de impares para \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\), es decir, para \(O(\log N)\) niveles. Cada nivel recorre las \(2^{15}\) clases de residuos impares módulo \(2^{16}\). Dentro de una clase hay una potencia modular y una cantidad constante de aritmética modular de tamaño fijo; como el módulo siempre es \(2^{48}\), ese coste interno es pequeño en la práctica.
En términos prácticos, el método se comporta como una constante pequeña por \(2^{15}\log N\), con memoria \(O(2^{15})\) para la tabla de inversas. Lo esencial es que el algoritmo nunca construye \(N!\) completo; solo calcula la información residual que puede afectar a los últimos 12 dígitos hexadecimales.
定义 \(f(N)\) 为：把 \(N!\) 的十六进制表示末尾所有十六进制零都删掉之后，剩下来的最后 12 位十六进制数字。题目要求的是 \(f(20!)\)。
如果直接去处理 \((20!)!\)，规模会大得完全不可行。真正可行的思路不是构造整个阶乘，而是只保留那些在“去掉末尾十六进制零”以及“只看最后 12 位”之后仍然会影响答案的信息，也就是模 \(16^{12}=2^{48}\) 的剩余信息。
核心观察是：十六进制末尾零只和 \(2\) 的幂有关，因为 \(16=2^4\)。所以我们可以把 \(N!\) 拆成“\(2\) 的幂次”与“奇数部分”，再分别处理。
对任意正整数 \(m\)，写成
$$m=2^{\nu_2(m)}\operatorname{odd}(m),$$
其中 \(\nu_2(m)\) 表示 \(m\) 中因子 \(2\) 的指数，\(\operatorname{odd}(m)\) 表示把所有因子 \(2\) 都除掉之后剩下的奇数部分。
应用到 \(N!\) 上，有
$$N!=2^{\nu_2(N!)}\operatorname{odd}(N!).$$
一个十六进制末尾零对应一个因子 \(16=2^4\)。所以把所有十六进制末尾零都删掉，相当于从 \(N!\) 里删去尽可能多的 \(2^4\)。删完之后，剩下来的 \(2\) 因子只可能是
$$2^{\nu_2(N!) \bmod 4}.$$
因此有
$$f(N)\equiv \operatorname{odd}(N!)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
而 \(\nu_2(N!)\) 可以用 Legendre 公式直接计算：
$$\nu_2(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{2^k}\right\rfloor.$$
定义
$$O(N)=\operatorname{odd}(N!),\qquad P(N)=\prod_{\substack{1\le m\le N\\ m\text{ 为奇数}}}m.$$
把 \(N!\) 的因子分成奇数和偶数。若某个因子是 \(2t\)，那么它的奇数部分就是 \(t\) 的奇数部分。因此得到递推关系
$$O(N)=P(N)\,O\!\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
不断重复这个关系，就得到
$$O(N)=\prod_{j\ge 0}P\!\left(\left\lfloor\frac{N}{2^j}\right\rfloor\right),$$
直到商变成 \(0\) 为止。这样一来，问题就变成了：如何高效计算若干个奇数前缀乘积 \(P(n)\)。
为了在模 \(2^{48}\) 下计算 \(P(n)\)，取分块大小
$$S=2^{16}.$$
把 \(n\) 写成
$$n=qS+u,\qquad 0\le u<S.$$
对于每个奇数剩余类 \(r\in\{1,3,5,\dots,S-1\}\)，不超过 \(n\) 的该类奇数恰好是
$$r,\ r+S,\ r+2S,\ \dots,\ r+(q-1)S,$$
如果 \(r\le u\)，还要再加上最后一个数 \(r+qS\)。
因此，\(P(n)\) 可以拆成“所有完整剩余类的乘积”与“部分尾块中的补充因子”：
$$P(n)=\prod_{\substack{1\le r<S\\ r\text{ 为奇数}}}\left(\prod_{j=0}^{q-1}(r+jS)\right)\cdot \prod_{\substack{1\le r\le u\\ r\text{ 为奇数}}}(r+qS).$$
固定一个奇数剩余类 \(r\)，定义完整类乘积
$$C_r(q)=\prod_{j=0}^{q-1}(r+jS).$$
因为 \(r\) 是奇数，所以它在模 \(2^{48}\) 下可逆。在环 \(\mathbb{Z}/2^{48}\mathbb{Z}\) 中可以写成
$$C_r(q)=r^q\prod_{j=0}^{q-1}(1+j\,a),\qquad a=S\,r^{-1}.$$
这里 \(S=2^{16}\)，所以 \(a\) 自带一个因子 \(2^{16}\)。在展开 \(\prod(1+j\,a)\) 时，任何三次及以上的项都会含有 \(a^3\)，也就是至少含有 \(2^{48}\)，在模 \(2^{48}\) 下全部消失。
因此只需要保留前两个对称和：
$$\prod_{j=0}^{q-1}(1+j\,a)\equiv 1+a\,e_1+a^2e_2\pmod{2^{48}},$$
其中
$$e_1=\sum_{j=0}^{q-1}j=\frac{q(q-1)}{2},$$
$$e_2=\sum_{0\le i<j<q}ij=\frac{q(q-1)(q-2)(3q-1)}{24}.$$
这一步的意义很大：原本很长的一串乘积，被压缩成一次模幂、一次模逆和一个很短的多项式计算。
对每一层
$$N,\ \left\lfloor\frac{N}{2}\right\rfloor,\ \left\lfloor\frac{N}{4}\right\rfloor,\ \dots$$
都用上面的剩余类公式算出相应的 \(P(\cdot)\)，再把这些层的结果全部乘起来，就得到 \(O(N)=\operatorname{odd}(N!)\) 在模 \(2^{48}\) 下的值。
最后把删掉十六进制末尾零之后还应保留的 \(2\) 因子乘回去：
$$f(N)\equiv O(N)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
由于题目的目标是 \(N=20!\)，所以实现首先算出 \(20!\)，再把上面的快速过程作用到这个 \(N\) 上。
题目中给出了 \(f(20)\) 作为校验值，这正好适合做一个完整的小例子。
先算 \(20!\) 中 \(2\) 的指数：
$$\nu_2(20!)=\left\lfloor\frac{20}{2}\right\rfloor+\left\lfloor\frac{20}{4}\right\rfloor+\left\lfloor\frac{20}{8}\right\rfloor+\left\lfloor\frac{20}{16}\right\rfloor=10+5+2+1=18.$$
所以删掉所有十六进制末尾零之后，剩下来的 \(2\) 因子是
$$2^{18\bmod 4}=2^2=4.$$
另一方面，递推公式给出
$$O(20)=P(20)\,P(10)\,P(5)\,P(2)\,P(1).$$
这些较小的前缀乘积可以直接写出：
$$P(20)=1\cdot 3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13\cdot 15\cdot 17\cdot 19=654729075,$$
$$P(10)=1\cdot 3\cdot 5\cdot 7\cdot 9=945,\qquad P(5)=1\cdot 3\cdot 5=15,\qquad P(2)=P(1)=1.$$
于是
$$O(20)=654729075\cdot 945\cdot 15=9280784638125.$$
把它模 \(2^{48}\) 化简，可得
$$O(20)\equiv \texttt{0870D9DF20AD}_{16}\pmod{2^{48}}.$$
再乘上剩下的因子 \(4\)，得到
$$f(20)\equiv \texttt{21C3677C82B4}_{16},$$
与题目给出的校验值完全一致。
C++、Python 和 Java 三个实现采用的是同一套数学结构。它们都在模 \(2^{48}\) 下运算，预先计算模 \(2^{16}\) 的所有奇数剩余类在模 \(2^{48}\) 下的逆元，并利用 Newton 迭代来求这些逆元，因为奇数在 \(2\) 的幂模数下总是可逆的。
对于题目要求的输入，它们先构造出整数 \(20!\)。然后生成序列
$$N,\ \left\lfloor\frac{N}{2}\right\rfloor,\ \left\lfloor\frac{N}{4}\right\rfloor,\ \dots$$
直到变成 \(0\)。在每一层，都遍历模 \(2^{16}\) 的全部奇数剩余类；对完整块使用上面的闭式公式，对最后不完整的尾块再补乘一个额外因子。
所有层的结果相乘，就得到 \(N!\) 的奇数部分。与此同时，\(\nu_2(N!)\) 通过不断除以 \(2\) 来累加。最后把 \(2^{\nu_2(N!)\bmod 4}\) 乘回去，并把结果格式化为 12 位的大写十六进制字符串。C++ 版本会并行计算彼此独立的各层前缀；Python 和 Java 版本则按相同逻辑串行完成。
主要工作是对 \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\) 这些值计算奇数前缀乘积，所以总共有 \(O(\log N)\) 层。每一层都需要扫描模 \(2^{16}\) 下的 \(2^{15}\) 个奇数剩余类。每个剩余类内部包含一次模幂和常数次固定宽度模运算；由于模数始终是 \(2^{48}\)，所以实际代价相当稳定。
从实践角度看，这个方法可以理解为一个较小常数乘上 \(2^{15}\log N\)，并使用 \(O(2^{15})\) 的空间来存储逆元表。真正关键的是：算法从头到尾都不会构造完整的 \(N!\)，而只保留那些足以决定最后 12 位十六进制数字的剩余信息。
Пусть \(f(N)\) обозначает последние 12 шестнадцатеричных цифр, остающиеся после удаления всех конечных шестнадцатеричных нулей из записи \(N!\). Требуется найти \(f(20!)\).
Прямо работать с \((20!)!\) невозможно. Поэтому решение хранит только ту информацию, которая может пережить удаление факторов \(16\) и усечение до 12 шестнадцатеричных цифр, то есть остаток по модулю \(16^{12}=2^{48}\).
Главное наблюдение состоит в том, что конечные нули в шестнадцатеричной записи зависят только от степеней двойки, поскольку \(16=2^4\). Остальная часть живет в нечетной составляющей факториала и может отслеживаться по модулю \(2^{48}\).
Для любого положительного целого \(m\) запишем
$$m=2^{\nu_2(m)}\operatorname{odd}(m),$$
где \(\nu_2(m)\) - показатель степени двойки в \(m\), а \(\operatorname{odd}(m)\) - нечетная часть.
Тогда для \(N!\) имеем
$$N!=2^{\nu_2(N!)}\operatorname{odd}(N!).$$
Один конечный шестнадцатеричный ноль соответствует множителю \(16=2^4\). Поэтому после удаления всех таких нулей остается только
$$2^{\nu_2(N!) \bmod 4}$$
как остаточная степень двойки. Следовательно,
$$f(N)\equiv \operatorname{odd}(N!)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
Значение \(\nu_2(N!)\) дается формулой Лежандра:
$$\nu_2(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{2^k}\right\rfloor.$$
Введем обозначения
$$O(N)=\operatorname{odd}(N!),\qquad P(N)=\prod_{\substack{1\le m\le N\\ m\text{ нечетно}}}m.$$
Если разделить множители \(N!\) на нечетные и четные, то у четного множителя \(2t\) нечетная часть совпадает с нечетной частью числа \(t\). Отсюда получается рекурсия
$$O(N)=P(N)\,O\!\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
Повторяя ее, получаем
$$O(N)=\prod_{j\ge 0}P\!\left(\left\lfloor\frac{N}{2^j}\right\rfloor\right),$$
и произведение заканчивается, когда частное становится нулем. Значит, ключевая задача - быстро считать нечетный префиксный продукт \(P(n)\) для нескольких значений \(n\).
Чтобы вычислять \(P(n)\) по модулю \(2^{48}\), выбираем размер блока
$$S=2^{16}.$$
Пишем
$$n=qS+u,\qquad 0\le u<S.$$
Для каждого нечетного вычета \(r\in\{1,3,5,\dots,S-1\}\) числа из этого класса, не превосходящие \(n\), имеют вид
$$r,\ r+S,\ r+2S,\ \dots,\ r+(q-1)S,$$
и еще один дополнительный множитель \(r+qS\) появляется тогда и только тогда, когда \(r\le u\).
Поэтому \(P(n)\) распадается на произведение полных классов и, возможно, одного дополнительного множителя из каждого класса:
$$P(n)=\prod_{\substack{1\le r<S\\ r\text{ нечетно}}}\left(\prod_{j=0}^{q-1}(r+jS)\right)\cdot \prod_{\substack{1\le r\le u\\ r\text{ нечетно}}}(r+qS).$$
Зафиксируем нечетный вычет \(r\) и определим произведение по полному классу
$$C_r(q)=\prod_{j=0}^{q-1}(r+jS).$$
Поскольку \(r\) нечетно, оно обратимо по модулю \(2^{48}\). В кольце \(\mathbb{Z}/2^{48}\mathbb{Z}\) можно записать
$$C_r(q)=r^q\prod_{j=0}^{q-1}(1+j\,a),\qquad a=S\,r^{-1}.$$
Так как \(S=2^{16}\), каждое \(a\) уже содержит множитель \(2^{16}\). Любой член степени \(3\) или выше в разложении \(\prod(1+j\,a)\) содержит \(a^3\), а значит и множитель \(2^{48}\), поэтому он зануляется по модулю \(2^{48}\).
Остаются только первые две элементарные симметрические суммы:
$$\prod_{j=0}^{q-1}(1+j\,a)\equiv 1+a\,e_1+a^2e_2\pmod{2^{48}},$$
где
$$e_1=\sum_{j=0}^{q-1}j=\frac{q(q-1)}{2},$$
$$e_2=\sum_{0\le i<j<q}ij=\frac{q(q-1)(q-2)(3q-1)}{24}.$$
Тем самым длинное произведение заменяется модульной степенью, модульным обратным элементом и вычислением короткого полинома.
Для каждого уровня \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\) вычисляется соответствующее значение \(P(\cdot)\) по формуле для классов вычетов, а затем все уровни перемножаются. Так получается \(O(N)=\operatorname{odd}(N!)\) по модулю \(2^{48}\).
После этого возвращаем оставшуюся степень двойки:
$$f(N)\equiv O(N)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
Поскольку в задаче нужно взять \(N=20!\), реализации сначала вычисляют \(20!\), а уже потом запускают быструю процедуру для этого значения.
В условии приведено значение \(f(20)\) как контрольная точка, и это удобный небольшой пример.
Сначала считаем показатель степени двойки:
$$\nu_2(20!)=\left\lfloor\frac{20}{2}\right\rfloor+\left\lfloor\frac{20}{4}\right\rfloor+\left\lfloor\frac{20}{8}\right\rfloor+\left\lfloor\frac{20}{16}\right\rfloor=10+5+2+1=18.$$
Значит, после удаления всех конечных шестнадцатеричных нулей остается множитель
$$2^{18\bmod 4}=2^2=4.$$
Рекурсивная формула дает
$$O(20)=P(20)\,P(10)\,P(5)\,P(2)\,P(1).$$
Малые префиксные произведения равны
$$P(20)=1\cdot 3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13\cdot 15\cdot 17\cdot 19=654729075,$$
$$P(10)=1\cdot 3\cdot 5\cdot 7\cdot 9=945,\qquad P(5)=1\cdot 3\cdot 5=15,\qquad P(2)=P(1)=1.$$
Следовательно,
$$O(20)=654729075\cdot 945\cdot 15=9280784638125.$$
По модулю \(2^{48}\) это
$$O(20)\equiv \texttt{0870D9DF20AD}_{16}\pmod{2^{48}}.$$
Умножая на оставшийся множитель \(4\), получаем
$$f(20)\equiv \texttt{21C3677C82B4}_{16},$$
что в точности совпадает с контрольным значением.
Реализации на C++, Python и Java используют одну и ту же математику. Все вычисления ведутся по модулю \(2^{48}\), заранее строится таблица обратных элементов для всех нечетных вычетов modulo \(2^{16}\), а для нахождения этих обратных используется итерация Ньютона, поскольку нечетные числа обратимы по модулю степеней двойки.
Для нужного входа сначала вычисляется число \(20!\). Затем строится последовательность
$$N,\ \left\lfloor\frac{N}{2}\right\rfloor,\ \left\lfloor\frac{N}{4}\right\rfloor,\ \dots$$
до нуля. На каждом уровне программа проходит по всем нечетным классам вычетов modulo \(2^{16}\), применяет закрытую формулу к полным блокам и при необходимости домножает один дополнительный множитель из неполного хвостового блока.
Произведение всех уровней дает нечетную часть \(N!\). Отдельно по повторному делению на \(2\) вычисляется \(\nu_2(N!)\). Затем возвращается множитель \(2^{\nu_2(N!)\bmod 4}\), и итог форматируется как 12-значная шестнадцатеричная строка в верхнем регистре. В версии на C++ независимые уровни считаются параллельно, а версии на Python и Java выполняют ту же логику последовательно.
Основная работа - вычисление нечетного префиксного произведения для значений \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\), то есть для \(O(\log N)\) уровней. На каждом уровне просматриваются \(2^{15}\) нечетных классов вычетов modulo \(2^{16}\). Внутри одного класса выполняются модульное возведение в степень и постоянное число операций с фиксированной шириной слова; так как модуль всегда равен \(2^{48}\), эта часть на практике невелика.
Практически метод ведет себя как небольшая константа, умноженная на \(2^{15}\log N\), и использует \(O(2^{15})\) памяти для таблицы обратных элементов. Самое важное здесь то, что алгоритм никогда не строит полный \(N!\); он вычисляет только ту остаточную информацию, которая действительно влияет на последние 12 шестнадцатеричных цифр.
لتكن \(f(N)\) هي آخر 12 خانة ست عشرية تبقى بعد حذف جميع الأصفار الست عشرية النهائية من \(N!\). المطلوب هو حساب \(f(20!)\).
من المستحيل عمليًا التعامل مباشرة مع \((20!)!\). لذلك تحتفظ الفكرة فقط بالمعلومة التي تبقى مؤثرة بعد إزالة عوامل \(16\) والاكتفاء بآخر 12 خانة ست عشرية، أي الحساب modulo \(16^{12}=2^{48}\).
الفكرة الأساسية هي أن الأصفار النهائية في النظام الست عشري تعتمد فقط على قوى \(2\)، لأن \(16=2^4\). أما بقية المعلومات فتقع داخل الجزء الفردي من العاملية ويمكن تتبعها modulo \(2^{48}\).
لكل عدد صحيح موجب \(m\) نكتب
$$m=2^{\nu_2(m)}\operatorname{odd}(m),$$
حيث \(\nu_2(m)\) هو أس \(2\) في \(m\)، و\(\operatorname{odd}(m)\) هو الجزء الفردي بعد حذف كل عوامل \(2\).
وبتطبيق ذلك على \(N!\) نحصل على
$$N!=2^{\nu_2(N!)}\operatorname{odd}(N!).$$
كل صفر نهائي ست عشري يستهلك عاملًا واحدًا من \(16=2^4\). لذلك بعد حذف كل الأصفار النهائية لا يبقى من قوة \(2\) إلا
$$2^{\nu_2(N!) \bmod 4}.$$
ومن ثم
$$f(N)\equiv \operatorname{odd}(N!)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
أما قيمة \(\nu_2(N!)\) فتُحسب بصيغة ليجاندر:
$$\nu_2(N!)=\sum_{k\ge 1}\left\lfloor\frac{N}{2^k}\right\rfloor.$$
نعرّف
$$O(N)=\operatorname{odd}(N!),\qquad P(N)=\prod_{\substack{1\le m\le N\\ m\text{ odd}}}m.$$
إذا قسمنا عوامل \(N!\) إلى عوامل فردية وعوامل زوجية، فإن العامل الزوجي \(2t\) له نفس الجزء الفردي الخاص بـ \(t\). لذلك نحصل على العلاقة
$$O(N)=P(N)\,O\!\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
وبتكرارها نحصل على
$$O(N)=\prod_{j\ge 0}P\!\left(\left\lfloor\frac{N}{2^j}\right\rfloor\right),$$
ويتوقف هذا الجداء عندما يصبح الخارج \(0\). وهكذا تتحول المسألة إلى حساب سريع لعدة جداءات بادئة للأعداد الفردية من الشكل \(P(n)\).
لحساب \(P(n)\) modulo \(2^{48}\)، نختار حجم الكتلة
$$S=2^{16}.$$
ثم نكتب
$$n=qS+u,\qquad 0\le u<S.$$
ولكل باقٍ فردي \(r\in\{1,3,5,\dots,S-1\}\)، فإن الأعداد الفردية في هذه الفئة حتى \(n\) هي
$$r,\ r+S,\ r+2S,\ \dots,\ r+(q-1)S,$$
ويظهر عامل إضافي \(r+qS\) بالضبط عندما يكون \(r\le u\).
إذن يتفكك \(P(n)\) إلى جداءات فئات كاملة، مع احتمال وجود عامل إضافي من كل فئة:
$$P(n)=\prod_{\substack{1\le r<S\\ r\text{ odd}}}\left(\prod_{j=0}^{q-1}(r+jS)\right)\cdot \prod_{\substack{1\le r\le u\\ r\text{ odd}}}(r+qS).$$
لنثبت فئة باقٍ فردي واحدة \(r\)، ونعرف جداء الفئة الكاملة
$$C_r(q)=\prod_{j=0}^{q-1}(r+jS).$$
بما أن \(r\) فردي، فهو قابل للعكس modulo \(2^{48}\). في الحلقة \(\mathbb{Z}/2^{48}\mathbb{Z}\) يمكن كتابة
$$C_r(q)=r^q\prod_{j=0}^{q-1}(1+j\,a),\qquad a=S\,r^{-1}.$$
وحيث إن \(S=2^{16}\)، فإن كل \(a\) يحمل عاملًا مقداره \(2^{16}\). لذلك فإن أي حد من الدرجة الثالثة أو أعلى في توسعة \(\prod(1+j\,a)\) يحتوي على \(a^3\)، أي على عامل \(2^{48}\)، ومن ثم يختفي modulo \(2^{48}\).
إذن لا يبقى إلا أول مجموعين تناظريين:
$$\prod_{j=0}^{q-1}(1+j\,a)\equiv 1+a\,e_1+a^2e_2\pmod{2^{48}},$$
حيث
$$e_1=\sum_{j=0}^{q-1}j=\frac{q(q-1)}{2},$$
$$e_2=\sum_{0\le i<j<q}ij=\frac{q(q-1)(q-2)(3q-1)}{24}.$$
وبذلك يتحول جداء طويل جدًا إلى قوة modular، ومعكوس modular، وتقييم كثير حدود قصير.
لكل مستوى من المستويات
$$N,\ \left\lfloor\frac{N}{2}\right\rfloor,\ \left\lfloor\frac{N}{4}\right\rfloor,\ \dots$$
نحسب \(P(\cdot)\) الموافق باستخدام صيغة فئات البواقي، ثم نضرب كل هذه القيم معًا لنحصل على \(O(N)=\operatorname{odd}(N!)\) modulo \(2^{48}\).
بعد ذلك نعيد ضرب العامل المتبقي من \(2\):
$$f(N)\equiv O(N)\cdot 2^{\nu_2(N!) \bmod 4}\pmod{2^{48}}.$$
وبما أن الهدف هنا هو \(N=20!\)، فإن التنفيذات تحسب \(20!\) أولًا، ثم تطبق هذه الآلية السريعة على تلك القيمة.
يعطي نص المسألة القيمة \(f(20)\) كنقطة تحقق، وهي مثال صغير مناسب جدًا.
أولًا نحسب
$$\nu_2(20!)=\left\lfloor\frac{20}{2}\right\rfloor+\left\lfloor\frac{20}{4}\right\rfloor+\left\lfloor\frac{20}{8}\right\rfloor+\left\lfloor\frac{20}{16}\right\rfloor=10+5+2+1=18.$$
إذن بعد حذف كل الأصفار الست عشرية النهائية، تبقى قوة \(2\) التالية:
$$2^{18\bmod 4}=2^2=4.$$
كما أن العلاقة التكرارية تعطي
$$O(20)=P(20)\,P(10)\,P(5)\,P(2)\,P(1).$$
وهذه الجداءات الصغيرة تساوي
$$P(20)=1\cdot 3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13\cdot 15\cdot 17\cdot 19=654729075,$$
$$P(10)=1\cdot 3\cdot 5\cdot 7\cdot 9=945,\qquad P(5)=1\cdot 3\cdot 5=15,\qquad P(2)=P(1)=1.$$
ومن ثم
$$O(20)=654729075\cdot 945\cdot 15=9280784638125.$$
وبأخذ هذا modulo \(2^{48}\) نحصل على
$$O(20)\equiv \texttt{0870D9DF20AD}_{16}\pmod{2^{48}}.$$
ثم بعد الضرب في العامل المتبقي \(4\) نحصل على
$$f(20)\equiv \texttt{21C3677C82B4}_{16},$$
وهو بالضبط نفس مقدار التحقق المعروف.
تتبع تنفيذات C++ وPython وJava نفس الفكرة الرياضية. جميعها تعمل modulo \(2^{48}\)، وتبني مسبقًا معكوسات جميع البواقي الفردية modulo \(2^{16}\)، وتستخدم تكرار Newton لأن الأعداد الفردية قابلة للعكس modulo قوى \(2\).
بالنسبة للمدخل المطلوب، تبدأ التنفيذات بحساب \(20!\). ثم تولد المتتالية
$$N,\ \left\lfloor\frac{N}{2}\right\rfloor,\ \left\lfloor\frac{N}{4}\right\rfloor,\ \dots$$
حتى تصل إلى \(0\). وفي كل مستوى يتم المرور على جميع فئات البواقي الفردية modulo \(2^{16}\)، مع استعمال الصيغة المغلقة للكتل الكاملة وإضافة عامل واحد عندما تمتد الكتلة الجزئية الأخيرة إلى ذلك الباقي.
جداء نتائج المستويات كلها يعطي الجزء الفردي من \(N!\). وبشكل منفصل، تُحسب \(\nu_2(N!)\) عن طريق القسمة المتكررة على \(2\). وفي النهاية يُعاد العامل \(2^{\nu_2(N!)\bmod 4}\) وتُنسق النتيجة كسلسلة ست عشرية من 12 خانة بأحرف كبيرة. تنفيذ C++ يوازي حسابات المستويات المستقلة، بينما ينفذ Python وJava الخطوات نفسها بصورة تسلسلية.
العمل المسيطر هو حساب جداء البادئة للأعداد الفردية للقيم \(N,\lfloor N/2\rfloor,\lfloor N/4\rfloor,\dots\)، أي لعدد \(O(\log N)\) من المستويات. في كل مستوى يتم المرور على \(2^{15}\) من فئات البواقي الفردية modulo \(2^{16}\). داخل كل فئة توجد قوة modular واحدة وعدد ثابت من العمليات modular ذات العرض الثابت؛ وبما أن المودول ثابت دائمًا ويساوي \(2^{48}\)، فإن الكلفة العملية الصغيرة تبقى مضبوطة.
عمليًا، يتصرف الأسلوب مثل ثابت صغير مضروب في \(2^{15}\log N\)، مع ذاكرة \(O(2^{15})\) لجدول المعكوسات. والمهم أن الخوارزمية لا تبني \(N!\) كاملًا أبدًا، بل تحسب فقط المعلومات المتبقية التي يمكن أن تؤثر في آخر 12 خانة ست عشرية.