Define
$$A(n)=\frac{1}{n}\sum_{i=1}^{n}\operatorname{lcm}(i,n),\qquad S(N)=\sum_{k=1}^{N}A(k).$$
The goal is to evaluate \(S(99999999019)\bmod 999999017\). A direct computation of every least common multiple is far too slow, so the solution rewrites the average in terms of multiplicative functions and then evaluates the resulting summatory functions with floor-division blocks.
Fix \(n\). For each \(i\in\{1,\dots,n\}\), let \(d=\gcd(i,n)\), write \(n=dk\), and write \(i=dj\). Then \(\gcd(j,k)=1\), and
$$\operatorname{lcm}(i,n)=\frac{in}{\gcd(i,n)}=\frac{djn}{d}=nj.$$
So the contribution depends only on the reduced residue \(j\) modulo \(k\). For a fixed divisor \(k\mid n\), the admissible \(j\) are exactly the integers \(1\le j\le k\) with \(\gcd(j,k)=1\). Therefore
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=n\sum_{k\mid n}\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j.$$
For \(k>1\), reduced residues come in pairs \(j\) and \(k-j\), so their sum is
$$\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j=\frac{k\varphi(k)}{2}.$$
The special case \(k=1\) contributes \(1\). Combining both cases gives the classical identity
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=\frac{n}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right),$$
hence
$$\boxed{A(n)=\frac{1}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right).}$$
Summing the formula for \(A(n)\) over \(1\le n\le N\) yields
$$S(N)=\frac{1}{2}\left(N+\sum_{n=1}^{N}\sum_{d\mid n}d\varphi(d)\right).$$
Swap the order of summation: every divisor \(d\) contributes once for each multiple of \(d\) up to \(N\), that is, \(\left\lfloor N/d\right\rfloor\) times. Define
$$R(N)=\sum_{d=1}^{N}d\varphi(d)\left\lfloor\frac{N}{d}\right\rfloor.$$
Then
$$\boxed{S(N)=\frac{N+R(N)}{2}.}$$
This is the key reduction: the original lcm-average problem becomes a weighted divisor summatory problem.
Introduce the weighted totient prefix sum
$$P(x)=\sum_{n\le x}n\varphi(n).$$
When \(\left\lfloor N/d\right\rfloor\) is constant on an interval \([l,r]\), we can collapse that whole interval into one prefix-difference:
$$R(N)=\sum_{[l,r]}\left\lfloor\frac{N}{l}\right\rfloor\bigl(P(r)-P(l-1)\bigr).$$
The intervals are determined by the standard rule \(v=\left\lfloor N/l\right\rfloor\), \(r=\left\lfloor N/v\right\rfloor\). There are only \(O(\sqrt{N})\) distinct quotient values, so block decomposition removes the need to scan every \(d\le N\) individually.
Use the identity
$$\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}.$$
Multiplying by \(n\) gives
$$n\varphi(n)=\sum_{d\mid n}d\mu(d)\left(\frac{n}{d}\right)^2.$$
Now sum over \(n\le x\), write \(n=dt\), and separate the variables:
$$P(x)=\sum_{d\le x}d\mu(d)\sum_{t\le x/d}t^2.$$
Let
$$U(m)=\sum_{t=1}^{m}t^2=\frac{m(m+1)(2m+1)}{6}.$$
Then
$$\boxed{P(x)=\sum_{d\le x}d\mu(d)\,U\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
So the only missing ingredient is a fast way to evaluate the prefix sum of \(d\mu(d)\).
Define
$$M(x)=\sum_{n\le x}n\mu(n).$$
Set \(f(n)=n\mu(n)\). The Dirichlet-convolution identity \(\operatorname{id}*\mu=\varphi\) implies another useful relation:
$$\sum_{d\mid m} d\,f\!\left(\frac{m}{d}\right)=m\sum_{e\mid m}\mu(e)= \begin{cases} 1,&m=1,\\ 0,&m>1. \end{cases}$$
Summing this over \(1\le m\le x\) and exchanging the order of summation gives
$$\sum_{d\le x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right)=1.$$
Separating the term \(d=1\) yields the recursion
$$\boxed{M(x)=1-\sum_{d=2}^{x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
Again, \(\left\lfloor x/d\right\rfloor\) is constant on quotient blocks, so this becomes
$$M(x)=1-\sum_{[l,r]\subseteq[2,x]}\left(\sum_{d=l}^{r}d\right)M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right).$$
The arithmetic progression sum \(\sum_{d=l}^{r}d=\frac{(l+r)(r-l+1)}{2}\) is what makes each block computable in constant time.
For \(n=10\), the divisors are \(1,2,5,10\), and
$$1\cdot\varphi(1)=1,\qquad 2\cdot\varphi(2)=2,\qquad 5\cdot\varphi(5)=20,\qquad 10\cdot\varphi(10)=40.$$
Therefore
$$A(10)=\frac{1}{2}(1+1+2+20+40)=32.$$
For the full prefix \(N=10\), compute
$$R(10)=\sum_{d=1}^{10}d\varphi(d)\left\lfloor\frac{10}{d}\right\rfloor=274,$$
so
$$S(10)=\frac{10+274}{2}=142.$$
This agrees with a direct brute-force evaluation of the first ten averages.
The C++, Python, and Java implementations all follow the same plan. They precompute \(\mu(n)\), \(\varphi(n)\), and the small prefix sums of \(n\mu(n)\) and \(n\varphi(n)\) up to a threshold \(L\approx N^{2/3}\) using a linear sieve. For arguments above that threshold, they evaluate the two large prefix functions recursively, cache every large result, and always group terms by equal floor-division quotients. The final summation for \(R(N)\) uses the same block structure. Because the modulus is prime, the divisions by \(2\) and \(6\) are carried out through modular inverses.
The sieve up to \(L\approx N^{2/3}\) costs \(O(L)\) time and \(O(L)\) memory. Each uncached large query visits only the distinct intervals on which a floor quotient is constant, rather than every integer one by one. With memoization, the total amount of large-query work stays on the same practical scale as the preprocessing. For the target size \(N\approx 10^{11}\), this reduces the problem from impossible brute force to an \(O(N^{2/3})\)-scale method in time and memory.
Definiert sind
$$A(n)=\frac{1}{n}\sum_{i=1}^{n}\operatorname{lcm}(i,n),\qquad S(N)=\sum_{k=1}^{N}A(k).$$
Gesucht ist \(S(99999999019)\bmod 999999017\). Eine direkte Berechnung aller kgV-Werte ist viel zu langsam, deshalb formt die Lösung den Mittelwert in Summen über multiplikative Funktionen um und wertet diese dann blockweise nach konstantem Ganzzahlquotienten aus.
Fixiere \(n\). Für jedes \(i\in\{1,\dots,n\}\) setze \(d=\gcd(i,n)\), schreibe \(n=dk\) und \(i=dj\). Dann gilt \(\gcd(j,k)=1\) und
$$\operatorname{lcm}(i,n)=\frac{in}{\gcd(i,n)}=\frac{djn}{d}=nj.$$
Damit hängt der Beitrag nur noch vom reduzierten Rest \(j\) modulo \(k\) ab. Für einen festen Teiler \(k\mid n\) sind die zulässigen \(j\) genau die Zahlen \(1\le j\le k\) mit \(\gcd(j,k)=1\). Also
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=n\sum_{k\mid n}\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j.$$
Für \(k>1\) treten reduzierte Reste paarweise als \(j\) und \(k-j\) auf, daher ist ihre Summe
$$\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j=\frac{k\varphi(k)}{2}.$$
Der Sonderfall \(k=1\) liefert den Beitrag \(1\). Insgesamt folgt damit
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=\frac{n}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right),$$
und somit
$$\boxed{A(n)=\frac{1}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right).}$$
Summiert man diese Formel für alle \(1\le n\le N\), so erhält man
$$S(N)=\frac{1}{2}\left(N+\sum_{n=1}^{N}\sum_{d\mid n}d\varphi(d)\right).$$
Vertauscht man die Summationsreihenfolge, dann trägt jeder Teiler \(d\) genau für seine Vielfachen bis \(N\) bei, also \(\left\lfloor N/d\right\rfloor\)-mal. Definiere daher
$$R(N)=\sum_{d=1}^{N}d\varphi(d)\left\lfloor\frac{N}{d}\right\rfloor.$$
Dann gilt
$$\boxed{S(N)=\frac{N+R(N)}{2}.}$$
Damit ist das ursprüngliche kgV-Mittelwertproblem auf eine gewichtete Summation über Teiler reduziert.
Führe die gewichtete Phi-Präfixsumme ein:
$$P(x)=\sum_{n\le x}n\varphi(n).$$
Ist \(\left\lfloor N/d\right\rfloor\) auf einem Intervall \([l,r]\) konstant, kann der ganze Block durch eine einzige Präfixdifferenz ersetzt werden:
$$R(N)=\sum_{[l,r]}\left\lfloor\frac{N}{l}\right\rfloor\bigl(P(r)-P(l-1)\bigr).$$
Die Blöcke ergeben sich aus \(v=\left\lfloor N/l\right\rfloor\) und \(r=\left\lfloor N/v\right\rfloor\). Da es nur \(O(\sqrt{N})\) verschiedene Quotienten gibt, muss man nicht mehr alle \(d\le N\) einzeln durchlaufen.
Verwendet wird die Identität
$$\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}.$$
Nach Multiplikation mit \(n\) erhält man
$$n\varphi(n)=\sum_{d\mid n}d\mu(d)\left(\frac{n}{d}\right)^2.$$
Summiert man über \(n\le x\) und setzt \(n=dt\), so folgt
$$P(x)=\sum_{d\le x}d\mu(d)\sum_{t\le x/d}t^2.$$
Mit
$$U(m)=\sum_{t=1}^{m}t^2=\frac{m(m+1)(2m+1)}{6}$$
wird daraus
$$\boxed{P(x)=\sum_{d\le x}d\mu(d)\,U\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
Damit bleibt als eigentliche Schwierigkeit nur noch die schnelle Berechnung der Präfixsumme von \(d\mu(d)\).
Definiere
$$M(x)=\sum_{n\le x}n\mu(n).$$
Setze \(f(n)=n\mu(n)\). Aus der Dirichlet-Faltung folgt die Relation
$$\sum_{d\mid m} d\,f\!\left(\frac{m}{d}\right)=m\sum_{e\mid m}\mu(e)= \begin{cases} 1,&m=1,\\ 0,&m>1. \end{cases}$$
Summiert man dies für \(1\le m\le x\) und vertauscht die Reihenfolge, erhält man
$$\sum_{d\le x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right)=1.$$
Nach Abtrennung des Terms \(d=1\) ergibt sich die Rekursion
$$\boxed{M(x)=1-\sum_{d=2}^{x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
Auch hier ist \(\left\lfloor x/d\right\rfloor\) auf Intervallen konstant, also
$$M(x)=1-\sum_{[l,r]\subseteq[2,x]}\left(\sum_{d=l}^{r}d\right)M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right).$$
Die Summe \(\sum_{d=l}^{r}d=\frac{(l+r)(r-l+1)}{2}\) macht jeden Block in \(O(1)\) auswertbar.
Für \(n=10\) sind die Teiler \(1,2,5,10\), also
$$1\cdot\varphi(1)=1,\qquad 2\cdot\varphi(2)=2,\qquad 5\cdot\varphi(5)=20,\qquad 10\cdot\varphi(10)=40.$$
Daher
$$A(10)=\frac{1}{2}(1+1+2+20+40)=32.$$
Für den Präfix bis \(N=10\) erhält man
$$R(10)=\sum_{d=1}^{10}d\varphi(d)\left\lfloor\frac{10}{d}\right\rfloor=274,$$
also
$$S(10)=\frac{10+274}{2}=142.$$
Das stimmt mit einer direkten Auswertung der ersten zehn Mittelwerte überein.
Die C++-, Python- und Java-Implementierungen verfolgen dieselbe Strategie. Zuerst werden \(\mu(n)\), \(\varphi(n)\) sowie die kleinen Präfixsummen von \(n\mu(n)\) und \(n\varphi(n)\) bis zu einer Grenze \(L\approx N^{2/3}\) mit einem linearen Sieb vorab berechnet. Für größere Argumente werden die beiden großen Präfixfunktionen rekursiv bestimmt, alle großen Ergebnisse zwischengespeichert und sämtliche Summen über Quotientenblöcke ausgewertet. Die Schlussformel für \(R(N)\) benutzt dieselbe Blockstruktur. Da der Modulus prim ist, werden die Divisionen durch \(2\) und \(6\) über modulare Inverse umgesetzt.
Das lineare Sieb bis \(L\approx N^{2/3}\) benötigt \(O(L)\) Zeit und \(O(L)\) Speicher. Jede nicht gecachte große Anfrage besucht nur die Intervalle, auf denen ein Ganzzahlquotient konstant bleibt, statt alle Werte einzeln abzulaufen. Mit Memoisierung bleibt die gesamte Zusatzarbeit praktisch in derselben Größenordnung wie die Vorverarbeitung. Für \(N\approx 10^{11}\) wird das Problem so von einer unbrauchbaren Brute-Force-Methode auf ein Verfahren der Größenordnung \(O(N^{2/3})\) in Zeit und Speicher reduziert.
Tanımlar şunlardır:
$$A(n)=\frac{1}{n}\sum_{i=1}^{n}\operatorname{lcm}(i,n),\qquad S(N)=\sum_{k=1}^{N}A(k).$$
Amaç \(S(99999999019)\bmod 999999017\) değerini bulmaktır. Tüm EKOK değerlerini tek tek hesaplamak mümkün olmadığı için çözüm, ortalamayı çarpımsal fonksiyonlar cinsinden yeniden yazar ve ortaya çıkan toplamları sabit bölüm bloklarıyla hesaplar.
Sabit bir \(n\) alalım. Her \(i\in\{1,\dots,n\}\) için \(d=\gcd(i,n)\) olsun; \(n=dk\) ve \(i=dj\) yazalım. Bu durumda \(\gcd(j,k)=1\) ve
$$\operatorname{lcm}(i,n)=\frac{in}{\gcd(i,n)}=\frac{djn}{d}=nj.$$
Yani katkı artık yalnızca \(k\) modülüne göre asal kalıntı olan \(j\)'ye bağlıdır. Sabit bir \(k\mid n\) için uygun \(j\) değerleri, \(\gcd(j,k)=1\) koşulunu sağlayan \(1\le j\le k\) sayılarıdır. Dolayısıyla
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=n\sum_{k\mid n}\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j.$$
\(k>1\) için bu kalıntılar \(j\) ve \(k-j\) çiftleri halinde gelir; bu nedenle toplamları
$$\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j=\frac{k\varphi(k)}{2}$$
olur. \(k=1\) durumu ise \(1\) katkısı verir. Böylece
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=\frac{n}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right),$$
ve sonuç olarak
$$\boxed{A(n)=\frac{1}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right).}$$
Bu formülü \(1\le n\le N\) için toplarsak
$$S(N)=\frac{1}{2}\left(N+\sum_{n=1}^{N}\sum_{d\mid n}d\varphi(d)\right)$$
elde edilir. Toplam sırasını değiştirince her \(d\) böleni, \(N\)'ye kadar olan katları kadar yani \(\left\lfloor N/d\right\rfloor\) kez görünür. Bu yüzden
$$R(N)=\sum_{d=1}^{N}d\varphi(d)\left\lfloor\frac{N}{d}\right\rfloor$$
tanımını yaparsak
$$\boxed{S(N)=\frac{N+R(N)}{2}.}$$
Böylece başlangıçtaki EKOK ortalaması problemi, ağırlıklı bir bölen toplamı problemine indirgenmiş olur.
Ağırlıklı phi önek toplamını tanımlayalım:
$$P(x)=\sum_{n\le x}n\varphi(n).$$
\(\left\lfloor N/d\right\rfloor\) değeri bir \([l,r]\) aralığında sabitse, o aralığın tamamı tek bir önek farkı olarak yazılabilir:
$$R(N)=\sum_{[l,r]}\left\lfloor\frac{N}{l}\right\rfloor\bigl(P(r)-P(l-1)\bigr).$$
Bloklar \(v=\left\lfloor N/l\right\rfloor\) ve \(r=\left\lfloor N/v\right\rfloor\) kuralıyla bulunur. Farklı bölüm sayısı yalnızca \(O(\sqrt{N})\) olduğundan tüm \(d\) değerlerini tek tek dolaşmak gerekmez.
Şu özdeşlik kullanılır:
$$\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}.$$
Bunu \(n\) ile çarpınca
$$n\varphi(n)=\sum_{d\mid n}d\mu(d)\left(\frac{n}{d}\right)^2$$
elde edilir. Şimdi \(n\le x\) üzerinde toplayıp \(n=dt\) yazalım:
$$P(x)=\sum_{d\le x}d\mu(d)\sum_{t\le x/d}t^2.$$
Ayrıca
$$U(m)=\sum_{t=1}^{m}t^2=\frac{m(m+1)(2m+1)}{6}$$
olduğundan
$$\boxed{P(x)=\sum_{d\le x}d\mu(d)\,U\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
Demek ki asıl ihtiyaç duyulan şey, \(d\mu(d)\) önek toplamını hızlı hesaplamaktır.
Şimdi
$$M(x)=\sum_{n\le x}n\mu(n)$$
olsun. \(f(n)=n\mu(n)\) dersek Dirichlet konvolüsyonundan şu ilişki gelir:
$$\sum_{d\mid m} d\,f\!\left(\frac{m}{d}\right)=m\sum_{e\mid m}\mu(e)= \begin{cases} 1,&m=1,\\ 0,&m>1. \end{cases}$$
Bunu \(1\le m\le x\) için toplayıp sıraları değiştirince
$$\sum_{d\le x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right)=1$$
elde edilir. \(d=1\) terimini ayırırsak
$$\boxed{M(x)=1-\sum_{d=2}^{x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
Burada da \(\left\lfloor x/d\right\rfloor\) bloklar üzerinde sabittir; dolayısıyla
$$M(x)=1-\sum_{[l,r]\subseteq[2,x]}\left(\sum_{d=l}^{r}d\right)M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right).$$
Aritmetik toplam \(\sum_{d=l}^{r}d=\frac{(l+r)(r-l+1)}{2}\) olduğu için her blok sabit zamanda işlenebilir.
\(n=10\) için bölenler \(1,2,5,10\) olur ve
$$1\cdot\varphi(1)=1,\qquad 2\cdot\varphi(2)=2,\qquad 5\cdot\varphi(5)=20,\qquad 10\cdot\varphi(10)=40.$$
Buradan
$$A(10)=\frac{1}{2}(1+1+2+20+40)=32$$
çıkar. Tüm önek için ise
$$R(10)=\sum_{d=1}^{10}d\varphi(d)\left\lfloor\frac{10}{d}\right\rfloor=274,$$
dolayısıyla
$$S(10)=\frac{10+274}{2}=142.$$
Bu değer, ilk on terimi doğrudan hesaplayarak da doğrulanır.
C++, Python ve Java uygulamaları aynı planı izler. Önce \(L\approx N^{2/3}\) eşiğine kadar \(\mu(n)\), \(\varphi(n)\), \(n\mu(n)\) önekleri ve \(n\varphi(n)\) önekleri lineer elek ile önceden hesaplanır. Bu eşikten büyük argümanlar için iki büyük önek fonksiyonu özyinelemeli biçimde değerlendirilir, tüm büyük sonuçlar bellekte tutulur ve tüm toplamlar sabit bölüm bloklarına ayrılarak yürütülür. Son aşamada \(R(N)\) da aynı blok tekniğiyle toplanır. Modül asal olduğu için \(2\) ve \(6\) ile bölmeler modüler ters kullanılarak yapılır.
\(L\approx N^{2/3}\) sınırına kadar lineer elek \(O(L)\) zaman ve \(O(L)\) bellek kullanır. Büyük önek sorgularının her biri, tüm sayıları tek tek gezmek yerine yalnızca bölümün değiştiği aralıkları işler. Memoization ile birlikte toplam ek iş, pratikte ön işleme ile aynı büyüklük düzeninde kalır. Böylece \(N\approx 10^{11}\) için yöntem, kaba kuvvetin yerine zaman ve bellek açısından \(O(N^{2/3})\) ölçeğinde çalışan uygulanabilir bir çözüm haline gelir.
Se definen
$$A(n)=\frac{1}{n}\sum_{i=1}^{n}\operatorname{lcm}(i,n),\qquad S(N)=\sum_{k=1}^{N}A(k).$$
Hay que calcular \(S(99999999019)\bmod 999999017\). Un cálculo directo de todos los m.c.m. es inviable, así que la solución transforma el promedio en sumas sobre funciones multiplicativas y luego evalúa esas sumas agrupando intervalos con el mismo cociente entero.
Fijemos \(n\). Para cada \(i\in\{1,\dots,n\}\), sea \(d=\gcd(i,n)\), escribamos \(n=dk\) e \(i=dj\). Entonces \(\gcd(j,k)=1\) y
$$\operatorname{lcm}(i,n)=\frac{in}{\gcd(i,n)}=\frac{djn}{d}=nj.$$
Por tanto, la contribución depende solo del residuo reducido \(j\) módulo \(k\). Para un divisor fijo \(k\mid n\), los valores admisibles de \(j\) son exactamente los enteros \(1\le j\le k\) con \(\gcd(j,k)=1\). Así,
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=n\sum_{k\mid n}\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j.$$
Si \(k>1\), los residuos reducidos aparecen en pares \(j\) y \(k-j\), de modo que
$$\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j=\frac{k\varphi(k)}{2}.$$
El caso especial \(k=1\) aporta \(1\). En consecuencia,
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=\frac{n}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right),$$
y por lo tanto
$$\boxed{A(n)=\frac{1}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right).}$$
Si sumamos esta fórmula para \(1\le n\le N\), obtenemos
$$S(N)=\frac{1}{2}\left(N+\sum_{n=1}^{N}\sum_{d\mid n}d\varphi(d)\right).$$
Al intercambiar el orden de sumación, cada divisor \(d\) aparece una vez por cada múltiplo suyo hasta \(N\), es decir, \(\left\lfloor N/d\right\rfloor\) veces. Definimos entonces
$$R(N)=\sum_{d=1}^{N}d\varphi(d)\left\lfloor\frac{N}{d}\right\rfloor.$$
Así resulta
$$\boxed{S(N)=\frac{N+R(N)}{2}.}$$
El problema original de promedios de m.c.m. queda reducido a una suma ponderada sobre divisores.
Introduzcamos la suma prefija ponderada
$$P(x)=\sum_{n\le x}n\varphi(n).$$
Cuando \(\left\lfloor N/d\right\rfloor\) es constante en un intervalo \([l,r]\), todo ese intervalo se resume en una sola diferencia de prefijos:
$$R(N)=\sum_{[l,r]}\left\lfloor\frac{N}{l}\right\rfloor\bigl(P(r)-P(l-1)\bigr).$$
Los bloques se obtienen con \(v=\left\lfloor N/l\right\rfloor\) y \(r=\left\lfloor N/v\right\rfloor\). Como solo hay \(O(\sqrt{N})\) valores distintos del cociente, ya no es necesario recorrer todos los \(d\le N\).
Usamos la identidad
$$\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}.$$
Multiplicando por \(n\), se obtiene
$$n\varphi(n)=\sum_{d\mid n}d\mu(d)\left(\frac{n}{d}\right)^2.$$
Ahora sumamos para \(n\le x\), escribimos \(n=dt\) y separamos variables:
$$P(x)=\sum_{d\le x}d\mu(d)\sum_{t\le x/d}t^2.$$
Con
$$U(m)=\sum_{t=1}^{m}t^2=\frac{m(m+1)(2m+1)}{6},$$
queda
$$\boxed{P(x)=\sum_{d\le x}d\mu(d)\,U\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
Así, el problema se reduce a calcular rápidamente el prefijo de \(d\mu(d)\).
Definamos
$$M(x)=\sum_{n\le x}n\mu(n).$$
Si \(f(n)=n\mu(n)\), entonces una identidad de convolución da
$$\sum_{d\mid m} d\,f\!\left(\frac{m}{d}\right)=m\sum_{e\mid m}\mu(e)= \begin{cases} 1,&m=1,\\ 0,&m>1. \end{cases}$$
Al sumar para \(1\le m\le x\) e intercambiar el orden de las sumas, obtenemos
$$\sum_{d\le x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right)=1.$$
Separando el término \(d=1\), aparece la recurrencia
$$\boxed{M(x)=1-\sum_{d=2}^{x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
Como \(\left\lfloor x/d\right\rfloor\) también es constante por bloques, se obtiene
$$M(x)=1-\sum_{[l,r]\subseteq[2,x]}\left(\sum_{d=l}^{r}d\right)M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right).$$
La suma aritmética \(\sum_{d=l}^{r}d=\frac{(l+r)(r-l+1)}{2}\) permite resolver cada bloque en tiempo constante.
Para \(n=10\), los divisores son \(1,2,5,10\), y
$$1\cdot\varphi(1)=1,\qquad 2\cdot\varphi(2)=2,\qquad 5\cdot\varphi(5)=20,\qquad 10\cdot\varphi(10)=40.$$
Por eso
$$A(10)=\frac{1}{2}(1+1+2+20+40)=32.$$
Para la suma acumulada hasta \(N=10\),
$$R(10)=\sum_{d=1}^{10}d\varphi(d)\left\lfloor\frac{10}{d}\right\rfloor=274,$$
y entonces
$$S(10)=\frac{10+274}{2}=142.$$
Ese valor coincide con una verificación directa término por término.
Las implementaciones en C++, Python y Java siguen la misma estrategia. Primero precalculan \(\mu(n)\), \(\varphi(n)\) y los prefijos pequeños de \(n\mu(n)\) y \(n\varphi(n)\) hasta un umbral \(L\approx N^{2/3}\) mediante una criba lineal. Para argumentos mayores que ese umbral, evalúan recursivamente las dos funciones prefijo grandes, memorizan cada resultado grande y agrupan todos los términos por bloques con el mismo cociente entero. La suma final de \(R(N)\) usa exactamente la misma técnica. Como el módulo es primo, las divisiones por \(2\) y \(6\) se realizan con inversos modulares.
La criba lineal hasta \(L\approx N^{2/3}\) cuesta \(O(L)\) tiempo y \(O(L)\) memoria. Cada consulta grande no memorizada visita solo los intervalos donde cambia el valor de un cociente entero, en lugar de recorrer todos los enteros uno a uno. Con memoización, el trabajo adicional total se mantiene en la misma escala práctica que la fase de preproceso. Para \(N\approx 10^{11}\), esto convierte un enfoque imposible por fuerza bruta en un método de escala \(O(N^{2/3})\) tanto en tiempo como en memoria.
定义
$$A(n)=\frac{1}{n}\sum_{i=1}^{n}\operatorname{lcm}(i,n),\qquad S(N)=\sum_{k=1}^{N}A(k).$$
目标是求 \(S(99999999019)\bmod 999999017\)。如果直接枚举所有最小公倍数，复杂度完全不可接受，因此解法先把平均值改写成乘法函数的求和，再用整除分块去计算这些前缀和。
固定 \(n\)。对每个 \(i\in\{1,\dots,n\}\)，令 \(d=\gcd(i,n)\)，并写成 \(n=dk,\ i=dj\)。此时 \(\gcd(j,k)=1\)，而且
$$\operatorname{lcm}(i,n)=\frac{in}{\gcd(i,n)}=\frac{djn}{d}=nj.$$
所以每一项的贡献只取决于模 \(k\) 的既约剩余 \(j\)。对固定的因子 \(k\mid n\)，合法的 \(j\) 正好是满足 \(\gcd(j,k)=1\) 的 \(1\le j\le k\)。于是
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=n\sum_{k\mid n}\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j.$$
当 \(k>1\) 时，既约剩余可以按 \(j\) 与 \(k-j\) 配对，因此它们的和为
$$\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j=\frac{k\varphi(k)}{2}.$$
\(k=1\) 时单独贡献 \(1\)。合并后得到经典恒等式
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=\frac{n}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right),$$
因此
$$\boxed{A(n)=\frac{1}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right).}$$
对 \(1\le n\le N\) 求和可得
$$S(N)=\frac{1}{2}\left(N+\sum_{n=1}^{N}\sum_{d\mid n}d\varphi(d)\right).$$
交换求和次序后，每个 \(d\) 会在不超过 \(N\) 的所有倍数中各出现一次，也就是出现 \(\left\lfloor N/d\right\rfloor\) 次。定义
$$R(N)=\sum_{d=1}^{N}d\varphi(d)\left\lfloor\frac{N}{d}\right\rfloor.$$
则有
$$\boxed{S(N)=\frac{N+R(N)}{2}.}$$
这样，原始的最小公倍数平均值问题就转成了一个带权因子前缀和问题。
引入加权欧拉函数前缀和
$$P(x)=\sum_{n\le x}n\varphi(n).$$
当 \(\left\lfloor N/d\right\rfloor\) 在区间 \([l,r]\) 上保持不变时，整段可以压缩成一个前缀差：
$$R(N)=\sum_{[l,r]}\left\lfloor\frac{N}{l}\right\rfloor\bigl(P(r)-P(l-1)\bigr).$$
区间由 \(v=\left\lfloor N/l\right\rfloor\)、\(r=\left\lfloor N/v\right\rfloor\) 确定。因为不同的整除商只有 \(O(\sqrt{N})\) 个，所以不需要逐个遍历所有 \(d\le N\)。
使用恒等式
$$\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}.$$
两边乘以 \(n\)，得到
$$n\varphi(n)=\sum_{d\mid n}d\mu(d)\left(\frac{n}{d}\right)^2.$$
接着对 \(n\le x\) 求和，并令 \(n=dt\)，便有
$$P(x)=\sum_{d\le x}d\mu(d)\sum_{t\le x/d}t^2.$$
再定义
$$U(m)=\sum_{t=1}^{m}t^2=\frac{m(m+1)(2m+1)}{6},$$
于是
$$\boxed{P(x)=\sum_{d\le x}d\mu(d)\,U\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
所以核心任务变成了快速求出 \(d\mu(d)\) 的前缀和。
设
$$M(x)=\sum_{n\le x}n\mu(n).$$
记 \(f(n)=n\mu(n)\)。由狄利克雷卷积可以推出
$$\sum_{d\mid m} d\,f\!\left(\frac{m}{d}\right)=m\sum_{e\mid m}\mu(e)= \begin{cases} 1,&m=1,\\ 0,&m>1. \end{cases}$$
把它对 \(1\le m\le x\) 求和并交换顺序，得到
$$\sum_{d\le x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right)=1.$$
把 \(d=1\) 的项移到左边，就得到递推公式
$$\boxed{M(x)=1-\sum_{d=2}^{x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
由于 \(\left\lfloor x/d\right\rfloor\) 仍然可以按区间分块，所以还可以写成
$$M(x)=1-\sum_{[l,r]\subseteq[2,x]}\left(\sum_{d=l}^{r}d\right)M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right).$$
其中 \(\sum_{d=l}^{r}d=\frac{(l+r)(r-l+1)}{2}\)，因此每个区间都能在常数时间内处理。
当 \(n=10\) 时，它的因子是 \(1,2,5,10\)，并且
$$1\cdot\varphi(1)=1,\qquad 2\cdot\varphi(2)=2,\qquad 5\cdot\varphi(5)=20,\qquad 10\cdot\varphi(10)=40.$$
所以
$$A(10)=\frac{1}{2}(1+1+2+20+40)=32.$$
对前十项总和来说，
$$R(10)=\sum_{d=1}^{10}d\varphi(d)\left\lfloor\frac{10}{d}\right\rfloor=274,$$
从而
$$S(10)=\frac{10+274}{2}=142.$$
这和直接暴力计算前十个平均值完全一致。
C++、Python 和 Java 实现遵循同一条主线。先用线性筛预处理到阈值 \(L\approx N^{2/3}\)，得到 \(\mu(n)\)、\(\varphi(n)\) 以及 \(n\mu(n)\)、\(n\varphi(n)\) 的小范围前缀和。对于超过这个阈值的大参数，再递归计算两个大前缀函数，并把每个大结果缓存起来。所有求和步骤都按整除商不变的区间来分块，最终的 \(R(N)\) 也是同样处理。由于模数是素数，除以 \(2\) 和 \(6\) 时使用的是模逆元。
线性筛到 \(L\approx N^{2/3}\) 需要 \(O(L)\) 时间和 \(O(L)\) 空间。每个未缓存的大查询只访问整除商发生变化的那些区间，而不是逐个访问所有整数。结合记忆化以后，总体额外工作量在实践中与预处理处于同一数量级。对 \(N\approx 10^{11}\) 这样的规模，这就把原本完全不可行的暴力算法降到了时间和空间都约为 \(O(N^{2/3})\) 的层级。
Определены функции
$$A(n)=\frac{1}{n}\sum_{i=1}^{n}\operatorname{lcm}(i,n),\qquad S(N)=\sum_{k=1}^{N}A(k).$$
Требуется вычислить \(S(99999999019)\bmod 999999017\). Прямой перебор всех значений НОК невозможен, поэтому решение переписывает среднее через мультипликативные функции и затем вычисляет соответствующие сумматорные функции по блокам одинакового целочисленного частного.
Зафиксируем \(n\). Для каждого \(i\in\{1,\dots,n\}\) положим \(d=\gcd(i,n)\), запишем \(n=dk\) и \(i=dj\). Тогда \(\gcd(j,k)=1\), а
$$\operatorname{lcm}(i,n)=\frac{in}{\gcd(i,n)}=\frac{djn}{d}=nj.$$
Значит, вклад определяется только приведённым вычетом \(j\) по модулю \(k\). При фиксированном делителе \(k\mid n\) допустимые \(j\) - это все числа \(1\le j\le k\), взаимно простые с \(k\). Поэтому
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=n\sum_{k\mid n}\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j.$$
Если \(k>1\), приведённые вычеты разбиваются на пары \(j\) и \(k-j\), так что
$$\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j=\frac{k\varphi(k)}{2}.$$
Особый случай \(k=1\) даёт вклад \(1\). В итоге получаем
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=\frac{n}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right),$$
и, следовательно,
$$\boxed{A(n)=\frac{1}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right).}$$
Суммируя эту формулу по всем \(1\le n\le N\), получаем
$$S(N)=\frac{1}{2}\left(N+\sum_{n=1}^{N}\sum_{d\mid n}d\varphi(d)\right).$$
Если поменять порядок суммирования, каждый делитель \(d\) учитывается по одному разу для каждого своего кратного, не превосходящего \(N\), то есть \(\left\lfloor N/d\right\rfloor\) раз. Обозначим
$$R(N)=\sum_{d=1}^{N}d\varphi(d)\left\lfloor\frac{N}{d}\right\rfloor.$$
Тогда
$$\boxed{S(N)=\frac{N+R(N)}{2}.}$$
Тем самым задача о среднем НОК сводится к взвешенной сумме по делителям.
Введём префиксную сумму
$$P(x)=\sum_{n\le x}n\varphi(n).$$
Если \(\left\lfloor N/d\right\rfloor\) постоянно на отрезке \([l,r]\), весь этот отрезок сжимается в одну разность префиксов:
$$R(N)=\sum_{[l,r]}\left\lfloor\frac{N}{l}\right\rfloor\bigl(P(r)-P(l-1)\bigr).$$
Блоки задаются правилом \(v=\left\lfloor N/l\right\rfloor\), \(r=\left\lfloor N/v\right\rfloor\). Поскольку различных значений частного всего \(O(\sqrt{N})\), обход всех \(d\le N\) больше не нужен.
Используем тождество
$$\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}.$$
Умножая на \(n\), получаем
$$n\varphi(n)=\sum_{d\mid n}d\mu(d)\left(\frac{n}{d}\right)^2.$$
Теперь суммируем по \(n\le x\), подставляем \(n=dt\) и разделяем переменные:
$$P(x)=\sum_{d\le x}d\mu(d)\sum_{t\le x/d}t^2.$$
Положим
$$U(m)=\sum_{t=1}^{m}t^2=\frac{m(m+1)(2m+1)}{6}.$$
Тогда
$$\boxed{P(x)=\sum_{d\le x}d\mu(d)\,U\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
Таким образом, нужно лишь быстро считать префикс для \(d\mu(d)\).
Определим
$$M(x)=\sum_{n\le x}n\mu(n).$$
Пусть \(f(n)=n\mu(n)\). Тогда из свёртки следует соотношение
$$\sum_{d\mid m} d\,f\!\left(\frac{m}{d}\right)=m\sum_{e\mid m}\mu(e)= \begin{cases} 1,&m=1,\\ 0,&m>1. \end{cases}$$
Суммируя его по \(1\le m\le x\) и меняя порядок суммирования, получаем
$$\sum_{d\le x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right)=1.$$
Выделяя член \(d=1\), имеем рекурсию
$$\boxed{M(x)=1-\sum_{d=2}^{x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
И здесь \(\left\lfloor x/d\right\rfloor\) постоянно на блоках, поэтому
$$M(x)=1-\sum_{[l,r]\subseteq[2,x]}\left(\sum_{d=l}^{r}d\right)M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right).$$
Арифметическая сумма \(\sum_{d=l}^{r}d=\frac{(l+r)(r-l+1)}{2}\) делает обработку каждого блока константной.
Для \(n=10\) делители равны \(1,2,5,10\), и
$$1\cdot\varphi(1)=1,\qquad 2\cdot\varphi(2)=2,\qquad 5\cdot\varphi(5)=20,\qquad 10\cdot\varphi(10)=40.$$
Значит,
$$A(10)=\frac{1}{2}(1+1+2+20+40)=32.$$
Для полного префикса до \(N=10\)
$$R(10)=\sum_{d=1}^{10}d\varphi(d)\left\lfloor\frac{10}{d}\right\rfloor=274,$$
и поэтому
$$S(10)=\frac{10+274}{2}=142.$$
Это совпадает с прямой проверкой первых десяти значений.
Реализации на C++, Python и Java устроены одинаково. Сначала линейным решетом до порога \(L\approx N^{2/3}\) заранее вычисляются \(\mu(n)\), \(\varphi(n)\) и малые префиксные суммы для \(n\mu(n)\) и \(n\varphi(n)\). Для аргументов выше порога две большие префиксные функции считаются рекурсивно, причём каждое большое значение кэшируется. Все суммирования выполняются по блокам, на которых значение целочисленного частного постоянно. Финальная сумма для \(R(N)\) строится точно так же. Поскольку модуль прост, деление на \(2\) и \(6\) заменяется умножением на модульные обратные.
Линейное решето до \(L\approx N^{2/3}\) требует \(O(L)\) времени и \(O(L)\) памяти. Каждый некэшированный большой запрос проходит только по тем интервалам, где меняется значение целочисленного частного, а не по всем числам подряд. Благодаря мемоизации суммарная дополнительная работа на практике остаётся того же порядка, что и предобработка. Для масштаба \(N\approx 10^{11}\) это превращает безнадёжный перебор в метод уровня \(O(N^{2/3})\) по времени и памяти.
نعرّف
$$A(n)=\frac{1}{n}\sum_{i=1}^{n}\operatorname{lcm}(i,n),\qquad S(N)=\sum_{k=1}^{N}A(k).$$
المطلوب هو حساب \(S(99999999019)\bmod 999999017\). الحساب المباشر لكل قيم المضاعف المشترك الأصغر غير عملي إطلاقًا، لذلك يُعاد بناء المتوسط بصيغة تعتمد على دوال ضربّية، ثم تُحسب المجاميع الناتجة بأسلوب تجميع الفترات التي يبقى فيها خارج القسمة الصحيح ثابتًا.
ثبّت \(n\). لكل \(i\in\{1,\dots,n\}\)، لنأخذ \(d=\gcd(i,n)\)، ونكتب \(n=dk\) و\(i=dj\). عندئذٍ \(\gcd(j,k)=1\)، كما أن
$$\operatorname{lcm}(i,n)=\frac{in}{\gcd(i,n)}=\frac{djn}{d}=nj.$$
إذن مساهمة كل حد تعتمد فقط على الباقي المختزل \(j\) بالنسبة إلى \(k\). وعند تثبيت قاسم \(k\mid n\)، تكون قيم \(j\) المسموح بها هي تمامًا الأعداد \(1\le j\le k\) التي تحقق \(\gcd(j,k)=1\). لذلك
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=n\sum_{k\mid n}\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j.$$
عندما يكون \(k>1\)، تأتي البواقي المختزلة في أزواج من الشكل \(j\) و\(k-j\)، ولهذا يكون مجموعها
$$\sum_{\substack{1\le j\le k\\ \gcd(j,k)=1}} j=\frac{k\varphi(k)}{2}.$$
أما الحالة الخاصة \(k=1\) فتعطي المساهمة \(1\). ومن ثم نحصل على الهوية
$$\sum_{i=1}^{n}\operatorname{lcm}(i,n)=\frac{n}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right),$$
وبالتالي
$$\boxed{A(n)=\frac{1}{2}\left(1+\sum_{k\mid n}k\varphi(k)\right).}$$
إذا جمعنا هذه الصيغة من أجل \(1\le n\le N\)، نحصل على
$$S(N)=\frac{1}{2}\left(N+\sum_{n=1}^{N}\sum_{d\mid n}d\varphi(d)\right).$$
وعند تبديل ترتيب الجمع، يظهر كل قاسم \(d\) مرة واحدة لكل مضاعف له لا يتجاوز \(N\)، أي \(\left\lfloor N/d\right\rfloor\) مرة. لنعرّف إذًا
$$R(N)=\sum_{d=1}^{N}d\varphi(d)\left\lfloor\frac{N}{d}\right\rfloor.$$
عندها يصبح
$$\boxed{S(N)=\frac{N+R(N)}{2}.}$$
وهكذا تتحول المسألة الأصلية من متوسطات للمضاعف المشترك الأصغر إلى مسألة جمع موزون على القواسم.
لنعرّف مجموعًا تراكميًا موزونًا للدالة \(\varphi\):
$$P(x)=\sum_{n\le x}n\varphi(n).$$
إذا كانت القيمة \(\left\lfloor N/d\right\rfloor\) ثابتة على الفترة \([l,r]\)، فيمكن ضغط كامل هذه الفترة في فرق تراكمي واحد:
$$R(N)=\sum_{[l,r]}\left\lfloor\frac{N}{l}\right\rfloor\bigl(P(r)-P(l-1)\bigr).$$
تتحدد الكتل بالقاعدة \(v=\left\lfloor N/l\right\rfloor\) ثم \(r=\left\lfloor N/v\right\rfloor\). ولأن عدد القيم المختلفة لهذا الخارج لا يتجاوز \(O(\sqrt{N})\)، فلا حاجة إلى المرور على كل \(d\le N\) على حدة.
نستعمل الهوية
$$\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}.$$
وبعد الضرب في \(n\)، نحصل على
$$n\varphi(n)=\sum_{d\mid n}d\mu(d)\left(\frac{n}{d}\right)^2.$$
ثم نجمع على \(n\le x\)، ونكتب \(n=dt\)، فنحصل على
$$P(x)=\sum_{d\le x}d\mu(d)\sum_{t\le x/d}t^2.$$
وبتعريف
$$U(m)=\sum_{t=1}^{m}t^2=\frac{m(m+1)(2m+1)}{6},$$
تصبح الصيغة
$$\boxed{P(x)=\sum_{d\le x}d\mu(d)\,U\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
إذن العقدة الأساسية أصبحت هي حساب المجموع التراكمي لـ \(d\mu(d)\) بسرعة.
لنعرّف
$$M(x)=\sum_{n\le x}n\mu(n).$$
إذا وضعنا \(f(n)=n\mu(n)\)، فإن هوية التفاف تعطي
$$\sum_{d\mid m} d\,f\!\left(\frac{m}{d}\right)=m\sum_{e\mid m}\mu(e)= \begin{cases} 1,&m=1,\\ 0,&m>1. \end{cases}$$
وبالجمع على \(1\le m\le x\) مع تبديل ترتيب المجاميع، نحصل على
$$\sum_{d\le x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right)=1.$$
وبفصل حد \(d=1\) ينتج
$$\boxed{M(x)=1-\sum_{d=2}^{x} d\,M\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right).}$$
وبما أن \(\left\lfloor x/d\right\rfloor\) ثابت كذلك على كتل متجاورة، يمكن كتابة ذلك أيضًا بصيغة
$$M(x)=1-\sum_{[l,r]\subseteq[2,x]}\left(\sum_{d=l}^{r}d\right)M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right).$$
أما المجموع الحسابي \(\sum_{d=l}^{r}d=\frac{(l+r)(r-l+1)}{2}\)، فهو ما يجعل كل كتلة قابلة للحساب في زمن ثابت.
عند \(n=10\)، القواسم هي \(1,2,5,10\)، ولدينا
$$1\cdot\varphi(1)=1,\qquad 2\cdot\varphi(2)=2,\qquad 5\cdot\varphi(5)=20,\qquad 10\cdot\varphi(10)=40.$$
ومن هنا
$$A(10)=\frac{1}{2}(1+1+2+20+40)=32.$$
وبالنسبة للمجموع حتى \(N=10\)، فإن
$$R(10)=\sum_{d=1}^{10}d\varphi(d)\left\lfloor\frac{10}{d}\right\rfloor=274,$$
ومن ثم
$$S(10)=\frac{10+274}{2}=142.$$
وهذه القيمة تطابق الحساب المباشر لأول عشرة حدود.
تسير تطبيقات C++ وPython وJava على الخطة نفسها. أولًا تُحسب \(\mu(n)\) و\(\varphi(n)\) والمجاميع التراكمية الصغيرة لـ \(n\mu(n)\) و\(n\varphi(n)\) حتى حد \(L\approx N^{2/3}\) باستخدام غربال خطي. بعد ذلك، تُحسب القيم الكبيرة للدالتين التراكميتين المطلوبتين بطريقة رجوعية مع تخزين كل نتيجة كبيرة، وتُجمع الحدود كلها على كتل ذات خارج قسمة صحيح ثابت. ويُحسب \(R(N)\) النهائي بالطريقة نفسها. وبما أن المودول عدد أولي، فإن القسمة على \(2\) و\(6\) تُنفّذ باستعمال المعكوسات المعيارية.
الغربال الخطي حتى \(L\approx N^{2/3}\) يحتاج إلى \(O(L)\) زمنًا و\(O(L)\) ذاكرة. وكل استعلام كبير غير مخزّن يزور فقط الفترات التي يتغير عندها خارج القسمة الصحيح، بدل المرور على جميع الأعداد واحدًا واحدًا. ومع التخزين المؤقت، يبقى العمل الإضافي الكلي في نفس المرتبة العملية تقريبًا مثل مرحلة التهيئة. لذلك، عند \(N\approx 10^{11}\)، تنخفض المسألة من brute force غير ممكنة إلى طريقة على مقياس \(O(N^{2/3})\) في الزمن والذاكرة.