For Problem 802, the C++, Python, and Java implementations evaluate the arithmetic quantity
$$S(N)=\sum_{k=1}^{N}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}\pmod{M},\qquad M=1020340567,$$
with the final input \(N=10^7\). The difficulty is not the modular arithmetic itself, but organizing the computation so that Möbius values, prefix sums, and repeated floor quotients are reused instead of recomputed.
The implementations treat the problem as a Möbius-weighted transform of the basic sequence \(A(t)=2^t\). Two ideas drive the solution: compute \(\mu(k)\) efficiently for every \(k\le N\), and exploit the fact that \(\left\lfloor N/k\right\rfloor\) stays constant on long intervals.
The exact quantity being accumulated is
$$S(N)=\sum_{k=1}^{N}\mu(k)A\!\left(\left\lfloor\frac{N}{k}\right\rfloor\right),\qquad A(t)=2^t.$$
Each index \(k\) contributes two pieces: a Möbius weight \(\mu(k)\in\{-1,0,1\}\) and a power of two determined only by the quotient \(\left\lfloor N/k\right\rfloor\). This already suggests separating number-theoretic preprocessing from the final accumulation stage.
The Möbius function is defined by
$$\mu(1)=1,$$
$$\mu(n)=0 \text{ if } p^2\mid n \text{ for some prime } p,$$
$$\mu(n)=(-1)^r \text{ if } n \text{ is a product of } r \text{ distinct primes}.$$
So integers containing a squared prime factor disappear entirely, while square-free integers contribute with alternating sign. The sum is therefore an inclusion-exclusion style filter applied to the sequence \(2^{\left\lfloor N/k\right\rfloor}\).
Define the Mertens prefix function
$$\mathcal{M}(x)=\sum_{k\le x}\mu(k).$$
Then any interval sum can be written as
$$\sum_{k=a}^{b}\mu(k)=\mathcal{M}(b)-\mathcal{M}(a-1).$$
This converts a sum of many Möbius values into a constant-time difference. That becomes useful as soon as many adjacent indices share the same quotient \(\left\lfloor N/k\right\rfloor\).
Fix a starting index \(i\) and set
$$q=\left\lfloor\frac{N}{i}\right\rfloor.$$
All indices with this same quotient form the interval
$$i\le k\le j,\qquad j=\left\lfloor\frac{N}{q}\right\rfloor.$$
For every \(k\in[i,j]\), the power of two is identical:
$$2^{\left\lfloor N/k\right\rfloor}=2^q.$$
Hence the entire block contributes
$$\sum_{k=i}^{j}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}=\left(\mathcal{M}(j)-\mathcal{M}(i-1)\right)2^q.$$
After one block is processed, the next unexplored index is \(j+1\). The number of distinct quotients is only about \(2\sqrt N\), so the accumulation stage becomes much shorter than a literal term-by-term pass.
The same exponents appear repeatedly, so the implementations build the table
$$P(t)=2^t\bmod M,\qquad 0\le t\le N.$$
Every quotient block then needs only one lookup and one modular multiplication. No repeated exponentiation is performed inside the main block sweep.
For the first ten Möbius values we have
$$\mu(1),\dots,\mu(10)=1,-1,-1,0,-1,1,-1,0,0,1.$$
The quotient blocks are
$$\begin{aligned} k=1 &: \left\lfloor 10/k\right\rfloor=10,\quad \mathcal{M}(1)-\mathcal{M}(0)=1,\quad &&1\cdot 2^{10}=1024,\\ k=2 &: \left\lfloor 10/k\right\rfloor=5,\quad \mathcal{M}(2)-\mathcal{M}(1)=-1,\quad &&-1\cdot 2^5=-32,\\ k=3 &: \left\lfloor 10/k\right\rfloor=3,\quad \mathcal{M}(3)-\mathcal{M}(2)=-1,\quad &&-1\cdot 2^3=-8,\\ 4\le k\le 5 &: \left\lfloor 10/k\right\rfloor=2,\quad \mathcal{M}(5)-\mathcal{M}(3)=-1,\quad &&-1\cdot 2^2=-4,\\ 6\le k\le 10 &: \left\lfloor 10/k\right\rfloor=1,\quad \mathcal{M}(10)-\mathcal{M}(5)=1,\quad &&1\cdot 2^1=2. \end{aligned}$$
Adding the block contributions gives
$$1024-32-8-4+2=982.$$
This example makes the structure clear: five blocks replace ten individual terms, and the savings become much larger when \(N\) is large.
The C++, Python, and Java implementations follow the same pipeline. First they build Möbius values up to \(N\) with a linear sieve that also records the smallest prime dividing each integer. This produces the correct sign for square-free numbers and automatically assigns zero to integers divisible by a squared prime.
Next the implementation forms a cumulative Mertens array and, independently, a table of powers \(2^t\bmod M\) for every \(0\le t\le N\). With those two tables ready, the final loop no longer evaluates the sum term by term. Instead it jumps from one maximal quotient block to the next, computes the total Möbius weight of that block by a prefix-sum difference, multiplies by the precomputed power of two for the shared quotient, and accumulates the result modulo \(M\).
Because some block sums are negative, the modular arithmetic is normalized before or after multiplication, depending on the language. That keeps intermediate values safe while preserving the exact arithmetic meaning of the formula.
The linear sieve runs in \(O(N)\) time and stores \(O(N)\) data. Building the Mertens prefix sums and the power table also costs \(O(N)\) time and \(O(N)\) memory. The final quotient-block sweep touches only the distinct values of \(\left\lfloor N/k\right\rfloor\), so that stage is \(O(\sqrt N)\). Overall the method is \(O(N)\) time and \(O(N)\) memory, with preprocessing dominating for \(N=10^7\).
Für Problem 802 berechnen die C++-, Python- und Java-Implementierungen die arithmetische Größe
$$S(N)=\sum_{k=1}^{N}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}\pmod{M},\qquad M=1020340567,$$
wobei im Endlauf \(N=10^7\) eingesetzt wird. Die Schwierigkeit liegt nicht in der Modulo-Arithmetik selbst, sondern darin, Möbius-Werte, Präfixsummen und wiederkehrende Quotienten \(\left\lfloor N/k\right\rfloor\) so zu organisieren, dass sie nur einmal vorbereitet und dann vielfach wiederverwendet werden.
Die Implementierungen behandeln das Problem als Möbius-gewichtete Transformation der Grundfolge \(A(t)=2^t\). Zwei Ideen sind entscheidend: \(\mu(k)\) effizient für alle \(k\le N\) berechnen und ausnutzen, dass \(\left\lfloor N/k\right\rfloor\) auf langen Intervallen konstant bleibt.
Die exakt aufsummierte Größe ist
$$S(N)=\sum_{k=1}^{N}\mu(k)A\!\left(\left\lfloor\frac{N}{k}\right\rfloor\right),\qquad A(t)=2^t.$$
Jeder Index \(k\) liefert also zwei Bestandteile: ein Möbius-Gewicht \(\mu(k)\in\{-1,0,1\}\) und eine Zweierpotenz, die nur vom Quotienten \(\left\lfloor N/k\right\rfloor\) abhängt. Das legt unmittelbar nahe, zahlentheoretische Vorarbeit und Endakkumulation zu trennen.
Für die Möbius-Funktion gilt
$$\mu(1)=1,$$
$$\mu(n)=0 \text{ falls } p^2\mid n \text{ für ein Prim } p,$$
$$\mu(n)=(-1)^r \text{ falls } n \text{ Produkt aus } r \text{ verschiedenen Primzahlen ist}.$$
Zahlen mit quadratischem Primfaktor verschwinden also komplett aus der Summe, während quadratfreie Zahlen mit wechselndem Vorzeichen beitragen. Die Summe enthält damit bereits einen Inklusions-Exklusions-Filter auf der Folge \(2^{\left\lfloor N/k\right\rfloor}\).
Definiere die Mertens-Präfixfunktion
$$\mathcal{M}(x)=\sum_{k\le x}\mu(k).$$
Dann lässt sich jede Intervallsumme schreiben als
$$\sum_{k=a}^{b}\mu(k)=\mathcal{M}(b)-\mathcal{M}(a-1).$$
Damit wird aus einer Summe vieler Möbius-Werte eine Differenz in konstanter Zeit. Genau das ist später nützlich, wenn viele benachbarte Indizes denselben Quotienten \(\left\lfloor N/k\right\rfloor\) besitzen.
Fixiere einen Startindex \(i\) und setze
$$q=\left\lfloor\frac{N}{i}\right\rfloor.$$
Alle Indizes mit demselben Quotienten bilden das Intervall
$$i\le k\le j,\qquad j=\left\lfloor\frac{N}{q}\right\rfloor.$$
Für jedes \(k\in[i,j]\) ist die Zweierpotenz identisch:
$$2^{\left\lfloor N/k\right\rfloor}=2^q.$$
Der gesamte Blockbeitrag ist also
$$\sum_{k=i}^{j}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}=\left(\mathcal{M}(j)-\mathcal{M}(i-1)\right)2^q.$$
Nach einem Block beginnt der nächste unerledigte Index bei \(j+1\). Da es nur ungefähr \(2\sqrt N\) verschiedene Quotienten gibt, ist diese Akkumulationsphase deutlich kürzer als ein rein termweises Vorgehen.
Dieselben Exponenten tauchen immer wieder auf, daher wird die Tabelle
$$P(t)=2^t\bmod M,\qquad 0\le t\le N$$
vorab aufgebaut. Jeder Quotientenblock braucht danach nur noch einen Tabellenzugriff und eine modulare Multiplikation. Im Hauptdurchlauf wird also keine Potenz neu berechnet.
Für die ersten zehn Möbius-Werte gilt
$$\mu(1),\dots,\mu(10)=1,-1,-1,0,-1,1,-1,0,0,1.$$
Die Quotientenblöcke sind
$$\begin{aligned} k=1 &: \left\lfloor 10/k\right\rfloor=10,\quad \mathcal{M}(1)-\mathcal{M}(0)=1,\quad &&1\cdot 2^{10}=1024,\\ k=2 &: \left\lfloor 10/k\right\rfloor=5,\quad \mathcal{M}(2)-\mathcal{M}(1)=-1,\quad &&-1\cdot 2^5=-32,\\ k=3 &: \left\lfloor 10/k\right\rfloor=3,\quad \mathcal{M}(3)-\mathcal{M}(2)=-1,\quad &&-1\cdot 2^3=-8,\\ 4\le k\le 5 &: \left\lfloor 10/k\right\rfloor=2,\quad \mathcal{M}(5)-\mathcal{M}(3)=-1,\quad &&-1\cdot 2^2=-4,\\ 6\le k\le 10 &: \left\lfloor 10/k\right\rfloor=1,\quad \mathcal{M}(10)-\mathcal{M}(5)=1,\quad &&1\cdot 2^1=2. \end{aligned}$$
Die Summe der Blockbeiträge ist
$$1024-32-8-4+2=982.$$
Dieses Beispiel zeigt die Struktur sehr deutlich: Fünf Blöcke ersetzen zehn Einzelterme, und bei großem \(N\) wächst der Vorteil entsprechend.
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf. Zuerst erzeugen sie mit einem linearen Sieb alle Möbius-Werte bis \(N\) und speichern zugleich den kleinsten Primteiler jeder Zahl. Dadurch bekommen quadratfreie Zahlen automatisch das richtige Vorzeichen, während Zahlen mit quadratischem Primfaktor den Wert \(0\) erhalten.
Danach baut die Implementierung eine kumulative Mertens-Tabelle und unabhängig davon eine Tabelle aller Potenzen \(2^t\bmod M\) für \(0\le t\le N\) auf. Mit diesen beiden Tabellen summiert der letzte Durchlauf nicht mehr termweise, sondern springt von einem maximalen Quotientenblock zum nächsten, berechnet das gesamte Möbius-Gewicht des Blocks über eine Präfixdifferenz, multipliziert mit der vorberechneten Zweierpotenz und addiert das Resultat modulo \(M\).
Da manche Blocksummen negativ sind, wird die Modulo-Arithmetik vor oder nach der Multiplikation normalisiert, je nach Sprache. So bleiben die Zwischenwerte in sicherem Bereich, ohne die mathematische Bedeutung der Formel zu verändern.
Das lineare Sieb benötigt \(O(N)\) Zeit und \(O(N)\) Speicher. Die Mertens-Präfixsummen und die Potenztabelle kosten ebenfalls \(O(N)\) Zeit und \(O(N)\) Speicher. Der abschließende Quotientenblock-Durchlauf betrachtet nur die verschiedenen Werte von \(\left\lfloor N/k\right\rfloor\) und ist deshalb \(O(\sqrt N)\). Insgesamt ergibt sich \(O(N)\) Zeit und \(O(N)\) Speicher; bei \(N=10^7\) dominiert die Vorverarbeitung.
Problem 802 için C++, Python ve Java uygulamaları şu aritmetik ifadeyi hesaplar:
$$S(N)=\sum_{k=1}^{N}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}\pmod{M},\qquad M=1020340567,$$
ve nihai giriş \(N=10^7\) değeridir. Zorluk modüler aritmetikte değil, Möbius değerlerini, prefix toplamlarını ve tekrar eden \(\left\lfloor N/k\right\rfloor\) bölüm değerlerini yeniden hesaplamak yerine bir kez hazırlayıp tekrar kullanacak bir düzen kurmaktır.
Uygulamalar bu problemi, temel dizi \(A(t)=2^t\) üzerine kurulmuş Möbius ağırlıklı bir dönüşüm olarak ele alır. Çözümün omurgası iki fikirdir: \(\mu(k)\) değerlerini tüm \(k\le N\) için verimli biçimde üretmek ve \(\left\lfloor N/k\right\rfloor\) ifadesinin uzun aralıklarda sabit kaldığını kullanmak.
Toplanan tam ifade şudur:
$$S(N)=\sum_{k=1}^{N}\mu(k)A\!\left(\left\lfloor\frac{N}{k}\right\rfloor\right),\qquad A(t)=2^t.$$
Her \(k\) için iki parça vardır: \(\mu(k)\in\{-1,0,1\}\) biçimindeki Möbius ağırlığı ve sadece \(\left\lfloor N/k\right\rfloor\) bölümüne bağlı olan bir iki kuvveti. Bu da doğal olarak sayı kuramsal ön hazırlığı son toplama aşamasından ayırmayı önerir.
Möbius fonksiyonu için
$$\mu(1)=1,$$
$$\mu(n)=0 \text{ eğer bir asal } p \text{ için } p^2\mid n \text{ ise},$$
$$\mu(n)=(-1)^r \text{ eğer } n,\ r \text{ farklı asalın çarpımıysa}.$$
Böylece karesel asal böleni olan sayılar toplamdan tamamen silinir; kareden arınmış sayılar ise farklı asal sayısının parity'sine göre artı veya eksi katkı verir. Yani toplamın içinde baştan itibaren bir dahil et-çıkar filtresi vardır.
Mertens prefix fonksiyonunu
$$\mathcal{M}(x)=\sum_{k\le x}\mu(k)$$
olarak tanımlayalım. O zaman herhangi bir \([a,b]\) aralığı için
$$\sum_{k=a}^{b}\mu(k)=\mathcal{M}(b)-\mathcal{M}(a-1)$$
olur. Böylece çok sayıda Möbius terimini tek tek toplamak yerine sabit zamanda bir fark hesaplarız. Özellikle birçok komşu \(k\) için \(\left\lfloor N/k\right\rfloor\) aynı olduğunda bu dönüşüm çok değerlidir.
Bir başlangıç indeksi \(i\) seçip
$$q=\left\lfloor\frac{N}{i}\right\rfloor$$
diyelim. Bu aynı bölüm değerine sahip tüm indeksler
$$i\le k\le j,\qquad j=\left\lfloor\frac{N}{q}\right\rfloor$$
aralığında yer alır. Bu aralıktaki her \(k\) için iki kuvveti aynıdır:
$$2^{\left\lfloor N/k\right\rfloor}=2^q.$$
Dolayısıyla tüm blok katkısı
$$\sum_{k=i}^{j}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}=\left(\mathcal{M}(j)-\mathcal{M}(i-1)\right)2^q$$
şeklinde tek adımda yazılır. Bir blok bittiğinde sıradaki işlenmemiş indeks \(j+1\) olur. Farklı bölüm değerlerinin sayısı yaklaşık \(2\sqrt N\) olduğundan, toplama aşaması düz bir terim terim geçişten çok daha kısalır.
Aynı üsler tekrar tekrar ortaya çıktığı için uygulamalar
$$P(t)=2^t\bmod M,\qquad 0\le t\le N$$
tablosunu önceden hesaplar. Böylece her bölüm bloğunda yalnızca bir tablo erişimi ve bir modüler çarpma gerekir; ana döngü içinde tekrar tekrar üs alma yapılmaz.
İlk on Möbius değeri
$$\mu(1),\dots,\mu(10)=1,-1,-1,0,-1,1,-1,0,0,1$$
şeklindedir. Bölüm blokları da
$$\begin{aligned} k=1 &: \left\lfloor 10/k\right\rfloor=10,\quad \mathcal{M}(1)-\mathcal{M}(0)=1,\quad &&1\cdot 2^{10}=1024,\\ k=2 &: \left\lfloor 10/k\right\rfloor=5,\quad \mathcal{M}(2)-\mathcal{M}(1)=-1,\quad &&-1\cdot 2^5=-32,\\ k=3 &: \left\lfloor 10/k\right\rfloor=3,\quad \mathcal{M}(3)-\mathcal{M}(2)=-1,\quad &&-1\cdot 2^3=-8,\\ 4\le k\le 5 &: \left\lfloor 10/k\right\rfloor=2,\quad \mathcal{M}(5)-\mathcal{M}(3)=-1,\quad &&-1\cdot 2^2=-4,\\ 6\le k\le 10 &: \left\lfloor 10/k\right\rfloor=1,\quad \mathcal{M}(10)-\mathcal{M}(5)=1,\quad &&1\cdot 2^1=2. \end{aligned}$$
Bu katkılar toplandığında
$$1024-32-8-4+2=982$$
elde edilir. Örnek, yapının neden etkili olduğunu açıkça gösterir: on ayrı terim yerine yalnızca beş blok işlenir; \(N\) büyüdükçe kazanç daha da belirginleşir.
C++, Python ve Java uygulamaları aynı işlem hattını izler. Önce doğrusal bir elek ile \(N\)'e kadar tüm Möbius değerleri üretilir; aynı anda her sayının en küçük asal böleni de kaydedilir. Bu yapı sayesinde kareden arınmış sayılar doğru işareti alır, karesel asal böleni olan sayılar ise otomatik olarak \(0\) olur.
Daha sonra uygulama bir Mertens prefix tablosu ve bağımsız olarak tüm \(0\le t\le N\) için \(2^t\bmod M\) tablosu kurar. Bu iki hazırlık tamamlandığında son döngü artık her terimi tek tek toplamaya çalışmaz. Bunun yerine bir maksimum bölüm bloğundan sonrakine sıçrar, o bloğun toplam Möbius ağırlığını prefix farkı ile bulur, ortak bölüm için önceden hesaplanmış iki kuvveti ile çarpar ve sonucu mod \(M\) altında biriktirir.
Bazı blok toplamları negatif olduğu için modüler değerler çarpmadan önce ya da toplamadan sonra normalize edilir. Böylece ara değerler güvenli aralıkta kalırken formülün tam aritmetik anlamı korunur.
Doğrusal elek \(O(N)\) zamanda çalışır ve \(O(N)\) bellek kullanır. Mertens prefix dizisi ile kuvvet tablosu da \(O(N)\) zaman ve \(O(N)\) bellek gerektirir. Son bölüm-blok taraması yalnızca \(\left\lfloor N/k\right\rfloor\) ifadesinin farklı değerlerine dokunduğu için \(O(\sqrt N)\) sürer. Genel yöntem bu yüzden \(O(N)\) zaman ve \(O(N)\) bellek maliyetine sahiptir; \(N=10^7\) için baskın kısım ön işlemedir.
Para el Problema 802, las implementaciones en C++, Python y Java evalúan la cantidad aritmética
$$S(N)=\sum_{k=1}^{N}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}\pmod{M},\qquad M=1020340567,$$
con la entrada final \(N=10^7\). La dificultad no está en la aritmética modular en sí, sino en organizar el cálculo para reutilizar los valores de Möbius, las sumas prefijas y los cocientes repetidos \(\left\lfloor N/k\right\rfloor\) en lugar de recalcularlos.
Las implementaciones tratan el problema como una transformación ponderada por Möbius de la sucesión básica \(A(t)=2^t\). La solución se apoya en dos ideas: calcular \(\mu(k)\) eficientemente para todo \(k\le N\) y aprovechar que \(\left\lfloor N/k\right\rfloor\) permanece constante en intervalos largos.
La cantidad exacta que se acumula es
$$S(N)=\sum_{k=1}^{N}\mu(k)A\!\left(\left\lfloor\frac{N}{k}\right\rfloor\right),\qquad A(t)=2^t.$$
Cada índice \(k\) aporta dos piezas: un peso de Möbius \(\mu(k)\in\{-1,0,1\}\) y una potencia de dos determinada únicamente por el cociente \(\left\lfloor N/k\right\rfloor\). Eso sugiere separar la preparación aritmética de la etapa final de acumulación.
La función de Möbius satisface
$$\mu(1)=1,$$
$$\mu(n)=0 \text{ si } p^2\mid n \text{ para algún primo } p,$$
$$\mu(n)=(-1)^r \text{ si } n \text{ es producto de } r \text{ primos distintos}.$$
Por tanto, los enteros con un factor primo cuadrado desaparecen por completo, mientras que los enteros libres de cuadrados contribuyen con signo alternante. La suma actúa así como un filtro de inclusión-exclusión sobre la sucesión \(2^{\left\lfloor N/k\right\rfloor}\).
Definimos la función prefija de Mertens
$$\mathcal{M}(x)=\sum_{k\le x}\mu(k).$$
Entonces cualquier suma sobre un intervalo se escribe como
$$\sum_{k=a}^{b}\mu(k)=\mathcal{M}(b)-\mathcal{M}(a-1).$$
Esto convierte una suma de muchos valores de Möbius en una sola resta de tiempo constante. Esa transformación es exactamente lo que hace falta cuando muchos índices consecutivos comparten el mismo cociente \(\left\lfloor N/k\right\rfloor\).
Fijemos un índice inicial \(i\) y definamos
$$q=\left\lfloor\frac{N}{i}\right\rfloor.$$
Todos los índices que producen ese mismo cociente forman el intervalo
$$i\le k\le j,\qquad j=\left\lfloor\frac{N}{q}\right\rfloor.$$
Para todo \(k\in[i,j]\), la potencia de dos es la misma:
$$2^{\left\lfloor N/k\right\rfloor}=2^q.$$
Por lo tanto, la contribución del bloque completo es
$$\sum_{k=i}^{j}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}=\left(\mathcal{M}(j)-\mathcal{M}(i-1)\right)2^q.$$
Después de procesar un bloque, el siguiente índice pendiente es \(j+1\). Como el número de cocientes distintos es de orden \(2\sqrt N\), la fase de acumulación se reduce mucho frente a un recorrido literal término a término.
Los mismos exponentes aparecen una y otra vez, así que las implementaciones construyen la tabla
$$P(t)=2^t\bmod M,\qquad 0\le t\le N.$$
De este modo, cada bloque solo necesita una consulta a la tabla y una multiplicación modular. Dentro del barrido principal no hay exponenciaciones repetidas.
Los diez primeros valores de Möbius son
$$\mu(1),\dots,\mu(10)=1,-1,-1,0,-1,1,-1,0,0,1.$$
Los bloques de cociente quedan así:
$$\begin{aligned} k=1 &: \left\lfloor 10/k\right\rfloor=10,\quad \mathcal{M}(1)-\mathcal{M}(0)=1,\quad &&1\cdot 2^{10}=1024,\\ k=2 &: \left\lfloor 10/k\right\rfloor=5,\quad \mathcal{M}(2)-\mathcal{M}(1)=-1,\quad &&-1\cdot 2^5=-32,\\ k=3 &: \left\lfloor 10/k\right\rfloor=3,\quad \mathcal{M}(3)-\mathcal{M}(2)=-1,\quad &&-1\cdot 2^3=-8,\\ 4\le k\le 5 &: \left\lfloor 10/k\right\rfloor=2,\quad \mathcal{M}(5)-\mathcal{M}(3)=-1,\quad &&-1\cdot 2^2=-4,\\ 6\le k\le 10 &: \left\lfloor 10/k\right\rfloor=1,\quad \mathcal{M}(10)-\mathcal{M}(5)=1,\quad &&1\cdot 2^1=2. \end{aligned}$$
La suma de los bloques es
$$1024-32-8-4+2=982.$$
El ejemplo deja clara la ventaja: cinco bloques sustituyen a diez términos individuales, y esa compresión mejora aún más cuando \(N\) crece.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero construyen los valores de Möbius hasta \(N\) mediante una criba lineal que además registra el menor primo divisor de cada entero. Esa criba produce el signo correcto para los números libres de cuadrados y asigna automáticamente valor \(0\) a los enteros divisibles por el cuadrado de un primo.
Después, la implementación forma un arreglo acumulado de la función de Mertens y, por separado, una tabla con todas las potencias \(2^t\bmod M\) para \(0\le t\le N\). Con esas dos estructuras listas, el último recorrido ya no suma término por término: salta de un bloque máximo de cociente al siguiente, obtiene el peso total de Möbius del bloque mediante una diferencia de prefijos, lo multiplica por la potencia de dos precalculada para ese cociente y acumula el resultado módulo \(M\).
Como algunas sumas de bloque son negativas, la aritmética modular se normaliza antes o después de la multiplicación, según el lenguaje. Así se mantienen seguros los valores intermedios sin alterar el significado exacto de la fórmula.
La criba lineal cuesta \(O(N)\) tiempo y \(O(N)\) memoria. Las sumas prefijas de Mertens y la tabla de potencias también requieren \(O(N)\) tiempo y \(O(N)\) memoria. El barrido final por bloques de cociente solo visita los distintos valores de \(\left\lfloor N/k\right\rfloor\), así que esa fase es \(O(\sqrt N)\). En conjunto, el método es \(O(N)\) en tiempo y \(O(N)\) en memoria, dominado por la preparación cuando \(N=10^7\).
对于 Problem 802，C++、Python 和 Java 三个实现都在计算同一个算术量：
$$S(N)=\sum_{k=1}^{N}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}\pmod{M},\qquad M=1020340567,$$
最终代入的参数是 \(N=10^7\)。真正的难点不在模运算本身，而在于如何把 Möbius 函数值、前缀和以及大量重复出现的 \(\left\lfloor N/k\right\rfloor\) 商值组织起来，只预处理一次，然后在主循环中反复复用。
这些实现把问题看成对基本序列 \(A(t)=2^t\) 做一次带 Möbius 权重的变换。核心有两个：第一，必须高效求出全部 \(\mu(k)\)；第二，要利用 \(\left\lfloor N/k\right\rfloor\) 在很长区间上保持不变这一事实。
程序实际累加的量是
$$S(N)=\sum_{k=1}^{N}\mu(k)A\!\left(\left\lfloor\frac{N}{k}\right\rfloor\right),\qquad A(t)=2^t.$$
这说明每个 \(k\) 的贡献由两部分组成：一部分是 Möbius 权重 \(\mu(k)\in\{-1,0,1\}\)，另一部分是只由商 \(\left\lfloor N/k\right\rfloor\) 决定的二的幂。这样一来，数论预处理和最终求和就可以明显分离开来。
Möbius 函数满足
$$\mu(1)=1,$$
$$\mu(n)=0 \text{，如果某个素数 } p \text{ 满足 } p^2\mid n,$$
$$\mu(n)=(-1)^r \text{，如果 } n \text{ 是 } r \text{ 个互异素数的乘积}.$$
因此，只要某个整数含有平方素因子，它对总和的贡献就直接变成零；而平方自由数则按照素因子个数的奇偶性贡献正号或负号。也就是说，这个求和本身就是一个带有容斥意味的 Möbius 过滤过程。
定义 Mertens 前缀函数
$$\mathcal{M}(x)=\sum_{k\le x}\mu(k).$$
于是任意区间 \([a,b]\) 上的 Möbius 和都能写成
$$\sum_{k=a}^{b}\mu(k)=\mathcal{M}(b)-\mathcal{M}(a-1).$$
这一步非常关键，因为它把“许多单独的 Möbius 值相加”变成了“一次前缀差分”。一旦我们发现一整段连续的 \(k\) 具有相同的 \(\left\lfloor N/k\right\rfloor\)，这一改写就能立刻把整段压缩成 \(O(1)\) 时间。
固定当前块的起点 \(i\)，令
$$q=\left\lfloor\frac{N}{i}\right\rfloor.$$
那么所有满足这个相同商值的下标 \(k\) 组成区间
$$i\le k\le j,\qquad j=\left\lfloor\frac{N}{q}\right\rfloor.$$
在整个区间 \([i,j]\) 内都有
$$2^{\left\lfloor N/k\right\rfloor}=2^q.$$
于是这一整块的贡献可直接写成
$$\sum_{k=i}^{j}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}=\left(\mathcal{M}(j)-\mathcal{M}(i-1)\right)2^q.$$
处理完当前块后，下一个未处理位置就是 \(j+1\)。由于 \(\left\lfloor N/k\right\rfloor\) 的不同取值个数只有大约 \(2\sqrt N\) 个，所以最终求和阶段会比逐项扫描短得多。
相同的指数会反复出现，因此实现中先建立表
$$P(t)=2^t\bmod M,\qquad 0\le t\le N.$$
这样每个分块只需要一次查表和一次模乘，主循环内部完全不必重新做快速幂或重复乘法链。
前十个 Möbius 值是
$$\mu(1),\dots,\mu(10)=1,-1,-1,0,-1,1,-1,0,0,1.$$
对应的整除分块如下：
$$\begin{aligned} k=1 &: \left\lfloor 10/k\right\rfloor=10,\quad \mathcal{M}(1)-\mathcal{M}(0)=1,\quad &&1\cdot 2^{10}=1024,\\ k=2 &: \left\lfloor 10/k\right\rfloor=5,\quad \mathcal{M}(2)-\mathcal{M}(1)=-1,\quad &&-1\cdot 2^5=-32,\\ k=3 &: \left\lfloor 10/k\right\rfloor=3,\quad \mathcal{M}(3)-\mathcal{M}(2)=-1,\quad &&-1\cdot 2^3=-8,\\ 4\le k\le 5 &: \left\lfloor 10/k\right\rfloor=2,\quad \mathcal{M}(5)-\mathcal{M}(3)=-1,\quad &&-1\cdot 2^2=-4,\\ 6\le k\le 10 &: \left\lfloor 10/k\right\rfloor=1,\quad \mathcal{M}(10)-\mathcal{M}(5)=1,\quad &&1\cdot 2^1=2. \end{aligned}$$
把这些块贡献加起来得到
$$1024-32-8-4+2=982.$$
这个例子非常直观地说明了为什么分块有效：原本需要处理十个单项，现在只需要五个块；当 \(N\) 增大时，这种压缩会更加明显。
C++、Python 和 Java 实现的处理流程是一样的。第一步是用线性筛同时生成 \(1\) 到 \(N\) 的 Möbius 值，并记录每个整数的最小素因子。这样做的好处是结构非常清楚：平方自由数会得到正确的符号，而带平方素因子的数会自动得到 \(0\)。
接着，程序构造 Mertens 前缀和数组，并且单独预处理所有 \(2^t\bmod M\) 的取值，其中 \(0\le t\le N\)。有了这两张表之后，最后的求和就不再逐项进行，而是从一个最大整除块跳到下一个最大整除块：先用前缀差得到整块的 Möbius 总权重，再乘上该块公共商值对应的二的幂，最后把结果累加到模 \(M\) 的答案中。
由于某些块的 Möbius 总和可能为负数，实现会在乘法之前或加法之后做一次模意义下的规范化。这样既保证中间值安全，也不改变公式本身的算术含义。
线性筛的时间复杂度是 \(O(N)\)，空间复杂度也是 \(O(N)\)。Mertens 前缀和与幂表的建立同样是 \(O(N)\) 时间、\(O(N)\) 空间。最后的整除分块扫描只访问 \(\left\lfloor N/k\right\rfloor\) 的不同取值，因此这一阶段是 \(O(\sqrt N)\)。综合起来，总体复杂度为 \(O(N)\) 时间和 \(O(N)\) 空间；在 \(N=10^7\) 时，主要开销仍然来自预处理。
Для Problem 802 реализации на C++, Python и Java вычисляют арифметическую величину
$$S(N)=\sum_{k=1}^{N}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}\pmod{M},\qquad M=1020340567,$$
где в основном запуске используется \(N=10^7\). Трудность состоит не в самой модульной арифметике, а в том, чтобы заранее подготовить значения функции Мёбиуса, префиксные суммы и повторяющиеся частные \(\left\lfloor N/k\right\rfloor\), а затем многократно переиспользовать их.
Реализации рассматривают задачу как преобразование базовой последовательности \(A(t)=2^t\), взвешенное функцией Мёбиуса. В основе решения лежат две идеи: эффективно вычислить \(\mu(k)\) для всех \(k\le N\) и воспользоваться тем, что \(\left\lfloor N/k\right\rfloor\) остается постоянным на длинных промежутках.
Точная суммируемая величина имеет вид
$$S(N)=\sum_{k=1}^{N}\mu(k)A\!\left(\left\lfloor\frac{N}{k}\right\rfloor\right),\qquad A(t)=2^t.$$
Каждый индекс \(k\) дает две составляющие: вес \(\mu(k)\in\{-1,0,1\}\) и степень двойки, зависящую только от частного \(\left\lfloor N/k\right\rfloor\). Поэтому естественно отделить теоретико-числовую подготовку от финального этапа накопления суммы.
Функция Мёбиуса определяется так:
$$\mu(1)=1,$$
$$\mu(n)=0 \text{, если } p^2\mid n \text{ для некоторого простого } p,$$
$$\mu(n)=(-1)^r \text{, если } n \text{ есть произведение } r \text{ различных простых}.$$
Значит, числа с квадратом простого делителя полностью исчезают из суммы, а квадратсвободные числа входят с чередующимся знаком. Иными словами, сама сумма уже содержит механизм включения-исключения, наложенный на последовательность \(2^{\left\lfloor N/k\right\rfloor}\).
Введем функцию Мертенса
$$\mathcal{M}(x)=\sum_{k\le x}\mu(k).$$
Тогда сумма по любому отрезку \([a,b]\) равна
$$\sum_{k=a}^{b}\mu(k)=\mathcal{M}(b)-\mathcal{M}(a-1).$$
Это превращает длинную сумму значений \(\mu\) в одну разность за \(O(1)\). Именно это нужно, когда подряд идет много индексов с одинаковым значением \(\left\lfloor N/k\right\rfloor\).
Зафиксируем левую границу блока \(i\) и положим
$$q=\left\lfloor\frac{N}{i}\right\rfloor.$$
Все индексы с тем же частным образуют отрезок
$$i\le k\le j,\qquad j=\left\lfloor\frac{N}{q}\right\rfloor.$$
Для каждого \(k\in[i,j]\) степень двойки одинакова:
$$2^{\left\lfloor N/k\right\rfloor}=2^q.$$
Следовательно, вклад всего блока равен
$$\sum_{k=i}^{j}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}=\left(\mathcal{M}(j)-\mathcal{M}(i-1)\right)2^q.$$
После обработки блока следующий необработанный индекс равен \(j+1\). Поскольку различных значений \(\left\lfloor N/k\right\rfloor\) всего порядка \(2\sqrt N\), этап суммирования становится значительно короче прямого прохода по всем \(k\).
Одни и те же показатели появляются много раз, поэтому реализации заранее строят таблицу
$$P(t)=2^t\bmod M,\qquad 0\le t\le N.$$
После этого для каждого блока достаточно одного обращения к таблице и одного умножения по модулю. Внутри главного блочного прохода повторного возведения в степень уже нет.
Первые десять значений функции Мёбиуса таковы:
$$\mu(1),\dots,\mu(10)=1,-1,-1,0,-1,1,-1,0,0,1.$$
Блоки по одинаковому частному имеют вид
$$\begin{aligned} k=1 &: \left\lfloor 10/k\right\rfloor=10,\quad \mathcal{M}(1)-\mathcal{M}(0)=1,\quad &&1\cdot 2^{10}=1024,\\ k=2 &: \left\lfloor 10/k\right\rfloor=5,\quad \mathcal{M}(2)-\mathcal{M}(1)=-1,\quad &&-1\cdot 2^5=-32,\\ k=3 &: \left\lfloor 10/k\right\rfloor=3,\quad \mathcal{M}(3)-\mathcal{M}(2)=-1,\quad &&-1\cdot 2^3=-8,\\ 4\le k\le 5 &: \left\lfloor 10/k\right\rfloor=2,\quad \mathcal{M}(5)-\mathcal{M}(3)=-1,\quad &&-1\cdot 2^2=-4,\\ 6\le k\le 10 &: \left\lfloor 10/k\right\rfloor=1,\quad \mathcal{M}(10)-\mathcal{M}(5)=1,\quad &&1\cdot 2^1=2. \end{aligned}$$
Сумма вкладов блоков равна
$$1024-32-8-4+2=982.$$
Пример хорошо показывает суть метода: вместо десяти отдельных слагаемых достаточно обработать пять блоков, а при больших \(N\) выигрыш становится еще заметнее.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала линейным решетом строятся значения функции Мёбиуса до \(N\), а заодно сохраняется наименьший простой делитель каждого числа. Это дает корректный знак для квадратсвободных чисел и автоматически присваивает ноль всем числам, делящимся на квадрат простого.
Затем реализация формирует массив префиксных сумм Мертенса и отдельно таблицу всех значений \(2^t\bmod M\) для \(0\le t\le N\). После этого финальный цикл уже не перебирает слагаемые по одному: он прыгает от одного максимального блока частного к следующему, получает общий вес Мёбиуса на блоке как разность префиксов, умножает его на заранее подготовленную степень двойки и добавляет результат по модулю \(M\).
Так как суммы по блокам могут быть отрицательными, модульное представление нормализуется до или после умножения в зависимости от языка. Это удерживает промежуточные значения в безопасном диапазоне и не меняет точный смысл формулы.
Линейное решето работает за \(O(N)\) времени и требует \(O(N)\) памяти. Построение префиксной функции Мертенса и таблицы степеней также стоит \(O(N)\) времени и \(O(N)\) памяти. Финальный проход по блокам использует только различные значения \(\left\lfloor N/k\right\rfloor\), поэтому эта стадия имеет сложность \(O(\sqrt N)\). В сумме метод дает \(O(N)\) времени и \(O(N)\) памяти, причем при \(N=10^7\) основная стоимость приходится на подготовку.
في Problem 802 تقوم تطبيقات C++ وPython وJava بحساب الكمية الحسابية
$$S(N)=\sum_{k=1}^{N}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}\pmod{M},\qquad M=1020340567,$$
مع الإدخال النهائي \(N=10^7\). الصعوبة ليست في الحساب بترديد \(M\) بحد ذاته، بل في تنظيم العمل بحيث نعيد استعمال قيم دالة Möbius والمجاميع البادئة وقيم القسمة الصحيحة \(\left\lfloor N/k\right\rfloor\) المتكررة بدل إعادة حسابها مرة بعد مرة.
تعامل هذه التطبيقات المسألة على أنها تحويل موزون بدالة Möbius للتتابع الأساسي \(A(t)=2^t\). ويقوم الحل على فكرتين: حساب \(\mu(k)\) بكفاءة لكل \(k\le N\)، ثم استغلال أن القيمة \(\left\lfloor N/k\right\rfloor\) تبقى ثابتة على فترات طويلة.
الكمية المجمعة فعليًا هي
$$S(N)=\sum_{k=1}^{N}\mu(k)A\!\left(\left\lfloor\frac{N}{k}\right\rfloor\right),\qquad A(t)=2^t.$$
كل عدد \(k\) يضيف جزأين: وزنًا من Möbius حيث \(\mu(k)\in\{-1,0,1\}\)، وقوة للعدد \(2\) تعتمد فقط على خارج القسمة \(\left\lfloor N/k\right\rfloor\). وهذا يقترح مباشرة فصل المعالجة العددية المسبقة عن مرحلة التجميع النهائية.
تُعرَّف دالة Möbius بالعلاقات
$$\mu(1)=1,$$
وإذا كان \(n\) قابلًا للقسمة على \(p^2\) من أجل عدد أولي \(p\)، فإن
$$\mu(n)=0.$$
وإذا كان \(n\) حاصل ضرب \(r\) أعداد أولية مختلفة، فإن
$$\mu(n)=(-1)^r.$$
إذن كل عدد يحتوي عاملًا أوليًا مربعًا يختفي تمامًا من المجموع، بينما تسهم الأعداد الخالية من المربعات بإشارة موجبة أو سالبة بحسب عدد عواملها الأولية المختلفة. لذلك فالمجموع يحمل بطبيعته مرشحًا من نوع الاشتمال والاستبعاد.
نعرّف دالة Mertens البادئة بـ
$$\mathcal{M}(x)=\sum_{k\le x}\mu(k).$$
وعندئذ يمكن كتابة أي مجموع على مجال \([a,b]\) بالشكل
$$\sum_{k=a}^{b}\mu(k)=\mathcal{M}(b)-\mathcal{M}(a-1).$$
هذه الخطوة تحوّل جمع عدد كبير من قيم Möbius إلى طرح واحد بزمن ثابت. وهذا هو المفتاح حين نجد أن مجموعة كبيرة من القيم المتجاورة لـ \(k\) تشترك في نفس القيمة \(\left\lfloor N/k\right\rfloor\).
لنثبت بداية كتلة عند \(i\)، ثم نضع
$$q=\left\lfloor\frac{N}{i}\right\rfloor.$$
كل الفهارس التي تعطي هذا الخارج نفسه تقع في المجال
$$i\le k\le j,\qquad j=\left\lfloor\frac{N}{q}\right\rfloor.$$
ولكل \(k\in[i,j]\) تكون قوة العدد \(2\) واحدة:
$$2^{\left\lfloor N/k\right\rfloor}=2^q.$$
لذلك تصبح مساهمة الكتلة كلها
$$\sum_{k=i}^{j}\mu(k)\,2^{\left\lfloor N/k\right\rfloor}=\left(\mathcal{M}(j)-\mathcal{M}(i-1)\right)2^q.$$
وبعد إنهاء هذه الكتلة ينتقل التنفيذ مباشرة إلى \(j+1\). وبما أن عدد القيم المختلفة لـ \(\left\lfloor N/k\right\rfloor\) يقارب \(2\sqrt N\) فقط، فإن مرحلة التجميع تصبح أقصر كثيرًا من المرور الساذج على كل حد على حدة.
بما أن الأسس نفسها تتكرر، تُبنى مسبقًا الجدول
$$P(t)=2^t\bmod M,\qquad 0\le t\le N.$$
وبذلك تحتاج كل كتلة إلى قراءة واحدة من الجدول وضرب واحد بترديد \(M\)، من دون أي إعادة لحساب الأسس داخل المسار الرئيسي.
أول عشر قيم لدالة Möbius هي
$$\mu(1),\dots,\mu(10)=1,-1,-1,0,-1,1,-1,0,0,1.$$
أما كتل خارج القسمة فتكون
$$\begin{aligned} k=1 &: \left\lfloor 10/k\right\rfloor=10,\quad \mathcal{M}(1)-\mathcal{M}(0)=1,\quad &&1\cdot 2^{10}=1024,\\ k=2 &: \left\lfloor 10/k\right\rfloor=5,\quad \mathcal{M}(2)-\mathcal{M}(1)=-1,\quad &&-1\cdot 2^5=-32,\\ k=3 &: \left\lfloor 10/k\right\rfloor=3,\quad \mathcal{M}(3)-\mathcal{M}(2)=-1,\quad &&-1\cdot 2^3=-8,\\ 4\le k\le 5 &: \left\lfloor 10/k\right\rfloor=2,\quad \mathcal{M}(5)-\mathcal{M}(3)=-1,\quad &&-1\cdot 2^2=-4,\\ 6\le k\le 10 &: \left\lfloor 10/k\right\rfloor=1,\quad \mathcal{M}(10)-\mathcal{M}(5)=1,\quad &&1\cdot 2^1=2. \end{aligned}$$
وبجمع مساهمات الكتل نحصل على
$$1024-32-8-4+2=982.$$
يوضح هذا المثال البنية بوضوح: خمس كتل فقط تحل محل عشرة حدود منفصلة، وتزداد فائدة هذا الضغط الحسابي كلما كبر \(N\).
تسير تطبيقات C++ وPython وJava على خط عمل واحد. تبدأ ببناء قيم Möbius حتى \(N\) باستخدام غربال خطي يسجل أيضًا أصغر قاسم أولي لكل عدد. وبهذه الطريقة تحصل الأعداد الخالية من المربعات على إشارتها الصحيحة، بينما تُعطى الأعداد القابلة للقسمة على مربع أولي القيمة \(0\) تلقائيًا.
بعد ذلك تُنشئ الشيفرة جدولًا تراكميًا لدالة Mertens وجدولًا مستقلًا لكل القيم \(2^t\bmod M\) عندما \(0\le t\le N\). وعندما تصبح هاتان البنيتان جاهزتين لا تعود الحلقة الأخيرة تمر على الحدود واحدًا واحدًا، بل تقفز من كتلة قصوى إلى الكتلة التالية، وتحسب وزن Möbius الكلي للكتلة بفارق مجاميع بادئة، ثم تضربه في قوة العدد \(2\) المحسوبة مسبقًا لذلك الخارج، ثم تضيف الناتج بترديد \(M\).
ولأن بعض مجاميع الكتل قد تكون سالبة، تُطبَّع القيمة المعيارية قبل الضرب أو بعد الجمع بحسب اللغة المستخدمة. هذا يحافظ على القيم الوسيطة ضمن مجال آمن من غير أن يغيّر المعنى الحسابي الدقيق للصيغة.
الغربال الخطي يحتاج إلى زمن \(O(N)\) وذاكرة \(O(N)\). كما أن بناء مجاميع Mertens البادئة وجدول القوى يحتاج أيضًا إلى \(O(N)\) زمنًا و\(O(N)\) ذاكرة. أما المسح النهائي للكتل فيزور فقط القيم المختلفة لـ \(\left\lfloor N/k\right\rfloor\)، ولذلك يكون \(O(\sqrt N)\). وبهذا تكون الكلفة الكلية \(O(N)\) زمنًا و\(O(N)\) ذاكرة، مع سيطرة مرحلة التحضير عندما يكون \(N=10^7\).