For every subset \(S\subseteq\{1,\dots,N\}\), including the empty set, we take its least common multiple and sum all those values:
$$G(N)=\sum_{S\subseteq\{1,\dots,N\}}\operatorname{lcm}(S),\qquad \operatorname{lcm}(\varnothing)=1.$$
The goal is to evaluate \(G(800)\bmod(10^9+7)\). Since there are \(2^{800}\) subsets, the solution cannot enumerate subsets directly. Instead it groups subsets by their exact LCM and rewrites the problem as a weighted sum over divisors.
Let
$$L_N=\operatorname{lcm}(1,2,\dots,N)=\prod_{p\le N}p^{M_p},\qquad M_p=\left\lfloor\log_p N\right\rfloor.$$
Every subset LCM is a divisor of \(L_N\), so the whole problem lives on the divisor lattice of \(L_N\).
For a divisor \(d\mid L_N\), define
$$A(d)=\#\{m\in\{1,\dots,N\}:m\mid d\}.$$
These are exactly the numbers that may appear in a subset whose LCM divides \(d\). Therefore, if
$$F(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)\mid d\},$$
then every subset of those \(A(d)\) admissible numbers is valid, so
$$F(d)=2^{A(d)}.$$
This converts subset enumeration into divisor counting.
Let
$$T(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)=d\}.$$
Since “the LCM divides \(d\)” means the exact LCM is some divisor of \(d\), we have
$$F(d)=\sum_{c\mid d}T(c).$$
Möbius inversion on divisors gives
$$T(d)=\sum_{r\mid d}\mu(r)\,F\left(\frac{d}{r}\right).$$
Now substitute this into
$$G(N)=\sum_{d\mid L_N} d\,T(d).$$
After reindexing the sum, we obtain
$$G(N)=\sum_{d\mid L_N} W(d)\,2^{A(d)},$$
where the weight is
$$W(d)=d\sum_{r\mid L_N/d} r\,\mu(r).$$
The Möbius function is zero on non-squarefree numbers, so only the choices \(r=1\) and \(r=p\) matter for each prime that is still missing from \(d\) at full exponent. Hence
$$W(d)=d\prod_{p\mid L_N/d}(1-p).$$
If \(v_p(d)=e\), the local factor is therefore
$$w_p(e)=\begin{cases} p^e(1-p), & e<M_p,\\ p^{M_p}, & e=M_p. \end{cases}$$
So the global weight factors multiplicatively as
$$W(d)=\prod_{p\le N} w_p\bigl(v_p(d)\bigr).$$
This is the mathematical reason the implementation multiplies by the prime power \(p^e\) and appends the factor \((1-p)\) whenever the exponent is not maximal.
Write any divisor \(d\mid L_N\) as
$$d=a\,b,$$
where \(a\) uses only primes \(q\le\sqrt N\) and \(b\) uses only primes \(p>\sqrt N\).
For a large prime \(p>\sqrt N\), we have \(p^2>N\), so its exponent in \(L_N\) is only \(1\). Thus the large-prime part \(b\) is squarefree.
Define
$$B_a(M)=\#\{n\le M:n\mid a,\ \text{and every prime factor of }n\text{ is }\le\sqrt N\}.$$
Any number \(m\le N\) dividing \(d\) contains either no large prime or exactly one large prime. It cannot contain two distinct large primes, because their product would exceed \(N\). Therefore
$$A(a b)=B_a(N)+\sum_{p\mid b} B_a\left(\left\lfloor\frac{N}{p}\right\rfloor\right).$$
This identity is the key simplification used by all three implementations.
Fix the small-prime part \(a\). Then
$$2^{A(a b)}=2^{B_a(N)}\prod_{p\mid b}2^{B_a(\lfloor N/p\rfloor)}.$$
Combining this with the local weight factors shows that the sum over every possible large-prime subset factorizes independently:
$$\sum_{b} W(a b)\,2^{A(a b)} = W_{\mathrm{small}}(a)\,2^{B_a(N)} \prod_{p>\sqrt N}\left((1-p)+p\,2^{B_a(\lfloor N/p\rfloor)}\right),$$
where \(W_{\mathrm{small}}(a)\) is the product of the local weights coming from the small primes only.
Many large primes share the same quotient
$$M=\left\lfloor\frac{N}{p}\right\rfloor.$$
Grouping primes by this common value lets the implementation precompute one product table per group.
If the small primes are \(q_1,\dots,q_k\), then \(a\) is determined by its exponent vector
$$\bigl(e_1,\dots,e_k\bigr),\qquad 0\le e_i\le M_{q_i}.$$
The number of states is
$$\prod_{i=1}^k (M_{q_i}+1).$$
For each needed limit \(M\), the implementation enumerates all small-only integers \(n\le M\), records their exact exponent vectors, and applies multidimensional prefix sums. After this transform, each state stores \(B_a(M)\): the number of small-only divisors of the corresponding \(a\) that do not exceed \(M\).
Once these tables are built, every state can be evaluated independently and all contributions are accumulated modulo \(10^9+7\).
Here
$$L_5=\operatorname{lcm}(1,2,3,4,5)=60=2^2\cdot 3\cdot 5.$$
The only small prime is \(2\), so the small-prime states are \(a\in\{1,2,4\}\). The large primes are \(3\) and \(5\), and both satisfy
$$\left\lfloor\frac{5}{3}\right\rfloor=\left\lfloor\frac{5}{5}\right\rfloor=1.$$
The small-only divisor counts are
$$B_1(5)=1,\qquad B_2(5)=2,\qquad B_4(5)=3,$$
because the admissible small-only divisors up to \(5\) are respectively \(\{1\}\), \(\{1,2\}\), and \(\{1,2,4\}\). Also
$$B_1(1)=B_2(1)=B_4(1)=1.$$
The small-prime weights are
$$W_{\mathrm{small}}(1)=1\cdot(1-2)=-1,\qquad W_{\mathrm{small}}(2)=2\cdot(1-2)=-2,\qquad W_{\mathrm{small}}(4)=4.$$
The common large-prime factor is
$$\bigl((1-3)+3\cdot 2^1\bigr)\bigl((1-5)+5\cdot 2^1\bigr)=4\cdot 6=24.$$
So the three state contributions are
$$\begin{aligned} a=1&:&&-1\cdot 2^{1}\cdot 24=-48,\\ a=2&:&&-2\cdot 2^{2}\cdot 24=-192,\\ a=4&:&&4\cdot 2^{3}\cdot 24=768. \end{aligned}$$
Adding them gives
$$-48-192+768=528,$$
which matches the known checkpoint for \(G(5)\).
The C++, Python, and Java implementations follow the same pipeline. They first generate all primes up to \(N\) and split them at \(\lfloor\sqrt N\rfloor\). For each small prime they record the maximum exponent occurring in \(L_N\), which determines the mixed-radix state space.
Next, they enumerate every small-only integer up to \(N\), attach it to its exponent state, and sort those values. For each needed limit \(M\in\{N\}\cup\{\lfloor N/p\rfloor:p>\sqrt N\}\), they mark the eligible small-only integers, run a multidimensional prefix accumulation, and obtain the table \(B_a(M)\) for every small state \(a\).
They also precompute the powers \(2^t\bmod(10^9+7)\) for \(0\le t\le N\), together with one table for each group of large primes sharing the same quotient \(\lfloor N/p\rfloor\). Finally, they iterate over all small-prime states, reconstruct the corresponding small weight, read the precomputed divisor counts, multiply the grouped large-prime factors, and accumulate the answer modulo \(10^9+7\).
Let
$$S=\prod_{q\le\sqrt N}(M_q+1)$$
be the number of small-prime states, and let \(K\) be the number of distinct values of \(\lfloor N/p\rfloor\) among primes \(p>\sqrt N\). Prime generation costs \(O(N\log\log N)\). After that, the main preprocessing and evaluation steps are near \(O(S\cdot K)\), with only a small multiplicative factor from the number of small primes and the prefix transforms. Memory usage is \(O(S\cdot K)\) for the stored count tables and grouped large-prime tables. For \(N=800\), these sizes remain comfortably manageable.
Für jede Teilmenge \(S\subseteq\{1,\dots,N\}\), einschließlich der leeren Menge, wird das kleinste gemeinsame Vielfache gebildet und alles aufsummiert:
$$G(N)=\sum_{S\subseteq\{1,\dots,N\}}\operatorname{lcm}(S),\qquad \operatorname{lcm}(\varnothing)=1.$$
Gesucht ist \(G(800)\bmod(10^9+7)\). Da es \(2^{800}\) Teilmengen gibt, ist direkte Enumeration ausgeschlossen. Die Lösung gruppiert daher nach dem exakten kgV und formt das Problem in eine gewichtete Summe über Teiler um.
Setze
$$L_N=\operatorname{lcm}(1,2,\dots,N)=\prod_{p\le N}p^{M_p},\qquad M_p=\left\lfloor\log_p N\right\rfloor.$$
Jedes Teilmengen-kgV ist ein Teiler von \(L_N\). Damit spielt sich das ganze Problem auf dem Teilerverband von \(L_N\) ab.
Für einen Teiler \(d\mid L_N\) definieren wir
$$A(d)=\#\{m\in\{1,\dots,N\}:m\mid d\}.$$
Genau diese Zahlen dürfen in einer Teilmenge vorkommen, deren kgV \(d\) teilt. Definieren wir also
$$F(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)\mid d\},$$
dann ist jede Teilmenge dieser \(A(d)\) zulässigen Zahlen erlaubt, also
$$F(d)=2^{A(d)}.$$
So wird aus dem Teilmengenproblem ein Teilerzählproblem.
Sei
$$T(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)=d\}.$$
Weil „kgV teilt \(d\)“ genau bedeutet, dass das exakte kgV ein Teiler von \(d\) ist, gilt
$$F(d)=\sum_{c\mid d}T(c).$$
Mit Möbius-Inversion auf Teilern folgt
$$T(d)=\sum_{r\mid d}\mu(r)\,F\left(\frac{d}{r}\right).$$
Setzt man dies in
$$G(N)=\sum_{d\mid L_N} d\,T(d)$$
ein und ordnet um, erhält man
$$G(N)=\sum_{d\mid L_N} W(d)\,2^{A(d)},$$
wobei
$$W(d)=d\sum_{r\mid L_N/d} r\,\mu(r)$$
das zugehörige Gewicht ist.
Die Möbius-Funktion verschwindet auf nicht quadratfreien Zahlen. Deshalb tragen für jede fehlende Primzahl nur die Möglichkeiten \(r=1\) und \(r=p\) bei. Daraus folgt
$$W(d)=d\prod_{p\mid L_N/d}(1-p).$$
Ist \(v_p(d)=e\), dann lautet der lokale Faktor
$$w_p(e)=\begin{cases} p^e(1-p), & e<M_p,\\ p^{M_p}, & e=M_p. \end{cases}$$
Somit faktorisiert das Gesamtgewicht zu
$$W(d)=\prod_{p\le N} w_p\bigl(v_p(d)\bigr).$$
Genau deshalb multipliziert die Implementierung die Primzahlpotenz \(p^e\) ein und hängt zusätzlich \((1-p)\) an, solange der Exponent noch nicht maximal ist.
Schreibe jeden Teiler \(d\mid L_N\) als
$$d=a\,b,$$
wobei \(a\) nur Primzahlen \(q\le\sqrt N\) enthält und \(b\) nur Primzahlen \(p>\sqrt N\).
Für eine große Primzahl \(p>\sqrt N\) gilt \(p^2>N\). Daher ist ihr Exponent in \(L_N\) nur \(1\), und der große Primzahlteil \(b\) ist quadratfrei.
Definiere
$$B_a(M)=\#\{n\le M:n\mid a,\ \text{und alle Primfaktoren von }n\text{ sind }\le\sqrt N\}.$$
Eine Zahl \(m\le N\), die \(d\) teilt, enthält entweder keine große Primzahl oder genau eine. Zwei verschiedene große Primzahlen wären unmöglich, weil ihr Produkt bereits größer als \(N\) wäre. Deshalb gilt
$$A(a b)=B_a(N)+\sum_{p\mid b} B_a\left(\left\lfloor\frac{N}{p}\right\rfloor\right).$$
Das ist die zentrale strukturelle Vereinfachung der Methode.
Fixiere nun den kleinen Primzahlteil \(a\). Dann ist
$$2^{A(a b)}=2^{B_a(N)}\prod_{p\mid b}2^{B_a(\lfloor N/p\rfloor)}.$$
Zusammen mit den lokalen Gewichten faktorisiert die Summe über alle möglichen großen Primzahlteile:
$$\sum_{b} W(a b)\,2^{A(a b)} = W_{\mathrm{small}}(a)\,2^{B_a(N)} \prod_{p>\sqrt N}\left((1-p)+p\,2^{B_a(\lfloor N/p\rfloor)}\right),$$
wobei \(W_{\mathrm{small}}(a)\) das Produkt der lokalen Gewichte der kleinen Primzahlen bezeichnet.
Viele große Primzahlen haben denselben Quotienten
$$M=\left\lfloor\frac{N}{p}\right\rfloor.$$
Darum gruppiert die Implementierung sie nach diesem Wert und berechnet pro Gruppe eine gemeinsame Produkttabelle.
Sind die kleinen Primzahlen \(q_1,\dots,q_k\), dann ist \(a\) durch seinen Exponentenvektor bestimmt:
$$\bigl(e_1,\dots,e_k\bigr),\qquad 0\le e_i\le M_{q_i}.$$
Die Anzahl der Zustände ist
$$\prod_{i=1}^k (M_{q_i}+1).$$
Für jedes benötigte Limit \(M\) enumeriert die Implementierung alle nur aus kleinen Primzahlen aufgebauten Zahlen \(n\le M\), markiert ihren exakten Exponentenvektor und führt dann mehrdimensionale Präfixsummen aus. Danach enthält jeder Zustand den Wert \(B_a(M)\): also die Anzahl kleiner Teiler des zugehörigen \(a\), die höchstens \(M\) sind.
Sobald diese Tabellen vorliegen, kann jeder Zustand unabhängig ausgewertet und alles modulo \(10^9+7\) aufsummiert werden.
Hier ist
$$L_5=\operatorname{lcm}(1,2,3,4,5)=60=2^2\cdot 3\cdot 5.$$
Die einzige kleine Primzahl ist \(2\), also sind die Zustände \(a\in\{1,2,4\}\). Die großen Primzahlen sind \(3\) und \(5\), und beide erfüllen
$$\left\lfloor\frac{5}{3}\right\rfloor=\left\lfloor\frac{5}{5}\right\rfloor=1.$$
Die kleinen Teileranzahlen sind
$$B_1(5)=1,\qquad B_2(5)=2,\qquad B_4(5)=3,$$
denn die zulässigen kleinen Teiler bis \(5\) sind jeweils \(\{1\}\), \(\{1,2\}\) und \(\{1,2,4\}\). Außerdem gilt
$$B_1(1)=B_2(1)=B_4(1)=1.$$
Die Gewichte des kleinen Primzahlteils lauten
$$W_{\mathrm{small}}(1)=1\cdot(1-2)=-1,\qquad W_{\mathrm{small}}(2)=2\cdot(1-2)=-2,\qquad W_{\mathrm{small}}(4)=4.$$
Der gemeinsame Großprimfaktor ist
$$\bigl((1-3)+3\cdot 2^1\bigr)\bigl((1-5)+5\cdot 2^1\bigr)=4\cdot 6=24.$$
Damit ergeben sich die drei Zustandsbeiträge
$$\begin{aligned} a=1&:&&-1\cdot 2^{1}\cdot 24=-48,\\ a=2&:&&-2\cdot 2^{2}\cdot 24=-192,\\ a=4&:&&4\cdot 2^{3}\cdot 24=768. \end{aligned}$$
Die Summe ist also
$$-48-192+768=528,$$
genau der bekannte Kontrollwert für \(G(5)\).
Die C++-, Python- und Java-Implementierungen folgen alle derselben Pipeline. Zuerst erzeugen sie alle Primzahlen bis \(N\) und teilen sie bei \(\lfloor\sqrt N\rfloor\) in kleine und große Primzahlen. Für jede kleine Primzahl wird der maximale Exponent in \(L_N\) bestimmt; daraus entsteht der Mixed-Radix-Zustandsraum.
Danach werden alle nur aus kleinen Primzahlen zusammengesetzten Zahlen bis \(N\) enumeriert, ihrem Exponenten-Zustand zugeordnet und nach Größe sortiert. Für jedes benötigte Limit \(M\in\{N\}\cup\{\lfloor N/p\rfloor:p>\sqrt N\}\) markieren die Implementierungen die zulässigen kleinen Zahlen, führen eine mehrdimensionale Präfixakkumulation aus und erhalten so die Tabelle \(B_a(M)\) für jeden kleinen Zustand \(a\).
Zusätzlich werden die Potenzen \(2^t\bmod(10^9+7)\) für \(0\le t\le N\) sowie eine Produkttabelle für jede Gruppe großer Primzahlen mit gleichem Quotienten \(\lfloor N/p\rfloor\) vorab berechnet. Anschließend laufen die Implementierungen über alle kleinen Zustände, rekonstruieren das zugehörige Gewicht, lesen die vorberechneten Zählwerte aus, multiplizieren die gruppierten Großprimfaktoren und summieren alles modulo \(10^9+7\) auf.
Sei
$$S=\prod_{q\le\sqrt N}(M_q+1)$$
die Anzahl der Zustände kleiner Primzahlen und \(K\) die Anzahl verschiedener Werte von \(\lfloor N/p\rfloor\) für Primzahlen \(p>\sqrt N\). Das Primzahl-Sieb kostet \(O(N\log\log N)\). Danach liegen Vorverarbeitung und Auswertung größenordnungsmäßig nahe bei \(O(S\cdot K)\); hinzu kommt nur ein kleiner Faktor durch die Anzahl kleiner Primzahlen und die Präfixtransformationen. Der Speicherbedarf beträgt \(O(S\cdot K)\) für die Zähltabellen und die gruppierten Großprim-Tabellen. Für \(N=800\) bleiben diese Größen problemlos handhabbar.
\(S\subseteq\{1,\dots,N\}\) olan her altküme için, boş küme dahil, EKOK değeri alınır ve hepsi toplanır:
$$G(N)=\sum_{S\subseteq\{1,\dots,N\}}\operatorname{lcm}(S),\qquad \operatorname{lcm}(\varnothing)=1.$$
İstenen şey \(G(800)\bmod(10^9+7)\) değeridir. \(2^{800}\) tane altküme olduğu için doğrudan saymak imkansızdır. Çözüm bunun yerine altkümeleri tam EKOK değerlerine göre gruplayıp problemi bölenler üzerinde ağırlıklı bir toplama dönüştürür.
Şunu tanımlayalım:
$$L_N=\operatorname{lcm}(1,2,\dots,N)=\prod_{p\le N}p^{M_p},\qquad M_p=\left\lfloor\log_p N\right\rfloor.$$
Her altkümenin EKOK'u \(L_N\)'in bir bölenidir. Dolayısıyla problem bütünüyle \(L_N\)'in bölenler kafesi üzerinde yaşar.
\(d\mid L_N\) için
$$A(d)=\#\{m\in\{1,\dots,N\}:m\mid d\}$$
tanımını yapalım. Bunlar, EKOK'u \(d\)'yi bölen bir altkümeye girebilecek sayılardır. Eğer
$$F(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)\mid d\}$$
ise, bu \(A(d)\) sayıların her altkümesi uygundur; dolayısıyla
$$F(d)=2^{A(d)}$$
olur. Böylece altküme taraması bir bölen sayma problemine dönüşür.
Şimdi
$$T(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)=d\}$$
olsun. “EKOK \(d\)'yi böler” demek, tam EKOK'un \(d\)'nin bir böleni olması demektir; yani
$$F(d)=\sum_{c\mid d}T(c).$$
Bölenler üzerinde Möbius terslemesi uygularsak
$$T(d)=\sum_{r\mid d}\mu(r)\,F\left(\frac{d}{r}\right)$$
elde edilir. Bunu
$$G(N)=\sum_{d\mid L_N} d\,T(d)$$
ifadesine yerleştirip toplamı yeniden düzenleyince
$$G(N)=\sum_{d\mid L_N} W(d)\,2^{A(d)}$$
olur; burada ağırlık
$$W(d)=d\sum_{r\mid L_N/d} r\,\mu(r)$$
şeklindedir.
Möbius fonksiyonu kareli çarpan taşıyan sayılarda sıfırdır. Bu yüzden \(d\)'de tam üsse ulaşmamış her asal için sadece \(r=1\) ve \(r=p\) seçenekleri katkı verir. Böylece
$$W(d)=d\prod_{p\mid L_N/d}(1-p)$$
olur. Eğer \(v_p(d)=e\) ise yerel çarpan
$$w_p(e)=\begin{cases} p^e(1-p), & e<M_p,\\ p^{M_p}, & e=M_p \end{cases}$$
şeklindedir. Yani toplam ağırlık
$$W(d)=\prod_{p\le N} w_p\bigl(v_p(d)\bigr)$$
olarak çarpımsal biçimde ayrılır. Uygulamadaki “\(p^e\) ile çarp, üs maksimum değilse \((1-p)\) ekle” kuralı tam olarak buradan gelir.
Her \(d\mid L_N\) bölenini
$$d=a\,b$$
şeklinde yazalım. Burada \(a\) yalnızca \(q\le\sqrt N\) asallarını, \(b\) ise yalnızca \(p>\sqrt N\) asallarını içerir.
\(p>\sqrt N\) için \(p^2>N\) olduğundan, böyle bir asalın \(L_N\) içindeki üssü sadece \(1\)'dir. Bu nedenle büyük asal kısmı \(b\) karesizdir.
Şimdi
$$B_a(M)=\#\{n\le M:n\mid a,\ \text{ve }n\text{'in tüm asal çarpanları }\le\sqrt N\}$$
tanımını yapalım. \(d\)'yi bölen ve \(N\)'i aşmayan bir sayı ya hiç büyük asal içermez ya da tam bir tane büyük asal içerir. İki farklı büyük asal içeremez; çünkü çarpımları zaten \(N\)'den büyük olur. Dolayısıyla
$$A(a b)=B_a(N)+\sum_{p\mid b} B_a\left(\left\lfloor\frac{N}{p}\right\rfloor\right)$$
bağıntısını elde ederiz. Yöntemin asıl hız kazandıran kısmı budur.
Küçük asal kısmı \(a\) sabit olsun. O zaman
$$2^{A(a b)}=2^{B_a(N)}\prod_{p\mid b}2^{B_a(\lfloor N/p\rfloor)}$$
yazılır. Bunu ağırlıkla birleştirince, tüm büyük asal seçimleri bağımsız şekilde çarpanlara ayrılır:
$$\sum_{b} W(a b)\,2^{A(a b)} = W_{\mathrm{small}}(a)\,2^{B_a(N)} \prod_{p>\sqrt N}\left((1-p)+p\,2^{B_a(\lfloor N/p\rfloor)}\right),$$
burada \(W_{\mathrm{small}}(a)\), yalnızca küçük asallardan gelen yerel ağırlıkların çarpımıdır.
Birçok büyük asal için
$$M=\left\lfloor\frac{N}{p}\right\rfloor$$
değeri aynıdır. Uygulama bu ortak değere göre gruplama yaparak her grup için tek bir çarpım tablosu oluşturur.
Küçük asallar \(q_1,\dots,q_k\) olsun. O zaman \(a\), üs vektörüyle tamamen belirlenir:
$$\bigl(e_1,\dots,e_k\bigr),\qquad 0\le e_i\le M_{q_i}.$$
Durum sayısı
$$\prod_{i=1}^k (M_{q_i}+1)$$
kadardır. Her gerekli limit \(M\) için uygulama, yalnızca küçük asallardan oluşan \(n\le M\) sayılarını listeler, tam üs vektörlerini işaretler ve çok boyutlu prefix toplamı uygular. Bu dönüşümden sonra her durumda ilgili \(a\) için \(B_a(M)\) değeri, yani \(M\)'i aşmayan küçük bölen sayısı hazır olur.
Bu tablolar kurulduktan sonra her durum ayrı ayrı değerlendirilip sonuçlar \(10^9+7\) modunda toplanır.
Bu durumda
$$L_5=\operatorname{lcm}(1,2,3,4,5)=60=2^2\cdot 3\cdot 5.$$
Tek küçük asal \(2\) olduğundan küçük asal durumları \(a\in\{1,2,4\}\) olur. Büyük asallar \(3\) ve \(5\)'tir; ikisi için de
$$\left\lfloor\frac{5}{3}\right\rfloor=\left\lfloor\frac{5}{5}\right\rfloor=1$$
geçerlidir. Küçük bölen sayıları
$$B_1(5)=1,\qquad B_2(5)=2,\qquad B_4(5)=3$$
olur; çünkü \(5\)'i aşmayan uygun küçük bölen kümeleri sırasıyla \(\{1\}\), \(\{1,2\}\) ve \(\{1,2,4\}\)'tür. Ayrıca
$$B_1(1)=B_2(1)=B_4(1)=1$$
olur. Küçük asal ağırlıkları ise
$$W_{\mathrm{small}}(1)=1\cdot(1-2)=-1,\qquad W_{\mathrm{small}}(2)=2\cdot(1-2)=-2,\qquad W_{\mathrm{small}}(4)=4$$
şeklindedir. Ortak büyük asal çarpanı
$$\bigl((1-3)+3\cdot 2^1\bigr)\bigl((1-5)+5\cdot 2^1\bigr)=4\cdot 6=24$$
olduğundan üç durumun katkıları
$$\begin{aligned} a=1&:&&-1\cdot 2^{1}\cdot 24=-48,\\ a=2&:&&-2\cdot 2^{2}\cdot 24=-192,\\ a=4&:&&4\cdot 2^{3}\cdot 24=768 \end{aligned}$$
olur. Toplam
$$-48-192+768=528$$
çıkar; bu da \(G(5)\) için bilinen kontrol değeridir.
C++, Python ve Java implementasyonları aynı akışı izler. Önce \(N\)'ye kadar olan asalları üretir ve \(\lfloor\sqrt N\rfloor\) sınırında küçük ve büyük olarak ayırırlar. Her küçük asal için \(L_N\) içinde görülen en büyük üs hesaplanır; bu bilgiler mixed-radix durum uzayını belirler.
Daha sonra yalnızca küçük asallardan oluşan ve \(N\)'i aşmayan tüm sayılar üretilir, üs durumlarına bağlanır ve büyüklüklerine göre sıralanır. Her gerekli limit \(M\in\{N\}\cup\{\lfloor N/p\rfloor:p>\sqrt N\}\) için uygun küçük sayılar işaretlenir, çok boyutlu prefix birikimi uygulanır ve her küçük durum \(a\) için \(B_a(M)\) tablosu elde edilir.
Ayrıca \(0\le t\le N\) için \(2^t\bmod(10^9+7)\) değerleri ve \(\lfloor N/p\rfloor\) değeri aynı olan büyük asal grupları için çarpım tabloları önceden hazırlanır. Son aşamada uygulama tüm küçük durumlar üzerinde dolaşır, ilgili ağırlığı yeniden kurar, önceden hesaplanan bölen sayılarını okur, grup katkılarını çarpar ve sonucu \(10^9+7\) modunda toplar.
$$S=\prod_{q\le\sqrt N}(M_q+1)$$
küçük asal durum sayısı, \(K\) ise \(p>\sqrt N\) asalları için farklı \(\lfloor N/p\rfloor\) değerlerinin sayısı olsun. Asal üretimi \(O(N\log\log N)\) zaman alır. Bundan sonraki ana ön hesaplama ve değerlendirme adımları, küçük asalların sayısı ve prefix dönüşümlerinden gelen küçük bir katsayıyla birlikte yaklaşık \(O(S\cdot K)\) mertebesindedir. Bellek kullanımı da saklanan sayım tabloları ve büyük asal grup tabloları nedeniyle \(O(S\cdot K)\) olur. \(N=800\) için bu boyutlar rahatlıkla yönetilebilir.
Para cada subconjunto \(S\subseteq\{1,\dots,N\}\), incluido el vacío, se toma su mínimo común múltiplo y se suman todos esos valores:
$$G(N)=\sum_{S\subseteq\{1,\dots,N\}}\operatorname{lcm}(S),\qquad \operatorname{lcm}(\varnothing)=1.$$
Hay que calcular \(G(800)\bmod(10^9+7)\). Como existen \(2^{800}\) subconjuntos, no se puede iterar sobre ellos uno por uno. La solución agrupa los subconjuntos por su mcm exacto y transforma el problema en una suma ponderada sobre divisores.
Definimos
$$L_N=\operatorname{lcm}(1,2,\dots,N)=\prod_{p\le N}p^{M_p},\qquad M_p=\left\lfloor\log_p N\right\rfloor.$$
Todo mcm de un subconjunto es un divisor de \(L_N\), así que todo el problema vive en la retícula de divisores de \(L_N\).
Para un divisor \(d\mid L_N\), definimos
$$A(d)=\#\{m\in\{1,\dots,N\}:m\mid d\}.$$
Esos son exactamente los valores que pueden aparecer en un subconjunto cuyo mcm divide a \(d\). Si
$$F(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)\mid d\},$$
entonces cualquier subconjunto de esos \(A(d)\) elementos sirve, y por tanto
$$F(d)=2^{A(d)}.$$
Así, el problema de subconjuntos se convierte en un problema de conteo de divisores.
Sea
$$T(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)=d\}.$$
Como “el mcm divide a \(d\)” significa que el mcm exacto es algún divisor de \(d\), se cumple
$$F(d)=\sum_{c\mid d}T(c).$$
La inversión de Möbius sobre divisores da
$$T(d)=\sum_{r\mid d}\mu(r)\,F\left(\frac{d}{r}\right).$$
Al sustituir esto en
$$G(N)=\sum_{d\mid L_N} d\,T(d)$$
y reordenar la suma, obtenemos
$$G(N)=\sum_{d\mid L_N} W(d)\,2^{A(d)},$$
donde el peso es
$$W(d)=d\sum_{r\mid L_N/d} r\,\mu(r).$$
La función de Möbius es cero en los enteros no libres de cuadrados. Por eso, para cada primo que aún no aparece con exponente máximo en \(d\), solo contribuyen las opciones \(r=1\) y \(r=p\). De ahí resulta
$$W(d)=d\prod_{p\mid L_N/d}(1-p).$$
Si \(v_p(d)=e\), el factor local es
$$w_p(e)=\begin{cases} p^e(1-p), & e<M_p,\\ p^{M_p}, & e=M_p. \end{cases}$$
Por tanto, el peso total se separa multiplicativamente como
$$W(d)=\prod_{p\le N} w_p\bigl(v_p(d)\bigr).$$
Eso explica la regla usada por la implementación: multiplicar por la potencia prima \(p^e\) y añadir \((1-p)\) cuando el exponente todavía no es máximo.
Escribimos cualquier divisor \(d\mid L_N\) como
$$d=a\,b,$$
donde \(a\) usa solo primos \(q\le\sqrt N\) y \(b\) usa solo primos \(p>\sqrt N\).
Si \(p>\sqrt N\), entonces \(p^2>N\), así que su exponente en \(L_N\) es solamente \(1\). En consecuencia, la parte \(b\) es libre de cuadrados.
Definimos
$$B_a(M)=\#\{n\le M:n\mid a,\ \text{y todos los factores primos de }n\text{ son }\le\sqrt N\}.$$
Cualquier número \(m\le N\) que divide a \(d\) contiene o bien ningún primo grande o bien exactamente uno. No puede contener dos primos grandes distintos, porque su producto superaría \(N\). Por tanto
$$A(a b)=B_a(N)+\sum_{p\mid b} B_a\left(\left\lfloor\frac{N}{p}\right\rfloor\right).$$
Esta identidad es la simplificación estructural decisiva del método.
Fijemos la parte de primos pequeños \(a\). Entonces
$$2^{A(a b)}=2^{B_a(N)}\prod_{p\mid b}2^{B_a(\lfloor N/p\rfloor)}.$$
Al combinarlo con los pesos locales, la suma sobre todas las elecciones posibles de primos grandes se factoriza de forma independiente:
$$\sum_{b} W(a b)\,2^{A(a b)} = W_{\mathrm{small}}(a)\,2^{B_a(N)} \prod_{p>\sqrt N}\left((1-p)+p\,2^{B_a(\lfloor N/p\rfloor)}\right),$$
donde \(W_{\mathrm{small}}(a)\) es el producto de los factores de peso procedentes solo de los primos pequeños.
Muchos primos grandes comparten el mismo cociente
$$M=\left\lfloor\frac{N}{p}\right\rfloor.$$
La implementación aprovecha eso agrupándolos por ese valor común y precalculando una tabla de productos para cada grupo.
Si los primos pequeños son \(q_1,\dots,q_k\), entonces \(a\) queda determinado por su vector de exponentes
$$\bigl(e_1,\dots,e_k\bigr),\qquad 0\le e_i\le M_{q_i}.$$
El número de estados es
$$\prod_{i=1}^k (M_{q_i}+1).$$
Para cada límite necesario \(M\), la implementación enumera todos los enteros formados solo por primos pequeños con \(n\le M\), marca su vector exacto de exponentes y después aplica sumas prefijo multidimensionales. Tras esa transformación, cada estado contiene \(B_a(M)\): el número de divisores pequeños del \(a\) correspondiente que no superan \(M\).
Con esas tablas ya construidas, cada estado se evalúa de manera independiente y todas las contribuciones se acumulan módulo \(10^9+7\).
En este caso
$$L_5=\operatorname{lcm}(1,2,3,4,5)=60=2^2\cdot 3\cdot 5.$$
El único primo pequeño es \(2\), así que los estados pequeños son \(a\in\{1,2,4\}\). Los primos grandes son \(3\) y \(5\), y ambos cumplen
$$\left\lfloor\frac{5}{3}\right\rfloor=\left\lfloor\frac{5}{5}\right\rfloor=1.$$
Los conteos de divisores pequeños son
$$B_1(5)=1,\qquad B_2(5)=2,\qquad B_4(5)=3,$$
porque los divisores pequeños admisibles hasta \(5\) son \(\{1\}\), \(\{1,2\}\) y \(\{1,2,4\}\), respectivamente. Además,
$$B_1(1)=B_2(1)=B_4(1)=1.$$
Los pesos de la parte pequeña son
$$W_{\mathrm{small}}(1)=1\cdot(1-2)=-1,\qquad W_{\mathrm{small}}(2)=2\cdot(1-2)=-2,\qquad W_{\mathrm{small}}(4)=4.$$
El factor común de los primos grandes vale
$$\bigl((1-3)+3\cdot 2^1\bigr)\bigl((1-5)+5\cdot 2^1\bigr)=4\cdot 6=24.$$
Por tanto, las tres contribuciones de estado son
$$\begin{aligned} a=1&:&&-1\cdot 2^{1}\cdot 24=-48,\\ a=2&:&&-2\cdot 2^{2}\cdot 24=-192,\\ a=4&:&&4\cdot 2^{3}\cdot 24=768. \end{aligned}$$
La suma total es
$$-48-192+768=528,$$
que coincide con el valor de comprobación conocido para \(G(5)\).
Las implementaciones en C++, Python y Java siguen el mismo flujo. Primero generan todos los primos hasta \(N\) y los separan en \(\lfloor\sqrt N\rfloor\) entre primos pequeños y grandes. Para cada primo pequeño registran el mayor exponente que aparece en \(L_N\), y eso define el espacio de estados de radix mixto.
Después enumeran todos los enteros formados solo por primos pequeños y no mayores que \(N\), los asocian con su estado de exponentes y los ordenan por tamaño. Para cada límite necesario \(M\in\{N\}\cup\{\lfloor N/p\rfloor:p>\sqrt N\}\), marcan los valores elegibles, ejecutan una acumulación prefijo multidimensional y obtienen así la tabla \(B_a(M)\) para cada estado pequeño \(a\).
También precalculan las potencias \(2^t\bmod(10^9+7)\) para \(0\le t\le N\), junto con una tabla por cada grupo de primos grandes que comparten el mismo cociente \(\lfloor N/p\rfloor\). Al final recorren todos los estados pequeños, reconstruyen el peso correspondiente, leen los conteos ya preparados, multiplican los factores agrupados de primos grandes y acumulan la respuesta módulo \(10^9+7\).
Sea
$$S=\prod_{q\le\sqrt N}(M_q+1)$$
el número de estados de primos pequeños, y sea \(K\) el número de valores distintos de \(\lfloor N/p\rfloor\) entre los primos \(p>\sqrt N\). Generar los primos cuesta \(O(N\log\log N)\). Después de eso, la fase principal de preprocesamiento y evaluación está cerca de \(O(S\cdot K)\), con un pequeño factor adicional debido al número de primos pequeños y a las transformadas prefijo. La memoria usada es \(O(S\cdot K)\) por las tablas de conteo y las tablas agrupadas de primos grandes. Para \(N=800\), estos tamaños siguen siendo cómodos.
对每个子集 \(S\subseteq\{1,\dots,N\}\)，包括空集，都取它的最小公倍数并求和：
$$G(N)=\sum_{S\subseteq\{1,\dots,N\}}\operatorname{lcm}(S),\qquad \operatorname{lcm}(\varnothing)=1.$$
目标是计算 \(G(800)\bmod(10^9+7)\)。由于子集总数是 \(2^{800}\)，不可能直接暴力枚举。真正可行的办法，是按“子集的精确最小公倍数”来分类，再把原问题改写成对所有约数的加权求和。
记
$$L_N=\operatorname{lcm}(1,2,\dots,N)=\prod_{p\le N}p^{M_p},\qquad M_p=\left\lfloor\log_p N\right\rfloor.$$
任意子集的最小公倍数一定是 \(L_N\) 的某个约数，因此整个问题都可以放在 \(L_N\) 的约数格上来处理。
对任意 \(d\mid L_N\)，定义
$$A(d)=\#\{m\in\{1,\dots,N\}:m\mid d\}.$$
这正是所有“可以出现在某个子集中，且该子集的最小公倍数整除 \(d\)”的候选数字个数。如果记
$$F(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)\mid d\},$$
那么这些 \(A(d)\) 个候选数字的任意子集都满足条件，因此
$$F(d)=2^{A(d)}.$$
这样一来，原本的“枚举子集”问题就变成了“统计约数所覆盖的数字个数”问题。
设
$$T(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)=d\}.$$
因为“最小公倍数整除 \(d\)”等价于“精确最小公倍数是 \(d\) 的某个约数”，所以
$$F(d)=\sum_{c\mid d}T(c).$$
在约数偏序上使用 Möbius 反演，就得到
$$T(d)=\sum_{r\mid d}\mu(r)\,F\left(\frac{d}{r}\right).$$
而原问题就是
$$G(N)=\sum_{d\mid L_N} d\,T(d).$$
把反演结果代入并整理求和指标后，可以写成
$$G(N)=\sum_{d\mid L_N} W(d)\,2^{A(d)},$$
其中权重为
$$W(d)=d\sum_{r\mid L_N/d} r\,\mu(r).$$
Möbius 函数在含平方因子的整数上为零。因此，对于那些在 \(d\) 中还没有达到最大指数的素数，只会留下 \(r=1\) 和 \(r=p\) 两种贡献。于是
$$W(d)=d\prod_{p\mid L_N/d}(1-p).$$
若 \(v_p(d)=e\)，则对应的局部因子为
$$w_p(e)=\begin{cases} p^e(1-p), & e<M_p,\\ p^{M_p}, & e=M_p. \end{cases}$$
因此总权重具有乘法分解
$$W(d)=\prod_{p\le N} w_p\bigl(v_p(d)\bigr).$$
这正是实现里那条规则的数学来源：先乘上素数幂 \(p^e\)，如果该素数的指数还没到上界，再额外乘一个 \((1-p)\)。
把任意 \(d\mid L_N\) 写成
$$d=a\,b,$$
其中 \(a\) 只含 \(q\le\sqrt N\) 的素数，\(b\) 只含 \(p>\sqrt N\) 的素数。
对大素数 \(p>\sqrt N\) 而言，有 \(p^2>N\)，所以它在 \(L_N\) 中的指数最多只能是 \(1\)。这说明大素数部分 \(b\) 一定是无平方因子的。
现在定义
$$B_a(M)=\#\{n\le M:n\mid a,\ \text{且 }n\text{ 的所有素因子都 }\le\sqrt N\}.$$
一个不超过 \(N\) 且整除 \(d\) 的整数 \(m\)，要么不含大素数，要么恰好含一个大素数。它不可能同时含有两个不同的大素数，因为那样它们的乘积就已经大于 \(N\) 了。因此
$$A(a b)=B_a(N)+\sum_{p\mid b} B_a\left(\left\lfloor\frac{N}{p}\right\rfloor\right).$$
这一步是整个算法最关键的结构化简。
固定小素数部分 \(a\) 之后，有
$$2^{A(a b)}=2^{B_a(N)}\prod_{p\mid b}2^{B_a(\lfloor N/p\rfloor)}.$$
再与局部权重结合，就会发现对所有大素数“选或不选”的求和完全可以独立分解：
$$\sum_{b} W(a b)\,2^{A(a b)} = W_{\mathrm{small}}(a)\,2^{B_a(N)} \prod_{p>\sqrt N}\left((1-p)+p\,2^{B_a(\lfloor N/p\rfloor)}\right),$$
其中 \(W_{\mathrm{small}}(a)\) 表示仅由小素数部分贡献的权重乘积。
很多大素数会给出相同的商
$$M=\left\lfloor\frac{N}{p}\right\rfloor.$$
实现正是按这个公共值分组，为每个组预先计算一张乘积表，从而避免重复工作。
如果小素数依次为 \(q_1,\dots,q_k\)，那么 \(a\) 完全由其指数向量决定：
$$\bigl(e_1,\dots,e_k\bigr),\qquad 0\le e_i\le M_{q_i}.$$
这样的状态总数是
$$\prod_{i=1}^k (M_{q_i}+1).$$
对每个需要的上界 \(M\)，实现会枚举所有只由小素数组成且满足 \(n\le M\) 的整数，记录它们的精确指数向量，然后在各个维度上做多维前缀和。经过这个变换以后，每个状态就保存了对应 \(a\) 的 \(B_a(M)\) 值，也就是“不超过 \(M\) 的小素数约数个数”。
有了这些表之后，每个状态都可以独立计算，最后把所有贡献对 \(10^9+7\) 取模求和即可。
此时
$$L_5=\operatorname{lcm}(1,2,3,4,5)=60=2^2\cdot 3\cdot 5.$$
唯一的小素数是 \(2\)，因此小素数状态只有 \(a\in\{1,2,4\}\)。大素数是 \(3\) 和 \(5\)，并且二者都满足
$$\left\lfloor\frac{5}{3}\right\rfloor=\left\lfloor\frac{5}{5}\right\rfloor=1.$$
小素数约数计数为
$$B_1(5)=1,\qquad B_2(5)=2,\qquad B_4(5)=3,$$
因为不超过 \(5\) 的可用小素数约数分别是 \(\{1\}\)、\(\{1,2\}\) 和 \(\{1,2,4\}\)。同时
$$B_1(1)=B_2(1)=B_4(1)=1.$$
小素数权重分别为
$$W_{\mathrm{small}}(1)=1\cdot(1-2)=-1,\qquad W_{\mathrm{small}}(2)=2\cdot(1-2)=-2,\qquad W_{\mathrm{small}}(4)=4.$$
大素数部分的公共因子是
$$\bigl((1-3)+3\cdot 2^1\bigr)\bigl((1-5)+5\cdot 2^1\bigr)=4\cdot 6=24.$$
因此三个状态的贡献分别为
$$\begin{aligned} a=1&:&&-1\cdot 2^{1}\cdot 24=-48,\\ a=2&:&&-2\cdot 2^{2}\cdot 24=-192,\\ a=4&:&&4\cdot 2^{3}\cdot 24=768. \end{aligned}$$
相加得到
$$-48-192+768=528,$$
这正好是 \(G(5)\) 的已知校验值。
C++、Python 和 Java 实现遵循同一条计算流程。首先筛出所有不超过 \(N\) 的素数，并在 \(\lfloor\sqrt N\rfloor\) 处分成小素数和大素数。对每个小素数，记录它在 \(L_N\) 中出现的最大指数，这些上界共同决定混合进制状态空间。
随后，程序枚举所有仅由小素数组成且不超过 \(N\) 的整数，把它们映射到各自的指数状态，并按数值大小排序。对每个需要的上界 \(M\in\{N\}\cup\{\lfloor N/p\rfloor:p>\sqrt N\}\)，程序先标记满足 \(n\le M\) 的小素数整数，再执行多维前缀累加，从而得到每个小状态 \(a\) 的 \(B_a(M)\) 表。
程序还会预先计算 \(0\le t\le N\) 的 \(2^t\bmod(10^9+7)\)，以及每个“大素数组”对应的乘积表，这里的分组依据就是相同的 \(\lfloor N/p\rfloor\)。最后，程序遍历所有小素数状态，重建该状态的权重，读取预处理好的计数，乘上各个大素数组的贡献，并把结果累加到最终答案中。
记
$$S=\prod_{q\le\sqrt N}(M_q+1)$$
为小素数状态总数，记 \(K\) 为大素数 \(p>\sqrt N\) 所产生的不同 \(\lfloor N/p\rfloor\) 值的个数。筛素数的代价是 \(O(N\log\log N)\)。在此之后，主要的预处理和状态求值阶段大致接近 \(O(S\cdot K)\)，只带有一个与小素数个数和前缀变换有关的较小常数因子。内存消耗为 \(O(S\cdot K)\)，主要来自各个计数表和大素数组的乘积表。对于 \(N=800\)，这些规模都完全可控。
Для каждого подмножества \(S\subseteq\{1,\dots,N\}\), включая пустое, берётся его наименьшее общее кратное, и все эти значения суммируются:
$$G(N)=\sum_{S\subseteq\{1,\dots,N\}}\operatorname{lcm}(S),\qquad \operatorname{lcm}(\varnothing)=1.$$
Нужно вычислить \(G(800)\bmod(10^9+7)\). Поскольку подмножеств \(2^{800}\), прямой перебор невозможен. Поэтому решение группирует подмножества по их точному НОК и сводит задачу к взвешенной сумме по делителям.
Обозначим
$$L_N=\operatorname{lcm}(1,2,\dots,N)=\prod_{p\le N}p^{M_p},\qquad M_p=\left\lfloor\log_p N\right\rfloor.$$
Любой НОК подмножества является делителем \(L_N\), так что вся задача естественно живёт на решётке делителей числа \(L_N\).
Для делителя \(d\mid L_N\) введём
$$A(d)=\#\{m\in\{1,\dots,N\}:m\mid d\}.$$
Это в точности те числа, которые могут входить в подмножество с условием \(\operatorname{lcm}(S)\mid d\). Поэтому, если
$$F(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)\mid d\},$$
то любое подмножество этих \(A(d)\) чисел подходит, и значит
$$F(d)=2^{A(d)}.$$
Тем самым задача о подмножествах превращается в задачу о делителях.
Пусть
$$T(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)=d\}.$$
Условие “НОК делит \(d\)” означает, что точный НОК является некоторым делителем \(d\). Следовательно,
$$F(d)=\sum_{c\mid d}T(c).$$
Инверсия Мёбиуса по делителям даёт
$$T(d)=\sum_{r\mid d}\mu(r)\,F\left(\frac{d}{r}\right).$$
Исходная сумма имеет вид
$$G(N)=\sum_{d\mid L_N} d\,T(d).$$
Подставляя формулу выше и меняя порядок суммирования, получаем
$$G(N)=\sum_{d\mid L_N} W(d)\,2^{A(d)},$$
где вес равен
$$W(d)=d\sum_{r\mid L_N/d} r\,\mu(r).$$
Функция Мёбиуса обращается в ноль на числах с квадратным делителем. Поэтому для каждого простого, у которого показатель в \(d\) ещё не максимален, остаются только варианты \(r=1\) и \(r=p\). Отсюда следует
$$W(d)=d\prod_{p\mid L_N/d}(1-p).$$
Если \(v_p(d)=e\), то локальный множитель равен
$$w_p(e)=\begin{cases} p^e(1-p), & e<M_p,\\ p^{M_p}, & e=M_p. \end{cases}$$
Значит, полный вес мультипликативно раскладывается так:
$$W(d)=\prod_{p\le N} w_p\bigl(v_p(d)\bigr).$$
Именно этим объясняется правило в реализации: умножить на простую степень \(p^e\) и дополнительно умножить на \((1-p)\), если показатель ещё не достиг предела.
Любой делитель \(d\mid L_N\) представим в виде
$$d=a\,b,$$
где \(a\) состоит только из простых \(q\le\sqrt N\), а \(b\) только из простых \(p>\sqrt N\).
Для большого простого \(p>\sqrt N\) выполняется \(p^2>N\), поэтому его показатель в \(L_N\) может быть только равен \(1\). Значит, часть \(b\) всегда бесквадратна.
Теперь определим
$$B_a(M)=\#\{n\le M:n\mid a,\ \text{и все простые делители }n\text{ не превосходят }\sqrt N\}.$$
Число \(m\le N\), делящее \(d\), либо не содержит больших простых, либо содержит ровно один большой простой. Двух разных больших простых быть не может, потому что их произведение уже превышает \(N\). Поэтому
$$A(a b)=B_a(N)+\sum_{p\mid b} B_a\left(\left\lfloor\frac{N}{p}\right\rfloor\right).$$
Это и есть главное структурное упрощение решения.
Зафиксируем малую часть \(a\). Тогда
$$2^{A(a b)}=2^{B_a(N)}\prod_{p\mid b}2^{B_a(\lfloor N/p\rfloor)}.$$
Если совместить это с локальными весами, то сумма по всем возможным выборам больших простых факторизуется независимо:
$$\sum_{b} W(a b)\,2^{A(a b)} = W_{\mathrm{small}}(a)\,2^{B_a(N)} \prod_{p>\sqrt N}\left((1-p)+p\,2^{B_a(\lfloor N/p\rfloor)}\right),$$
где \(W_{\mathrm{small}}(a)\) обозначает произведение локальных весов, идущих только от малых простых.
Многие большие простые дают одинаковое значение
$$M=\left\lfloor\frac{N}{p}\right\rfloor.$$
Поэтому реализация группирует их по этому общему значению и заранее вычисляет таблицу произведений для каждой группы.
Если малые простые равны \(q_1,\dots,q_k\), то число \(a\) полностью задаётся вектором показателей
$$\bigl(e_1,\dots,e_k\bigr),\qquad 0\le e_i\le M_{q_i}.$$
Число состояний равно
$$\prod_{i=1}^k (M_{q_i}+1).$$
Для каждого нужного ограничения \(M\) реализация перечисляет все числа \(n\le M\), состоящие только из малых простых, отмечает их точные векторы показателей, а затем выполняет многомерные префиксные суммы. После такой обработки каждое состояние хранит величину \(B_a(M)\), то есть число малых делителей соответствующего \(a\), не превосходящих \(M\).
Когда эти таблицы готовы, каждое состояние можно обрабатывать независимо и аккумулировать вклад по модулю \(10^9+7\).
Здесь
$$L_5=\operatorname{lcm}(1,2,3,4,5)=60=2^2\cdot 3\cdot 5.$$
Единственный малый простой равен \(2\), поэтому малые состояния таковы: \(a\in\{1,2,4\}\). Большие простые — это \(3\) и \(5\), причём для обоих
$$\left\lfloor\frac{5}{3}\right\rfloor=\left\lfloor\frac{5}{5}\right\rfloor=1.$$
Число малых делителей равно
$$B_1(5)=1,\qquad B_2(5)=2,\qquad B_4(5)=3,$$
потому что допустимые малые делители до \(5\) — это соответственно \(\{1\}\), \(\{1,2\}\) и \(\{1,2,4\}\). Кроме того,
$$B_1(1)=B_2(1)=B_4(1)=1.$$
Веса малой части равны
$$W_{\mathrm{small}}(1)=1\cdot(1-2)=-1,\qquad W_{\mathrm{small}}(2)=2\cdot(1-2)=-2,\qquad W_{\mathrm{small}}(4)=4.$$
Общий множитель от больших простых равен
$$\bigl((1-3)+3\cdot 2^1\bigr)\bigl((1-5)+5\cdot 2^1\bigr)=4\cdot 6=24.$$
Поэтому три вклада состояний равны
$$\begin{aligned} a=1&:&&-1\cdot 2^{1}\cdot 24=-48,\\ a=2&:&&-2\cdot 2^{2}\cdot 24=-192,\\ a=4&:&&4\cdot 2^{3}\cdot 24=768. \end{aligned}$$
Сумма даёт
$$-48-192+768=528,$$
что совпадает с известным контрольным значением для \(G(5)\).
Реализации на C++, Python и Java используют одну и ту же схему. Сначала они строят список всех простых до \(N\) и разделяют его по границе \(\lfloor\sqrt N\rfloor\) на малые и большие простые. Для каждого малого простого сохраняется максимальный показатель, который встречается в \(L_N\); именно эти пределы задают пространство состояний в смешанной системе счисления.
Затем перечисляются все числа, составленные только из малых простых и не превосходящие \(N\). Каждое такое число связывается со своим вектором показателей, после чего все значения сортируются по величине. Для каждого нужного ограничения \(M\in\{N\}\cup\{\lfloor N/p\rfloor:p>\sqrt N\}\) отмечаются подходящие малые числа, выполняется многомерное префиксное накопление, и так получается таблица \(B_a(M)\) для каждого малого состояния \(a\).
Дополнительно заранее вычисляются степени \(2^t\bmod(10^9+7)\) для \(0\le t\le N\), а также таблицы произведений для групп больших простых с одинаковым значением \(\lfloor N/p\rfloor\). После этого код перебирает все малые состояния, восстанавливает соответствующий вес, читает подготовленные значения счёта, умножает на вклад групп больших простых и накапливает итоговый ответ по модулю \(10^9+7\).
Пусть
$$S=\prod_{q\le\sqrt N}(M_q+1)$$
— число состояний малых простых, а \(K\) — число различных значений \(\lfloor N/p\rfloor\) для простых \(p>\sqrt N\). Построение решета простых стоит \(O(N\log\log N)\). После этого основная предварительная обработка и вычисление находятся примерно на уровне \(O(S\cdot K)\), с небольшим дополнительным множителем из-за числа малых простых и многомерных префиксных преобразований. Память составляет \(O(S\cdot K)\), поскольку нужно хранить таблицы счёта и таблицы групп больших простых. Для \(N=800\) эти объёмы остаются вполне умеренными.
لكل مجموعة جزئية \(S\subseteq\{1,\dots,N\}\)، بما في ذلك المجموعة الخالية، نأخذ المضاعف المشترك الأصغر لها ثم نجمع جميع هذه القيم:
$$G(N)=\sum_{S\subseteq\{1,\dots,N\}}\operatorname{lcm}(S),\qquad \operatorname{lcm}(\varnothing)=1.$$
المطلوب هو حساب \(G(800)\bmod(10^9+7)\). وبما أن عدد المجموعات الجزئية هو \(2^{800}\)، فلا يمكن التعداد المباشر. لذلك تعيد الفكرة تنظيم المسألة بحسب القيمة الدقيقة للمضاعف المشترك الأصغر، ثم تحوّلها إلى مجموع موزون على قواسم عدد واحد كبير.
لنعرّف
$$L_N=\operatorname{lcm}(1,2,\dots,N)=\prod_{p\le N}p^{M_p},\qquad M_p=\left\lfloor\log_p N\right\rfloor.$$
كل قيمة ممكنة لـ \(\operatorname{lcm}\) لأي مجموعة جزئية هي قاسم لـ \(L_N\)، ولذلك تصبح المسألة كلها مسألة على شبكة قواسم \(L_N\).
لكل \(d\mid L_N\) نعرّف
$$A(d)=\#\{m\in\{1,\dots,N\}:m\mid d\}.$$
هذه هي بالضبط الأعداد التي يمكن أن تظهر داخل مجموعة جزئية يكون \(\operatorname{lcm}\) الخاص بها قاسمًا لـ \(d\). وإذا كتبنا
$$F(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)\mid d\},$$
فإن أي مجموعة جزئية من هذه الأعداد \(A(d)\) تكون صالحة، ومن ثم
$$F(d)=2^{A(d)}.$$
بهذا نكون قد استبدلنا تعداد المجموعات الجزئية بمسألة عدّ مرتبطة بالقواسم.
ليكن
$$T(d)=\#\{S\subseteq\{1,\dots,N\}:\operatorname{lcm}(S)=d\}.$$
العبارة “\(\operatorname{lcm}(S)\) يقسم \(d\)” تعني أن القيمة الدقيقة لـ \(\operatorname{lcm}\) هي أحد قواسم \(d\)، ولذلك
$$F(d)=\sum_{c\mid d}T(c).$$
وباستعمال انعكاس Möbius على شبكة القواسم نحصل على
$$T(d)=\sum_{r\mid d}\mu(r)\,F\left(\frac{d}{r}\right).$$
أما المطلوب الأصلي فهو
$$G(N)=\sum_{d\mid L_N} d\,T(d).$$
وبعد التعويض وإعادة ترتيب المجاميع نحصل على
$$G(N)=\sum_{d\mid L_N} W(d)\,2^{A(d)},$$
حيث الوزن يساوي
$$W(d)=d\sum_{r\mid L_N/d} r\,\mu(r).$$
دالة Möbius تساوي صفرًا على الأعداد التي تحتوي على مربع أولي. لذلك، لكل عدد أولي لم يصل بعد إلى أسه الأقصى داخل \(d\)، لا يبقى إلا الخياران \(r=1\) و \(r=p\). ومن هنا ينتج
$$W(d)=d\prod_{p\mid L_N/d}(1-p).$$
إذا كان \(v_p(d)=e\)، فإن العامل المحلي يصبح
$$w_p(e)=\begin{cases} p^e(1-p), & e<M_p,\\ p^{M_p}, & e=M_p. \end{cases}$$
وبالتالي فإن الوزن الكلي يتحلل ضربيًا على الصورة
$$W(d)=\prod_{p\le N} w_p\bigl(v_p(d)\bigr).$$
وهذا هو السبب الرياضي وراء القاعدة المستخدمة في التنفيذ: نضرب في \(p^e\)، وإذا لم يكن الأس قد بلغ حده الأقصى بعد نضرب أيضًا في \((1-p)\).
نكتب كل \(d\mid L_N\) بالشكل
$$d=a\,b,$$
حيث يحتوي \(a\) فقط على الأوليات \(q\le\sqrt N\)، ويحتوي \(b\) فقط على الأوليات \(p>\sqrt N\).
إذا كان \(p>\sqrt N\) فإن \(p^2>N\)، ولذلك لا يمكن أن يظهر هذا الأولي في \(L_N\) إلا بالأس \(1\). هذا يعني أن الجزء \(b\) خالٍ من المربعات.
عرّف الآن
$$B_a(M)=\#\{n\le M:n\mid a,\ n\text{ uses only small primes}\}.$$
أي عدد \(m\le N\) يقسم \(d\) إما أن لا يحتوي على أي أولي كبير، أو يحتوي على أولي كبير واحد بالضبط. ولا يمكنه احتواء أوليين كبيرين مختلفين، لأن حاصل ضربهما سيتجاوز \(N\). لذلك
$$A(a b)=B_a(N)+\sum_{p\mid b} B_a\left(\left\lfloor\frac{N}{p}\right\rfloor\right).$$
هذه هي الفكرة البنيوية الأساسية التي تجعل الخوارزمية سريعة.
لنثبت الجزء الصغير \(a\). عندها
$$2^{A(a b)}=2^{B_a(N)}\prod_{p\mid b}2^{B_a(\lfloor N/p\rfloor)}.$$
وعند دمج هذه الصيغة مع الأوزان المحلية، يتفكك الجمع على جميع اختيارات الأوليات الكبيرة بشكل مستقل:
$$\sum_{b} W(a b)\,2^{A(a b)} = W_{\mathrm{small}}(a)\,2^{B_a(N)} \prod_{p>\sqrt N}\left((1-p)+p\,2^{B_a(\lfloor N/p\rfloor)}\right),$$
حيث \(W_{\mathrm{small}}(a)\) هو حاصل ضرب الأوزان المحلية القادمة من الأوليات الصغيرة فقط.
كثير من الأوليات الكبيرة تشترك في نفس القيمة
$$M=\left\lfloor\frac{N}{p}\right\rfloor.$$
ولذلك يقوم التنفيذ بتجميعها بحسب هذه القيمة المشتركة، ثم يبني جدولًا واحدًا لكل مجموعة.
إذا كانت الأوليات الصغيرة هي \(q_1,\dots,q_k\)، فإن \(a\) يتحدد تمامًا من متجه الأسس
$$\bigl(e_1,\dots,e_k\bigr),\qquad 0\le e_i\le M_{q_i}.$$
وعدد هذه الحالات هو
$$\prod_{i=1}^k (M_{q_i}+1).$$
لكل حد مطلوب \(M\)، يقوم التنفيذ بتعداد كل الأعداد \(n\le M\) التي تتكون فقط من أوليات صغيرة، ثم يسجل متجه الأسس الدقيق لكل عدد، وبعد ذلك يطبّق مجاميع prefix متعددة الأبعاد. بعد هذه الخطوة تصبح كل حالة حاوية على قيمة \(B_a(M)\)، أي عدد القواسم الصغيرة للعدد الموافق لـ \(a\) والتي لا تتجاوز \(M\).
وبعد بناء هذه الجداول يمكن تقييم كل حالة على حدة وجمع جميع المساهمات بترديد \(10^9+7\).
لدينا هنا
$$L_5=\operatorname{lcm}(1,2,3,4,5)=60=2^2\cdot 3\cdot 5.$$
الأولي الصغير الوحيد هو \(2\)، ولذلك تكون الحالات الصغيرة \(a\in\{1,2,4\}\). أما الأوليات الكبيرة فهي \(3\) و\(5\)، وكلاهما يحقق
$$\left\lfloor\frac{5}{3}\right\rfloor=\left\lfloor\frac{5}{5}\right\rfloor=1.$$
قيم العدّ للأجزاء الصغيرة هي
$$B_1(5)=1,\qquad B_2(5)=2,\qquad B_4(5)=3,$$
لأن القواسم الصغيرة المسموح بها حتى \(5\) هي على الترتيب \(\{1\}\) و\(\{1,2\}\) و\(\{1,2,4\}\). كذلك
$$B_1(1)=B_2(1)=B_4(1)=1.$$
أما أوزان الجزء الصغير فهي
$$W_{\mathrm{small}}(1)=1\cdot(1-2)=-1,\qquad W_{\mathrm{small}}(2)=2\cdot(1-2)=-2,\qquad W_{\mathrm{small}}(4)=4.$$
والعامل المشترك القادم من الأوليات الكبيرة يساوي
$$\bigl((1-3)+3\cdot 2^1\bigr)\bigl((1-5)+5\cdot 2^1\bigr)=4\cdot 6=24.$$
إذن مساهمات الحالات الثلاث هي
$$\begin{aligned} a=1&:&&-1\cdot 2^{1}\cdot 24=-48,\\ a=2&:&&-2\cdot 2^{2}\cdot 24=-192,\\ a=4&:&&4\cdot 2^{3}\cdot 24=768. \end{aligned}$$
وبجمعها نحصل على
$$-48-192+768=528,$$
وهي قيمة التحقق المعروفة لـ \(G(5)\).
تسير تطبيقات C++ وPython وJava وفق المراحل نفسها. تبدأ أولًا بتوليد جميع الأعداد الأولية حتى \(N\)، ثم تقسيمها عند \(\lfloor\sqrt N\rfloor\) إلى أوليات صغيرة وأوليات كبيرة. ولكل أولي صغير تسجل أكبر أس ممكن له داخل \(L_N\)، وبذلك يتحدد فضاء الحالات ذي الأساس المختلط.
بعد ذلك تُعدِّد الشيفرة جميع الأعداد التي تتكون فقط من أوليات صغيرة ولا تتجاوز \(N\)، وتربط كل عدد بحالته الأسّية، ثم ترتب هذه الأعداد تصاعديًا. ولكل حد مطلوب \(M\in\{N\}\cup\{\lfloor N/p\rfloor:p>\sqrt N\}\)، يتم تعليم القيم المناسبة، ثم تنفيذ تجميع prefix متعدد الأبعاد للحصول على جدول \(B_a(M)\) لكل حالة صغيرة \(a\).
وتُحسب أيضًا قيم \(2^t\bmod(10^9+7)\) مسبقًا لكل \(0\le t\le N\)، مع بناء جدول لكل مجموعة من الأوليات الكبيرة التي تشترك في نفس القيمة \(\lfloor N/p\rfloor\). وفي المرحلة الأخيرة تمر الشيفرة على جميع الحالات الصغيرة، وتعيد تركيب الوزن الموافق لها، ثم تقرأ قيم العدّ المحسوبة مسبقًا، وتضرب في مساهمات مجموعات الأوليات الكبيرة، وأخيرًا تجمع النتيجة كلها بترديد \(10^9+7\).
إذا كان
$$S=\prod_{q\le\sqrt N}(M_q+1)$$
هو عدد حالات الأوليات الصغيرة، وكان \(K\) هو عدد القيم المختلفة لـ \(\lfloor N/p\rfloor\) بين الأوليات \(p>\sqrt N\)، فإن توليد الأوليات يكلف \(O(N\log\log N)\). بعد ذلك تصبح مرحلة المعالجة الأساسية والتقييم قريبة من \(O(S\cdot K)\)، مع عامل صغير إضافي ناتج من عدد الأوليات الصغيرة ومن تحويلات prefix متعددة الأبعاد. أما الذاكرة فتبلغ \(O(S\cdot K)\) بسبب جداول العدّ وجداول مجموعات الأوليات الكبيرة. وعند \(N=800\) تبقى هذه الأحجام مريحة جدًا عمليًا.