Problem 937 asks us to sum those factorials \(k!\) that satisfy the equiproduct-partition condition from the statement, with the final result taken modulo \(10^9+7\). The implementations never search for partitions directly. Instead, they rely on a theorem that converts the condition for \(k!\) into a parity test built from the prime exponents of \(k!\).
So the computational problem is: for every \(1 \le k \le n\), evaluate that arithmetic test quickly, keep track of \(k! \bmod 10^9+7\), and add the current factorial exactly when the equiproduct criterion is true.
The difficult combinatorial part of the problem is already distilled into one number-theoretic characterization. The remaining job is to evaluate that characterization for every \(k\) without recomputing the full factorization of each factorial from scratch.
Let
\[ \mathcal P=\{p \le n : p \equiv 2,5,7 \pmod 8\}. \]
For each prime \(p\in\mathcal P\), define
\[ e_p(k)=v_p(k!), \]
where \(v_p\) is the usual \(p\)-adic valuation. Also let \(s_2(m)\) denote the sum of the binary digits of \(m\), and set
\[ t(m)=s_2(m)\bmod 2. \]
The implementations use the characterization
\[ I(k)=\sum_{p\in\mathcal P} t(e_p(k)) \pmod 2. \]
The factorial \(k!\) contributes to the answer if and only if \(I(k)=0\).
The crucial subtlety is that the code is not taking the parity of \(e_p(k)\) itself. It is taking the parity of the number of 1-bits in the binary expansion of \(e_p(k)\). That is exactly why the implementation uses a bit-parity primitive instead of a simple odd/even test.
The residue classes \(2,5,7 \pmod 8\) are therefore not a heuristic. They are the precise prime classes singled out by the equiproduct criterion behind the solver.
For a fixed prime \(p\), the exponent of \(p\) in \(k!\) is given by Legendre's formula:
\[ e_p(k)=\sum_{a\ge 1}\left\lfloor \frac{k}{p^a}\right\rfloor. \]
Evaluating this independently for every pair \((p,k)\) would be far too slow. The useful observation is that \(e_p(k)\) changes only when \(k\) is divisible by \(p\). If \(q\) is a multiple of \(p\), then
\[ e_p(q)=e_p(q-1)+v_p(q), \]
while for nonmultiples we simply have \(e_p(k)=e_p(k-1)\).
That means each prime can be processed by scanning only
\[ p,2p,3p,\dots \]
and maintaining the current value of \(e_p(k)\). The inner divisions in the code do nothing mysterious: they are just extracting \(v_p(q)\) when \(q\) contains higher powers of \(p\).
For each selected prime, define the bit
\[ B_p(k)=t(e_p(k)). \]
The global equiproduct indicator is the xor, or equivalently the sum modulo 2, of all these bits. Instead of storing the full table of every \(B_p(k)\), the implementation stores only the places where a prime contribution changes:
\[ \Delta_p(k)=B_p(k)\oplus B_p(k-1). \]
Because \(B_p(k)\) can change only at multiples of \(p\), \(\Delta_p(k)\) is sparse. The shared array `diff` accumulates
\[ \Delta(k)=\bigoplus_{p\in\mathcal P}\Delta_p(k). \]
Once that array has been built, the true state is reconstructed by one prefix xor:
\[ I(k)=I(k-1)\oplus \Delta(k). \]
This is the central invariant of the whole method. The solver never recomputes the full criterion for a given \(k\); it only tracks when the criterion flips.
Up to \(7\), the relevant primes are \(2,5,7\). For \(k=6\) we have
\[ v_2(6!)=4,\qquad v_5(6!)=1,\qquad v_7(6!)=0. \]
Now compute the binary-digit parities:
\[ t(4)=s_2(4)\bmod 2=1,\qquad t(1)=1,\qquad t(0)=0. \]
Therefore
\[ I(6)=1+1+0\equiv 0 \pmod 2, \]
so \(6!=720\) is added to the answer.
Passing from \(6!\) to \(7!\) changes only the exponent of prime \(7\): now \(v_7(7!)=1\), hence \(t(v_7(7!))=1\). So the global state flips once:
\[ I(7)=I(6)\oplus 1=1. \]
Thus \(7!\) does not contribute. This matches the checkpoint values: up to \(7\), the contributing factorials are \(1!\), \(4!\), and \(6!\).
While the prefix xor reconstructs \(I(k)\), the implementation also maintains
\[ F(k)\equiv k! \pmod{10^9+7} \]
through the recurrence
\[ F(k)=k\cdot F(k-1)\pmod{10^9+7}. \]
Whenever \(I(k)=0\), the current value \(F(k)\) is added to the running total. No factorial is factored separately, and no partition object is generated explicitly.
The C++ and Java implementations begin with a standard sieve of Eratosthenes up to \(n\). They discard primes congruent to \(1\) or \(3\) modulo \(8\), because those primes never affect the equiproduct criterion encoded by the solver. For every remaining prime, they walk through its multiples, update the running factorial exponent for that prime, compare the old and new values of \(t(e)\), and xor the resulting flip into one shared byte array.
This is why the code needs only one running exponent per prime and one global difference array. It never materializes all values of \(v_p(k!)\) for all \(p\) and \(k\).
After all prime events have been merged into the difference array, one left-to-right pass finishes the job. The implementation keeps a running xor for the equiproduct indicator and a running factorial modulo \(10^9+7\). Whenever the indicator is zero, it adds the current factorial to the answer.
The C++ and Java implementations perform this arithmetic directly. The provided Python entry point is a thin wrapper around the same compiled computation, so all three delivered implementations are driven by the same mathematical test and the same final accumulation rule.
The sieve costs \(O(n \log \log n)\). The main multiple-scan work is
\[ \sum_{p\in\mathcal P}\left\lfloor \frac{n}{p}\right\rfloor, \]
and the extra divisions needed to detect higher prime powers contribute
\[ \sum_{p\le n}\sum_{a\ge 2}\left\lfloor \frac{n}{p^a}\right\rfloor. \]
The first sum is \(O(n\log\log n)\), and the second is \(O(n)\), so the preprocessing remains \(O(n\log\log n)\) overall.
The final prefix-xor and factorial sweep is \(O(n)\). Memory usage is \(O(n)\), dominated by the difference array and the sieve storage.
Problem 937 verlangt die Summe genau der Fakultäten \(k!\), die die Equiproduct-Partition-Bedingung aus der Aufgabenstellung erfüllen; das Endergebnis wird modulo \(10^9+7\) genommen. Die Implementierungen suchen diese Partitionen nicht direkt. Stattdessen verwenden sie einen Satz, der die Bedingung für \(k!\) in einen Paritätstest über die Primexponenten von \(k!\) übersetzt.
Damit lautet die eigentliche Rechenaufgabe: Für jedes \(1 \le k \le n\) diesen arithmetischen Test schnell auswerten, gleichzeitig \(k! \bmod 10^9+7\) fortschreiben und die aktuelle Fakultät genau dann addieren, wenn das Equiproduct-Kriterium erfüllt ist.
Der schwierige kombinatorische Teil der Aufgabe ist bereits in einer einzigen zahlentheoretischen Charakterisierung zusammengefasst. Der Rest der Lösung besteht darin, diese Charakterisierung für alle \(k\) effizient auszuwerten, ohne die Faktorisierung jeder Fakultät immer wieder neu zu berechnen.
Sei
\[ \mathcal P=\{p \le n : p \equiv 2,5,7 \pmod 8\}. \]
Für jede Primzahl \(p\in\mathcal P\) setzen wir
\[ e_p(k)=v_p(k!), \]
wobei \(v_p\) die übliche \(p\)-adische Bewertung ist. Bezeichne außerdem \(s_2(m)\) als Summe der Binärziffern von \(m\), und definiere
\[ t(m)=s_2(m)\bmod 2. \]
Die Implementierungen benutzen dann die Charakterisierung
\[ I(k)=\sum_{p\in\mathcal P} t(e_p(k)) \pmod 2. \]
Die Fakultät \(k!\) trägt genau dann zur Antwort bei, wenn \(I(k)=0\).
Der entscheidende Punkt ist: Der Code betrachtet nicht die Parität von \(e_p(k)\) selbst, sondern die Parität der Anzahl von Einsen in der Binärdarstellung von \(e_p(k)\). Genau deshalb wird eine Bit-Paritätsfunktion verwendet und kein bloßer Gerade-Ungerade-Test.
Die Restklassen \(2,5,7 \pmod 8\) sind also kein Trick, sondern genau die Primklassen, die im Equiproduct-Kriterium der Lösung auftreten.
Für eine feste Primzahl \(p\) gilt nach der Formel von Legendre
\[ e_p(k)=\sum_{a\ge 1}\left\lfloor \frac{k}{p^a}\right\rfloor. \]
Diese Formel für jedes Paar \((p,k)\) separat auszuwerten, wäre viel zu teuer. Die nützliche Beobachtung ist, dass sich \(e_p(k)\) nur dann ändert, wenn \(k\) durch \(p\) teilbar ist. Ist \(q\) ein Vielfaches von \(p\), dann gilt
\[ e_p(q)=e_p(q-1)+v_p(q), \]
während für Nichtvielfache einfach \(e_p(k)=e_p(k-1)\) bleibt.
Damit kann jede Primzahl verarbeitet werden, indem man nur
\[ p,2p,3p,\dots \]
durchläuft und den aktuellen Wert von \(e_p(k)\) fortschreibt. Die inneren Divisionen im Code sind lediglich die Auswertung von \(v_p(q)\), wenn \(q\) höhere Potenzen von \(p\) enthält.
Für jede relevante Primzahl definieren wir das Bit
\[ B_p(k)=t(e_p(k)). \]
Der globale Equiproduct-Indikator ist das XOR, also äquivalent die Summe modulo 2, über alle diese Bits. Statt die vollständige Tabelle aller \(B_p(k)\) zu speichern, hält die Implementierung nur die Stellen fest, an denen sich ein Primbeitrag ändert:
\[ \Delta_p(k)=B_p(k)\oplus B_p(k-1). \]
Da \(B_p(k)\) sich nur an Vielfachen von \(p\) ändern kann, ist \(\Delta_p(k)\) dünn besetzt. Das gemeinsame Array `diff` akkumuliert
\[ \Delta(k)=\bigoplus_{p\in\mathcal P}\Delta_p(k). \]
Aus diesem Array wird der wahre Zustand anschließend durch ein einziges Präfix-XOR rekonstruiert:
\[ I(k)=I(k-1)\oplus \Delta(k). \]
Das ist die zentrale Invariante der gesamten Methode. Der Solver berechnet das Kriterium für ein gegebenes \(k\) nie komplett neu, sondern verfolgt nur, wann es kippt.
Bis \(7\) sind die relevanten Primzahlen \(2,5,7\). Für \(k=6\) gilt
\[ v_2(6!)=4,\qquad v_5(6!)=1,\qquad v_7(6!)=0. \]
Die zugehörigen Binärziffern-Paritäten sind
\[ t(4)=s_2(4)\bmod 2=1,\qquad t(1)=1,\qquad t(0)=0. \]
Also folgt
\[ I(6)=1+1+0\equiv 0 \pmod 2, \]
und deshalb wird \(6!=720\) addiert.
Der Übergang von \(6!\) zu \(7!\) ändert nur den Exponenten der Primzahl \(7\): Nun ist \(v_7(7!)=1\), also \(t(v_7(7!))=1\). Damit kippt der globale Zustand genau einmal:
\[ I(7)=I(6)\oplus 1=1. \]
Folglich trägt \(7!\) nicht bei. Das stimmt mit den kleinen Kontrollwerten überein: Bis \(7\) zählen genau \(1!\), \(4!\) und \(6!\).
Während das Präfix-XOR \(I(k)\) rekonstruiert, hält die Implementierung gleichzeitig
\[ F(k)\equiv k! \pmod{10^9+7} \]
über die Rekursion
\[ F(k)=k\cdot F(k-1)\pmod{10^9+7} \]
auf dem neuesten Stand. Immer wenn \(I(k)=0\) ist, wird der aktuelle Wert \(F(k)\) zur Antwort addiert. Keine Fakultät wird separat faktorisiert, und kein Partitionsobjekt wird explizit konstruiert.
Die C++- und Java-Implementierungen starten mit einem klassischen Sieb des Eratosthenes bis \(n\). Primzahlen kongruent zu \(1\) oder \(3\) modulo \(8\) werden verworfen, weil sie das im Solver kodierte Equiproduct-Kriterium nicht beeinflussen. Für jede verbleibende Primzahl werden ihre Vielfachen durchlaufen, der laufende Fakultätsexponent aktualisiert, der alte und der neue Wert von \(t(e)\) verglichen und der resultierende Flip in ein gemeinsames Byte-Array geXORt.
Darum benötigt der Code nur einen laufenden Exponenten pro Primzahl und ein globales Differenzarray. Alle Werte \(v_p(k!)\) für alle \(p\) und \(k\) werden nie vollständig materialisiert.
Sobald alle Primereignisse im Differenzarray zusammengeführt sind, genügt ein einziger Durchlauf von links nach rechts. Die Implementierung führt ein laufendes XOR für den Equiproduct-Indikator und eine laufende Fakultät modulo \(10^9+7\). Wenn der Indikator null ist, wird die aktuelle Fakultät zur Summe hinzugefügt.
Die C++- und Java-Versionen führen diese Arithmetik direkt aus. Der bereitgestellte Python-Einstiegspunkt ist nur eine schlanke Hülle um dieselbe kompilierte Rechnung; alle drei gelieferten Implementierungen benutzen also denselben mathematischen Test und dieselbe Akkumulationsregel.
Das Sieb kostet \(O(n \log \log n)\). Die eigentliche Vielfachenarbeit ist
\[ \sum_{p\in\mathcal P}\left\lfloor \frac{n}{p}\right\rfloor, \]
und die zusätzlichen Divisionen zum Erkennen höherer Primzahlpotenzen liefern
\[ \sum_{p\le n}\sum_{a\ge 2}\left\lfloor \frac{n}{p^a}\right\rfloor. \]
Die erste Summe ist \(O(n\log\log n)\), die zweite \(O(n)\), also bleibt die gesamte Vorverarbeitung \(O(n\log\log n)\).
Der abschließende Präfix-XOR- und Fakultätsdurchlauf ist \(O(n)\). Der Speicherverbrauch ist \(O(n)\), dominiert vom Differenzarray und der Siebstruktur.
Problem 937, sorudaki equiproduct partition koşulunu sağlayan \(k!\) değerlerinin toplamını istemektedir; sonuç \(10^9+7\) modunda verilir. Uygulamalar bu bölmeleri doğrudan aramaz. Bunun yerine, \(k!\) için gerekli koşulu, \(k!\) içindeki asal üslerden kurulan bir parite testine dönüştüren bir karakterizasyon kullanırlar.
Dolayısıyla gerçek hesaplama görevi şudur: Her \(1 \le k \le n\) için bu aritmetik testi hızlıca değerlendirmek, aynı anda \(k! \bmod 10^9+7\) değerini güncel tutmak ve equiproduct koşulu sağlandığında o andaki faktöriyeli cevaba eklemek.
Problemin zor kombinatorik kısmı tek bir sayılar kuramı kriterine indirgenmiş durumdadır. Geriye kalan iş, her \(k\) için bu kriteri, her faktöriyelin asal çarpanlara ayrımını baştan kurmadan değerlendirmektir.
Şunu tanımlayalım:
\[ \mathcal P=\{p \le n : p \equiv 2,5,7 \pmod 8\}. \]
Her \(p\in\mathcal P\) asalı için
\[ e_p(k)=v_p(k!) \]
olsun; burada \(v_p\), standart \(p\)-adik değerlemedir. Ayrıca \(s_2(m)\), \(m\)'nin ikilik yazımındaki 1'lerin sayısı olsun ve
\[ t(m)=s_2(m)\bmod 2 \]
tanımlansın. Uygulamalar şu karakterizasyonu kullanır:
\[ I(k)=\sum_{p\in\mathcal P} t(e_p(k)) \pmod 2. \]
\(k!\) ancak ve ancak \(I(k)=0\) olduğunda toplama girer.
Buradaki kritik incelik şudur: Kod, \(e_p(k)\)'nin tek-çiftliğine bakmıyor. \(e_p(k)\)'nin ikilik açılımındaki 1 bitlerinin sayısının tek-çiftliğine bakıyor. Bu yüzden çözüm basit bir mod 2 testi değil, bit paritesi kullanan bir ilkel işleme dayanıyor.
Dolayısıyla \(2,5,7 \pmod 8\) sınıfları da sezgisel bir seçim değildir; çözümün kullandığı equiproduct kriterinde ortaya çıkan tam asal sınıflarıdır.
Sabit bir \(p\) asalı için \(p\)'nin \(k!\) içindeki üssü Legendre formülüyle verilir:
\[ e_p(k)=\sum_{a\ge 1}\left\lfloor \frac{k}{p^a}\right\rfloor. \]
Bu formülü her \((p,k)\) çifti için ayrı ayrı hesaplamak çok pahalı olurdu. Önemli gözlem, \(e_p(k)\) değerinin yalnızca \(k\), \(p\)'ye bölündüğünde değişmesidir. Eğer \(q\), \(p\)'nin bir katıysa
\[ e_p(q)=e_p(q-1)+v_p(q), \]
yoksa sadece \(e_p(k)=e_p(k-1)\) kalır.
Böylece her asal için yalnızca
\[ p,2p,3p,\dots \]
değerlerini dolaşmak ve o asalın mevcut toplam üssünü güncellemek yeterlidir. Kod içindeki tekrar bölmeler, \(q\) sayısının \(p\)'nin daha yüksek kuvvetlerini kaç kez içerdiğini, yani \(v_p(q)\)'yu çıkarmaktan ibarettir.
Her seçili asal için
\[ B_p(k)=t(e_p(k)) \]
bitini tanımlayalım. Global equiproduct göstergesi, bu bitlerin XOR'u, yani mod 2 toplamıdır. Çözüm, bütün \(B_p(k)\) tablolarını saklamak yerine yalnızca bir asal katkısının değiştiği yerleri tutar:
\[ \Delta_p(k)=B_p(k)\oplus B_p(k-1). \]
\(B_p(k)\) yalnızca \(p\)'nin katlarında değişebildiği için \(\Delta_p(k)\) seyrektir. Ortak `diff` dizisi
\[ \Delta(k)=\bigoplus_{p\in\mathcal P}\Delta_p(k) \]
değerini biriktirir. Bundan sonra gerçek durum tek bir prefix XOR ile geri kazanılır:
\[ I(k)=I(k-1)\oplus \Delta(k). \]
Yöntemin merkezindeki invariant budur. Çözüm, belli bir \(k\) için kriteri baştan hesaplamaz; yalnızca kriterin hangi adımlarda ters döndüğünü izler.
\(7\)'ye kadar ilgili asallar \(2,5,7\)'dir. \(k=6\) için
\[ v_2(6!)=4,\qquad v_5(6!)=1,\qquad v_7(6!)=0. \]
Şimdi ikilik basamak paritelerini hesaplayalım:
\[ t(4)=s_2(4)\bmod 2=1,\qquad t(1)=1,\qquad t(0)=0. \]
Dolayısıyla
\[ I(6)=1+1+0\equiv 0 \pmod 2, \]
ve \(6!=720\) cevaba eklenir.
\(6!\)'dan \(7!\)'a geçerken yalnızca \(7\) asalının üssü değişir: artık \(v_7(7!)=1\), dolayısıyla \(t(v_7(7!))=1\). Global durum bir kez flip eder:
\[ I(7)=I(6)\oplus 1=1. \]
Böylece \(7!\) katkı vermez. Bu, küçük doğrulamalarla da aynıdır: \(7\)'ye kadar katkı yapan faktöriyeller \(1!\), \(4!\) ve \(6!\)'dir.
Prefix XOR ile \(I(k)\) geri kurulurken uygulama aynı zamanda
\[ F(k)\equiv k! \pmod{10^9+7} \]
değerini
\[ F(k)=k\cdot F(k-1)\pmod{10^9+7} \]
bağıntısıyla güncel tutar. \(I(k)=0\) olduğunda o andaki \(F(k)\) cevap toplamına eklenir. Her faktöriyel ayrı ayrı çarpanlarına ayrılmaz ve hiçbir partition nesnesi açıkça üretilmez.
C++ ve Java uygulamaları önce \(n\)'ye kadar klasik Eratosthenes eleğini kurar. \(1\) veya \(3 \pmod 8\) olan asallar atılır; çünkü çözümde kullanılan equiproduct kriterini bunlar etkilemez. Kalan her asal için katlar dolaşılır, o asalın mevcut faktöriyel üssü güncellenir, \(t(e)\)'nin eski ve yeni değeri karşılaştırılır ve ortaya çıkan flip ortak bir byte dizisine XOR ile işlenir.
Bu yüzden kod, her asal için yalnızca tek bir yürüyen üs değeri ve global bir fark dizisi tutar. Bütün \(v_p(k!)\) değerlerini tüm \(p\) ve \(k\) için saklamaya ihtiyaç yoktur.
Bütün asal olayları fark dizisine işlendiğinde soldan sağa tek geçiş yeterlidir. Uygulama bir yandan equiproduct göstergesinin XOR durumunu, öte yandan \(10^9+7\) modundaki faktöriyeli taşır. Gösterge sıfır olduğunda o andaki faktöriyel cevaba eklenir.
C++ ve Java sürümleri bu aritmetiği doğrudan uygular. Verilen Python giriş noktası ise aynı derlenmiş hesabın ince bir sarmalayıcısıdır; dolayısıyla sunulan üç uygulamanın tamamı aynı matematiksel teste ve aynı son toplama kuralına dayanır.
Elek aşaması \(O(n \log \log n)\) zaman alır. Katlar üzerinde yapılan ana iş miktarı
\[ \sum_{p\in\mathcal P}\left\lfloor \frac{n}{p}\right\rfloor \]
kadardır. Daha yüksek asal kuvvetlerini tespit etmek için yapılan ek bölmelerin toplamı ise
\[ \sum_{p\le n}\sum_{a\ge 2}\left\lfloor \frac{n}{p^a}\right\rfloor \]
şeklindedir. İlk toplam \(O(n\log\log n)\), ikinci toplam \(O(n)\) olduğundan tüm ön işlem yine \(O(n\log\log n)\) kalır.
Son prefix XOR ve faktöriyel taraması \(O(n)\) sürer. Bellek kullanımı \(O(n)\)'dir; baskın yapılar fark dizisi ile eleğin tuttuğu verilerdir.
El problema 937 pide sumar exactamente los factoriales \(k!\) que cumplen la condición de equiproduct partition descrita en el enunciado, tomando el resultado final módulo \(10^9+7\). Las implementaciones no buscan esas particiones de manera directa. En su lugar, usan un criterio que transforma la condición para \(k!\) en una prueba de paridad construida a partir de los exponentes primos de \(k!\).
Así, la tarea computacional real es: para cada \(1 \le k \le n\), evaluar rápidamente ese test aritmético, mantener \(k! \bmod 10^9+7\) y añadir el factorial actual exactamente cuando el criterio de equiproducto es verdadero.
La parte combinatoria difícil ya está comprimida en una sola caracterización aritmética. Lo que queda es evaluarla para todos los \(k\) sin recomputar desde cero la factorización completa de cada factorial.
Definimos
\[ \mathcal P=\{p \le n : p \equiv 2,5,7 \pmod 8\}. \]
Para cada primo \(p\in\mathcal P\), sea
\[ e_p(k)=v_p(k!), \]
donde \(v_p\) es la valoración \(p\)-ádica usual. Sea además \(s_2(m)\) la suma de los dígitos binarios de \(m\), y pongamos
\[ t(m)=s_2(m)\bmod 2. \]
Las implementaciones usan entonces la caracterización
\[ I(k)=\sum_{p\in\mathcal P} t(e_p(k)) \pmod 2. \]
El factorial \(k!\) contribuye si y solo si \(I(k)=0\).
La sutileza central es que el código no toma la paridad de \(e_p(k)\) como entero. Lo que toma es la paridad del número de bits iguales a 1 en la expansión binaria de \(e_p(k)\). Por eso la implementación usa una operación de paridad de bits y no una simple comprobación de imparidad.
En consecuencia, las clases \(2,5,7 \pmod 8\) no son una heurística: son exactamente las clases primas que aparecen en el criterio de equiproducto que utiliza la solución.
Para un primo fijo \(p\), el exponente de \(p\) en \(k!\) viene dado por la fórmula de Legendre:
\[ e_p(k)=\sum_{a\ge 1}\left\lfloor \frac{k}{p^a}\right\rfloor. \]
Evaluar esta fórmula de forma independiente para cada par \((p,k)\) sería demasiado caro. La observación útil es que \(e_p(k)\) solo cambia cuando \(k\) es múltiplo de \(p\). Si \(q\) es un múltiplo de \(p\), entonces
\[ e_p(q)=e_p(q-1)+v_p(q), \]
mientras que para los no múltiplos simplemente se cumple \(e_p(k)=e_p(k-1)\).
Eso permite procesar cada primo recorriendo solo
\[ p,2p,3p,\dots \]
y manteniendo el valor corriente de \(e_p(k)\). Las divisiones repetidas del código no son más que la extracción de \(v_p(q)\) cuando \(q\) contiene potencias superiores de \(p\).
Para cada primo relevante definimos el bit
\[ B_p(k)=t(e_p(k)). \]
El indicador global de equiproducto es el xor, o equivalentemente la suma módulo 2, de todos esos bits. En lugar de guardar la tabla completa de cada \(B_p(k)\), la implementación solo registra los puntos en los que cambia la contribución de un primo:
\[ \Delta_p(k)=B_p(k)\oplus B_p(k-1). \]
Como \(B_p(k)\) solo puede cambiar en múltiplos de \(p\), \(\Delta_p(k)\) es disperso. El arreglo compartido `diff` acumula
\[ \Delta(k)=\bigoplus_{p\in\mathcal P}\Delta_p(k). \]
Una vez construido ese arreglo, el estado real se recupera con un solo xor prefijo:
\[ I(k)=I(k-1)\oplus \Delta(k). \]
Ese es el invariante central de todo el método. La solución no vuelve a calcular el criterio completo para cada \(k\); solo sigue los instantes en que dicho criterio cambia.
Hasta \(7\), los primos relevantes son \(2,5,7\). Para \(k=6\) tenemos
\[ v_2(6!)=4,\qquad v_5(6!)=1,\qquad v_7(6!)=0. \]
Ahora calculamos las paridades de las sumas de bits:
\[ t(4)=s_2(4)\bmod 2=1,\qquad t(1)=1,\qquad t(0)=0. \]
Por tanto,
\[ I(6)=1+1+0\equiv 0 \pmod 2, \]
y \(6!=720\) se añade a la respuesta.
Al pasar de \(6!\) a \(7!\) solo cambia el exponente del primo \(7\): ahora \(v_7(7!)=1\), de modo que \(t(v_7(7!))=1\). El estado global cambia una sola vez:
\[ I(7)=I(6)\oplus 1=1. \]
Así, \(7!\) no contribuye. Esto coincide con las comprobaciones pequeñas: hasta \(7\), los factoriales que sí cuentan son \(1!\), \(4!\) y \(6!\).
Mientras el xor prefijo reconstruye \(I(k)\), la implementación también mantiene
\[ F(k)\equiv k! \pmod{10^9+7} \]
mediante la recurrencia
\[ F(k)=k\cdot F(k-1)\pmod{10^9+7}. \]
Cada vez que \(I(k)=0\), el valor actual \(F(k)\) se añade al acumulado. No se factoriza cada factorial por separado ni se construye explícitamente ningún objeto de partición.
Las implementaciones en C++ y Java empiezan con una criba de Eratóstenes hasta \(n\). Descarta los primos congruentes con \(1\) o \(3\) módulo \(8\), porque esos primos no afectan el criterio de equiproducto codificado en la solución. Para cada primo restante, recorre sus múltiplos, actualiza el exponente acumulado de ese primo dentro del factorial actual, compara el valor viejo y el nuevo de \(t(e)\), y hace xor del cambio en un único arreglo de bytes.
Por eso el código solo necesita un exponente en marcha por primo y un arreglo global de diferencias. Nunca materializa todos los valores \(v_p(k!)\) para todos los \(p\) y todos los \(k\).
Una vez fusionados todos los eventos primos en el arreglo de diferencias, basta un único barrido de izquierda a derecha. La implementación mantiene un xor acumulado para el indicador de equiproducto y un factorial acumulado módulo \(10^9+7\). Cuando el indicador vale cero, suma el factorial actual a la respuesta.
Las versiones en C++ y Java realizan esa aritmética de forma directa. La entrada proporcionada en Python es una envoltura mínima sobre el mismo cálculo compilado, así que las tres implementaciones entregadas usan la misma prueba matemática y la misma regla final de acumulación.
La criba cuesta \(O(n \log \log n)\). El trabajo principal sobre múltiplos es
\[ \sum_{p\in\mathcal P}\left\lfloor \frac{n}{p}\right\rfloor, \]
y las divisiones extra necesarias para detectar potencias superiores de un primo aportan
\[ \sum_{p\le n}\sum_{a\ge 2}\left\lfloor \frac{n}{p^a}\right\rfloor. \]
La primera suma es \(O(n\log\log n)\) y la segunda es \(O(n)\), de modo que todo el preprocesamiento sigue siendo \(O(n\log\log n)\).
El barrido final con xor prefijo y actualización del factorial es \(O(n)\). El uso de memoria es \(O(n)\), dominado por el arreglo de diferencias y el almacenamiento de la criba.
第 937 题要求把所有满足题目中 equiproduct partition 条件的 \(k!\) 加起来，并将结果对 \(10^9+7\) 取模。给出的实现并不会显式搜索这些分割。它们依赖的是一个等价刻画：是否满足该条件，可以从 \(k!\) 的素因子指数中构造出一个二值判定。
因此，真正的计算任务变成了：对每个 \(1 \le k \le n\)，高效判断这个算术条件是否成立，同时维护 \(k! \bmod 10^9+7\)，并且只在 equiproduct 条件成立时把当前的 \(k!\) 加入答案。
题目中最难的组合部分，在代码里已经被压缩成了一个纯数论判据。后面的工作不是重新理解所有分割，而是把这个判据对所有 \(k\) 快速算出来，并且避免为每个 factorial 都重新做一遍完整分解。
定义素数集合
\[ \mathcal P=\{p \le n : p \equiv 2,5,7 \pmod 8\}. \]
对每个 \(p\in\mathcal P\)，记
\[ e_p(k)=v_p(k!), \]
其中 \(v_p\) 是通常的 \(p\)-进赋值。再记 \(s_2(m)\) 为整数 \(m\) 的二进制数位和，并定义
\[ t(m)=s_2(m)\bmod 2. \]
实现真正使用的就是下面这个判定：
\[ I(k)=\sum_{p\in\mathcal P} t(e_p(k)) \pmod 2. \]
当且仅当 \(I(k)=0\) 时，\(k!\) 才会被计入答案。
这里最容易误读的一点是：代码看的 不是 \(e_p(k)\) 本身的奇偶性，而是 \(e_p(k)\) 的二进制展开里 1 的个数的奇偶性。也正因为如此，实现里用的是“位奇偶”操作，而不是普通的奇偶判断。
同样，\(2,5,7 \pmod 8\) 这些剩余类也不是经验性的筛选，而是这个 equiproduct 判据中真正出现的素数类别。
对固定素数 \(p\)，\(p\) 在 \(k!\) 中的指数由 Legendre 公式给出：
\[ e_p(k)=\sum_{a\ge 1}\left\lfloor \frac{k}{p^a}\right\rfloor. \]
如果对每一对 \((p,k)\) 都独立计算这个式子，代价会非常高。真正有用的观察是：只有当 \(k\) 是 \(p\) 的倍数时，\(e_p(k)\) 才会发生变化。若 \(q\) 是 \(p\) 的倍数，则
\[ e_p(q)=e_p(q-1)+v_p(q), \]
而当 \(k\) 不是 \(p\) 的倍数时，只是简单地有 \(e_p(k)=e_p(k-1)\)。
这意味着每个素数都只需要扫描
\[ p,2p,3p,\dots \]
这些位置，并维护当前的 \(e_p(k)\)。代码中的反复整除并没有别的含义，它只是把 \(q\) 中含有多少个 \(p\) 提取出来，也就是在计算 \(v_p(q)\)。
对每个相关素数，定义一个二值状态
\[ B_p(k)=t(e_p(k)). \]
全局的 equiproduct 指示量，就是这些状态的 xor，也等价于它们的模 2 和。实现并没有把每个 \(B_p(k)\) 的整张表都存下来，而是只记录某个素数贡献发生翻转的位置：
\[ \Delta_p(k)=B_p(k)\oplus B_p(k-1). \]
因为 \(B_p(k)\) 只可能在 \(p\) 的倍数处变化，所以 \(\Delta_p(k)\) 是稀疏的。共享数组 `diff` 累加的是
\[ \Delta(k)=\bigoplus_{p\in\mathcal P}\Delta_p(k). \]
当这个数组建好以后，只需做一次前缀 xor，就能还原真实状态：
\[ I(k)=I(k-1)\oplus \Delta(k). \]
这就是整个算法的核心不变量。程序从不为某个固定的 \(k\) 重新完整计算一遍判据，而只是追踪判据会在哪些位置翻转。
在 \(7\) 以内，相关素数是 \(2,5,7\)。当 \(k=6\) 时，
\[ v_2(6!)=4,\qquad v_5(6!)=1,\qquad v_7(6!)=0. \]
于是对应的二进制数位奇偶为
\[ t(4)=s_2(4)\bmod 2=1,\qquad t(1)=1,\qquad t(0)=0. \]
因此
\[ I(6)=1+1+0\equiv 0 \pmod 2, \]
所以 \(6!=720\) 会被加入答案。
从 \(6!\) 过渡到 \(7!\) 时，只有素数 \(7\) 的指数发生变化：现在 \(v_7(7!)=1\)，因此 \(t(v_7(7!))=1\)。于是全局状态恰好翻转一次：
\[ I(7)=I(6)\oplus 1=1. \]
这就说明 \(7!\) 不再贡献。它和小样例完全一致：到 \(7\) 为止，被计入的恰好是 \(1!\)、\(4!\) 和 \(6!\)。
当前缀 xor 用来恢复 \(I(k)\) 时，程序还同时维护
\[ F(k)\equiv k! \pmod{10^9+7} \]
并按递推式
\[ F(k)=k\cdot F(k-1)\pmod{10^9+7} \]
更新它。每当 \(I(k)=0\)，当前的 \(F(k)\) 就加入总答案。程序不会对每个 factorial 单独分解，也不会显式构造任何 partition 对象。
C++ 和 Java 实现先做一个到 \(n\) 为止的埃氏筛。所有满足 \(p\equiv 1\) 或 \(3 \pmod 8\) 的素数都会被跳过，因为它们不会影响这里使用的 equiproduct 判定。对每个保留下来的素数，程序遍历其倍数，更新该素数在当前阶乘中的累计指数，比较 \(t(e)\) 的旧值和新值，并把是否翻转这一位 xor 到一个共享的字节数组里。
所以代码真正需要保存的只是“某个素数当前的累计指数”和“全局翻转事件数组”。它从头到尾都不会把所有 \(v_p(k!)\) 的二维表展开出来。
当所有素数事件都已经并入差分数组之后，再做一次从左到右的扫描就足够了。实现维护 equiproduct 指示量的前缀 xor，同时维护 \(10^9+7\) 模意义下的当前阶乘值。只要指示量为零，就把当前阶乘值累加进答案。
C++ 与 Java 版本直接完成这套算术。提供的 Python 入口则只是对同一套编译后计算的轻量封装，因此三种实现入口在数学上完全一致，使用的判定与累加规则也完全相同。
筛法本身是 \(O(n \log \log n)\)。在选中素数上的主要访问次数为
\[ \sum_{p\in\mathcal P}\left\lfloor \frac{n}{p}\right\rfloor, \]
而为了识别更高次素数幂所做的额外整除次数为
\[ \sum_{p\le n}\sum_{a\ge 2}\left\lfloor \frac{n}{p^a}\right\rfloor. \]
前一项是 \(O(n\log\log n)\)，后一项是 \(O(n)\)，所以整个预处理仍然是 \(O(n\log\log n)\)。
最后的前缀 xor 加阶乘扫描是 \(O(n)\)。空间复杂度是 \(O(n)\)，主要由差分数组和筛法所占的存储决定。
В задаче 937 требуется сложить все факториалы \(k!\), удовлетворяющие условию equiproduct partition из формулировки, и взять результат по модулю \(10^9+7\). Реализации не ищут такие разбиения напрямую. Вместо этого они используют критерий, который переводит условие для \(k!\) в проверку четности, построенную по простым показателям факториала.
Поэтому реальная вычислительная задача такова: для каждого \(1 \le k \le n\) быстро проверять этот арифметический критерий, поддерживать значение \(k! \bmod 10^9+7\) и добавлять текущий факториал в ответ ровно тогда, когда условие equiproduct выполнено.
Трудная комбинаторная часть уже сведена в коде к одному числовому критерию. Остается только эффективно вычислять этот критерий для всех \(k\), не раскладывая каждый факториал заново.
Определим множество простых
\[ \mathcal P=\{p \le n : p \equiv 2,5,7 \pmod 8\}. \]
Для каждого \(p\in\mathcal P\) положим
\[ e_p(k)=v_p(k!), \]
где \(v_p\) обозначает обычную \(p\)-адическую валюацию. Пусть \(s_2(m)\) есть сумма двоичных цифр числа \(m\), и определим
\[ t(m)=s_2(m)\bmod 2. \]
Реализации используют следующий критерий:
\[ I(k)=\sum_{p\in\mathcal P} t(e_p(k)) \pmod 2. \]
Факториал \(k!\) входит в сумму тогда и только тогда, когда \(I(k)=0\).
Главная тонкость в том, что программа берет не четность самого \(e_p(k)\), а четность числа единиц в двоичной записи \(e_p(k)\). Именно поэтому в коде используется битовая паритетная операция, а не простой тест на четность числа.
Следовательно, классы \(2,5,7 \pmod 8\) выбраны не эвристически. Это ровно те классы простых, которые реально входят в критерий equiproduct, лежащий в основе решения.
Для фиксированного простого \(p\) показатель \(p\) в \(k!\) задается формулой Лежандра:
\[ e_p(k)=\sum_{a\ge 1}\left\lfloor \frac{k}{p^a}\right\rfloor. \]
Считать эту формулу независимо для каждой пары \((p,k)\) было бы слишком дорого. Полезное наблюдение состоит в том, что \(e_p(k)\) меняется только тогда, когда \(k\) делится на \(p\). Если \(q\) кратно \(p\), то
\[ e_p(q)=e_p(q-1)+v_p(q), \]
а для некратных \(p\) значений просто выполняется \(e_p(k)=e_p(k-1)\).
Это позволяет обрабатывать каждый простой, проходя только по точкам
\[ p,2p,3p,\dots \]
и поддерживая текущее значение \(e_p(k)\). Повторные деления внутри цикла лишь извлекают \(v_p(q)\), когда \(q\) содержит более высокие степени \(p\).
Для каждого нужного простого введем бит
\[ B_p(k)=t(e_p(k)). \]
Глобальный индикатор equiproduct есть xor этих битов, то есть сумма по модулю 2. Вместо хранения полной таблицы всех \(B_p(k)\) решение хранит только моменты, когда вклад данного простого меняется:
\[ \Delta_p(k)=B_p(k)\oplus B_p(k-1). \]
Поскольку \(B_p(k)\) может измениться только на кратных \(p\), величина \(\Delta_p(k)\) разрежена. Общий массив `diff` накапливает
\[ \Delta(k)=\bigoplus_{p\in\mathcal P}\Delta_p(k). \]
После этого настоящий статус восстанавливается одним префиксным xor:
\[ I(k)=I(k-1)\oplus \Delta(k). \]
Это главный инвариант всей схемы. Решение никогда не пересчитывает критерий для данного \(k\) целиком; оно лишь отслеживает точки, где критерий меняет значение.
До \(7\) участвующие простые равны \(2,5,7\). Для \(k=6\) имеем
\[ v_2(6!)=4,\qquad v_5(6!)=1,\qquad v_7(6!)=0. \]
Соответствующие двоичные паритеты таковы:
\[ t(4)=s_2(4)\bmod 2=1,\qquad t(1)=1,\qquad t(0)=0. \]
Следовательно,
\[ I(6)=1+1+0\equiv 0 \pmod 2, \]
поэтому \(6!=720\) добавляется в ответ.
При переходе от \(6!\) к \(7!\) меняется только показатель простого \(7\): теперь \(v_7(7!)=1\), значит \(t(v_7(7!))=1\). Глобальное состояние переворачивается один раз:
\[ I(7)=I(6)\oplus 1=1. \]
Значит, \(7!\) уже не входит в сумму. Это полностью совпадает с малыми проверками: до \(7\) учитываются именно \(1!\), \(4!\) и \(6!\).
Пока префиксный xor восстанавливает \(I(k)\), реализация одновременно поддерживает
\[ F(k)\equiv k! \pmod{10^9+7} \]
по рекуррентной формуле
\[ F(k)=k\cdot F(k-1)\pmod{10^9+7}. \]
Как только \(I(k)=0\), текущее значение \(F(k)\) прибавляется к ответу. Ни один факториал не факторизуется отдельно, и никакой объект разбиения явно не строится.
Реализации на C++ и Java начинают со стандартного решета Эратосфена до \(n\). Простые, сравнимые с \(1\) или \(3\) по модулю \(8\), отбрасываются, потому что они не влияют на зашитый в решении критерий equiproduct. Для каждого оставшегося простого программа проходит по его кратным, обновляет накопленный показатель этого простого в текущем факториале, сравнивает старое и новое значение \(t(e)\) и xor'ит факт изменения в единый массив байтов.
Именно поэтому коду нужен только один текущий показатель на простой и один общий массив изменений. Полная таблица всех \(v_p(k!)\) для всех \(p\) и \(k\) нигде не строится.
После того как все простые события объединены в массиве изменений, хватает одного прохода слева направо. Реализация поддерживает текущий xor индикатора equiproduct и текущий факториал по модулю \(10^9+7\). Если индикатор равен нулю, текущий факториал добавляется к ответу.
Версии на C++ и Java выполняют эту арифметику напрямую. Предоставленный Python-вход является тонкой оболочкой над тем же скомпилированным вычислением, так что все три поставленные реализации используют один и тот же математический тест и одно и то же правило накопления.
Решето занимает \(O(n \log \log n)\). Основная работа по кратным имеет вид
\[ \sum_{p\in\mathcal P}\left\lfloor \frac{n}{p}\right\rfloor, \]
а дополнительные деления для выявления более высоких степеней простых дают вклад
\[ \sum_{p\le n}\sum_{a\ge 2}\left\lfloor \frac{n}{p^a}\right\rfloor. \]
Первая сумма есть \(O(n\log\log n)\), вторая равна \(O(n)\), так что вся предварительная обработка остается \(O(n\log\log n)\).
Заключительный проход с префиксным xor и обновлением факториала стоит \(O(n)\). Память равна \(O(n)\) и в основном расходуется на массив изменений и данные решета.
المطلوب في المسألة 937 هو جمع جميع القيم \(k!\) التي تحقق شرط equiproduct partition الوارد في نص المسألة، ثم أخذ الناتج بترديد \(10^9+7\). التطبيقات المعطاة لا تبحث عن هذه التقسيمات بصورة مباشرة. بدلًا من ذلك، تعتمد على توصيف يحول الشرط الخاص بـ \(k!\) إلى اختبار زوجية مبني على أسس العوامل الأولية في \(k!\).
إذن المهمة الحسابية الحقيقية هي: لكل \(1 \le k \le n\)، نقيّم هذا الاختبار العددي بسرعة، ونحافظ في الوقت نفسه على \(k! \bmod 10^9+7\)، ثم نضيف العاملية الحالية فقط عندما يكون معيار equiproduct محققًا.
الجزء التوافقي الأصعب في المسألة قد اختُزل في الشيفرة إلى معيار واحد من نظرية الأعداد. وما يبقى هو تقييم هذا المعيار لكل \(k\) بكفاءة، من غير إعادة تحليل كل عاملية إلى عواملها الأولية من الصفر.
لنعرّف مجموعة الأوليات
\[ \mathcal P=\{p \le n : p \equiv 2,5,7 \pmod 8\}. \]
ولكل أولي \(p\in\mathcal P\) نضع
\[ e_p(k)=v_p(k!), \]
حيث \(v_p\) هو التقييم \(p\)-adic المعتاد. ولتكن \(s_2(m)\) هي مجموع أرقام \(m\) في الكتابة الثنائية، ثم نعرّف
\[ t(m)=s_2(m)\bmod 2. \]
التطبيقات تستخدم عندئذٍ التوصيف
\[ I(k)=\sum_{p\in\mathcal P} t(e_p(k)) \pmod 2. \]
القيمة \(k!\) تدخل في المجموع إذا وفقط إذا كان \(I(k)=0\).
النقطة الدقيقة هنا أن الشيفرة لا تنظر إلى زوجية \(e_p(k)\) نفسه، بل إلى زوجية عدد الخانات التي تساوي 1 في التمثيل الثنائي لـ \(e_p(k)\). ولهذا السبب تحديدًا تستعمل الشيفرة عملية parity على البتات، لا مجرد اختبار فردي/زوجي عادي.
ولهذا أيضًا فإن الأصناف \(2,5,7 \pmod 8\) ليست اختيارًا تجريبيًا، بل هي بالضبط أصناف الأوليات التي تظهر في معيار equiproduct الذي يبنى عليه الحل.
لأولي ثابت \(p\)، فإن أس \(p\) في \(k!\) يعطى بصيغة ليجاندر:
\[ e_p(k)=\sum_{a\ge 1}\left\lfloor \frac{k}{p^a}\right\rfloor. \]
وحساب هذه الصيغة مستقلةً لكل زوج \((p,k)\) سيكون مكلفًا جدًا. الملاحظة المهمة هي أن \(e_p(k)\) لا يتغير إلا عندما يكون \(k\) من مضاعفات \(p\). فإذا كان \(q\) مضاعفًا لـ \(p\)، فإن
\[ e_p(q)=e_p(q-1)+v_p(q), \]
أما إذا لم يكن \(k\) مضاعفًا لـ \(p\)، فتبقى لدينا ببساطة العلاقة \(e_p(k)=e_p(k-1)\).
وهذا يعني أن معالجة كل أولي لا تحتاج إلا إلى المرور على
\[ p,2p,3p,\dots \]
مع الاحتفاظ بالقيمة الجارية لـ \(e_p(k)\). أما القسمة المتكررة داخل الشيفرة فليست إلا وسيلة لاستخراج \(v_p(q)\) عندما يحتوي \(q\) على قوى أعلى من \(p\).
لكل أولي مطلوب نعرّف البت
\[ B_p(k)=t(e_p(k)). \]
المؤشر العام لـ equiproduct هو xor هذه البتات، أو بصورة مكافئة مجموعها بترديد 2. وبدل تخزين الجدول الكامل لكل \(B_p(k)\)، تحتفظ الشيفرة فقط بالمواضع التي يتغير فيها تأثير أولي واحد:
\[ \Delta_p(k)=B_p(k)\oplus B_p(k-1). \]
وبما أن \(B_p(k)\) لا يمكن أن يتغير إلا عند مضاعفات \(p\)، فإن \(\Delta_p(k)\) متناثرة بطبيعتها. المصفوفة المشتركة `diff` تجمع
\[ \Delta(k)=\bigoplus_{p\in\mathcal P}\Delta_p(k). \]
وبعد بناء هذه المصفوفة، نستعيد الحالة الحقيقية بواسطة xor تراكمي واحد:
\[ I(k)=I(k-1)\oplus \Delta(k). \]
هذه هي الثابتة الأساسية في الطريقة كلها. الحل لا يعيد حساب المعيار كاملًا لكل \(k\)، بل يلاحق فقط المواضع التي ينقلب فيها هذا المعيار.
حتى \(7\)، الأوليات المؤثرة هي \(2,5,7\). عندما \(k=6\) نجد
\[ v_2(6!)=4,\qquad v_5(6!)=1,\qquad v_7(6!)=0. \]
ومن ثم تكون قيم parity الثنائية
\[ t(4)=s_2(4)\bmod 2=1,\qquad t(1)=1,\qquad t(0)=0. \]
إذًا
\[ I(6)=1+1+0\equiv 0 \pmod 2, \]
ولذلك تُضاف \(6!=720\) إلى الجواب.
عند الانتقال من \(6!\) إلى \(7!\) لا يتغير إلا أس الأولي \(7\): إذ يصبح \(v_7(7!)=1\)، وبالتالي \(t(v_7(7!))=1\). ومن ثم تنقلب الحالة العامة مرة واحدة:
\[ I(7)=I(6)\oplus 1=1. \]
وعليه فإن \(7!\) لا يساهم في الناتج. وهذا يطابق فحوصات القيم الصغيرة: حتى \(7\)، القيم التي تُحسب هي \(1!\) و\(4!\) و\(6!\).
بينما يعيد xor التراكمي بناء \(I(k)\)، تحافظ الشيفرة أيضًا على
\[ F(k)\equiv k! \pmod{10^9+7} \]
وفق العلاقة
\[ F(k)=k\cdot F(k-1)\pmod{10^9+7}. \]
وكلما كان \(I(k)=0\)، تُضاف القيمة الحالية \(F(k)\) إلى المجموع النهائي. لا تُفكك أي عاملية على حدة، ولا يُنشأ أي كائن partition بصورة صريحة.
تبدأ تطبيقا C++ وJava بغربال إراتوستينس قياسي حتى \(n\). ثم تُهمَل الأوليات الموافقة لـ \(1\) أو \(3\) بترديد \(8\)، لأنها لا تؤثر في معيار equiproduct الذي يشفره الحل. ولكل أولي متبقٍّ، تمر الشيفرة على مضاعفاته، وتحدّث الأس المتراكم لهذا الأولي داخل العاملية الحالية، وتقارن القيمة القديمة والجديدة لـ \(t(e)\)، ثم تدرج حدث الانقلاب الناتج في مصفوفة بايتات مشتركة بواسطة xor.
ولهذا لا تحتاج الشيفرة إلا إلى أس جارٍ واحد لكل أولي، وإلى مصفوفة فروق عامة. فهي لا تبني أبدًا الجدول الكامل لجميع القيم \(v_p(k!)\) لكل \(p\) ولكل \(k\).
بعد دمج جميع أحداث الأوليات في مصفوفة الفروق، يكفي مرور واحد من اليسار إلى اليمين. تحتفظ الشيفرة بـ xor جارٍ لمؤشر equiproduct، وبعاملية جارية بترديد \(10^9+7\). وعندما يكون المؤشر صفرًا، تُضاف العاملية الحالية إلى الجواب.
نسختا C++ وJava تنفذان هذه الحسابات مباشرة. أما نقطة الدخول في Python فهي غلاف خفيف فوق الحساب المترجم نفسه، ولذلك فإن المداخل الثلاثة المقدمة تعتمد جميعًا على الاختبار الرياضي نفسه وعلى قاعدة التجميع النهائية نفسها.
تكلفة الغربال هي \(O(n \log \log n)\). والعمل الرئيسي على المضاعفات يساوي
\[ \sum_{p\in\mathcal P}\left\lfloor \frac{n}{p}\right\rfloor, \]
أما القسمة الإضافية اللازمة لاكتشاف قوى الأوليات الأعلى فتساهم بالمقدار
\[ \sum_{p\le n}\sum_{a\ge 2}\left\lfloor \frac{n}{p^a}\right\rfloor. \]
المجموع الأول هو \(O(n\log\log n)\)، والثاني \(O(n)\)، ولذلك تبقى مرحلة التمهيد كلها \(O(n\log\log n)\).
المرور الأخير الذي يجمع بين xor التراكمي وتحديث العاملية هو \(O(n)\). واستخدام الذاكرة هو \(O(n)\)، وتسيطر عليه مصفوفة الفروق وبيانات الغربال.