For each positive integer \(n\), consider every subset \(S\) of the divisors of \(n\). Give that subset the weight
$$w(S)=\prod_{d\in S}\Phi_d(2),$$
where \(\Phi_d(x)\) is the \(d\)-th cyclotomic polynomial. Let \(P(n)\) be the total weight of those subsets whose least common multiple is exactly \(n\). The cumulative target is
$$Q(N)=\sum_{n=1}^{N} P(n),$$
computed modulo \(10^9+7\) for \(N=10^7\). A brute-force search would enumerate all divisor subsets for every \(n\), so the fast solution rewrites the problem as a pair of divisor transforms followed by Möbius inversion.
Write \(\mu\) for the Möbius function and \(M(x)=\sum_{k\le x}\mu(k)\) for the Mertens function. The implementations are based on the following chain of identities.
The classical factorization
$$x^n-1=\prod_{d\mid n}\Phi_d(x)$$
can be inverted on the divisor lattice, which gives
$$\Phi_n(x)=\prod_{d\mid n}\left(x^d-1\right)^{\mu(n/d)}.$$
Evaluating at \(x=2\), define
$$C(n)=\Phi_n(2)=\prod_{d\mid n}\left(2^d-1\right)^{\mu(n/d)}=\prod_{k\mid n}\left(2^{n/k}-1\right)^{\mu(k)}.$$
The second form matches the efficient loop structure directly: when \(\mu(k)=1\) we multiply by \(2^m-1\), when \(\mu(k)=-1\) we multiply by its modular inverse, and when \(\mu(k)=0\) nothing happens.
For a fixed \(n\), each divisor \(d\mid n\) is either excluded from a subset or included with weight \(C(d)\). Therefore
$$A(n)=\prod_{d\mid n}\left(1+C(d)\right)$$
is exactly the generating product for all subsets of divisors of \(n\). Expanding it gives
$$A(n)=\sum_{S\subseteq D(n)} \prod_{d\in S} C(d),$$
where \(D(n)\) denotes the divisor set of \(n\). With the convention used by the direct check, \(\operatorname{lcm}(\emptyset)=1\) and the empty subset has weight \(1\).
Every divisor selected in a subset \(S\) divides \(n\), so \(\operatorname{lcm}(S)\) is itself a divisor of \(n\). Define \(P(m)\) as the total weight of those subsets whose least common multiple is exactly \(m\). Then every term in the expansion of \(A(n)\) belongs to exactly one divisor \(m\mid n\), and therefore
$$A(n)=\sum_{m\mid n} P(m).$$
This is the crucial compression step: instead of remembering the subset itself, we only remember the final lcm that the subset generates.
The previous identity is a divisor sum, so Möbius inversion gives
$$P(n)=\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
That formula removes all contributions that already belong to proper divisors of \(n\). It replaces exponential subset enumeration with a purely arithmetic transform.
The required total is
$$Q(N)=\sum_{n\le N}P(n)=\sum_{n\le N}\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
Write \(n=md\). Then
$$Q(N)=\sum_{m\le N} A(m)\sum_{d\le N/m}\mu(d)=\sum_{m\le N} A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
This is the final form used by the implementations. Once all values \(A(m)\) and the prefix values of \(M\) are known, the answer is obtained in one linear sweep.
Using the cyclotomic product,
$$C(6)=\frac{(2^6-1)(2^1-1)}{(2^2-1)(2^3-1)}=\frac{63\cdot1}{3\cdot7}=3.$$
Together with \(C(1)=1\), \(C(2)=3\), and \(C(3)=7\), this gives
$$A(6)=\left(1+C(1)\right)\left(1+C(2)\right)\left(1+C(3)\right)\left(1+C(6)\right)=2\cdot4\cdot8\cdot4=256.$$
We also have \(A(1)=2\), \(A(2)=8\), and \(A(3)=16\). Möbius inversion yields
$$P(6)=A(6)-A(3)-A(2)+A(1)=256-16-8+2=234.$$
For the cumulative quantity we use \(A(4)=48\), \(A(5)=64\), and the Mertens values \(M(6)=-1\), \(M(3)=-1\), \(M(2)=0\), \(M(1)=1\). Therefore
$$Q(6)=2(-1)+8(-1)+16(0)+48(1)+64(1)+256(1)=358,$$
which agrees with direct subset enumeration on small input.
The C++, Python, and Java implementations follow the same pipeline. First they compute the Möbius function up to \(N\) with a linear sieve and convert it into prefix Mertens values modulo \(10^9+7\).
Next they precompute the sequence \(2^m-1 \pmod{10^9+7}\) together with modular inverses. A divisor-style loop then constructs every \(C(n)=\Phi_n(2)\) simultaneously by applying the Möbius product to all multiples of each index.
After that, a second divisor loop multiplies \(1+C(d)\) into every multiple of \(d\). This builds the generating product \(A(n)\) for all \(n\le N\) at once.
The final pass accumulates
$$A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
for all \(m\) from \(1\) to \(N\). A small exact check on tiny inputs confirms that this transformed formula matches explicit subset enumeration.
The linear sieve is \(O(N)\). Constructing all cyclotomic values \(C(n)\) uses a harmonic divisor loop of size \(\sum_{k\le N}\lfloor N/k\rfloor = O(N\log N)\), and building all products \(A(n)\) has the same order. The final Mertens-weighted accumulation is \(O(N)\). Hence the overall running time is \(O(N\log N)\), while the arrays for Möbius values, prefix sums, cyclotomic values, and divisor products require \(O(N)\) memory.
Für jede positive ganze Zahl \(n\) betrachtet man alle Teilmengen \(S\) der Teiler von \(n\). Einer solchen Teilmenge wird das Gewicht
$$w(S)=\prod_{d\in S}\Phi_d(2)$$
zugeordnet, wobei \(\Phi_d(x)\) das \(d\)-te Kreisteilungspolynom ist. Sei \(P(n)\) das Gesamtgewicht aller Teilmengen, deren kleinstes gemeinsames Vielfaches genau \(n\) ist. Gesucht ist die kumulative Summe
$$Q(N)=\sum_{n=1}^{N} P(n),$$
berechnet modulo \(10^9+7\) für \(N=10^7\). Eine direkte Suche müsste für jedes \(n\) alle Teilmengen der Teiler durchgehen; die schnelle Lösung ersetzt das durch Divisorprodukte, Möbius-Umkehr und Mertens-Präfixsummen.
Wir schreiben \(\mu\) für die Möbius-Funktion und \(M(x)=\sum_{k\le x}\mu(k)\) für die Mertens-Funktion. Die Implementierungen beruhen auf der folgenden Kette von Umformungen.
Aus der klassischen Faktorisierung
$$x^n-1=\prod_{d\mid n}\Phi_d(x)$$
erhält man per Möbius-Umkehr auf dem Divisorverband
$$\Phi_n(x)=\prod_{d\mid n}\left(x^d-1\right)^{\mu(n/d)}.$$
Für \(x=2\) definieren wir damit
$$C(n)=\Phi_n(2)=\prod_{d\mid n}\left(2^d-1\right)^{\mu(n/d)}=\prod_{k\mid n}\left(2^{n/k}-1\right)^{\mu(k)}.$$
Die zweite Schreibweise passt direkt zur effizienten Schleife: Bei \(\mu(k)=1\) wird mit \(2^m-1\) multipliziert, bei \(\mu(k)=-1\) mit dem modularen Inversen, und bei \(\mu(k)=0\) entfällt der Beitrag.
Für ein festes \(n\) wird jeder Teiler \(d\mid n\) entweder nicht gewählt oder mit Gewicht \(C(d)\) gewählt. Deshalb ist
$$A(n)=\prod_{d\mid n}\left(1+C(d)\right)$$
genau das erzeugende Produkt aller Teilmengen der Teiler von \(n\). Nach dem Ausmultiplizieren erhält man
$$A(n)=\sum_{S\subseteq D(n)} \prod_{d\in S} C(d),$$
wobei \(D(n)\) die Teilermenge von \(n\) bezeichnet. In der direkten Kontrolle gilt die Konvention \(\operatorname{lcm}(\emptyset)=1\), und die leere Menge hat Gewicht \(1\).
Jeder gewählte Teiler in einer Teilmenge \(S\) teilt \(n\), also ist auch \(\operatorname{lcm}(S)\) ein Teiler von \(n\). Definiere \(P(m)\) als das Gesamtgewicht aller Teilmengen mit kgV genau \(m\). Dann gehört jeder Summand in der Entwicklung von \(A(n)\) genau zu einem Divisor \(m\mid n\), also
$$A(n)=\sum_{m\mid n} P(m).$$
Das ist der entscheidende Verdichtungsschritt: Statt die Teilmenge selbst zu speichern, genügt es, ihr endgültiges kgV zu kennen.
Die vorige Beziehung ist eine Divisorsumme, daher liefert Möbius-Umkehr
$$P(n)=\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
Damit werden alle Beiträge entfernt, die bereits zu echten Teilern von \(n\) gehören. Aus exponentieller Teilmengen-Suche wird so eine rein arithmetische Transformation.
Gesucht ist
$$Q(N)=\sum_{n\le N}P(n)=\sum_{n\le N}\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
Setzt man \(n=md\), folgt
$$Q(N)=\sum_{m\le N} A(m)\sum_{d\le N/m}\mu(d)=\sum_{m\le N} A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
Genau diese Form verwenden die Implementierungen. Sobald alle Werte \(A(m)\) und die Präfixwerte von \(M\) bekannt sind, ist die Antwort nur noch ein linearer Durchlauf.
Mit dem Kreisteilungsprodukt erhält man
$$C(6)=\frac{(2^6-1)(2^1-1)}{(2^2-1)(2^3-1)}=\frac{63\cdot1}{3\cdot7}=3.$$
Zusammen mit \(C(1)=1\), \(C(2)=3\) und \(C(3)=7\) folgt
$$A(6)=\left(1+C(1)\right)\left(1+C(2)\right)\left(1+C(3)\right)\left(1+C(6)\right)=2\cdot4\cdot8\cdot4=256.$$
Außerdem gelten \(A(1)=2\), \(A(2)=8\) und \(A(3)=16\). Mit Möbius-Umkehr ergibt sich
$$P(6)=A(6)-A(3)-A(2)+A(1)=256-16-8+2=234.$$
Für die kumulative Größe verwenden wir zusätzlich \(A(4)=48\), \(A(5)=64\) sowie die Mertens-Werte \(M(6)=-1\), \(M(3)=-1\), \(M(2)=0\), \(M(1)=1\). Damit
$$Q(6)=2(-1)+8(-1)+16(0)+48(1)+64(1)+256(1)=358,$$
genau wie bei expliziter Teilmengen-Enumeration für kleine Eingaben.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Pipeline. Zuerst berechnen sie die Möbius-Funktion bis \(N\) mit einem linearen Sieb und bilden daraus die Präfixwerte der Mertens-Funktion modulo \(10^9+7\).
Anschließend werden die Werte \(2^m-1 \pmod{10^9+7}\) und die zugehörigen modularen Inversen vorab erzeugt. Eine divisorartige Schleife konstruiert dann alle Werte \(C(n)=\Phi_n(2)\) gleichzeitig, indem sie das Möbius-Produkt auf alle Vielfachen jedes Index anwendet.
Danach multipliziert eine zweite Divisorschleife den Faktor \(1+C(d)\) in alle Vielfachen von \(d\). So entsteht das erzeugende Produkt \(A(n)\) für alle \(n\le N\) parallel.
Im letzten Durchlauf wird
$$A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
für alle \(m\) von \(1\) bis \(N\) aufsummiert. Eine kleine exakte Kontrolle auf winzigen Eingaben bestätigt, dass diese transformierte Formel mit der direkten Teilmengen-Zählung übereinstimmt.
Das lineare Sieb kostet \(O(N)\). Die Konstruktion aller Kreisteilungswerte \(C(n)\) verwendet eine harmonische Divisorschleife der Größe \(\sum_{k\le N}\lfloor N/k\rfloor = O(N\log N)\), und der Aufbau aller Produkte \(A(n)\) hat dieselbe Größenordnung. Die abschließende Mertens-gewichtete Summe ist \(O(N)\). Insgesamt beträgt die Laufzeit also \(O(N\log N)\), während die Arrays für Möbius-Werte, Präfixsummen, Kreisteilungswerte und Divisorprodukte \(O(N)\) Speicher benötigen.
Her pozitif tamsayı \(n\) için, \(n\)'in bölenlerinden oluşan tüm alt kümeleri \(S\) düşünülür. Böyle bir alt kümeye
$$w(S)=\prod_{d\in S}\Phi_d(2)$$
ağırlığı verilir; burada \(\Phi_d(x)\), \(d\). cyclotomic polinomdur. En küçük ortak katı tam olarak \(n\) olan alt kümelerin toplam ağırlığını \(P(n)\) ile gösterelim. İstenen kümülatif değer
$$Q(N)=\sum_{n=1}^{N} P(n),$$
ve sonuç \(N=10^7\) için \(10^9+7\) modunda hesaplanır. Ham yaklaşım her \(n\) için bütün bölen alt kümelerini denemek zorunda kalır; hızlı çözüm bunu bölen çarpımlarına, Möbius ters dönüşümüne ve Mertens ön toplamlarına çevirir.
\(\mu\) Möbius fonksiyonu, \(M(x)=\sum_{k\le x}\mu(k)\) ise Mertens fonksiyonu olsun. Uygulamalar aşağıdaki özdeşlik zincirine dayanır.
Klasik çarpanlara ayırma
$$x^n-1=\prod_{d\mid n}\Phi_d(x)$$
bölen kafesinde ters çevrilince
$$\Phi_n(x)=\prod_{d\mid n}\left(x^d-1\right)^{\mu(n/d)}$$
elde edilir. \(x=2\) konursa
$$C(n)=\Phi_n(2)=\prod_{d\mid n}\left(2^d-1\right)^{\mu(n/d)}=\prod_{k\mid n}\left(2^{n/k}-1\right)^{\mu(k)}$$
tanımını yaparız. İkinci yazım verimli döngü yapısına doğrudan uyar: \(\mu(k)=1\) ise \(2^m-1\) ile çarpılır, \(\mu(k)=-1\) ise modüler tersiyle çarpılır, \(\mu(k)=0\) ise hiçbir katkı gelmez.
Sabit bir \(n\) için her bölen \(d\mid n\) ya seçilmez ya da \(C(d)\) ağırlığıyla seçilir. Bu yüzden
$$A(n)=\prod_{d\mid n}\left(1+C(d)\right)$$
ifadesi, \(n\)'in bölenlerinin bütün alt kümeleri için tam oluşturucu çarpımdır. Açınca
$$A(n)=\sum_{S\subseteq D(n)} \prod_{d\in S} C(d)$$
elde edilir; burada \(D(n)\), \(n\)'in bölen kümesidir. Doğrudan küçük kontrolle uyumlu olarak \(\operatorname{lcm}(\emptyset)=1\) ve boş kümenin ağırlığı \(1\) kabul edilir.
Bir alt kümede seçilen her bölen \(n\)'i böldüğü için \(\operatorname{lcm}(S)\) de \(n\)'in bir bölenidir. EKOK'u tam olarak \(m\) olan alt kümelerin toplam ağırlığını \(P(m)\) ile tanımlayalım. O zaman \(A(n)\)'in açılımındaki her terim tam olarak bir \(m\mid n\) bölenine aittir ve
$$A(n)=\sum_{m\mid n} P(m)$$
olur. Kritik sıkıştırma adımı budur: alt kümenin kendisini değil, ürettiği son EKOK'u takip ederiz.
Önceki ilişki bir bölen toplamı olduğundan Möbius ters dönüşümü
$$P(n)=\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right)$$
sonucunu verir. Böylece aslında \(n\)'in uygun alt bölenlerine ait olan katkılar temizlenir. Üstel büyüklükte alt küme dolaşımı, salt aritmetik bir dönüşüme dönüşür.
İstenen toplam
$$Q(N)=\sum_{n\le N}P(n)=\sum_{n\le N}\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right)$$
şeklindedir. \(n=md\) yazarsak
$$Q(N)=\sum_{m\le N} A(m)\sum_{d\le N/m}\mu(d)=\sum_{m\le N} A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
elde edilir. Uygulamanın kullandığı son kapalı form budur. \(A(m)\) ve \(M\)'in ön toplamları hazırsa cevap tek doğrusal geçişte bulunur.
Cyclotomic çarpımdan
$$C(6)=\frac{(2^6-1)(2^1-1)}{(2^2-1)(2^3-1)}=\frac{63\cdot1}{3\cdot7}=3$$
bulunur. Ayrıca \(C(1)=1\), \(C(2)=3\) ve \(C(3)=7\) olduğundan
$$A(6)=\left(1+C(1)\right)\left(1+C(2)\right)\left(1+C(3)\right)\left(1+C(6)\right)=2\cdot4\cdot8\cdot4=256.$$
Bunun yanında \(A(1)=2\), \(A(2)=8\), \(A(3)=16\) değerleri vardır. Möbius ters dönüşümüyle
$$P(6)=A(6)-A(3)-A(2)+A(1)=256-16-8+2=234$$
çıkar. Kümülatif toplam için \(A(4)=48\), \(A(5)=64\) ve \(M(6)=-1\), \(M(3)=-1\), \(M(2)=0\), \(M(1)=1\) kullanılır. Böylece
$$Q(6)=2(-1)+8(-1)+16(0)+48(1)+64(1)+256(1)=358,$$
ki bu da küçük girişlerde açık alt küme sayımıyla aynı sonucu verir.
C++, Python ve Java uygulamaları aynı boru hattını izler. Önce lineer bir elek ile \(N\)'e kadar Möbius fonksiyonu hesaplanır ve bundan \(10^9+7\) modunda Mertens ön toplamları üretilir.
Daha sonra \(2^m-1 \pmod{10^9+7}\) dizisi ve bunların modüler tersleri önceden hazırlanır. Bölen tabanlı bir döngü, Möbius çarpımını her indeksin tüm katlarına uygulayarak bütün \(C(n)=\Phi_n(2)\) değerlerini aynı anda kurar.
Ardından ikinci bir bölen döngüsü \(1+C(d)\) çarpanını \(d\)'nin tüm katlarına uygular. Böylece bütün \(n\le N\) için \(A(n)\) üretici çarpımı aynı anda oluşur.
Son geçişte
$$A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
ifadesi \(m=1\)'den \(N\)'e kadar toplanır. Küçük girdilerde yapılan tam karşılaştırma, dönüştürülmüş formülün açık alt küme sayımıyla birebir örtüştüğünü doğrular.
Lineer elek \(O(N)\) zaman alır. Bütün cyclotomic değerleri \(C(n)\) için kullanılan harmonik bölen döngüsünün büyüklüğü \(\sum_{k\le N}\lfloor N/k\rfloor = O(N\log N)\) düzeyindedir; tüm \(A(n)\) çarpımlarını kurmak da aynı büyüklüktedir. Son Mertens ağırlıklı toplama \(O(N)\) sürer. Böylece toplam çalışma süresi \(O(N\log N)\), Möbius değerleri, ön toplamlar, cyclotomic değerler ve bölen çarpımları için gereken bellek ise \(O(N)\) olur.
Para cada entero positivo \(n\), se consideran todos los subconjuntos \(S\) de los divisores de \(n\). A cada subconjunto se le asigna el peso
$$w(S)=\prod_{d\in S}\Phi_d(2),$$
donde \(\Phi_d(x)\) es el \(d\)-ésimo polinomio ciclotómico. Sea \(P(n)\) el peso total de los subconjuntos cuyo mínimo común múltiplo es exactamente \(n\). La cantidad acumulada buscada es
$$Q(N)=\sum_{n=1}^{N} P(n),$$
calculada módulo \(10^9+7\) para \(N=10^7\). Un enfoque directo tendría que enumerar todos los subconjuntos de divisores para cada \(n\), así que la solución rápida reemplaza esa búsqueda por productos sobre divisores, inversión de Möbius y prefijos de Mertens.
Escribimos \(\mu\) para la función de Möbius y \(M(x)=\sum_{k\le x}\mu(k)\) para la función de Mertens. Las implementaciones se apoyan en la siguiente cadena de identidades.
La factorización clásica
$$x^n-1=\prod_{d\mid n}\Phi_d(x)$$
puede invertirse en la retícula de divisores, lo que da
$$\Phi_n(x)=\prod_{d\mid n}\left(x^d-1\right)^{\mu(n/d)}.$$
Al evaluar en \(x=2\), definimos
$$C(n)=\Phi_n(2)=\prod_{d\mid n}\left(2^d-1\right)^{\mu(n/d)}=\prod_{k\mid n}\left(2^{n/k}-1\right)^{\mu(k)}.$$
La segunda forma coincide de manera natural con el bucle eficiente: si \(\mu(k)=1\) se multiplica por \(2^m-1\), si \(\mu(k)=-1\) se multiplica por su inverso modular, y si \(\mu(k)=0\) no hay aporte.
Para un \(n\) fijo, cada divisor \(d\mid n\) se excluye o se incluye con peso \(C(d)\). Por lo tanto,
$$A(n)=\prod_{d\mid n}\left(1+C(d)\right)$$
es exactamente el producto generador de todos los subconjuntos de divisores de \(n\). Al expandirlo obtenemos
$$A(n)=\sum_{S\subseteq D(n)} \prod_{d\in S} C(d),$$
donde \(D(n)\) denota el conjunto de divisores de \(n\). En la comprobación directa se adopta la convención \(\operatorname{lcm}(\emptyset)=1\), y el subconjunto vacío tiene peso \(1\).
Todo divisor elegido en un subconjunto \(S\) divide a \(n\), así que \(\operatorname{lcm}(S)\) también es un divisor de \(n\). Definimos \(P(m)\) como el peso total de los subconjuntos cuyo mínimo común múltiplo es exactamente \(m\). Entonces cada término de la expansión de \(A(n)\) pertenece a un único divisor \(m\mid n\), y por tanto
$$A(n)=\sum_{m\mid n} P(m).$$
Este es el paso de compresión decisivo: en lugar de recordar el subconjunto completo, basta con recordar el mcm final que produce.
La identidad anterior es una suma sobre divisores, así que la inversión de Möbius produce
$$P(n)=\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
Esa fórmula elimina todas las contribuciones que ya pertenecen a divisores propios de \(n\). Así, la enumeración exponencial de subconjuntos se reemplaza por una transformación puramente aritmética.
La cantidad buscada es
$$Q(N)=\sum_{n\le N}P(n)=\sum_{n\le N}\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
Escribiendo \(n=md\), se obtiene
$$Q(N)=\sum_{m\le N} A(m)\sum_{d\le N/m}\mu(d)=\sum_{m\le N} A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
Esta es la forma final usada por las implementaciones. Una vez conocidas todas las cantidades \(A(m)\) y los prefijos de \(M\), la respuesta sale de un único recorrido lineal.
Usando el producto ciclotómico,
$$C(6)=\frac{(2^6-1)(2^1-1)}{(2^2-1)(2^3-1)}=\frac{63\cdot1}{3\cdot7}=3.$$
Junto con \(C(1)=1\), \(C(2)=3\) y \(C(3)=7\), resulta
$$A(6)=\left(1+C(1)\right)\left(1+C(2)\right)\left(1+C(3)\right)\left(1+C(6)\right)=2\cdot4\cdot8\cdot4=256.$$
Además, \(A(1)=2\), \(A(2)=8\) y \(A(3)=16\). La inversión de Möbius da
$$P(6)=A(6)-A(3)-A(2)+A(1)=256-16-8+2=234.$$
Para la cantidad acumulada usamos también \(A(4)=48\), \(A(5)=64\), y los valores \(M(6)=-1\), \(M(3)=-1\), \(M(2)=0\), \(M(1)=1\). Entonces
$$Q(6)=2(-1)+8(-1)+16(0)+48(1)+64(1)+256(1)=358,$$
en acuerdo con la enumeración explícita de subconjuntos en entradas pequeñas.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero calculan la función de Möbius hasta \(N\) mediante una criba lineal y la convierten en prefijos de Mertens módulo \(10^9+7\).
Después precomputan la sucesión \(2^m-1 \pmod{10^9+7}\) y sus inversos modulares. Un bucle de estilo divisor construye simultáneamente todos los valores \(C(n)=\Phi_n(2)\) aplicando el producto de Möbius a todos los múltiplos de cada índice.
Luego un segundo bucle sobre divisores multiplica \(1+C(d)\) en todos los múltiplos de \(d\). De ese modo se forma el producto generador \(A(n)\) para todos los \(n\le N\) al mismo tiempo.
En la pasada final se acumula
$$A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
para todos los \(m\) entre \(1\) y \(N\). Una comprobación exacta sobre casos muy pequeños confirma que esta fórmula transformada coincide con la enumeración explícita.
La criba lineal cuesta \(O(N)\). La construcción de todos los valores ciclotómicos \(C(n)\) usa un bucle armónico sobre divisores de tamaño \(\sum_{k\le N}\lfloor N/k\rfloor = O(N\log N)\), y construir todos los productos \(A(n)\) tiene el mismo orden. La suma final ponderada por Mertens es \(O(N)\). En consecuencia, el tiempo total es \(O(N\log N)\), mientras que los arreglos para los valores de Möbius, sumas prefijo, valores ciclotómicos y productos sobre divisores requieren \(O(N)\) memoria.
对每个正整数 \(n\)，考虑 \(n\) 的所有因子子集 \(S\)。给这个子集赋予权重
$$w(S)=\prod_{d\in S}\Phi_d(2),$$
其中 \(\Phi_d(x)\) 表示第 \(d\) 个圆分多项式。记 \(P(n)\) 为所有最小公倍数恰好等于 \(n\) 的因子子集权重总和。题目要求的累计量是
$$Q(N)=\sum_{n=1}^{N} P(n),$$
并在 \(N=10^7\) 时对 \(10^9+7\) 取模。暴力做法需要对每个 \(n\) 枚举所有因子子集，复杂度会随因子个数呈指数增长，因此实现把问题改写成两个因子变换，再用 Möbius 反演消去重复计数。
记 \(\mu\) 为 Möbius 函数，\(M(x)=\sum_{k\le x}\mu(k)\) 为 Mertens 函数。快速解法建立在下面这组恒等式之上。
经典恒等式
$$x^n-1=\prod_{d\mid n}\Phi_d(x)$$
在因子格上做 Möbius 反演后，可得
$$\Phi_n(x)=\prod_{d\mid n}\left(x^d-1\right)^{\mu(n/d)}.$$
令 \(x=2\)，定义
$$C(n)=\Phi_n(2)=\prod_{d\mid n}\left(2^d-1\right)^{\mu(n/d)}=\prod_{k\mid n}\left(2^{n/k}-1\right)^{\mu(k)}.$$
第二种写法与程序中的高效循环完全对应：当 \(\mu(k)=1\) 时乘上 \(2^m-1\)，当 \(\mu(k)=-1\) 时乘上它的模逆，当 \(\mu(k)=0\) 时该项直接跳过。
对固定的 \(n\)，每个因子 \(d\mid n\) 都只有两种选择：不选，或者以权重 \(C(d)\) 被选入子集。因此
$$A(n)=\prod_{d\mid n}\left(1+C(d)\right)$$
正好是“所有因子子集”的生成乘积。把它展开后得到
$$A(n)=\sum_{S\subseteq D(n)} \prod_{d\in S} C(d),$$
其中 \(D(n)\) 表示 \(n\) 的因子集合。与小规模直接校验保持一致，这里采用约定 \(\operatorname{lcm}(\emptyset)=1\)，空集的权重为 \(1\)。
子集 \(S\) 中被选中的每个因子都整除 \(n\)，所以 \(\operatorname{lcm}(S)\) 也必然是 \(n\) 的一个因子。定义 \(P(m)\) 为所有最小公倍数恰好等于 \(m\) 的子集总权重。这样一来，\(A(n)\) 展开式中的每一项都会落入某个唯一的 \(m\mid n\)，于是
$$A(n)=\sum_{m\mid n} P(m).$$
这是整个推导中最关键的压缩步骤：我们不再记住“到底选了哪个子集”，而只记住“这个子集最终产生了哪个最小公倍数”。
上式是标准的因子求和关系，因此可以直接反演：
$$P(n)=\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
这个公式会把那些已经属于真因子的贡献剔除掉，只留下“最小公倍数第一次等于 \(n\)”的那部分权重。这样就把指数级的子集枚举转换成了纯数论的因子变换。
目标量为
$$Q(N)=\sum_{n\le N}P(n)=\sum_{n\le N}\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
把 \(n\) 写成 \(n=md\)，便得到
$$Q(N)=\sum_{m\le N} A(m)\sum_{d\le N/m}\mu(d)=\sum_{m\le N} A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
这就是实现最终使用的闭式。只要全部 \(A(m)\) 和 Mertens 前缀值都已经准备好，最后答案就是一次从 \(1\) 到 \(N\) 的线性累加。
由圆分乘积公式可得
$$C(6)=\frac{(2^6-1)(2^1-1)}{(2^2-1)(2^3-1)}=\frac{63\cdot1}{3\cdot7}=3.$$
再结合 \(C(1)=1\)、\(C(2)=3\)、\(C(3)=7\)，得到
$$A(6)=\left(1+C(1)\right)\left(1+C(2)\right)\left(1+C(3)\right)\left(1+C(6)\right)=2\cdot4\cdot8\cdot4=256.$$
同时有 \(A(1)=2\)、\(A(2)=8\)、\(A(3)=16\)。代入 Möbius 反演：
$$P(6)=A(6)-A(3)-A(2)+A(1)=256-16-8+2=234.$$
如果继续计算累计量，再用到 \(A(4)=48\)、\(A(5)=64\)，以及 \(M(6)=-1\)、\(M(3)=-1\)、\(M(2)=0\)、\(M(1)=1\)，便有
$$Q(6)=2(-1)+8(-1)+16(0)+48(1)+64(1)+256(1)=358,$$
与小输入下直接枚举因子子集的结果完全一致。
C++、Python 和 Java 实现都遵循同一条流水线。第一步是用线性筛求出所有 \(1\le n\le N\) 的 Möbius 函数值，并把它们转成 \(10^9+7\) 模下的 Mertens 前缀和。
第二步预计算序列 \(2^m-1 \pmod{10^9+7}\) 及其模逆。随后通过一层按因子展开的循环，把 Möbius 乘积同时作用到每个下标的所有倍数上，从而一次性构造出全部 \(C(n)=\Phi_n(2)\)。
第三步再做一层因子循环，把 \(1+C(d)\) 乘进所有 \(d\) 的倍数里，于是所有 \(n\le N\) 的生成乘积 \(A(n)\) 就被并行构造出来了。
最后一遍遍历只需累加
$$A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
在 \(m=1,2,\dots,N\) 上的值。实现里还保留了一个非常小规模的精确校验，用来确认这个变换公式与显式子集枚举完全相符。
线性筛部分是 \(O(N)\)。构造所有圆分值 \(C(n)\) 需要一层调和级数规模的因子循环，其总工作量为 \(\sum_{k\le N}\lfloor N/k\rfloor = O(N\log N)\)；构造全部 \(A(n)\) 也是同一数量级。最终的 Mertens 加权求和是 \(O(N)\)。因此总时间复杂度为 \(O(N\log N)\)，而保存 Möbius 值、前缀和、圆分值和因子乘积的数组需要 \(O(N)\) 空间。
Для каждого положительного целого \(n\) рассматриваются все подмножества \(S\) множества делителей числа \(n\). Такому подмножеству приписывается вес
$$w(S)=\prod_{d\in S}\Phi_d(2),$$
где \(\Phi_d(x)\) обозначает \(d\)-й циклотомический многочлен. Пусть \(P(n)\) означает суммарный вес всех подмножеств, для которых наименьшее общее кратное равно ровно \(n\). Требуется найти накопленную величину
$$Q(N)=\sum_{n=1}^{N} P(n),$$
по модулю \(10^9+7\) при \(N=10^7\). Прямой перебор должен был бы для каждого \(n\) проходить по всем подмножествам его делителей, поэтому быстрая схема заменяет эту процедуру произведениями по делителям, обращением Мёбиуса и префиксами функции Мертенса.
Обозначим через \(\mu\) функцию Мёбиуса, а через \(M(x)=\sum_{k\le x}\mu(k)\) функцию Мертенса. Реализация опирается на следующую цепочку тождеств.
Классическое разложение
$$x^n-1=\prod_{d\mid n}\Phi_d(x)$$
обращается на решетке делителей и дает
$$\Phi_n(x)=\prod_{d\mid n}\left(x^d-1\right)^{\mu(n/d)}.$$
Подставляя \(x=2\), вводим обозначение
$$C(n)=\Phi_n(2)=\prod_{d\mid n}\left(2^d-1\right)^{\mu(n/d)}=\prod_{k\mid n}\left(2^{n/k}-1\right)^{\mu(k)}.$$
Вторая форма напрямую совпадает с эффективным циклом: при \(\mu(k)=1\) нужно умножать на \(2^m-1\), при \(\mu(k)=-1\) умножать на обратный по модулю элемент, а при \(\mu(k)=0\) ничего не делать.
Для фиксированного \(n\) каждый делитель \(d\mid n\) либо не выбирается, либо выбирается с весом \(C(d)\). Поэтому
$$A(n)=\prod_{d\mid n}\left(1+C(d)\right)$$
является точным производящим произведением для всех подмножеств делителей числа \(n\). После раскрытия скобок получаем
$$A(n)=\sum_{S\subseteq D(n)} \prod_{d\in S} C(d),$$
где \(D(n)\) обозначает множество делителей числа \(n\). В прямой проверке используется соглашение \(\operatorname{lcm}(\emptyset)=1\), а вес пустого множества равен \(1\).
Каждый выбранный делитель из подмножества \(S\) делит \(n\), следовательно, \(\operatorname{lcm}(S)\) тоже является делителем \(n\). Обозначим через \(P(m)\) суммарный вес всех подмножеств, у которых НОК равен ровно \(m\). Тогда каждый член в раскрытии \(A(n)\) относится к единственному делителю \(m\mid n\), и потому
$$A(n)=\sum_{m\mid n} P(m).$$
Это и есть ключевое сжатие задачи: вместо того чтобы помнить само подмножество, достаточно помнить конечный НОК, который оно порождает.
Предыдущее равенство является суммой по делителям, поэтому обращение Мёбиуса дает
$$P(n)=\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
Эта формула вычитает все вклады, которые уже относятся к собственным делителям числа \(n\). Экспоненциальный перебор подмножеств заменяется чисто арифметическим преобразованием.
Нужная величина равна
$$Q(N)=\sum_{n\le N}P(n)=\sum_{n\le N}\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
Если написать \(n=md\), то получится
$$Q(N)=\sum_{m\le N} A(m)\sum_{d\le N/m}\mu(d)=\sum_{m\le N} A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
Именно эта форма используется в реализации. Когда все значения \(A(m)\) и префиксы функции \(M\) уже посчитаны, ответ находится одним линейным проходом.
Из циклотомического произведения имеем
$$C(6)=\frac{(2^6-1)(2^1-1)}{(2^2-1)(2^3-1)}=\frac{63\cdot1}{3\cdot7}=3.$$
Совместно с \(C(1)=1\), \(C(2)=3\) и \(C(3)=7\) это дает
$$A(6)=\left(1+C(1)\right)\left(1+C(2)\right)\left(1+C(3)\right)\left(1+C(6)\right)=2\cdot4\cdot8\cdot4=256.$$
Кроме того, \(A(1)=2\), \(A(2)=8\) и \(A(3)=16\). Тогда по обращению Мёбиуса
$$P(6)=A(6)-A(3)-A(2)+A(1)=256-16-8+2=234.$$
Для накопленной суммы берем еще \(A(4)=48\), \(A(5)=64\) и значения \(M(6)=-1\), \(M(3)=-1\), \(M(2)=0\), \(M(1)=1\). Получаем
$$Q(6)=2(-1)+8(-1)+16(0)+48(1)+64(1)+256(1)=358,$$
что совпадает с явным перебором подмножеств на малом примере.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала линейным решетом вычисляются значения функции Мёбиуса для всех \(1\le n\le N\), а затем из них строятся префиксы функции Мертенса по модулю \(10^9+7\).
После этого заранее считаются значения \(2^m-1 \pmod{10^9+7}\) и соответствующие обратные элементы. Далее цикл по делителям одновременно строит все \(C(n)=\Phi_n(2)\), применяя произведение с показателями \(\mu\) ко всем кратным каждого индекса.
Затем второй цикл по делителям домножает множитель \(1+C(d)\) во все кратные \(d\). Так производящее произведение \(A(n)\) получается сразу для всех \(n\le N\).
В последнем проходе накапливается
$$A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
для всех \(m\) от \(1\) до \(N\). Небольшая точная проверка на крошечных входах подтверждает, что преобразованная формула в точности совпадает с явным перебором подмножеств.
Линейное решето работает за \(O(N)\). Построение всех циклотомических значений \(C(n)\) использует гармонический цикл по делителям размера \(\sum_{k\le N}\lfloor N/k\rfloor = O(N\log N)\), и построение всех произведений \(A(n)\) имеет тот же порядок. Итоговая сумма с весами Мертенса вычисляется за \(O(N)\). Следовательно, суммарная асимптотика по времени равна \(O(N\log N)\), а массивы для значений Мёбиуса, префиксных сумм, циклотомических значений и произведений по делителям требуют \(O(N)\) памяти.
لكل عدد صحيح موجب \(n\)، ننظر إلى جميع المجموعات الجزئية \(S\) من قواسم \(n\). ويُعطى كل اختيار الوزن
$$w(S)=\prod_{d\in S}\Phi_d(2),$$
حيث تمثل \(\Phi_d(x)\) كثيرة الحدود الدورية ذات الرتبة \(d\). ولتكن \(P(n)\) مجموع الأوزان لكل المجموعات الجزئية التي يكون المضاعف المشترك الأصغر لها مساويًا تمامًا لـ \(n\). والكمية التراكمية المطلوبة هي
$$Q(N)=\sum_{n=1}^{N} P(n),$$
مع الحساب بترديد \(10^9+7\) عند \(N=10^7\). الحل المباشر سيضطر إلى تعداد جميع مجموعات القواسم لكل \(n\)، لذلك تحوّل الخوارزمية السريعة المسألة إلى جداءات على القواسم ثم تستخدم عكس Möbius ومجاميع Mertens التراكمية.
لنكتب \(\mu\) من أجل دالة Möbius، ولتكن \(M(x)=\sum_{k\le x}\mu(k)\) دالة Mertens. تعتمد الحلول على السلسلة التالية من الهويات.
من التحليل الكلاسيكي
$$x^n-1=\prod_{d\mid n}\Phi_d(x)$$
يمكن إجراء عكس Möbius على شبكة القواسم للحصول على
$$\Phi_n(x)=\prod_{d\mid n}\left(x^d-1\right)^{\mu(n/d)}.$$
وبالتعويض بـ \(x=2\) نعرّف
$$C(n)=\Phi_n(2)=\prod_{d\mid n}\left(2^d-1\right)^{\mu(n/d)}=\prod_{k\mid n}\left(2^{n/k}-1\right)^{\mu(k)}.$$
الصيغة الثانية هي التي تناسب البنية الفعالة في التنفيذ مباشرة: إذا كانت \(\mu(k)=1\) نضرب في \(2^m-1\)، وإذا كانت \(\mu(k)=-1\) نضرب في معكوسه المعياري، وإذا كانت \(\mu(k)=0\) فلا يوجد أثر لهذا الحد.
لعدد ثابت \(n\)، كل قاسم \(d\mid n\) إما يُستبعد من المجموعة أو يُختار بوزن \(C(d)\). لذلك فإن
$$A(n)=\prod_{d\mid n}\left(1+C(d)\right)$$
هو الجداء المولِّد الدقيق لجميع المجموعات الجزئية لقواسم \(n\). وبعد التوسيع نحصل على
$$A(n)=\sum_{S\subseteq D(n)} \prod_{d\in S} C(d),$$
حيث \(D(n)\) هي مجموعة قواسم \(n\). وفي الفحص المباشر الصغير تُستعمل الاتفاقية \(\operatorname{lcm}(\emptyset)=1\)، ويكون وزن المجموعة الفارغة مساويًا لـ \(1\).
كل قاسم مختار في مجموعة جزئية \(S\) يقسم \(n\)، ولذلك فإن \(\operatorname{lcm}(S)\) نفسه قاسم لـ \(n\). لنعرّف \(P(m)\) بأنه مجموع أوزان جميع المجموعات الجزئية التي يكون مضاعفها المشترك الأصغر مساويًا تمامًا لـ \(m\). عندئذ ينتمي كل حد في توسعة \(A(n)\) إلى قاسم وحيد \(m\mid n\)، ومن ثم
$$A(n)=\sum_{m\mid n} P(m).$$
هذه هي خطوة الضغط الأساسية: بدلًا من تتبع المجموعة الجزئية نفسها، نكتفي بتتبع قيمة المضاعف المشترك الأصغر النهائية التي تولدها.
العلاقة السابقة هي مجموع على القواسم، ولذلك يعطينا عكس Möbius
$$P(n)=\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
هذه الصيغة تزيل كل المساهمات التي تعود في الأصل إلى قواسم أصغر من \(n\). وهكذا يتحول تعداد المجموعات الجزئية ذي النمو الأسي إلى تحويل حسابي بحت.
الكمية المطلوبة هي
$$Q(N)=\sum_{n\le N}P(n)=\sum_{n\le N}\sum_{d\mid n}\mu(d)\,A\!\left(\frac{n}{d}\right).$$
وبكتابة \(n=md\) نحصل على
$$Q(N)=\sum_{m\le N} A(m)\sum_{d\le N/m}\mu(d)=\sum_{m\le N} A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
هذه هي الصيغة النهائية التي تعتمدها الحلول. وما إن تصبح جميع قيم \(A(m)\) وقيم Mertens التراكمية جاهزة، حتى يمكن استخراج الجواب بمرور خطي واحد.
من صيغة الجداء الدوري نحصل على
$$C(6)=\frac{(2^6-1)(2^1-1)}{(2^2-1)(2^3-1)}=\frac{63\cdot1}{3\cdot7}=3.$$
ومع \(C(1)=1\) و\(C(2)=3\) و\(C(3)=7\) ينتج
$$A(6)=\left(1+C(1)\right)\left(1+C(2)\right)\left(1+C(3)\right)\left(1+C(6)\right)=2\cdot4\cdot8\cdot4=256.$$
ولدينا أيضًا \(A(1)=2\) و\(A(2)=8\) و\(A(3)=16\). ومن عكس Möbius نحصل على
$$P(6)=A(6)-A(3)-A(2)+A(1)=256-16-8+2=234.$$
ولإكمال المجموع التراكمي نستخدم كذلك \(A(4)=48\) و\(A(5)=64\)، مع القيم \(M(6)=-1\) و\(M(3)=-1\) و\(M(2)=0\) و\(M(1)=1\). ومن ثم
$$Q(6)=2(-1)+8(-1)+16(0)+48(1)+64(1)+256(1)=358,$$
وهو نفس الناتج الذي نحصل عليه عند تعداد المجموعات الجزئية صراحة على دخل صغير.
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولًا تُحسب دالة Möbius حتى \(N\) بواسطة غربال خطي، ثم تُحوَّل إلى مجاميع بادئة لدالة Mertens بترديد \(10^9+7\).
بعد ذلك تُحسب القيم \(2^m-1 \pmod{10^9+7}\) ومعكوساتها المعيارية مسبقًا. ثم تُستعمل حلقة على القواسم لبناء جميع القيم \(C(n)=\Phi_n(2)\) دفعة واحدة عبر تطبيق جداء Möbius على كل مضاعفات كل فهرس.
بعدها تأتي حلقة ثانية على القواسم لضرب العامل \(1+C(d)\) في كل مضاعفات \(d\). بهذه الطريقة يتكوَّن الجداء المولِّد \(A(n)\) لجميع \(n\le N\) في الوقت نفسه.
وفي المرور الأخير تُجمع الكمية
$$A(m)\,M\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
لكل \(m\) من \(1\) حتى \(N\). كما يوجد فحص صغير دقيق على مدخلات متناهية الصغر للتأكد من أن الصيغة المحوَّلة تطابق التعداد الصريح تمامًا.
الغربال الخطي يكلف \(O(N)\). وبناء جميع القيم الدورية \(C(n)\) يستخدم حلقة توافقية على القواسم بحجم \(\sum_{k\le N}\lfloor N/k\rfloor = O(N\log N)\)، كما أن بناء جميع الجداءات \(A(n)\) له نفس الرتبة. أما الجمع النهائي الموزون بدالة Mertens فهو \(O(N)\). لذلك يكون الزمن الكلي \(O(N\log N)\)، بينما تحتاج المصفوفات الخاصة بقيم Möbius والمجاميع البادئة والقيم الدورية وجدءات القواسم إلى \(O(N)\) من الذاكرة.