For a positive integer \(n\), let \(H(n)\) be the number of sets of positive integers whose least common multiple is exactly \(n\). The problem then defines
$$L(n)=\operatorname{lcm}(1,2,\dots,n),\qquad HL(n)=H(L(n)),$$
and asks for \(HL(50000)\bmod 10^9\).
If a set has lcm \(N\), then every element of that set must divide \(N\). So the problem is really about counting subsets of the divisor set of \(N=L(50000)\) whose lcm is exactly \(N\). The challenge is that \(L(50000)\) has many prime factors and an enormous number of divisors, so direct enumeration is completely infeasible.
Write a general target number as
$$N=\prod_{i=1}^{k} p_i^{e_i},\qquad d_i=e_i+1.$$
Each divisor of \(N\) is determined by choosing, for every prime \(p_i\), an exponent from \(0\) to \(e_i\). Hence \(d_i\) is the number of choices contributed by the \(i\)-th prime.
Let \(\mathcal{D}(N)\) be the set of all positive divisors of \(N\). Any valid set is a subset of \(\mathcal{D}(N)\), and because we are counting sets rather than sequences, each divisor is either present or absent exactly once.
For the lcm of a chosen subset to equal \(N\), every prime power \(p_i^{e_i}\) must appear at full strength in at least one selected divisor. In other words, for each prime \(p_i\), at least one chosen divisor must use exponent \(e_i\) at that prime.
For each \(i\), let \(A_i\) be the bad event that no selected divisor reaches exponent \(e_i\) at prime \(p_i\). If a set avoids all bad events, then its lcm is exactly \(N\).
Now choose a subset \(S\subseteq\{1,\dots,k\}\) of primes that are forced to miss their top exponent. For \(i\in S\), a divisor may use only \(0,1,\dots,e_i-1\), so it has \(d_i-1\) choices. For \(i\notin S\), it still has all \(d_i\) choices. Therefore the number of divisors compatible with these restrictions is
$$M(S)=\prod_{i\in S}(d_i-1)\prod_{i\notin S}d_i.$$
Any subset of those \(M(S)\) divisors satisfies all restrictions in \(S\), so there are \(2^{M(S)}\) such subsets. Inclusion-exclusion gives
$$\boxed{H(N)=\sum_{S\subseteq\{1,\dots,k\}}(-1)^{|S|}2^{M(S)}.}$$
The empty subset is harmless here: it lies in every bad event, so inclusion-exclusion cancels it automatically.
For \(N=L(n)\), the exponent of a prime \(p\le n\) is
$$e_p=\max\{a\ge 0 : p^a\le n\},$$
so
$$d_p=e_p+1.$$
Many primes have the same \(d_p\). That matters because the formula above depends on a prime only through \(d_p\). Suppose one particular value \(d\) occurs for exactly \(c\) primes. If exactly \(i\) of those \(c\) primes belong to \(S\), then:
$$(-1)^i\binom{c}{i}$$
is the signed combinatorial coefficient, and
$$(d-1)^i d^{\,c-i}$$
is the factor contributed to \(M(S)\).
If the distinct \(d\)-values are \(d_1,\dots,d_t\) with multiplicities \(c_1,\dots,c_t\), then the subset sum collapses to
$$\boxed{HL(n)=\sum_{0\le i_j\le c_j}\left(\prod_{j=1}^{t}(-1)^{i_j}\binom{c_j}{i_j}\right)\,2^{\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}}.}$$
This is the key reduction: the naive formula has one binary decision per prime, while the grouped formula has only one integer choice per distinct \(d\)-value. Since \(d_p=e_p+1\) and \(e_p\le \lfloor \log_2 n\rfloor\), the number of groups is only \(O(\log n)\).
The exponent
$$E=\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}$$
is enormous, so the implementation never stores it exactly. Instead it only stores the information needed to evaluate \(2^E \bmod 10^9\).
Because
$$10^9=2^9\cdot 5^9,$$
we distinguish two cases. If \(E<9\), then \(2^E\) can be computed directly. If \(E\ge 9\), then the residue modulo \(2^9\) is already fixed, and modulo \(5^9\) the powers of \(2\) repeat with multiplicative order
$$\operatorname{ord}_{5^9}(2)=4\cdot 5^8=1{,}562{,}500.$$
Therefore, for \(E\ge 9\),
$$2^E \bmod 10^9 = 2^{\,9+((E-9)\bmod 1{,}562{,}500)} \bmod 10^9.$$
So each grouped contribution only needs two pieces of data: the exponent modulo \(1{,}562{,}500\), and a capped indicator telling whether the true exponent is still below \(9\).
We have
$$L(4)=\operatorname{lcm}(1,2,3,4)=12=2^2\cdot 3.$$
Hence the local choice counts are \(d=3\) for prime \(2\) and \(d=2\) for prime \(3\). There are four inclusion-exclusion cases:
$$\begin{aligned} S=\varnothing &:&& M=3\cdot 2=6,\\ S=\{2\} &:&& M=2\cdot 2=4,\\ S=\{3\} &:&& M=3\cdot 1=3,\\ S=\{2,3\} &:&& M=2\cdot 1=2. \end{aligned}$$
So
$$HL(4)=H(12)=2^6-2^4-2^3+2^2=64-16-8+4=44.$$
This is exactly the small checkpoint used by the implementation.
The C++, Python, and Java implementations all follow the grouped inclusion-exclusion formula above. They first sieve the primes up to \(n\), then compute \(e_p\) and \(d_p=e_p+1\) for each prime using repeated integer division, which avoids any floating-point issues.
Next, they count how many times each \(d\)-value occurs and build one choice table per group. For every possible value \(i=0,\dots,c\) in a group of size \(c\), the table stores the signed binomial coefficient, the corresponding exponent factor modulo \(1{,}562{,}500\), and the capped information needed to detect whether the true exponent is still below \(9\).
After that, the implementation combines all groups except the largest into aggregate states. Each aggregate state represents many original subsets, but it keeps only the data required for the final modular evaluation. The last accumulation step pairs those aggregate states with the choices from the largest group and converts the stored exponent information into the correct value of \(2^E \bmod 10^9\).
The C++ implementation parallelizes that outer accumulation over several threads. The Python implementation performs the same arithmetic serially. The Java implementation acts as a thin wrapper around the same compiled computation, so all three language versions are numerically consistent.
Let the distinct grouped values be \(d_1,\dots,d_t\) with multiplicities \(c_1,\dots,c_t\). A naive inclusion-exclusion over primes would require \(2^{\pi(n)}\) cases, which is hopeless for \(n=50000\). The grouped method reduces that to roughly
$$\prod_{j=1}^{t}(c_j+1)$$
combined choices, plus sieve and preprocessing work.
The prime sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. Building the per-group binomial data costs \(O\!\left(\sum_j c_j^2\right)\) time. The final state-combination phase is proportional to the grouped state count above, with extra practical speedup in the multithreaded C++ version. Memory usage is \(O(n)\) for the sieve plus the stored grouped states.
Für eine positive ganze Zahl \(n\) bezeichne \(H(n)\) die Anzahl der Mengen positiver ganzer Zahlen, deren kleinstes gemeinsames Vielfaches genau \(n\) ist. Außerdem gilt
$$L(n)=\operatorname{lcm}(1,2,\dots,n),\qquad HL(n)=H(L(n)),$$
und gesucht ist \(HL(50000)\bmod 10^9\).
Hat eine Menge das kgV \(N\), dann muss jedes ihrer Elemente ein Teiler von \(N\) sein. Damit zählt die Aufgabe in Wirklichkeit Teilmengen der Teilermenge von \(N=L(50000)\), deren kgV genau \(N\) ist. Direkte Enumeration scheidet aus, weil \(L(50000)\) sehr viele Primfaktoren und extrem viele Teiler besitzt.
Schreibe allgemein
$$N=\prod_{i=1}^{k} p_i^{e_i},\qquad d_i=e_i+1.$$
Jeder Teiler von \(N\) entsteht durch die Wahl eines Exponenten zwischen \(0\) und \(e_i\) für jede Primzahl \(p_i\). Also gibt der Wert \(d_i\) die lokale Anzahl dieser Möglichkeiten an.
Sei \(\mathcal{D}(N)\) die Menge aller positiven Teiler von \(N\). Jede gültige Menge ist eine Teilmenge von \(\mathcal{D}(N)\), und weil Mengen keine Wiederholungen enthalten, ist jeder Teiler entweder enthalten oder nicht.
Damit das kgV der gewählten Teilmenge gleich \(N\) ist, muss jede Primzahlpotenz \(p_i^{e_i}\) irgendwo mit ihrem maximalen Exponenten auftreten. Für jedes \(p_i\) muss also mindestens ein gewählter Teiler den Exponenten \(e_i\) an dieser Primzahl besitzen.
Für jedes \(i\) sei \(A_i\) das schlechte Ereignis, dass kein gewählter Teiler den Exponenten \(e_i\) bei \(p_i\) erreicht. Eine Menge hat genau dann kgV \(N\), wenn sie keines dieser Ereignisse erfüllt.
Wähle nun eine Teilmenge \(S\subseteq\{1,\dots,k\}\) von Primindizes, bei denen der höchste Exponent verboten ist. Für \(i\in S\) sind nur \(0,1,\dots,e_i-1\) erlaubt, also \(d_i-1\) Möglichkeiten. Für \(i\notin S\) bleiben alle \(d_i\) Möglichkeiten erhalten. Damit ist die Zahl der unter diesen Restriktionen zulässigen Teiler
$$M(S)=\prod_{i\in S}(d_i-1)\prod_{i\notin S}d_i.$$
Aus diesen \(M(S)\) Teilern kann jede Teilmenge gewählt werden, also gibt es \(2^{M(S)}\) passende Mengen. Mit Inklusion-Exklusion folgt
$$\boxed{H(N)=\sum_{S\subseteq\{1,\dots,k\}}(-1)^{|S|}2^{M(S)}.}$$
Die leere Menge stört dabei nicht: Sie liegt in jedem schlechten Ereignis und hebt sich in der Formel automatisch weg.
Für \(N=L(n)\) ist der Exponent einer Primzahl \(p\le n\)
$$e_p=\max\{a\ge 0 : p^a\le n\},$$
also
$$d_p=e_p+1.$$
Viele Primzahlen besitzen denselben \(d_p\)-Wert. Das ist entscheidend, weil die Formel eine Primzahl nur über \(d_p\) sieht. Kommt ein bestimmter Wert \(d\) genau \(c\)-mal vor und liegen davon genau \(i\) Primzahlen in \(S\), dann ist
$$(-1)^i\binom{c}{i}$$
der signierte kombinatorische Faktor und
$$(d-1)^i d^{\,c-i}$$
der Beitrag zu \(M(S)\).
Bezeichnet man die verschiedenen \(d\)-Werte mit \(d_1,\dots,d_t\) und ihre Häufigkeiten mit \(c_1,\dots,c_t\), so reduziert sich die Summe zu
$$\boxed{HL(n)=\sum_{0\le i_j\le c_j}\left(\prod_{j=1}^{t}(-1)^{i_j}\binom{c_j}{i_j}\right)\,2^{\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}}.}$$
Das ist die zentrale Vereinfachung: Statt einer binären Entscheidung pro Primzahl gibt es nur noch eine ganzzahlige Wahl pro verschiedenem \(d\)-Wert. Da \(e_p\le \lfloor \log_2 n\rfloor\), ist die Anzahl dieser Gruppen nur \(O(\log n)\).
Der Exponent
$$E=\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}$$
ist astronomisch groß. Die Implementierung speichert ihn deshalb nie vollständig, sondern nur die Information, die für \(2^E \bmod 10^9\) nötig ist.
Wegen
$$10^9=2^9\cdot 5^9$$
unterscheidet man zwei Fälle. Für \(E<9\) kann \(2^E\) direkt berechnet werden. Für \(E\ge 9\) ist der Rest modulo \(2^9\) bereits festgelegt, und modulo \(5^9\) wiederholen sich die Potenzen von \(2\) mit der Ordnung
$$\operatorname{ord}_{5^9}(2)=4\cdot 5^8=1{,}562{,}500.$$
Daher gilt für \(E\ge 9\)
$$2^E \bmod 10^9 = 2^{\,9+((E-9)\bmod 1{,}562{,}500)} \bmod 10^9.$$
Jeder gruppierte Beitrag braucht also nur zwei Daten: den Exponenten modulo \(1{,}562{,}500\) und eine gekappte Information darüber, ob der echte Exponent noch kleiner als \(9\) ist.
Es gilt
$$L(4)=\operatorname{lcm}(1,2,3,4)=12=2^2\cdot 3.$$
Damit sind die lokalen Wahlzahlen \(d=3\) für die Primzahl \(2\) und \(d=2\) für die Primzahl \(3\). Es gibt vier Inklusion-Exklusion-Fälle:
$$\begin{aligned} S=\varnothing &:&& M=3\cdot 2=6,\\ S=\{2\} &:&& M=2\cdot 2=4,\\ S=\{3\} &:&& M=3\cdot 1=3,\\ S=\{2,3\} &:&& M=2\cdot 1=2. \end{aligned}$$
Also
$$HL(4)=H(12)=2^6-2^4-2^3+2^2=64-16-8+4=44.$$
Genau dieser Wert dient als kleiner Kontrollpunkt in der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen alle exakt der gruppierten Inklusion-Exklusion-Formel. Zuerst werden alle Primzahlen bis \(n\) gesiebt. Danach werden \(e_p\) und \(d_p=e_p+1\) per wiederholter Ganzzahldivision bestimmt, ohne Fließkomma zu verwenden.
Anschließend wird gezählt, wie oft jeder \(d\)-Wert vorkommt, und für jede Gruppe wird eine Tabelle aller Möglichkeiten \(i=0,\dots,c\) aufgebaut. Für jede dieser Möglichkeiten speichert die Implementierung den vorzeichenbehafteten Binomialkoeffizienten, den zugehörigen Exponentenfaktor modulo \(1{,}562{,}500\) und die gekappte Information, ob der echte Exponent noch unter \(9\) liegt.
Danach werden alle Gruppen außer der größten zu aggregierten Zuständen zusammengefasst. Jeder solche Zustand repräsentiert viele ursprüngliche Teilmengen, enthält aber nur die Daten, die für die Endauswertung nötig sind. Im letzten Schritt werden diese Zustände mit den Wahlmöglichkeiten der größten Gruppe kombiniert und in den korrekten Wert von \(2^E \bmod 10^9\) übersetzt.
Die C++-Version parallelisiert diese äußere Summation über mehrere Threads. Die Python-Version führt dieselbe Arithmetik seriell aus. Die Java-Version ist eine dünne Hülle um dieselbe kompilierte Rechnung, sodass alle drei Sprachfassungen numerisch übereinstimmen.
Seien \(d_1,\dots,d_t\) die verschiedenen Gruppenwerte mit Häufigkeiten \(c_1,\dots,c_t\). Eine naive Inklusion-Exklusion über alle Primzahlen würde \(2^{\pi(n)}\) Fälle benötigen und ist damit unbrauchbar. Die gruppierte Methode reduziert das auf ungefähr
$$\prod_{j=1}^{t}(c_j+1)$$
kombinierte Fälle, zusätzlich zu Sieb- und Vorberechnungsarbeit.
Das Primzahlsieb kostet \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Der Aufbau der gruppenweisen Binomialdaten kostet \(O\!\left(\sum_j c_j^2\right)\) Zeit. Die Endphase ist proportional zur Zahl der gruppierten Zustände; in der multithreaded C++-Version kommt dort noch ein praktischer Parallelisierungsvorteil hinzu. Der Gesamtspeicher besteht aus \(O(n)\) für das Sieb plus dem Platz für die gespeicherten Gruppenzustände.
Pozitif bir \(n\) için \(H(n)\), EKOK'u tam olarak \(n\) olan pozitif tamsayı kümelerinin sayısı olsun. Problem ayrıca
$$L(n)=\operatorname{lcm}(1,2,\dots,n),\qquad HL(n)=H(L(n)),$$
tanımını veriyor ve \(HL(50000)\bmod 10^9\) değerini istiyor.
Bir kümenin EKOK'u \(N\) ise, o kümedeki her sayı \(N\)'yi bölmek zorundadır. Dolayısıyla mesele, \(N=L(50000)\) sayısının bölenleri arasından seçilen alt kümelerden EKOK'u tam olarak \(N\) olanları saymaktır. Ancak \(L(50000)\) çok fazla asal çarpan ve çok büyük sayıda bölen içerdiği için doğrudan sayma mümkün değildir.
Genel olarak
$$N=\prod_{i=1}^{k} p_i^{e_i},\qquad d_i=e_i+1$$
yazalım. \(N\)'nin her böleni, her asal \(p_i\) için \(0\) ile \(e_i\) arasında bir üs seçilerek belirlenir. Bu yüzden \(d_i\), o asalın sağladığı yerel seçenek sayısıdır.
\(\mathcal{D}(N)\), \(N\)'nin tüm pozitif bölenlerinin kümesi olsun. Geçerli her aday küme, \(\mathcal{D}(N)\)'nin bir alt kümesidir. Ayrıca burada dizi değil küme saydığımız için her bölen ya seçilir ya seçilmez; tekrar yoktur.
Seçilen alt kümenin EKOK'unun \(N\) olabilmesi için her asal kuvvet \(p_i^{e_i}\) en az bir seçilen bölen içinde tam kuvvetiyle görünmelidir. Yani her \(p_i\) için, seçilen bölenlerden en az biri bu asalda üssü tam olarak \(e_i\) yapmalıdır.
Her \(i\) için \(A_i\) kötü olayı, seçilen hiçbir bölenin \(p_i\) asalında üs \(e_i\)'ye ulaşmaması olsun. Bir alt kümenin EKOK'u ancak ve ancak bu kötü olayların hiçbirine düşmüyorsa \(N\) olur.
Şimdi \(S\subseteq\{1,\dots,k\}\) şeklinde bir asal indeks kümesi seçelim ve bu asalarda en büyük üssü yasaklayalım. \(i\in S\) için izin verilen üsler yalnızca \(0,1,\dots,e_i-1\) olduğundan \(d_i-1\) seçenek vardır. \(i\notin S\) için ise tüm \(d_i\) seçenekleri kalır. Dolayısıyla bu kısıtlarla uyumlu bölen sayısı
$$M(S)=\prod_{i\in S}(d_i-1)\prod_{i\notin S}d_i$$
olur. Bu \(M(S)\) bölen arasından her alt küme seçilebileceği için toplam sayı \(2^{M(S)}\)'dir. Böylece dahil etme-çıkarma ile
$$\boxed{H(N)=\sum_{S\subseteq\{1,\dots,k\}}(-1)^{|S|}2^{M(S)}.}$$
Boş küme burada sorun yaratmaz; tüm kötü olayların içinde yer aldığı için formülde otomatik olarak birbirini götürür.
\(N=L(n)\) olduğunda, \(p\le n\) asalı için üs
$$e_p=\max\{a\ge 0 : p^a\le n\}$$
ve dolayısıyla
$$d_p=e_p+1$$
olur. Birçok asal için \(d_p\) aynı değeri alır. Bu çok önemlidir, çünkü yukarıdaki formül bir asalı yalnızca \(d_p\) üzerinden görür. Belirli bir \(d\) değeri tam \(c\) kez ortaya çıkıyorsa ve bu grubun içinden tam \(i\) asal \(S\)'ye giriyorsa, katkı
$$(-1)^i\binom{c}{i}$$
çarpanı ve
$$(d-1)^i d^{\,c-i}$$
üs faktörü ile ifade edilir.
Farklı \(d\) değerleri \(d_1,\dots,d_t\), bunların çoklukları da \(c_1,\dots,c_t\) ise formül
$$\boxed{HL(n)=\sum_{0\le i_j\le c_j}\left(\prod_{j=1}^{t}(-1)^{i_j}\binom{c_j}{i_j}\right)\,2^{\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}}.}$$
şeklinde küçülür. Asıl kazanç budur: asal başına bir ikili seçim yapmak yerine, her farklı \(d\) değeri için yalnızca bir tamsayı seçimi yapılır. \(e_p\le \lfloor \log_2 n\rfloor\) olduğundan grup sayısı yalnızca \(O(\log n)\) mertebesindedir.
Üs
$$E=\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}$$
son derece büyüktür. Bu yüzden uygulama \(E\)'yi tam olarak saklamaz; sadece \(2^E \bmod 10^9\) hesabı için gerekli bilgiyi tutar.
Çünkü
$$10^9=2^9\cdot 5^9,$$
iki durum vardır. \(E<9\) ise \(2^E\) doğrudan hesaplanır. \(E\ge 9\) ise mod \(2^9\) kısmı zaten sabittir ve mod \(5^9\) altında \(2\)'nin kuvvetleri
$$\operatorname{ord}_{5^9}(2)=4\cdot 5^8=1{,}562{,}500$$
periyodu ile tekrar eder. Dolayısıyla \(E\ge 9\) için
$$2^E \bmod 10^9 = 2^{\,9+((E-9)\bmod 1{,}562{,}500)} \bmod 10^9$$
yeterlidir. Bu nedenle her grup katkısı için yalnızca iki bilgi saklanır: üssün \(1{,}562{,}500\) modundaki değeri ve gerçek üssün henüz \(9\)'un altında olup olmadığını belirten sınırlı bir gösterge.
Şu değeri alırız:
$$L(4)=\operatorname{lcm}(1,2,3,4)=12=2^2\cdot 3.$$
Dolayısıyla asal \(2\) için \(d=3\), asal \(3\) için \(d=2\) vardır. Dört dahil etme-çıkarma durumu şunlardır:
$$\begin{aligned} S=\varnothing &:&& M=3\cdot 2=6,\\ S=\{2\} &:&& M=2\cdot 2=4,\\ S=\{3\} &:&& M=3\cdot 1=3,\\ S=\{2,3\} &:&& M=2\cdot 1=2. \end{aligned}$$
Böylece
$$HL(4)=H(12)=2^6-2^4-2^3+2^2=64-16-8+4=44.$$
Bu, uygulamanın kullandığı küçük doğrulama değerlerinden biridir.
C++, Python ve Java uygulamalarının üçü de yukarıdaki gruplanmış dahil etme-çıkarma formülünü uygular. İlk olarak \(n\)'ye kadar olan asallar elenir. Sonra her asal için \(e_p\) ve \(d_p=e_p+1\), kayan nokta kullanmadan tekrar eden tam sayı bölmeleriyle hesaplanır.
Bundan sonra her \(d\) değerinin kaç kez görüldüğü sayılır ve her grup için bir seçim tablosu oluşturulur. Boyutu \(c\) olan bir grup için \(i=0,\dots,c\) seçeneklerinin her birinde işaretli binom katsayısı, \(1{,}562{,}500\) modunda üs katkısı ve gerçek üssün \(9\)'dan küçük kalıp kalmadığını belirleyen sınırlı bilgi saklanır.
Daha sonra en büyük grup dışındaki tüm gruplar birleştirilmiş durumlar halinde toplanır. Bu durumlar, çok sayıda orijinal alt kümeyi temsil eder ama yalnızca son modüler hesap için gereken veriyi taşır. Son aşamada bu durumlar en büyük grubun seçenekleriyle eşleştirilir ve saklanan bilgi doğru \(2^E \bmod 10^9\) değerine dönüştürülür.
C++ sürümü bu dış toplamayı birden fazla iş parçacığına böler. Python sürümü aynı hesabı seri olarak yapar. Java sürümü ise aynı derlenmiş sayısal yolu ince bir katmanla çağırdığı için üç dil sürümü de aynı sonucu verir.
Farklı grup değerleri \(d_1,\dots,d_t\) ve çoklukları \(c_1,\dots,c_t\) olsun. Asallara göre doğrudan dahil etme-çıkarma yapmak \(2^{\pi(n)}\) durum gerektirir ve \(n=50000\) için imkansızdır. Gruplanmış yöntem bunu yaklaşık
$$\prod_{j=1}^{t}(c_j+1)$$
adet birleşik seçime indirir; buna ek olarak eleme ve ön işleme maliyeti vardır.
Asal eleği \(O(n\log\log n)\) zaman ve \(O(n)\) bellek ister. Grup bazlı binom verilerini kurmak \(O\!\left(\sum_j c_j^2\right)\) zaman alır. Son durum birleştirme evresi yukarıdaki grup durum sayısıyla orantılıdır; çok iş parçacıklı C++ sürümünde burada ek pratik hızlanma görülür. Toplam bellek kullanımı, eleme için \(O(n)\) ve grup durumlarının saklanması için ek alandan oluşur.
Para un entero positivo \(n\), sea \(H(n)\) el número de conjuntos de enteros positivos cuyo mínimo común múltiplo es exactamente \(n\). El problema además define
$$L(n)=\operatorname{lcm}(1,2,\dots,n),\qquad HL(n)=H(L(n)),$$
y pide calcular \(HL(50000)\bmod 10^9\).
Si un conjunto tiene mcm igual a \(N\), entonces todos sus elementos deben ser divisores de \(N\). Por tanto, el problema consiste en contar subconjuntos del conjunto de divisores de \(N=L(50000)\) cuyo mcm sea exactamente \(N\). La enumeración directa es imposible porque \(L(50000)\) tiene muchos factores primos y una cantidad gigantesca de divisores.
Escribamos en general
$$N=\prod_{i=1}^{k} p_i^{e_i},\qquad d_i=e_i+1.$$
Cada divisor de \(N\) queda determinado por elegir, para cada primo \(p_i\), un exponente entre \(0\) y \(e_i\). Por eso \(d_i\) es el número de opciones locales aportadas por el primo \(p_i\).
Sea \(\mathcal{D}(N)\) el conjunto de todos los divisores positivos de \(N\). Todo conjunto válido es un subconjunto de \(\mathcal{D}(N)\), y como estamos contando conjuntos y no secuencias, cada divisor aparece a lo sumo una vez.
Para que el mcm del subconjunto elegido sea \(N\), cada potencia prima \(p_i^{e_i}\) debe aparecer con su exponente máximo en al menos un divisor seleccionado. Es decir, para cada \(p_i\), al menos un divisor elegido debe usar el exponente \(e_i\) en ese primo.
Para cada \(i\), definamos \(A_i\) como el mal evento de que ningún divisor escogido alcance el exponente \(e_i\) en el primo \(p_i\). Un subconjunto tiene mcm exactamente \(N\) si y solo si evita todos esos eventos.
Ahora tomemos un subconjunto \(S\subseteq\{1,\dots,k\}\) de índices primos en los que se prohíbe el exponente máximo. Para \(i\in S\), solo se permiten \(0,1,\dots,e_i-1\), es decir, \(d_i-1\) opciones. Para \(i\notin S\), siguen disponibles las \(d_i\) opciones. Por tanto, el número de divisores compatibles con esas restricciones es
$$M(S)=\prod_{i\in S}(d_i-1)\prod_{i\notin S}d_i.$$
Cualquier subconjunto de esos \(M(S)\) divisores cumple las restricciones, así que hay \(2^{M(S)}\) posibilidades. Por inclusión-exclusión obtenemos
$$\boxed{H(N)=\sum_{S\subseteq\{1,\dots,k\}}(-1)^{|S|}2^{M(S)}.}$$
El subconjunto vacío no causa ningún problema: pertenece a todos los eventos malos y queda cancelado automáticamente por la fórmula.
Para \(N=L(n)\), el exponente del primo \(p\le n\) es
$$e_p=\max\{a\ge 0 : p^a\le n\},$$
de modo que
$$d_p=e_p+1.$$
Muchos primos comparten el mismo valor \(d_p\). Eso es crucial porque la fórmula solo depende de cada primo a través de \(d_p\). Si un valor \(d\) aparece exactamente \(c\) veces y exactamente \(i\) de esos \(c\) primos están dentro de \(S\), entonces el aporte del grupo es
$$(-1)^i\binom{c}{i}$$
como coeficiente con signo, y
$$(d-1)^i d^{\,c-i}$$
como factor dentro de \(M(S)\).
Si los valores distintos son \(d_1,\dots,d_t\) con multiplicidades \(c_1,\dots,c_t\), la suma se reduce a
$$\boxed{HL(n)=\sum_{0\le i_j\le c_j}\left(\prod_{j=1}^{t}(-1)^{i_j}\binom{c_j}{i_j}\right)\,2^{\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}}.}$$
Ésta es la reducción decisiva: en vez de una decisión binaria por primo, solo queda una elección entera por cada valor distinto de \(d\). Como \(e_p\le \lfloor \log_2 n\rfloor\), el número de grupos es apenas \(O(\log n)\).
El exponente
$$E=\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}$$
es gigantesco, por lo que la implementación no lo almacena exactamente. Solo conserva la información necesaria para evaluar \(2^E \bmod 10^9\).
Como
$$10^9=2^9\cdot 5^9,$$
hay dos regímenes. Si \(E<9\), se calcula \(2^E\) directamente. Si \(E\ge 9\), el residuo módulo \(2^9\) ya queda fijado, y módulo \(5^9\) las potencias de \(2\) repiten con orden multiplicativo
$$\operatorname{ord}_{5^9}(2)=4\cdot 5^8=1{,}562{,}500.$$
Por tanto, para \(E\ge 9\),
$$2^E \bmod 10^9 = 2^{\,9+((E-9)\bmod 1{,}562{,}500)} \bmod 10^9.$$
Así, cada contribución agrupada solo necesita dos datos: el exponente módulo \(1{,}562{,}500\) y una marca acotada que indique si el exponente real todavía es menor que \(9\).
Tenemos
$$L(4)=\operatorname{lcm}(1,2,3,4)=12=2^2\cdot 3.$$
Por tanto, los valores locales son \(d=3\) para el primo \(2\) y \(d=2\) para el primo \(3\). Hay cuatro casos de inclusión-exclusión:
$$\begin{aligned} S=\varnothing &:&& M=3\cdot 2=6,\\ S=\{2\} &:&& M=2\cdot 2=4,\\ S=\{3\} &:&& M=3\cdot 1=3,\\ S=\{2,3\} &:&& M=2\cdot 1=2. \end{aligned}$$
Entonces
$$HL(4)=H(12)=2^6-2^4-2^3+2^2=64-16-8+4=44.$$
Ese valor coincide con la comprobación pequeña usada por la implementación.
Las implementaciones en C++, Python y Java siguen exactamente la fórmula agrupada de inclusión-exclusión. Primero generan los primos hasta \(n\). Después calculan \(e_p\) y \(d_p=e_p+1\) mediante divisiones enteras repetidas, evitando cualquier dependencia de logaritmos en coma flotante.
Luego cuentan cuántas veces aparece cada valor \(d\) y construyen una tabla de elecciones para cada grupo. Para cada posible \(i=0,\dots,c\) en un grupo de tamaño \(c\), la tabla guarda el coeficiente binomial con signo, el factor del exponente módulo \(1{,}562{,}500\) y la información acotada que indica si el exponente real todavía está por debajo de \(9\).
Después, la implementación combina todos los grupos salvo el mayor en estados agregados. Cada estado resume muchísimos subconjuntos originales, pero retiene solo la información necesaria para la evaluación modular final. El último paso combina esos estados con las opciones del grupo más grande y transforma los datos almacenados en el valor correcto de \(2^E \bmod 10^9\).
La versión en C++ paraleliza esa suma exterior entre varios hilos. La versión en Python realiza la misma aritmética en serie. La versión en Java actúa como una envoltura ligera sobre el mismo cálculo compilado, de modo que las tres versiones son coherentes numéricamente.
Sean \(d_1,\dots,d_t\) los valores agrupados distintos con multiplicidades \(c_1,\dots,c_t\). Una inclusión-exclusión ingenua sobre todos los primos requeriría \(2^{\pi(n)}\) casos, lo cual es inviable para \(n=50000\). El método agrupado reduce esto a aproximadamente
$$\prod_{j=1}^{t}(c_j+1)$$
elecciones combinadas, además del trabajo de cribado y preprocesamiento.
La criba de primos cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. Construir los datos binomiales por grupo cuesta \(O\!\left(\sum_j c_j^2\right)\) tiempo. La fase final de combinación es proporcional al número de estados agrupados anterior, con una mejora práctica adicional en la versión multihilo de C++. La memoria total es \(O(n)\) para la criba más el almacenamiento de los estados agrupados.
对任意正整数 \(n\)，记 \(H(n)\) 为“最小公倍数恰好等于 \(n\)”的正整数集合个数。题目进一步定义
$$L(n)=\operatorname{lcm}(1,2,\dots,n),\qquad HL(n)=H(L(n)),$$
要求计算 \(HL(50000)\bmod 10^9\)。
如果某个集合的最小公倍数是 \(N\)，那么这个集合中的每个元素都必须整除 \(N\)。因此，本题本质上是在 \(N=L(50000)\) 的全部正因子中取子集，并统计那些最小公倍数恰好为 \(N\) 的子集个数。由于 \(L(50000)\) 的素因子很多、因子总数又极其庞大，直接枚举不可能实现。
先把一般情形写成
$$N=\prod_{i=1}^{k} p_i^{e_i},\qquad d_i=e_i+1.$$
\(N\) 的每个因子都由一组指数选择决定：对每个素数 \(p_i\)，指数可以从 \(0\) 到 \(e_i\) 之间取值。所以 \(d_i\) 就是该素数在局部上提供的选择数。
记 \(\mathcal{D}(N)\) 为 \(N\) 的全部正因子集合。任何合法答案都只是 \(\mathcal{D}(N)\) 的一个子集。因为题目统计的是“集合”而不是“序列”，所以每个因子只有“选”或“不选”两种状态，不存在重复选择。
要让所选子集的最小公倍数等于 \(N\)，就必须保证每个素数幂 \(p_i^{e_i}\) 都在某个被选因子中以最大指数出现。换句话说，对于每个素数 \(p_i\)，至少要有一个被选因子在该素数上的指数正好是 \(e_i\)。
对每个 \(i\)，定义坏事件 \(A_i\)：所选集合中没有任何因子在素数 \(p_i\) 上达到指数 \(e_i\)。当且仅当所有坏事件都没有发生时，所选集合的最小公倍数才会是 \(N\)。
现在取一个素数下标集合 \(S\subseteq\{1,\dots,k\}\)，表示这些素数不允许出现最大指数。若 \(i\in S\)，则指数只能取 \(0,1,\dots,e_i-1\)，共有 \(d_i-1\) 种选择；若 \(i\notin S\)，则仍有完整的 \(d_i\) 种选择。因此，满足这组限制的因子总数为
$$M(S)=\prod_{i\in S}(d_i-1)\prod_{i\notin S}d_i.$$
在这 \(M(S)\) 个允许因子中，每个因子都可以独立地选或不选，因此符合这些限制的子集数是 \(2^{M(S)}\)。应用容斥原理可得
$$\boxed{H(N)=\sum_{S\subseteq\{1,\dots,k\}}(-1)^{|S|}2^{M(S)}.}$$
空集并不会带来额外麻烦，因为它属于所有坏事件，在容斥求和中会自动被抵消掉。
当 \(N=L(n)\) 时，对每个素数 \(p\le n\)，其指数为
$$e_p=\max\{a\ge 0 : p^a\le n\},$$
因此
$$d_p=e_p+1.$$
很多素数会得到相同的 \(d_p\) 值。这一点非常重要，因为上面的公式只通过 \(d_p\) 区分素数。如果某个固定的 \(d\) 一共出现 \(c\) 次，而其中恰有 \(i\) 个素数被放入限制集合 \(S\)，那么这一组带来的贡献就是
$$(-1)^i\binom{c}{i}$$
这个带符号的组合系数，以及
$$(d-1)^i d^{\,c-i}$$
这个乘进 \(M(S)\) 的指数因子。
若不同的 \(d\) 值为 \(d_1,\dots,d_t\)，对应出现次数为 \(c_1,\dots,c_t\)，则整个求和可以缩并为
$$\boxed{HL(n)=\sum_{0\le i_j\le c_j}\left(\prod_{j=1}^{t}(-1)^{i_j}\binom{c_j}{i_j}\right)\,2^{\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}}.}$$
这就是核心简化。朴素容斥需要对每个素数做一次二元选择，而合并之后，只需要对每一种不同的 \(d\) 值做一次整数选择。由于 \(e_p\le \lfloor \log_2 n\rfloor\)，所以组数仅为 \(O(\log n)\) 级别。
指数
$$E=\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}$$
会大到无法直接保存，因此实现并不真正构造 \(E\)，而只保留足以求出 \(2^E \bmod 10^9\) 的信息。
因为
$$10^9=2^9\cdot 5^9,$$
所以要分两种情况讨论。若 \(E<9\)，则可以直接计算 \(2^E\)。若 \(E\ge 9\)，那么模 \(2^9\) 的部分已经固定，而模 \(5^9\) 时，\(2\) 的幂按照乘法阶
$$\operatorname{ord}_{5^9}(2)=4\cdot 5^8=1{,}562{,}500$$
循环。因此当 \(E\ge 9\) 时，有
$$2^E \bmod 10^9 = 2^{\,9+((E-9)\bmod 1{,}562{,}500)} \bmod 10^9.$$
这意味着每个分组贡献只需要维护两项信息：\(E\) 对 \(1{,}562{,}500\) 取模后的值，以及“真实指数是否仍小于 \(9\)”这一截断状态。
先算
$$L(4)=\operatorname{lcm}(1,2,3,4)=12=2^2\cdot 3.$$
于是，对素数 \(2\) 有 \(d=3\)，对素数 \(3\) 有 \(d=2\)。容斥一共有四种情况：
$$\begin{aligned} S=\varnothing &:&& M=3\cdot 2=6,\\ S=\{2\} &:&& M=2\cdot 2=4,\\ S=\{3\} &:&& M=3\cdot 1=3,\\ S=\{2,3\} &:&& M=2\cdot 1=2. \end{aligned}$$
因此
$$HL(4)=H(12)=2^6-2^4-2^3+2^2=64-16-8+4=44.$$
这个值正是实现中使用的小型校验结果之一。
C++、Python 和 Java 三种实现都遵循上面的分组容斥公式。第一步是筛出所有不超过 \(n\) 的素数。随后通过反复整数除法求出每个素数在 \(L(n)\) 中的指数 \(e_p\)，再得到 \(d_p=e_p+1\)，整个过程不依赖浮点对数。
接着，程序统计每个 \(d\) 值出现了多少次，并为每一组预先建立选择表。对于大小为 \(c\) 的一组，表中会列出 \(i=0,\dots,c\) 的全部可能，同时存储带符号的二项式系数、对应的指数因子在模 \(1{,}562{,}500\) 下的值，以及判断真实指数是否仍低于 \(9\) 的截断信息。
然后，程序把最大组之外的所有组先合并成若干聚合状态。每个聚合状态实际上代表大量原始子集，但它只保留最终模运算所需要的数据。最后一步再把这些聚合状态与最大组的所有选择逐一配对，并把存下来的指数信息还原成正确的 \(2^E \bmod 10^9\)。
C++ 版本会把最后这层外循环分配到多个线程上并行计算。Python 版本做的是同一套串行算术。Java 版本则作为一个很薄的外层包装，调用同一条编译后的数值计算路径，因此三种语言版本在数值上保持一致。
设不同的分组值为 \(d_1,\dots,d_t\)，对应重数为 \(c_1,\dots,c_t\)。如果对所有素数直接做朴素容斥，那么需要处理 \(2^{\pi(n)}\) 种情况，对 \(n=50000\) 来说完全不可行。分组后的方法把规模压缩到大约
$$\prod_{j=1}^{t}(c_j+1)$$
个组合状态，再加上筛法和预处理成本。
素数筛需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 内存。按组构造二项式数据需要 \(O\!\left(\sum_j c_j^2\right)\) 时间。最终状态合并阶段与上述分组状态总数成正比，而多线程的 C++ 版本还能在这一阶段获得额外的实际加速。总内存由筛法所需的 \(O(n)\) 与分组状态存储共同构成。
Для положительного целого \(n\) обозначим через \(H(n)\) количество множеств положительных целых чисел, у которых наименьшее общее кратное равно ровно \(n\). Далее вводится
$$L(n)=\operatorname{lcm}(1,2,\dots,n),\qquad HL(n)=H(L(n)),$$
и требуется найти \(HL(50000)\bmod 10^9\).
Если у множества НОК равен \(N\), то каждый его элемент обязан делить \(N\). Значит, задача сводится к подсчету подмножеств множества делителей числа \(N=L(50000)\), у которых НОК равен точно \(N\). Прямой перебор невозможен, потому что у \(L(50000)\) очень много простых множителей и чрезвычайно много делителей.
Рассмотрим общее число вида
$$N=\prod_{i=1}^{k} p_i^{e_i},\qquad d_i=e_i+1.$$
Каждый делитель \(N\) задается выбором показателя от \(0\) до \(e_i\) для каждого простого \(p_i\). Поэтому \(d_i\) есть число локальных вариантов, приходящихся на \(i\)-й простой множитель.
Обозначим через \(\mathcal{D}(N)\) множество всех положительных делителей \(N\). Любой допустимый ответ является подмножеством \(\mathcal{D}(N)\). Поскольку считаются именно множества, а не последовательности, каждый делитель либо выбран, либо нет.
Чтобы НОК выбранного подмножества был равен \(N\), каждая простая степень \(p_i^{e_i}\) должна где-то встретиться с максимальным показателем. То есть для каждого \(p_i\) должен существовать хотя бы один выбранный делитель, в котором показатель при этом простом равен \(e_i\).
Для каждого \(i\) введем плохое событие \(A_i\): ни один выбранный делитель не достигает показателя \(e_i\) у простого \(p_i\). Подмножество имеет НОК ровно \(N\) тогда и только тогда, когда оно избегает всех таких событий.
Теперь выберем множество индексов \(S\subseteq\{1,\dots,k\}\), для которых максимальный показатель запрещен. Если \(i\in S\), то разрешены только показатели \(0,1,\dots,e_i-1\), то есть \(d_i-1\) вариантов. Если \(i\notin S\), то остаются все \(d_i\) вариантов. Поэтому число делителей, удовлетворяющих этим ограничениям, равно
$$M(S)=\prod_{i\in S}(d_i-1)\prod_{i\notin S}d_i.$$
Любое подмножество этих \(M(S)\) делителей подходит под ограничения, значит таких подмножеств \(2^{M(S)}\). По принципу включений-исключений получаем
$$\boxed{H(N)=\sum_{S\subseteq\{1,\dots,k\}}(-1)^{|S|}2^{M(S)}.}$$
Пустое множество здесь не мешает: оно лежит во всех плохих событиях и автоматически сокращается в формуле.
Для \(N=L(n)\) показатель простого \(p\le n\) равен
$$e_p=\max\{a\ge 0 : p^a\le n\},$$
следовательно,
$$d_p=e_p+1.$$
Многие простые числа имеют одинаковое значение \(d_p\). Это важно, потому что формула зависит от простого только через \(d_p\). Если некоторое значение \(d\) встречается ровно \(c\) раз и ровно \(i\) из этих \(c\) простых попадают в \(S\), то вклад группы равен
$$(-1)^i\binom{c}{i}$$
как знаковый комбинаторный коэффициент и
$$(d-1)^i d^{\,c-i}$$
как множитель внутри \(M(S)\).
Если различные значения \(d\) обозначены как \(d_1,\dots,d_t\) с кратностями \(c_1,\dots,c_t\), то вся сумма сжимается до
$$\boxed{HL(n)=\sum_{0\le i_j\le c_j}\left(\prod_{j=1}^{t}(-1)^{i_j}\binom{c_j}{i_j}\right)\,2^{\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}}.}$$
Именно здесь происходит главное ускорение: вместо одного бинарного выбора на каждый простой множитель остается по одному целочисленному выбору на каждое различное значение \(d\). Так как \(e_p\le \lfloor \log_2 n\rfloor\), число групп равно лишь \(O(\log n)\).
Показатель
$$E=\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}$$
настолько велик, что хранить его целиком бессмысленно. Реализация хранит только ту информацию, которая нужна для вычисления \(2^E \bmod 10^9\).
Поскольку
$$10^9=2^9\cdot 5^9,$$
разбираются два случая. Если \(E<9\), то \(2^E\) можно вычислить напрямую. Если \(E\ge 9\), то остаток по модулю \(2^9\) уже фиксирован, а по модулю \(5^9\) степени двойки повторяются с мультипликативным порядком
$$\operatorname{ord}_{5^9}(2)=4\cdot 5^8=1{,}562{,}500.$$
Значит, при \(E\ge 9\)
$$2^E \bmod 10^9 = 2^{\,9+((E-9)\bmod 1{,}562{,}500)} \bmod 10^9.$$
Поэтому для каждого группового вклада достаточно хранить две величины: показатель по модулю \(1{,}562{,}500\) и усеченную информацию о том, не меньше ли реальный показатель числа \(9\).
Имеем
$$L(4)=\operatorname{lcm}(1,2,3,4)=12=2^2\cdot 3.$$
Следовательно, локальные значения равны \(d=3\) для простого \(2\) и \(d=2\) для простого \(3\). Получаем четыре случая включений-исключений:
$$\begin{aligned} S=\varnothing &:&& M=3\cdot 2=6,\\ S=\{2\} &:&& M=2\cdot 2=4,\\ S=\{3\} &:&& M=3\cdot 1=3,\\ S=\{2,3\} &:&& M=2\cdot 1=2. \end{aligned}$$
Поэтому
$$HL(4)=H(12)=2^6-2^4-2^3+2^2=64-16-8+4=44.$$
Именно это значение используется как маленькая проверка корректности.
Реализации на C++, Python и Java все следуют приведенной выше сгруппированной формуле включений-исключений. Сначала они просеивают простые числа до \(n\). Затем для каждого простого вычисляют \(e_p\) и \(d_p=e_p+1\) с помощью повторяющегося целочисленного деления, полностью обходясь без вещественных логарифмов.
После этого подсчитывается, сколько раз встречается каждое значение \(d\), и для каждой группы строится таблица всех вариантов \(i=0,\dots,c\). Для каждого такого варианта сохраняются знаковый биномиальный коэффициент, вклад в показатель по модулю \(1{,}562{,}500\) и усеченная информация о том, остается ли истинный показатель меньше \(9\).
Далее все группы, кроме самой крупной, объединяются в агрегированные состояния. Каждое такое состояние описывает множество исходных подмножеств, но хранит только данные, нужные для финальной модульной оценки. На последнем шаге эти состояния комбинируются с вариантами из крупнейшей группы и преобразуются в правильное значение \(2^E \bmod 10^9\).
Версия на C++ распараллеливает эту внешнюю сумму между несколькими потоками. Версия на Python выполняет те же вычисления последовательно. Версия на Java служит тонкой оболочкой над тем же скомпилированным вычислением, поэтому все три языковые версии совпадают численно.
Пусть различные групповые значения равны \(d_1,\dots,d_t\), а их кратности равны \(c_1,\dots,c_t\). Наивные включения-исключения по всем простым числам потребовали бы \(2^{\pi(n)}\) случаев, что для \(n=50000\) совершенно нереально. Группировка уменьшает это примерно до
$$\prod_{j=1}^{t}(c_j+1)$$
совмещенных вариантов, плюс стоимость решета и предвычислений.
Решето простых стоит \(O(n\log\log n)\) по времени и \(O(n)\) по памяти. Построение биномиальных данных по группам требует \(O\!\left(\sum_j c_j^2\right)\) времени. Финальная фаза объединения пропорциональна числу сгруппированных состояний, а многопоточная версия на C++ дает здесь дополнительное практическое ускорение. Полная память состоит из \(O(n)\) для решета и хранения сгруппированных состояний.
لأي عدد صحيح موجب \(n\)، لتكن \(H(n)\) هي عدد المجموعات من الأعداد الصحيحة الموجبة التي يكون المضاعف المشترك الأصغر لها مساويًا تمامًا لـ \(n\). ثم تعرّف المسألة
$$L(n)=\operatorname{lcm}(1,2,\dots,n),\qquad HL(n)=H(L(n)),$$
والمطلوب هو حساب \(HL(50000)\bmod 10^9\).
إذا كان المضاعف المشترك الأصغر لمجموعة ما يساوي \(N\)، فلا بد أن يكون كل عنصر فيها قاسمًا لـ \(N\). لذلك تتحول المسألة فعليًا إلى عدّ المجموعات الجزئية من مجموعة قواسم \(N=L(50000)\) التي يكون المضاعف المشترك الأصغر لها مساويًا تمامًا لـ \(N\). والعد المباشر مستحيل عمليًا لأن \(L(50000)\) يملك عددًا كبيرًا من العوامل الأولية وعددًا هائلًا من القواسم.
لنكتب الحالة العامة على الصورة
$$N=\prod_{i=1}^{k} p_i^{e_i},\qquad d_i=e_i+1.$$
كل قاسم لـ \(N\) يتحدد باختيار أس من \(0\) إلى \(e_i\) لكل أولي \(p_i\). ومن ثم فإن \(d_i\) هو عدد الاختيارات المحلية التي يوفّرها ذلك الأولي.
لتكن \(\mathcal{D}(N)\) مجموعة جميع القواسم الموجبة لـ \(N\). كل جواب صالح هو مجموعة جزئية من \(\mathcal{D}(N)\). وبما أننا نعد مجموعات لا متتاليات، فكل قاسم إما أن يُختار أو لا يُختار، ولا توجد تكرارات.
لكي يكون المضاعف المشترك الأصغر للمجموعة المختارة مساويًا لـ \(N\)، يجب أن تظهر كل قوة أولية \(p_i^{e_i}\) بكامل أسها في واحد على الأقل من القواسم المختارة. أي أنه لكل أولي \(p_i\) لا بد من وجود قاسم مختار يصل فيه الأس إلى \(e_i\).
لكل \(i\)، عرّف الحدث السيئ \(A_i\) بأنه لا يوجد أي قاسم مختار يصل إلى الأس \(e_i\) عند الأولي \(p_i\). تكون المجموعة ذات مضاعف مشترك أصغر يساوي \(N\) إذا وفقط إذا تجنبت جميع هذه الأحداث السيئة.
الآن خذ مجموعة فهارس \(S\subseteq\{1,\dots,k\}\) من الأوليات التي نمنع عندها ظهور الأس الأعظمي. إذا كان \(i\in S\)، فالمسموح فقط هو \(0,1,\dots,e_i-1\)، أي \(d_i-1\) اختيارًا. وإذا كان \(i\notin S\)، تبقى جميع \(d_i\) اختيارات ممكنة. إذن عدد القواسم الموافقة لهذه القيود هو
$$M(S)=\prod_{i\in S}(d_i-1)\prod_{i\notin S}d_i.$$
وأي مجموعة جزئية من هذه القواسم \(M(S)\) تحقق القيود، لذا يوجد \(2^{M(S)}\) مجموعة ممكنة. ومن مبدأ الإدراج والإقصاء نحصل على
$$\boxed{H(N)=\sum_{S\subseteq\{1,\dots,k\}}(-1)^{|S|}2^{M(S)}.}$$
المجموعة الفارغة لا تسبب مشكلة هنا، لأنها تقع داخل كل حدث سيئ، ولذلك تُلغى تلقائيًا داخل مجموع الإدراج والإقصاء.
عندما يكون \(N=L(n)\)، فإن أس الأولي \(p\le n\) يساوي
$$e_p=\max\{a\ge 0 : p^a\le n\},$$
ومن ثم
$$d_p=e_p+1.$$
عدد كبير من الأوليات يعطي القيمة نفسها لـ \(d_p\). وهذه ملاحظة حاسمة لأن الصيغة السابقة لا ترى الأولي إلا من خلال \(d_p\). إذا ظهرت قيمة معينة \(d\) عدد \(c\) مرات، وكان من بينها بالضبط \(i\) أوليات داخلة في \(S\)، فإن مساهمة هذه المجموعة هي
$$(-1)^i\binom{c}{i}$$
كمعامل إشاري، و
$$(d-1)^i d^{\,c-i}$$
كعامل داخل \(M(S)\).
إذا كانت القيم المختلفة هي \(d_1,\dots,d_t\) وتكراراتها هي \(c_1,\dots,c_t\)، فإن المجموع ينضغط إلى
$$\boxed{HL(n)=\sum_{0\le i_j\le c_j}\left(\prod_{j=1}^{t}(-1)^{i_j}\binom{c_j}{i_j}\right)\,2^{\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}}.}$$
وهذا هو الاختزال الأساسي: بدلًا من قرار ثنائي مستقل لكل أولي، يبقى لدينا اختيار عددي واحد لكل قيمة مختلفة من \(d\). وبما أن \(e_p\le \lfloor \log_2 n\rfloor\)، فإن عدد المجموعات لا يتجاوز رتبة \(O(\log n)\).
الأس
$$E=\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}$$
كبير جدًا إلى درجة أن التنفيذ لا يحفظه كاملًا. بل يحتفظ فقط بالمعلومات اللازمة لحساب \(2^E \bmod 10^9\).
بما أن
$$10^9=2^9\cdot 5^9,$$
فهناك حالتان. إذا كان \(E<9\)، يمكن حساب \(2^E\) مباشرة. وإذا كان \(E\ge 9\)، فإن الباقي modulo \(2^9\) يصبح ثابتًا بالفعل، أما modulo \(5^9\) فإن قوى \(2\) تتكرر وفق الرتبة الضربية
$$\operatorname{ord}_{5^9}(2)=4\cdot 5^8=1{,}562{,}500.$$
ولذلك عندما \(E\ge 9\) يكون
$$2^E \bmod 10^9 = 2^{\,9+((E-9)\bmod 1{,}562{,}500)} \bmod 10^9.$$
إذن كل مساهمة مجمعة تحتاج فقط إلى قيمتين: الأس modulo \(1{,}562{,}500\)، ومؤشرًا مقيدًا يحدد هل الأس الحقيقي ما يزال أقل من \(9\) أم لا.
لدينا
$$L(4)=\operatorname{lcm}(1,2,3,4)=12=2^2\cdot 3.$$
إذًا تكون القيم المحلية \(d=3\) للأولي \(2\) و\(d=2\) للأولي \(3\). توجد أربع حالات في الإدراج والإقصاء:
$$\begin{aligned} S=\varnothing &:&& M=3\cdot 2=6,\\ S=\{2\} &:&& M=2\cdot 2=4,\\ S=\{3\} &:&& M=3\cdot 1=3,\\ S=\{2,3\} &:&& M=2\cdot 1=2. \end{aligned}$$
وعليه
$$HL(4)=H(12)=2^6-2^4-2^3+2^2=64-16-8+4=44.$$
وهذه القيمة هي نفسها نقطة الفحص الصغيرة التي تستخدمها عملية التنفيذ.
تتبع تطبيقات C++ وPython وJava جميعها صيغة الإدراج والإقصاء المجمعة المذكورة أعلاه. تبدأ العملية بتوليد جميع الأوليات حتى \(n\). بعد ذلك يُحسب \(e_p\) و\(d_p=e_p+1\) لكل أولي عبر قسمة صحيحة متكررة، من دون الاعتماد على اللوغاريتمات العائمة.
ثم يُحصى عدد مرات ظهور كل قيمة \(d\)، وتُبنى لكل مجموعة جدول اختيارات. في المجموعة ذات الحجم \(c\)، يسجل الجدول جميع الحالات \(i=0,\dots,c\)، ويخزن لكل حالة المعامل الثنائي مع الإشارة، وعامل الأس modulo \(1{,}562{,}500\)، والمعلومة المقيدة التي تخبرنا هل الأس الحقيقي لا يزال أقل من \(9\).
بعد ذلك تُدمج كل المجموعات ما عدا الأكبر في حالات مجمعة. كل حالة مجمعة تمثل عددًا كبيرًا من المجموعات الأصلية، لكنها تحتفظ فقط بما نحتاجه في التقييم المعياري النهائي. وفي الخطوة الأخيرة تُقرن هذه الحالات مع اختيارات المجموعة الأكبر، ثم تُحوَّل البيانات المخزنة إلى القيمة الصحيحة لـ \(2^E \bmod 10^9\).
نسخة C++ توازي هذه المرحلة الخارجية على عدة خيوط. نسخة Python تنفذ الحساب نفسه بصورة تسلسلية. أما نسخة Java فهي غلاف خفيف فوق المسار العددي المترجم نفسه، ولذلك تتطابق النسخ الثلاث عدديًا.
إذا كانت القيم المجمعة المختلفة هي \(d_1,\dots,d_t\) وتكراراتها \(c_1,\dots,c_t\)، فإن الإدراج والإقصاء الساذج على جميع الأوليات يحتاج إلى \(2^{\pi(n)}\) حالة، وهو أمر غير عملي تمامًا عند \(n=50000\). أما الطريقة المجمعة فتخفض ذلك إلى نحو
$$\prod_{j=1}^{t}(c_j+1)$$
اختيارًا مركبًا، إضافة إلى تكلفة الغربال والتهيئة.
غربال الأوليات يكلف \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة. وبناء البيانات الثنائية على مستوى المجموعات يكلف \(O\!\left(\sum_j c_j^2\right)\) زمنًا. أما مرحلة دمج الحالات النهائية فتتناسب مع عدد الحالات المجمعة السابق، مع تسارع عملي إضافي في نسخة C++ متعددة الخيوط. ويكون الاستهلاك الكلي للذاكرة هو \(O(n)\) للغربال إضافة إلى تخزين الحالات المجمعة.