Let \(\sigma(n)\) denote the sum of all positive divisors of \(n\). The problem asks for
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sigma(xy)$$
with \(N=10^{11}\), reduced modulo \(10^9\). A direct double loop is hopeless, so the solution rewrites \(\sigma(xy)\) into a form that separates the common part of \(x\) and \(y\), then evaluates the resulting sums by quotient blocks.
The key identity used by the implementation is
$$\sigma(xy)=\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right),$$
where \(\mu\) is the Möbius function. Both sides are multiplicative in the pair \((x,y)\), so it is enough to check prime powers. Let \(x=p^a\) and \(y=p^b\).
If \(a=0\) or \(b=0\), then \(\gcd(x,y)=1\) and the identity is immediate. For \(a,b\ge 1\), only \(d=1\) and \(d=p\) contribute, because \(\mu(p^k)=0\) for \(k\ge 2\). Thus
$$\begin{aligned} \sum_{d\mid \gcd(p^a,p^b)} \mu(d)\,d\,\sigma\!\left(\frac{p^a}{d}\right)\sigma\!\left(\frac{p^b}{d}\right) &=\sigma(p^a)\sigma(p^b)-p\,\sigma(p^{a-1})\sigma(p^{b-1})\\ &=\frac{(p^{a+1}-1)(p^{b+1}-1)-p(p^a-1)(p^b-1)}{(p-1)^2}\\ &=\frac{p^{a+b+1}-1}{p-1} =\sigma(p^{a+b}). \end{aligned}$$
Since \(p^{a+b}=xy\), the identity holds for prime powers and therefore for all \(x,y\).
Insert the identity into the definition of \(S(N)\):
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
Exchange the order of summation and write \(x=da\), \(y=db\). Then \(a,b\le \lfloor N/d\rfloor\), so
$$S(N)=\sum_{d=1}^{N}\mu(d)\,d\left(\sum_{a\le N/d}\sigma(a)\right)\left(\sum_{b\le N/d}\sigma(b)\right).$$
Define the summatory divisor function
$$A(M)=\sum_{n=1}^{M}\sigma(n).$$
This gives the single outer sum
$$\boxed{S(N)=\sum_{d=1}^{N}\mu(d)\,d\,A\!\left(\left\lfloor\frac{N}{d}\right\rfloor\right)^2.}$$
We start from the divisor definition:
$$A(M)=\sum_{n=1}^{M}\sum_{e\mid n} e=\sum_{e=1}^{M} e\left\lfloor\frac{M}{e}\right\rfloor.$$
The implementations use an equivalent form that is better suited to quotient blocking. Let
$$T(q)=\frac{q(q+1)}{2}.$$
Then
$$A(M)=\sum_{t=1}^{M} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right),$$
because for each \(t\), the inner sum \(\sum_{e\le M/t} e\) is exactly \(T(\lfloor M/t\rfloor)\). Now \(\left\lfloor M/t\right\rfloor\) is constant on intervals \(l\le t\le r\) with
$$q=\left\lfloor\frac{M}{l}\right\rfloor,\qquad r=\left\lfloor\frac{M}{q}\right\rfloor.$$
So one whole block contributes
$$\sum_{t=l}^{r} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right)=(r-l+1)\,T(q).$$
There are only \(O(\sqrt{M})\) such blocks, which is the standard harmonic-sum speedup.
The outer formula needs interval sums of \(\mu(d)\,d\). Define
$$W(n)=\sum_{k=1}^{n} k\,\mu(k).$$
The implementation computes small values by sieve and large values by memoized recursion. The recurrence comes from the identity
$$\sum_{k=1}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=1.$$
Indeed, after expanding \(W\),
$$\sum_{k=1}^{n} k\sum_{m\le n/k} m\,\mu(m)=\sum_{km\le n} km\,\mu(m)=\sum_{t\le n} t\sum_{m\mid t}\mu(m)=1,$$
because \(\sum_{m\mid t}\mu(m)=0\) unless \(t=1\). Therefore
$$W(n)=1-\sum_{k=2}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Again, equal quotients are grouped into intervals. For any block \(l\le k\le r\) with \(\lfloor n/k\rfloor=v\), we replace the whole block by
$$\left(\sum_{k=l}^{r} k\right)W(v).$$
The same block idea is applied to the final sum for \(S(N)\). If \(\lfloor N/d\rfloor=q\) on \(l\le d\le r\), then the entire interval contributes
$$A(q)^2\sum_{d=l}^{r} d\,\mu(d)=A(q)^2\bigl(W(r)-W(l-1)\bigr).$$
So the computation walks over the \(O(\sqrt N)\) distinct quotient values of \(\lfloor N/d\rfloor\), evaluates \(A(q)\) once per block, and weights it by the corresponding difference of weighted Möbius prefixes.
For \(N=3\), the divisor sums are \(\sigma(1)=1\), \(\sigma(2)=3\), \(\sigma(3)=4\), so
$$A(3)=1+3+4=8,\qquad A(1)=1.$$
The outer formula gives
$$S(3)=\mu(1)\cdot 1\cdot A(3)^2+\mu(2)\cdot 2\cdot A(1)^2+\mu(3)\cdot 3\cdot A(1)^2,$$
hence
$$S(3)=1\cdot 64-2\cdot 1-3\cdot 1=59,$$
which matches the small validation target used by the implementations.
The C++, Python, and Java implementations all follow the same structure. First they precompute Möbius values up to a practical cutoff and store the prefix sums of \(k\mu(k)\). For larger arguments they reuse the recurrence for \(W(n)\) with memoization, so repeated quotient values are solved only once.
Next they enumerate the quotient blocks of \(\lfloor N/d\rfloor\). For each block they evaluate \(A(q)\) by the triangular-number block formula, square it modulo \(10^9\), multiply by the weighted Möbius difference for that block, and add the result to the running total. The large independent blocks can also be accumulated in parallel.
The direct definition needs \(N^2\) evaluations of \(\sigma(xy)\), which is completely infeasible. After the Möbius decomposition, the outer sum has only \(O(\sqrt N)\) distinct quotient blocks. One evaluation of \(A(M)\) costs \(O(\sqrt M)\), and summing this over the distinct values \(M=\lfloor N/d\rfloor\) gives about \(O(N^{3/4})\) total block work. The weighted Möbius prefix is also handled sublinearly by combining a sieve for small values with memoized quotient recursion for large ones. Memory usage is linear in the chosen sieve cutoff, plus \(O(\sqrt N)\) cached block data.
Sei \(\sigma(n)\) die Summe aller positiven Teiler von \(n\). Gesucht ist
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sigma(xy)$$
für \(N=10^{11}\), modulo \(10^9\). Eine direkte Doppelsumme ist unmöglich, daher zerlegt die Lösung \(\sigma(xy)\) nach dem gemeinsamen Anteil von \(x\) und \(y\) und wertet die verbleibenden Summen blockweise aus.
Die zentrale Identität der Implementierung lautet
$$\sigma(xy)=\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
Beide Seiten sind in den zwei Variablen \((x,y)\) multiplikativ, also genügt eine Prüfung auf Primzahlpotenzen. Setze \(x=p^a\) und \(y=p^b\).
Falls \(a=0\) oder \(b=0\) ist \(\gcd(x,y)=1\) und die Aussage sofort klar. Für \(a,b\ge 1\) tragen nur \(d=1\) und \(d=p\) bei, da \(\mu(p^k)=0\) für \(k\ge 2\). Damit erhält man
$$\begin{aligned} \sum_{d\mid \gcd(p^a,p^b)} \mu(d)\,d\,\sigma\!\left(\frac{p^a}{d}\right)\sigma\!\left(\frac{p^b}{d}\right) &=\sigma(p^a)\sigma(p^b)-p\,\sigma(p^{a-1})\sigma(p^{b-1})\\ &=\frac{(p^{a+1}-1)(p^{b+1}-1)-p(p^a-1)(p^b-1)}{(p-1)^2}\\ &=\frac{p^{a+b+1}-1}{p-1} =\sigma(p^{a+b}). \end{aligned}$$
Da \(p^{a+b}=xy\), gilt die Identität für Primzahlpotenzen und damit für alle \(x,y\).
Setzt man die Identität in \(S(N)\) ein, so folgt
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
Nach Vertauschen der Summation und mit \(x=da\), \(y=db\) gilt \(a,b\le \lfloor N/d\rfloor\), also
$$S(N)=\sum_{d=1}^{N}\mu(d)\,d\left(\sum_{a\le N/d}\sigma(a)\right)\left(\sum_{b\le N/d}\sigma(b)\right).$$
Definiere
$$A(M)=\sum_{n=1}^{M}\sigma(n).$$
Dann erhält man die Einzelsumme
$$\boxed{S(N)=\sum_{d=1}^{N}\mu(d)\,d\,A\!\left(\left\lfloor\frac{N}{d}\right\rfloor\right)^2.}$$
Aus der Definition der Teilersumme folgt
$$A(M)=\sum_{n=1}^{M}\sum_{e\mid n} e=\sum_{e=1}^{M} e\left\lfloor\frac{M}{e}\right\rfloor.$$
Die Implementierungen benutzen die äquivalente Dreiecksformel
$$T(q)=\frac{q(q+1)}{2},\qquad A(M)=\sum_{t=1}^{M} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right).$$
Dies ist dieselbe Summe, denn für festes \(t\) ist \(\sum_{e\le M/t} e=T(\lfloor M/t\rfloor)\). Auf einem Intervall \(l\le t\le r\) mit konstantem Quotienten
$$q=\left\lfloor\frac{M}{l}\right\rfloor,\qquad r=\left\lfloor\frac{M}{q}\right\rfloor$$
liefert der gesamte Block den Beitrag
$$\sum_{t=l}^{r} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right)=(r-l+1)\,T(q).$$
Solcher Blöcke gibt es nur \(O(\sqrt M)\).
Für die Außensumme werden Intervallsummen von \(\mu(d)\,d\) benötigt. Dazu definiert man
$$W(n)=\sum_{k=1}^{n} k\,\mu(k).$$
Kleine Werte werden gesiebt, große Werte rekursiv mit Memoisierung berechnet. Die Rekursion folgt aus
$$\sum_{k=1}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=1.$$
Nach Ausmultiplizieren von \(W\) ergibt sich
$$\sum_{k=1}^{n} k\sum_{m\le n/k} m\,\mu(m)=\sum_{km\le n} km\,\mu(m)=\sum_{t\le n} t\sum_{m\mid t}\mu(m)=1,$$
weil \(\sum_{m\mid t}\mu(m)\) nur für \(t=1\) ungleich null ist. Also
$$W(n)=1-\sum_{k=2}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Auch hier fasst man gleiche Quotienten zusammen und ersetzt jeden Block \(l\le k\le r\) durch
$$\left(\sum_{k=l}^{r} k\right)W(v),\qquad v=\left\lfloor\frac{n}{l}\right\rfloor.$$
Für die Endformel werden Intervalle \(l\le d\le r\) mit konstantem \(q=\lfloor N/d\rfloor\) gemeinsam verarbeitet. Ein solcher Block trägt bei als
$$A(q)^2\sum_{d=l}^{r} d\,\mu(d)=A(q)^2\bigl(W(r)-W(l-1)\bigr).$$
Somit läuft die Berechnung nur noch über die \(O(\sqrt N)\) verschiedenen Quotientenwerte von \(\lfloor N/d\rfloor\).
Für \(N=3\) gilt \(\sigma(1)=1\), \(\sigma(2)=3\), \(\sigma(3)=4\), also
$$A(3)=1+3+4=8,\qquad A(1)=1.$$
Damit folgt aus der Formel
$$S(3)=\mu(1)\cdot 1\cdot A(3)^2+\mu(2)\cdot 2\cdot A(1)^2+\mu(3)\cdot 3\cdot A(1)^2,$$
also
$$S(3)=64-2-3=59,$$
genau wie im kleinen Kontrolltest der Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen demselben Schema. Zuerst werden Möbius-Werte bis zu einer praktikablen Grenze und die Präfixsummen von \(k\mu(k)\) vorbereitet. Für größere Argumente wird \(W(n)\) rekursiv mit Memoisierung ausgewertet, sodass identische Quotienten nur einmal berechnet werden.
Anschließend werden die Blockintervalle von \(\lfloor N/d\rfloor\) durchlaufen. Für jeden Block wird \(A(q)\) per Dreiecksformel berechnet, modulo \(10^9\) quadriert, mit der passenden Möbius-Präfixdifferenz gewichtet und zum Ergebnis addiert. Unabhängige Blöcke lassen sich parallel aufsummieren.
Die direkte Definition hätte Aufwand \(O(N^2)\). Nach der Möbius-Zerlegung besitzt die Außensumme nur \(O(\sqrt N)\) verschiedene Quotientenblöcke. Eine Auswertung von \(A(M)\) kostet \(O(\sqrt M)\), und über alle verschiedenen Werte \(M=\lfloor N/d\rfloor\) summiert ergibt das etwa \(O(N^{3/4})\) Blockarbeit. Die gewichtete Möbius-Präfixsumme bleibt ebenfalls subquadratisch, weil kleine Werte gesiebt und große Werte memoisiert rekursiv behandelt werden. Der Speicherbedarf ist linear in der gewählten Siebgrenze plus \(O(\sqrt N)\) für Blöcke und Cache.
\(\sigma(n)\), \(n\)'in pozitif bölenlerinin toplamı olsun. İstenen büyüklük
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sigma(xy)$$
ifadesidir; burada \(N=10^{11}\) için sonuç \(10^9\) modunda alınır. Doğrudan çift döngü kullanılamayacağı için çözüm, \(\sigma(xy)\) ifadesini \(x\) ile \(y\)'nin ortak kısmını ayıran bir özdeşliğe dönüştürür ve kalan toplamları bölüm-bloklarıyla hesaplar.
Uygulamanın dayandığı temel özdeşlik şudur:
$$\sigma(xy)=\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
Her iki taraf da \((x,y)\) çiftinde çarpımsaldır; bu yüzden asal kuvvetler üzerinde doğrulamak yeterlidir. \(x=p^a\), \(y=p^b\) olsun.
\(a=0\) veya \(b=0\) ise \(\gcd(x,y)=1\) olduğundan eşitlik açıktır. \(a,b\ge 1\) durumunda ise \(\mu(p^k)=0\) olduğu için yalnızca \(d=1\) ve \(d=p\) terimleri kalır:
$$\begin{aligned} \sum_{d\mid \gcd(p^a,p^b)} \mu(d)\,d\,\sigma\!\left(\frac{p^a}{d}\right)\sigma\!\left(\frac{p^b}{d}\right) &=\sigma(p^a)\sigma(p^b)-p\,\sigma(p^{a-1})\sigma(p^{b-1})\\ &=\frac{(p^{a+1}-1)(p^{b+1}-1)-p(p^a-1)(p^b-1)}{(p-1)^2}\\ &=\frac{p^{a+b+1}-1}{p-1} =\sigma(p^{a+b}). \end{aligned}$$
\(p^{a+b}=xy\) olduğundan özdeşlik tüm \(x,y\) için geçerlidir.
Bu özdeşliği \(S(N)\)'de yerine koyarsak
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right)$$
elde edilir. Toplamların sırası değiştirilip \(x=da\), \(y=db\) yazılırsa \(a,b\le \lfloor N/d\rfloor\) olur ve
$$S(N)=\sum_{d=1}^{N}\mu(d)\,d\left(\sum_{a\le N/d}\sigma(a)\right)\left(\sum_{b\le N/d}\sigma(b)\right)$$
bulunur. Şimdi
$$A(M)=\sum_{n=1}^{M}\sigma(n)$$
tanımını yaparsak
$$\boxed{S(N)=\sum_{d=1}^{N}\mu(d)\,d\,A\!\left(\left\lfloor\frac{N}{d}\right\rfloor\right)^2.}$$
Bölen toplamından başlayalım:
$$A(M)=\sum_{n=1}^{M}\sum_{e\mid n} e=\sum_{e=1}^{M} e\left\lfloor\frac{M}{e}\right\rfloor.$$
Uygulama bunun eşdeğer bir üçgensel biçimini kullanır. Önce
$$T(q)=\frac{q(q+1)}{2}$$
olsun. O zaman
$$A(M)=\sum_{t=1}^{M} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right),$$
çünkü sabit bir \(t\) için \(\sum_{e\le M/t} e\) toplamı tam olarak \(T(\lfloor M/t\rfloor)\) olur. Ayrıca \(\lfloor M/t\rfloor\) değeri bazı aralıklarda sabittir. Eğer
$$q=\left\lfloor\frac{M}{l}\right\rfloor,\qquad r=\left\lfloor\frac{M}{q}\right\rfloor$$
ise \(l\le t\le r\) aralığının katkısı
$$\sum_{t=l}^{r} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right)=(r-l+1)\,T(q)$$
olur. Bu tür blokların sayısı yalnızca \(O(\sqrt M)\)'dir.
Dış toplamda \(\sum d\,\mu(d)\) türünden aralık toplamları gerekir. Bunun için
$$W(n)=\sum_{k=1}^{n} k\,\mu(k)$$
tanımlanır. Küçük değerler elekle, büyük değerler ise ezberlemeli özyineleme ile hesaplanır. Kullanılan rekürans
$$\sum_{k=1}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=1$$
özdeşliğinden gelir. Gerçekten,
$$\sum_{k=1}^{n} k\sum_{m\le n/k} m\,\mu(m)=\sum_{km\le n} km\,\mu(m)=\sum_{t\le n} t\sum_{m\mid t}\mu(m)=1,$$
çünkü \(\sum_{m\mid t}\mu(m)\) yalnızca \(t=1\) için sıfır değildir. Dolayısıyla
$$W(n)=1-\sum_{k=2}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Burada da eşit bölüm değerleri bloklar halinde toplanır; \(l\le k\le r\) için bütün blok
$$\left(\sum_{k=l}^{r} k\right)W(v),\qquad v=\left\lfloor\frac{n}{l}\right\rfloor$$
şeklinde işlenir.
Son toplamda \(\lfloor N/d\rfloor=q\) sabit kaldığı her \(l\le d\le r\) bloğu için katkı
$$A(q)^2\sum_{d=l}^{r} d\,\mu(d)=A(q)^2\bigl(W(r)-W(l-1)\bigr)$$
olur. Böylece işlem yalnızca \(\lfloor N/d\rfloor\) ifadesinin \(O(\sqrt N)\) farklı bölüm değerleri üzerinde yürür.
\(N=3\) için \(\sigma(1)=1\), \(\sigma(2)=3\), \(\sigma(3)=4\) olduğundan
$$A(3)=1+3+4=8,\qquad A(1)=1.$$
Dış formül
$$S(3)=\mu(1)\cdot 1\cdot A(3)^2+\mu(2)\cdot 2\cdot A(1)^2+\mu(3)\cdot 3\cdot A(1)^2$$
verir; yani
$$S(3)=64-2-3=59.$$
Bu, uygulamalardaki küçük doğrulama sonucuyla aynıdır.
C++, Python ve Java uygulamaları aynı sayısal yapıyı izler. Önce Möbius değerleri belirli bir sınıra kadar hazırlanır ve \(k\mu(k)\) önek toplamları saklanır. Daha büyük girdiler için \(W(n)\), bölüm blokları üzerinde ezberlemeli özyineleme ile tekrar tekrar hesaplanmadan elde edilir.
Daha sonra \(\lfloor N/d\rfloor\) blokları dolaşılır. Her blokta \(A(q)\) üçgensel formülle hesaplanır, \(10^9\) modunda karesi alınır, ilgili Möbius önek farkı ile çarpılır ve toplam sonuca eklenir. Bağımsız bloklar paralel de toplanabilir.
Doğrudan tanım \(O(N^2)\) maliyetlidir. Möbius ayrışımından sonra dış toplam yalnızca \(O(\sqrt N)\) farklı bölüm bloğu içerir. Tek bir \(A(M)\) hesabı \(O(\sqrt M)\) sürer; bu maliyet tüm farklı \(M=\lfloor N/d\rfloor\) değerleri üzerinde toplandığında yaklaşık \(O(N^{3/4})\) blok işi verir. Ağırlıklı Möbius önekleri de küçük değerler için elekle, büyük değerler için memoized özyineleme ile alt-kuadratik şekilde hesaplanır. Bellek kullanımı, seçilen elek sınırı artı \(O(\sqrt N)\) kadar blok ve önbellek verisidir.
Sea \(\sigma(n)\) la suma de los divisores positivos de \(n\). Hay que calcular
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sigma(xy)$$
para \(N=10^{11}\), módulo \(10^9\). Una doble suma directa es inviable, así que la solución reescribe \(\sigma(xy)\) separando la parte común de \(x\) e \(y\) y después agrupa las sumas por bloques de cociente constante.
La identidad fundamental utilizada por la implementación es
$$\sigma(xy)=\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
Ambos lados son multiplicativos en el par \((x,y)\), así que basta verificarla en potencias primas. Tomemos \(x=p^a\) y \(y=p^b\).
Si \(a=0\) o \(b=0\), entonces \(\gcd(x,y)=1\) y la igualdad es inmediata. Si \(a,b\ge 1\), solo contribuyen \(d=1\) y \(d=p\), porque \(\mu(p^k)=0\) para \(k\ge 2\). Entonces
$$\begin{aligned} \sum_{d\mid \gcd(p^a,p^b)} \mu(d)\,d\,\sigma\!\left(\frac{p^a}{d}\right)\sigma\!\left(\frac{p^b}{d}\right) &=\sigma(p^a)\sigma(p^b)-p\,\sigma(p^{a-1})\sigma(p^{b-1})\\ &=\frac{(p^{a+1}-1)(p^{b+1}-1)-p(p^a-1)(p^b-1)}{(p-1)^2}\\ &=\frac{p^{a+b+1}-1}{p-1} =\sigma(p^{a+b}). \end{aligned}$$
Como \(p^{a+b}=xy\), la identidad vale para todos los enteros positivos \(x\) e \(y\).
Sustituyendo la identidad en \(S(N)\), obtenemos
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
Ahora cambiamos el orden de sumación y escribimos \(x=da\), \(y=db\). Entonces \(a,b\le \lfloor N/d\rfloor\), y por tanto
$$S(N)=\sum_{d=1}^{N}\mu(d)\,d\left(\sum_{a\le N/d}\sigma(a)\right)\left(\sum_{b\le N/d}\sigma(b)\right).$$
Si definimos
$$A(M)=\sum_{n=1}^{M}\sigma(n),$$
la fórmula principal queda
$$\boxed{S(N)=\sum_{d=1}^{N}\mu(d)\,d\,A\!\left(\left\lfloor\frac{N}{d}\right\rfloor\right)^2.}$$
Desde la definición de \(\sigma\),
$$A(M)=\sum_{n=1}^{M}\sum_{e\mid n} e=\sum_{e=1}^{M} e\left\lfloor\frac{M}{e}\right\rfloor.$$
La implementación usa una forma equivalente basada en números triangulares. Sea
$$T(q)=\frac{q(q+1)}{2}.$$
Entonces
$$A(M)=\sum_{t=1}^{M} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right),$$
porque \(\sum_{e\le M/t} e=T(\lfloor M/t\rfloor)\). Además, \(\lfloor M/t\rfloor\) permanece constante en intervalos. Si
$$q=\left\lfloor\frac{M}{l}\right\rfloor,\qquad r=\left\lfloor\frac{M}{q}\right\rfloor,$$
entonces el bloque completo \(l\le t\le r\) aporta
$$\sum_{t=l}^{r} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right)=(r-l+1)\,T(q).$$
Solo aparecen \(O(\sqrt M)\) bloques distintos.
La suma exterior requiere intervalos de \(\sum d\,\mu(d)\). Se define
$$W(n)=\sum_{k=1}^{n} k\,\mu(k).$$
Los valores pequeños se obtienen con una criba y los grandes mediante una recurrencia con memoización. La identidad clave es
$$\sum_{k=1}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=1.$$
En efecto, al expandir \(W\),
$$\sum_{k=1}^{n} k\sum_{m\le n/k} m\,\mu(m)=\sum_{km\le n} km\,\mu(m)=\sum_{t\le n} t\sum_{m\mid t}\mu(m)=1,$$
ya que \(\sum_{m\mid t}\mu(m)\) solo es no nula cuando \(t=1\). Por lo tanto,
$$W(n)=1-\sum_{k=2}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
Otra vez se agrupan cocientes iguales, sustituyendo cada bloque \(l\le k\le r\) por
$$\left(\sum_{k=l}^{r} k\right)W(v),\qquad v=\left\lfloor\frac{n}{l}\right\rfloor.$$
En la suma final, cuando \(\lfloor N/d\rfloor=q\) es constante en \(l\le d\le r\), toda la contribución del bloque es
$$A(q)^2\sum_{d=l}^{r} d\,\mu(d)=A(q)^2\bigl(W(r)-W(l-1)\bigr).$$
Así, el cálculo solo recorre los \(O(\sqrt N)\) valores distintos de \(\lfloor N/d\rfloor\).
Para \(N=3\), \(\sigma(1)=1\), \(\sigma(2)=3\), \(\sigma(3)=4\), luego
$$A(3)=1+3+4=8,\qquad A(1)=1.$$
La fórmula exterior da
$$S(3)=\mu(1)\cdot 1\cdot A(3)^2+\mu(2)\cdot 2\cdot A(1)^2+\mu(3)\cdot 3\cdot A(1)^2,$$
y por tanto
$$S(3)=64-2-3=59,$$
que coincide con la validación pequeña de las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma idea. Primero precalculan valores de Möbius hasta un límite práctico y almacenan los prefijos de \(k\mu(k)\). Para argumentos grandes reutilizan la recurrencia de \(W(n)\) con memoización, de modo que cada cociente grande se resuelve una sola vez.
Después recorren los bloques de \(\lfloor N/d\rfloor\). En cada bloque evalúan \(A(q)\) con la fórmula triangular por bloques, elevan al cuadrado módulo \(10^9\), multiplican por la diferencia correspondiente del prefijo ponderado de Möbius y acumulan el resultado. Los bloques independientes también pueden sumarse en paralelo.
La definición directa tendría coste \(O(N^2)\). Tras la descomposición con Möbius, la suma exterior solo posee \(O(\sqrt N)\) bloques distintos. Una evaluación de \(A(M)\) cuesta \(O(\sqrt M)\), y al sumar sobre todos los valores distintos \(M=\lfloor N/d\rfloor\) se obtiene aproximadamente \(O(N^{3/4})\) trabajo total de bloques. El prefijo ponderado de Möbius también se maneja en tiempo subcuadrático gracias a la combinación de criba para valores pequeños y recurrencia memoizada para valores grandes. La memoria es lineal en el límite de criba elegido, más \(O(\sqrt N)\) para bloques y caché.
记 \(\sigma(n)\) 为 \(n\) 的所有正因数之和。题目要求计算
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sigma(xy)$$
其中 \(N=10^{11}\)，并对 \(10^9\) 取模。直接枚举所有 \((x,y)\) 对显然不可行，因此实现先把 \(\sigma(xy)\) 改写成可以分离 \(\gcd(x,y)\) 的形式，再用整除分块求和。
实现使用的核心恒等式是
$$\sigma(xy)=\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
等式两边关于二元变量 \((x,y)\) 都是乘法性的，所以只需检查素数幂情形。设 \(x=p^a\)，\(y=p^b\)。
当 \(a=0\) 或 \(b=0\) 时，\(\gcd(x,y)=1\)，恒等式显然成立。若 \(a,b\ge 1\)，由于 \(\mu(p^k)=0\) 对 \(k\ge 2\) 成立，只有 \(d=1\) 和 \(d=p\) 两项保留，于是
$$\begin{aligned} \sum_{d\mid \gcd(p^a,p^b)} \mu(d)\,d\,\sigma\!\left(\frac{p^a}{d}\right)\sigma\!\left(\frac{p^b}{d}\right) &=\sigma(p^a)\sigma(p^b)-p\,\sigma(p^{a-1})\sigma(p^{b-1})\\ &=\frac{(p^{a+1}-1)(p^{b+1}-1)-p(p^a-1)(p^b-1)}{(p-1)^2}\\ &=\frac{p^{a+b+1}-1}{p-1} =\sigma(p^{a+b}). \end{aligned}$$
而 \(p^{a+b}=xy\)，因此该恒等式对所有正整数 \(x,y\) 都成立。
将上式代入 \(S(N)\)，得到
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
交换求和顺序，并写成 \(x=da\)、\(y=db\)，于是 \(a,b\le \lfloor N/d\rfloor\)。因此
$$S(N)=\sum_{d=1}^{N}\mu(d)\,d\left(\sum_{a\le N/d}\sigma(a)\right)\left(\sum_{b\le N/d}\sigma(b)\right).$$
定义约数和前缀函数
$$A(M)=\sum_{n=1}^{M}\sigma(n),$$
便得到主公式
$$\boxed{S(N)=\sum_{d=1}^{N}\mu(d)\,d\,A\!\left(\left\lfloor\frac{N}{d}\right\rfloor\right)^2.}$$
由定义可得
$$A(M)=\sum_{n=1}^{M}\sum_{e\mid n} e=\sum_{e=1}^{M} e\left\lfloor\frac{M}{e}\right\rfloor.$$
实现采用了等价但更适合分块的三角数形式。设
$$T(q)=\frac{q(q+1)}{2}.$$
那么
$$A(M)=\sum_{t=1}^{M} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right),$$
因为固定 \(t\) 时，\(\sum_{e\le M/t} e=T(\lfloor M/t\rfloor)\)。当
$$q=\left\lfloor\frac{M}{l}\right\rfloor,\qquad r=\left\lfloor\frac{M}{q}\right\rfloor$$
时，区间 \(l\le t\le r\) 上的商都相同，于是整段贡献为
$$\sum_{t=l}^{r} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right)=(r-l+1)\,T(q).$$
不同区间的数量只有 \(O(\sqrt M)\)。
外层公式需要大量区间和 \(\sum d\,\mu(d)\)。定义
$$W(n)=\sum_{k=1}^{n} k\,\mu(k).$$
较小的值用筛法预处理，较大的值用带记忆化的递推计算。关键恒等式是
$$\sum_{k=1}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=1.$$
展开 \(W\) 后有
$$\sum_{k=1}^{n} k\sum_{m\le n/k} m\,\mu(m)=\sum_{km\le n} km\,\mu(m)=\sum_{t\le n} t\sum_{m\mid t}\mu(m)=1,$$
因为只有 \(t=1\) 时 \(\sum_{m\mid t}\mu(m)\neq 0\)。因此
$$W(n)=1-\sum_{k=2}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
同样地，按相同商值分块后，每个区间 \(l\le k\le r\) 可以整体替换为
$$\left(\sum_{k=l}^{r} k\right)W(v),\qquad v=\left\lfloor\frac{n}{l}\right\rfloor.$$
当 \(\lfloor N/d\rfloor=q\) 在区间 \(l\le d\le r\) 上保持不变时，整个区间对答案的贡献是
$$A(q)^2\sum_{d=l}^{r} d\,\mu(d)=A(q)^2\bigl(W(r)-W(l-1)\bigr).$$
于是最终只需要遍历 \(\lfloor N/d\rfloor\) 的 \(O(\sqrt N)\) 个不同取值。
当 \(N=3\) 时，\(\sigma(1)=1\)、\(\sigma(2)=3\)、\(\sigma(3)=4\)，所以
$$A(3)=1+3+4=8,\qquad A(1)=1.$$
外层公式给出
$$S(3)=\mu(1)\cdot 1\cdot A(3)^2+\mu(2)\cdot 2\cdot A(1)^2+\mu(3)\cdot 3\cdot A(1)^2,$$
因此
$$S(3)=64-2-3=59,$$
这与实现中的小规模校验结果一致。
C++、Python 和 Java 实现都遵循同一套数论分解。首先在一个合适的上界内预处理 Möbius 值，并保存 \(k\mu(k)\) 的前缀和。对于更大的参数，则利用 \(W(n)\) 的递推关系和记忆化缓存，避免重复求解相同的大商值。
随后程序遍历 \(\lfloor N/d\rfloor\) 的所有分块。对每个分块，先用三角数公式分块计算 \(A(q)\)，再在 \(10^9\) 模下平方，乘上对应的加权 Möbius 前缀差，并把结果累加到总答案中。相互独立的分块还可以并行求和。
直接按定义求和需要 \(O(N^2)\) 次计算，完全不可行。经过 Möbius 分解后，外层只剩下 \(O(\sqrt N)\) 个不同的商值分块。单次计算 \(A(M)\) 需要 \(O(\sqrt M)\) 个块，而把这些代价加总到所有不同的 \(M=\lfloor N/d\rfloor\) 上，整体约为 \(O(N^{3/4})\) 的分块工作量。加权 Möbius 前缀和通过“小值筛法 + 大值记忆化递推”同样保持在远低于平方级的复杂度。空间复杂度为筛法上界的线性规模，再加上 \(O(\sqrt N)\) 的缓存和分块信息。
Пусть \(\sigma(n)\) обозначает сумму всех положительных делителей числа \(n\). Требуется вычислить
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sigma(xy)$$
для \(N=10^{11}\) по модулю \(10^9\). Прямой двойной перебор невозможен, поэтому решение сначала раскладывает \(\sigma(xy)\) по общему делителю чисел \(x\) и \(y\), а затем считает полученные суммы по гармоническим блокам.
Ключевое тождество, используемое в реализации, имеет вид
$$\sigma(xy)=\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
Обе стороны мультипликативны по паре \((x,y)\), поэтому достаточно проверить его на простых степенях. Пусть \(x=p^a\), \(y=p^b\).
Если \(a=0\) или \(b=0\), то \(\gcd(x,y)=1\), и равенство очевидно. При \(a,b\ge 1\) остаются только члены \(d=1\) и \(d=p\), поскольку \(\mu(p^k)=0\) для \(k\ge 2\). Тогда
$$\begin{aligned} \sum_{d\mid \gcd(p^a,p^b)} \mu(d)\,d\,\sigma\!\left(\frac{p^a}{d}\right)\sigma\!\left(\frac{p^b}{d}\right) &=\sigma(p^a)\sigma(p^b)-p\,\sigma(p^{a-1})\sigma(p^{b-1})\\ &=\frac{(p^{a+1}-1)(p^{b+1}-1)-p(p^a-1)(p^b-1)}{(p-1)^2}\\ &=\frac{p^{a+b+1}-1}{p-1} =\sigma(p^{a+b}). \end{aligned}$$
Так как \(p^{a+b}=xy\), тождество верно для всех положительных \(x\) и \(y\).
Подставим тождество в определение \(S(N)\):
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
Меняем порядок суммирования и пишем \(x=da\), \(y=db\). Тогда \(a,b\le \lfloor N/d\rfloor\), и получаем
$$S(N)=\sum_{d=1}^{N}\mu(d)\,d\left(\sum_{a\le N/d}\sigma(a)\right)\left(\sum_{b\le N/d}\sigma(b)\right).$$
Обозначим
$$A(M)=\sum_{n=1}^{M}\sigma(n).$$
Тогда основная формула принимает вид
$$\boxed{S(N)=\sum_{d=1}^{N}\mu(d)\,d\,A\!\left(\left\lfloor\frac{N}{d}\right\rfloor\right)^2.}$$
Из определения функции суммы делителей следует
$$A(M)=\sum_{n=1}^{M}\sum_{e\mid n} e=\sum_{e=1}^{M} e\left\lfloor\frac{M}{e}\right\rfloor.$$
Реализация использует эквивалентную форму через треугольные числа. Пусть
$$T(q)=\frac{q(q+1)}{2}.$$
Тогда
$$A(M)=\sum_{t=1}^{M} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right),$$
потому что \(\sum_{e\le M/t} e=T(\lfloor M/t\rfloor)\). Если
$$q=\left\lfloor\frac{M}{l}\right\rfloor,\qquad r=\left\lfloor\frac{M}{q}\right\rfloor,$$
то на всём интервале \(l\le t\le r\) частное постоянно, и вклад блока равен
$$\sum_{t=l}^{r} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right)=(r-l+1)\,T(q).$$
Таких блоков всего \(O(\sqrt M)\).
Во внешней сумме нужны интервальные значения \(\sum d\,\mu(d)\). Для этого вводится
$$W(n)=\sum_{k=1}^{n} k\,\mu(k).$$
Малые значения считаются решетом, большие восстанавливаются рекурсивно с мемоизацией. Основа рекурсии:
$$\sum_{k=1}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=1.$$
Действительно, после раскрытия \(W\),
$$\sum_{k=1}^{n} k\sum_{m\le n/k} m\,\mu(m)=\sum_{km\le n} km\,\mu(m)=\sum_{t\le n} t\sum_{m\mid t}\mu(m)=1,$$
так как \(\sum_{m\mid t}\mu(m)\) отлично от нуля только при \(t=1\). Поэтому
$$W(n)=1-\sum_{k=2}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
И здесь одинаковые значения частного объединяются в блоки: каждый интервал \(l\le k\le r\) заменяется выражением
$$\left(\sum_{k=l}^{r} k\right)W(v),\qquad v=\left\lfloor\frac{n}{l}\right\rfloor.$$
Если \(\lfloor N/d\rfloor=q\) постоянно на интервале \(l\le d\le r\), то весь блок даёт вклад
$$A(q)^2\sum_{d=l}^{r} d\,\mu(d)=A(q)^2\bigl(W(r)-W(l-1)\bigr).$$
Значит, итоговый алгоритм проходит только по \(O(\sqrt N)\) различным значениям \(\lfloor N/d\rfloor\).
При \(N=3\) имеем \(\sigma(1)=1\), \(\sigma(2)=3\), \(\sigma(3)=4\), поэтому
$$A(3)=1+3+4=8,\qquad A(1)=1.$$
Основная формула даёт
$$S(3)=\mu(1)\cdot 1\cdot A(3)^2+\mu(2)\cdot 2\cdot A(1)^2+\mu(3)\cdot 3\cdot A(1)^2,$$
следовательно,
$$S(3)=64-2-3=59,$$
что совпадает с контрольным значением, используемым в реализациях.
Реализации на C++, Python и Java используют одну и ту же числовую схему. Сначала они предвычисляют значения функции Мёбиуса до практического предела и сохраняют префиксы для \(k\mu(k)\). Для больших аргументов значение \(W(n)\) вычисляется по рекуррентной формуле с мемоизацией, чтобы одинаковые крупные частные не пересчитывались повторно.
Затем программа перебирает блоки постоянного значения \(\lfloor N/d\rfloor\). Для каждого блока вычисляется \(A(q)\) по блочной формуле с треугольными числами, затем это значение возводится в квадрат по модулю \(10^9\), умножается на разность префиксов \(W\) для данного блока и добавляется к ответу. Независимые блоки можно обрабатывать параллельно.
Прямое вычисление по определению имеет сложность \(O(N^2)\). После разложения с функцией Мёбиуса внешняя сумма содержит лишь \(O(\sqrt N)\) различных блоков. Одно вычисление \(A(M)\) требует \(O(\sqrt M)\) шагов, а суммарная стоимость по всем различным значениям \(M=\lfloor N/d\rfloor\) составляет примерно \(O(N^{3/4})\) блочной работы. Префиксная сумма с весами \(d\,\mu(d)\) также вычисляется субквадратично благодаря сочетанию решета для малых значений и мемоизированной рекурсии для больших. Память линейна по выбранному пределу решета плюс \(O(\sqrt N)\) для блоков и кэша.
لتكن \(\sigma(n)\) مجموع القواسم الموجبة للعدد \(n\). المطلوب هو حساب
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sigma(xy)$$
عند \(N=10^{11}\)، ثم أخذ النتيجة بترديد \(10^9\). الجمع المزدوج المباشر غير ممكن عملياً، لذلك يعيد الحل كتابة \(\sigma(xy)\) بطريقة تفصل الجزء المشترك بين \(x\) و\(y\)، ثم يحسب المجاميع الناتجة على كتل يكون فيها خارج القسمة ثابتاً.
المتطابقة الأساسية التي تعتمد عليها الخوارزمية هي
$$\sigma(xy)=\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
الطرفان دالتان ضربيّتان في الزوج \((x,y)\)، ولذلك يكفي التحقق من الحالة التي يكون فيها كل من \(x\) و\(y\) قوة لعدد أولي. لنكتب \(x=p^a\) و\(y=p^b\).
إذا كان \(a=0\) أو \(b=0\) فإن \(\gcd(x,y)=1\) وتصبح المتطابقة مباشرة. أما عندما \(a,b\ge 1\)، فلا يبقى إلا الحدّان \(d=1\) و\(d=p\) لأن \(\mu(p^k)=0\) لكل \(k\ge 2\). وعندئذ نحصل على
$$\begin{aligned} \sum_{d\mid \gcd(p^a,p^b)} \mu(d)\,d\,\sigma\!\left(\frac{p^a}{d}\right)\sigma\!\left(\frac{p^b}{d}\right) &=\sigma(p^a)\sigma(p^b)-p\,\sigma(p^{a-1})\sigma(p^{b-1})\\ &=\frac{(p^{a+1}-1)(p^{b+1}-1)-p(p^a-1)(p^b-1)}{(p-1)^2}\\ &=\frac{p^{a+b+1}-1}{p-1} =\sigma(p^{a+b}). \end{aligned}$$
وبما أن \(p^{a+b}=xy\)، فالمتطابقة صحيحة لكل \(x\) و\(y\).
بعد التعويض في تعريف \(S(N)\) نحصل على
$$S(N)=\sum_{x=1}^{N}\sum_{y=1}^{N}\sum_{d\mid \gcd(x,y)} \mu(d)\,d\,\sigma\!\left(\frac{x}{d}\right)\sigma\!\left(\frac{y}{d}\right).$$
نبدل ترتيب المجاميع، ثم نكتب \(x=da\) و\(y=db\). عندها يكون \(a,b\le \lfloor N/d\rfloor\)، ولذلك
$$S(N)=\sum_{d=1}^{N}\mu(d)\,d\left(\sum_{a\le N/d}\sigma(a)\right)\left(\sum_{b\le N/d}\sigma(b)\right).$$
إذا عرّفنا
$$A(M)=\sum_{n=1}^{M}\sigma(n),$$
فإن الصيغة الرئيسية تصبح
$$\boxed{S(N)=\sum_{d=1}^{N}\mu(d)\,d\,A\!\left(\left\lfloor\frac{N}{d}\right\rfloor\right)^2.}$$
من تعريف مجموع القواسم نحصل على
$$A(M)=\sum_{n=1}^{M}\sum_{e\mid n} e=\sum_{e=1}^{M} e\left\lfloor\frac{M}{e}\right\rfloor.$$
لكن التنفيذ يستخدم صيغة مكافئة أنسب للتجميع على الكتل. لنعرّف
$$T(q)=\frac{q(q+1)}{2}.$$
عندئذ
$$A(M)=\sum_{t=1}^{M} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right),$$
لأن \(\sum_{e\le M/t} e=T(\lfloor M/t\rfloor)\). وإذا كان
$$q=\left\lfloor\frac{M}{l}\right\rfloor,\qquad r=\left\lfloor\frac{M}{q}\right\rfloor,$$
فإن \(\lfloor M/t\rfloor\) يبقى ثابتاً على المجال \(l\le t\le r\)، ويكون إسهام الكتلة كلها
$$\sum_{t=l}^{r} T\!\left(\left\lfloor\frac{M}{t}\right\rfloor\right)=(r-l+1)\,T(q).$$
وعدد هذه الكتل هو فقط \(O(\sqrt M)\).
الصيغة الخارجية تحتاج إلى مجاميع من الشكل \(\sum d\,\mu(d)\) على فترات. لذلك نعرّف
$$W(n)=\sum_{k=1}^{n} k\,\mu(k).$$
القيم الصغيرة تُحسب بالغربال، أما القيم الكبيرة فتُحسب بعلاقة عودية مع الحفظ. المتطابقة الأساسية هنا هي
$$\sum_{k=1}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=1.$$
وبتوسيع \(W\) نحصل على
$$\sum_{k=1}^{n} k\sum_{m\le n/k} m\,\mu(m)=\sum_{km\le n} km\,\mu(m)=\sum_{t\le n} t\sum_{m\mid t}\mu(m)=1,$$
لأن \(\sum_{m\mid t}\mu(m)\) يساوي صفراً إلا عندما \(t=1\). ومن ثم
$$W(n)=1-\sum_{k=2}^{n} k\,W\!\left(\left\lfloor\frac{n}{k}\right\rfloor\right).$$
وكما في الخطوات السابقة، تُجمع القيم ذات خارج القسمة نفسه في كتلة واحدة، ويُستبدل المجال \(l\le k\le r\) بالتعبير
$$\left(\sum_{k=l}^{r} k\right)W(v),\qquad v=\left\lfloor\frac{n}{l}\right\rfloor.$$
إذا كان \(\lfloor N/d\rfloor=q\) ثابتاً على المجال \(l\le d\le r\)، فإن إسهام الكتلة في النتيجة هو
$$A(q)^2\sum_{d=l}^{r} d\,\mu(d)=A(q)^2\bigl(W(r)-W(l-1)\bigr).$$
وهكذا لا يبقى إلا المرور على \(O(\sqrt N)\) قيمة مختلفة لـ \(\lfloor N/d\rfloor\).
عندما \(N=3\)، لدينا \(\sigma(1)=1\)، و\(\sigma(2)=3\)، و\(\sigma(3)=4\)، ومن ثم
$$A(3)=1+3+4=8,\qquad A(1)=1.$$
وتعطي الصيغة الخارجية
$$S(3)=\mu(1)\cdot 1\cdot A(3)^2+\mu(2)\cdot 2\cdot A(1)^2+\mu(3)\cdot 3\cdot A(1)^2,$$
أي
$$S(3)=64-2-3=59,$$
وهو نفس ناتج التحقق الصغير المستخدم في التنفيذ.
تنفذ نسخ C++ وPython وJava البنية العددية نفسها. في البداية تُحسب قيم دالة موبيوس حتى حد عملي، وتُخزن المجاميع التراكمية لـ \(k\mu(k)\). وبعد ذلك تُستخدم علاقة \(W(n)\) مع الحفظ لتقييم القيم الكبيرة مرة واحدة فقط لكل خارج قسمة مميز.
ثم تمر الخوارزمية على كتل \(\lfloor N/d\rfloor\). في كل كتلة يُحسب \(A(q)\) بصيغة الأعداد المثلثية المجمعة، ثم يُربّع modulo \(10^9\)، ويُضرب في فرق المجاميع التراكمية الموزونة، ثم يُضاف إلى المجموع النهائي. كما يمكن جمع الكتل المستقلة على التوازي.
التعريف المباشر يحتاج إلى \(O(N^2)\) عملية، وهذا غير ممكن عند \(N=10^{11}\). بعد تفكيك موبيوس، يصبح لدينا فقط \(O(\sqrt N)\) كتل مختلفة في الجمع الخارجي. حساب واحد لـ \(A(M)\) يكلف \(O(\sqrt M)\)، وعند جمع ذلك على جميع القيم المختلفة \(M=\lfloor N/d\rfloor\) نحصل تقريباً على \(O(N^{3/4})\) من عمل الكتل. كذلك تُحسب البادئة الموزونة لدالة موبيوس بزمن دون تربيعي باستخدام الغربال للقيم الصغيرة والعلاقة المحفوظة للقيم الكبيرة. الذاكرة خطية في حد الغربال المختار، إضافة إلى \(O(\sqrt N)\) لبيانات الكتل والذاكرة المؤقتة.