Define
$$g(n)=\sum_{i=1}^{n}(-1)^i\gcd(n,i^2),\qquad G(N)=\sum_{n=1}^{N} g(n).$$
For the actual problem, \(N=12{,}345{,}678\). Computing every \(\gcd(n,i^2)\) directly would require a quadratic amount of work, so the implementation rewrites the alternating sum as a divisor sum with a multiplicative weight.
The key is to transform the inner alternating gcd sum into something that depends only on divisors of \(n\), and then to package those divisor contributions into a multiplicative arithmetic function.
For any positive integers \(u\) and \(v\),
$$\gcd(u,v)=\sum_{d\mid \gcd(u,v)} \varphi(d).$$
Applying this to \(u=n\) and \(v=i^2\) gives
$$g(n)=\sum_{i=1}^{n}(-1)^i\sum_{\substack{d\mid n\\ d\mid i^2}} \varphi(d).$$
Interchanging the order of summation yields
$$g(n)=\sum_{d\mid n}\varphi(d)\,S_d(n),$$
where
$$S_d(n)=\sum_{\substack{1\le i\le n\\ d\mid i^2}} (-1)^i.$$
So the problem is reduced to understanding the sign pattern of those \(i\) for which \(d\mid i^2\).
Write
$$d=\prod_{p^{e_p}\parallel d} p^{e_p}.$$
The condition \(d\mid i^2\) means \(e_p\le 2v_p(i)\) for every prime \(p\), so it is equivalent to
$$v_p(i)\ge \left\lceil \frac{e_p}{2}\right\rceil \quad \text{for all } p\mid d.$$
Define
$$\rho(d)=\prod_{p^{e_p}\parallel d} p^{\lceil e_p/2\rceil}.$$
This is the smallest positive integer whose square is divisible by \(d\). Then
$$d\mid i^2 \iff \rho(d)\mid i.$$
Because \(\rho(d)\mid d\) and \(d\mid n\), we also have \(\rho(d)\mid n\). Therefore
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^{\rho(d)k}.$$
The parity of \(\rho(d)\) is the same as the parity of \(d\), so two different cases appear.
If \(d\) is even, then \(\rho(d)\) is even, every sign is \(+1\), and
$$S_d(n)=\frac{n}{\rho(d)}.$$
If \(d\) is odd, then \(\rho(d)\) is odd, so
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^k=\begin{cases} 0, & n \text{ even},\\ -1, & n \text{ odd}. \end{cases}$$
Indeed, dividing by an odd number preserves parity, so \(n/\rho(d)\) has the same parity as \(n\).
For odd \(n\), all divisors of \(n\) are odd, hence
$$g(n)=-\sum_{d\mid n}\varphi(d)=-n,$$
using the standard identity \(\sum_{d\mid n}\varphi(d)=n\). For even \(n\), the odd-divisor contribution vanishes. Thus
$$g(n)= -n\,\mathbf{1}_{n\text{ odd}}+\sum_{\substack{d\mid n\\ d\text{ even}}}\varphi(d)\frac{n}{\rho(d)}.$$
It is convenient to rewrite the even-divisor term as a divisor sum of \(n/d\). Define
$$a(d)=\frac{\varphi(d)\,d}{\rho(d)}.$$
Then
$$\varphi(d)\frac{n}{\rho(d)}=a(d)\frac{n}{d},$$
so the formula becomes
$$g(n)= -n\,\mathbf{1}_{n\text{ odd}}+\sum_{\substack{d\mid n\\ d\text{ even}}} a(d)\frac{n}{d}.$$
The function \(a\) is multiplicative because both \(\varphi(d)\) and \(d/\rho(d)\) are multiplicative. For a prime power \(p^e\),
$$a(p^e)=\frac{\varphi(p^e)p^e}{p^{\lceil e/2\rceil}}=(p-1)p^{\lfloor 3e/2\rfloor-1}.$$
Equivalently,
$$a\bigl(p^{2t-1}\bigr)=(p-1)p^{3t-3},\qquad a\bigl(p^{2t}\bigr)=(p-1)p^{3t-1}.$$
This immediately gives the recurrence used by the implementations: when a new prime \(p\) is attached, multiply by \(p-1\); when the exponent of the current smallest prime increases, multiply by \(p\) if the new exponent is odd and by \(p^2\) if the new exponent is even.
Now sum the formula for \(g(n)\) from \(1\) to \(N\). The odd baseline contributes
$$\sum_{\substack{1\le n\le N\\ n\text{ odd}}} n = 1+3+\cdots +(2\lceil N/2\rceil-1)=\left\lceil \frac N2\right\rceil^2.$$
For a fixed even divisor \(d\), write \(n=dm\). Then
$$\sum_{\substack{1\le n\le N\\ d\mid n}} \frac{n}{d}=\sum_{m=1}^{\lfloor N/d\rfloor} m=\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.$$
Therefore
$$\boxed{G(N)=-\left\lceil \frac N2\right\rceil^2+\sum_{\substack{2\le d\le N\\ d\text{ even}}} a(d)\,\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.}$$
This is the exact formula evaluated by the implementation.
From the original definition,
$$g(4)=-\gcd(4,1)+\gcd(4,4)-\gcd(4,9)+\gcd(4,16)=-1+4-1+4=6.$$
The divisor formula gives the same result. The even divisors of \(4\) are \(2\) and \(4\). Here
$$\rho(2)=2,\quad a(2)=\frac{\varphi(2)\cdot 2}{2}=1,$$
$$\rho(4)=2,\quad a(4)=\frac{\varphi(4)\cdot 4}{2}=4.$$
Since \(4\) is even, there is no odd baseline term, and
$$g(4)=a(2)\frac{4}{2}+a(4)\frac{4}{4}=1\cdot 2+4\cdot 1=6.$$
For the cumulative sum,
$$G(4)=g(1)+g(2)+g(3)+g(4)=-1+1-3+6=3.$$
The closed form matches this exactly:
$$G(4)=-\left\lceil \frac 42\right\rceil^2+a(2)\frac{2\cdot 3}{2}+a(4)\frac{1\cdot 2}{2}=-4+3+4=3.$$
The C++, Python, and Java implementations all follow the same pipeline. First they build a linear sieve that records the least prime factor of every integer up to \(N\). That makes it possible to derive the factorization of each new integer from the already processed quotient obtained after removing one least prime factor.
During the same pass, the implementation evaluates the multiplicative weight \(a(d)\) for every \(d\le N\). If the least prime factor appears for the first time, the new prime-power contribution is \(p-1\). If that same prime factor continues an existing prime power, the parity of the updated exponent determines whether the multiplier is \(p\) or \(p^2\). This incremental rule is just the prime-power formula above written in a sieve-friendly form.
After the weight table is complete, the final accumulation starts from the baseline \(-\lceil N/2\rceil^2\). Then it loops over even \(d\), computes \(m=\lfloor N/d\rfloor\), adds \(a(d)\,m(m+1)/2\), and obtains the required value of \(G(N)\) without ever evaluating the original double sum directly.
The least-prime-factor sieve is linear, and the weight table is filled in the same linear pass, so the preprocessing cost is \(O(N)\). The final summation over even \(d\) is also \(O(N)\). The overall running time is therefore \(O(N)\), and the memory usage is \(O(N)\) for the sieve data and the coefficient table.
Definiert sind
$$g(n)=\sum_{i=1}^{n}(-1)^i\gcd(n,i^2),\qquad G(N)=\sum_{n=1}^{N} g(n).$$
Im eigentlichen Problem ist \(N=12{,}345{,}678\). Eine direkte Auswertung aller \(\gcd(n,i^2)\)-Terme wäre quadratisch und damit viel zu langsam. Deshalb formt die Lösung die alternierende Summe in eine Divisorsumme mit einem multiplikativen Gewicht um.
Die Grundidee besteht darin, die innere Summe zunächst nach Teilern von \(n\) umzuschreiben und den entstehenden Beitrag anschließend in einer multiplikativen arithmetischen Funktion zusammenzufassen.
Für positive ganze Zahlen \(u\) und \(v\) gilt
$$\gcd(u,v)=\sum_{d\mid \gcd(u,v)} \varphi(d).$$
Mit \(u=n\) und \(v=i^2\) folgt
$$g(n)=\sum_{i=1}^{n}(-1)^i\sum_{\substack{d\mid n\\ d\mid i^2}} \varphi(d).$$
Nach Vertauschen der Summationen erhält man
$$g(n)=\sum_{d\mid n}\varphi(d)\,S_d(n),$$
wobei
$$S_d(n)=\sum_{\substack{1\le i\le n\\ d\mid i^2}} (-1)^i$$
den alternierenden Beitrag aller \(i\) beschreibt, deren Quadrat durch \(d\) teilbar ist.
Schreibe
$$d=\prod_{p^{e_p}\parallel d} p^{e_p}.$$
Die Bedingung \(d\mid i^2\) ist äquivalent zu \(e_p\le 2v_p(i)\) für alle beteiligten Primzahlen und damit zu
$$v_p(i)\ge \left\lceil \frac{e_p}{2}\right\rceil \quad \text{für alle } p\mid d.$$
Definiere daher
$$\rho(d)=\prod_{p^{e_p}\parallel d} p^{\lceil e_p/2\rceil}.$$
Dies ist die kleinste positive Zahl, deren Quadrat ein Vielfaches von \(d\) ist. Dann gilt
$$d\mid i^2 \iff \rho(d)\mid i.$$
Wegen \(\rho(d)\mid d\mid n\) folgt sofort
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^{\rho(d)k}.$$
Die Parität von \(\rho(d)\) ist dieselbe wie die Parität von \(d\), daher gibt es zwei Fälle.
Ist \(d\) gerade, dann ist \(\rho(d)\) gerade, alle Vorzeichen sind \(+1\), und somit
$$S_d(n)=\frac{n}{\rho(d)}.$$
Ist \(d\) ungerade, dann ist \(\rho(d)\) ebenfalls ungerade und es gilt
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^k=\begin{cases} 0, & n \text{ gerade},\\ -1, & n \text{ ungerade}. \end{cases}$$
Die Division durch eine ungerade Zahl ändert nämlich die Parität nicht. Für ungerades \(n\) sind alle Teiler ungerade, also
$$g(n)=-\sum_{d\mid n}\varphi(d)=-n,$$
weil \(\sum_{d\mid n}\varphi(d)=n\) gilt. Für gerades \(n\) verschwindet der ungerade Teil. Insgesamt also
$$g(n)= -n\,\mathbf{1}_{n\text{ ungerade}}+\sum_{\substack{d\mid n\\ d\text{ gerade}}}\varphi(d)\frac{n}{\rho(d)}.$$
Nun definieren wir
$$a(d)=\frac{\varphi(d)\,d}{\rho(d)}.$$
Dann ist
$$\varphi(d)\frac{n}{\rho(d)}=a(d)\frac{n}{d},$$
und damit
$$g(n)= -n\,\mathbf{1}_{n\text{ ungerade}}+\sum_{\substack{d\mid n\\ d\text{ gerade}}} a(d)\frac{n}{d}.$$
Die Funktion \(a\) ist multiplikativ. Für eine Primzahlpotenz \(p^e\) ergibt sich
$$a(p^e)=\frac{\varphi(p^e)p^e}{p^{\lceil e/2\rceil}}=(p-1)p^{\lfloor 3e/2\rfloor-1}.$$
Äquivalent dazu:
$$a\bigl(p^{2t-1}\bigr)=(p-1)p^{3t-3},\qquad a\bigl(p^{2t}\bigr)=(p-1)p^{3t-1}.$$
Daraus folgt genau die Rekursion der Implementierung: Kommt eine neue Primzahl hinzu, multipliziert man mit \(p-1\); wächst die bestehende Primzahlpotenz weiter, multipliziert man je nach neuer Exponentenparität mit \(p\) oder mit \(p^2\).
Summiert man die Formel für \(g(n)\) von \(1\) bis \(N\), so liefert der ungerade Basisterm
$$\sum_{\substack{1\le n\le N\\ n\text{ ungerade}}} n = 1+3+\cdots +(2\lceil N/2\rceil-1)=\left\lceil \frac N2\right\rceil^2.$$
Für einen festen geraden Teiler \(d\) setzt man \(n=dm\). Dann gilt
$$\sum_{\substack{1\le n\le N\\ d\mid n}} \frac{n}{d}=\sum_{m=1}^{\lfloor N/d\rfloor} m=\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.$$
Also erhält man die geschlossene Form
$$\boxed{G(N)=-\left\lceil \frac N2\right\rceil^2+\sum_{\substack{2\le d\le N\\ d\text{ gerade}}} a(d)\,\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.}$$
Genau diese Summe wird im Programm ausgewertet.
Aus der ursprünglichen Definition folgt
$$g(4)=-\gcd(4,1)+\gcd(4,4)-\gcd(4,9)+\gcd(4,16)=-1+4-1+4=6.$$
Mit der Divisordarstellung erhält man denselben Wert. Die geraden Teiler von \(4\) sind \(2\) und \(4\), und
$$\rho(2)=2,\quad a(2)=\frac{\varphi(2)\cdot 2}{2}=1,$$
$$\rho(4)=2,\quad a(4)=\frac{\varphi(4)\cdot 4}{2}=4.$$
Da \(4\) gerade ist, gibt es keinen ungeraden Basisterm, also
$$g(4)=a(2)\frac{4}{2}+a(4)\frac{4}{4}=1\cdot 2+4\cdot 1=6.$$
Für die aufsummierte Größe ergibt sich
$$G(4)=g(1)+g(2)+g(3)+g(4)=-1+1-3+6=3.$$
Die geschlossene Formel liefert ebenfalls
$$G(4)=-\left\lceil \frac 42\right\rceil^2+a(2)\frac{2\cdot 3}{2}+a(4)\frac{1\cdot 2}{2}=-4+3+4=3.$$
Die Implementierungen in C++, Python und Java verwenden alle denselben Ablauf. Zuerst wird mit einem linearen Sieb der kleinste Primfaktor jeder Zahl bis \(N\) bestimmt. Dadurch lässt sich die Faktorisierung jeder neuen Zahl unmittelbar aus dem bereits behandelten Quotienten gewinnen, nachdem ein solcher Primfaktor entfernt wurde.
Im selben Durchlauf wird für jedes \(d\le N\) das Gewicht \(a(d)\) berechnet. Tritt der kleinste Primfaktor zum ersten Mal auf, ist der neue Beitrag \(p-1\). Gehört er zu einer bereits vorhandenen Primzahlpotenz, entscheidet die Parität des aktualisierten Exponenten darüber, ob mit \(p\) oder mit \(p^2\) multipliziert wird. So wird die Primzahlpotenzformel direkt in eine lineare Berechnung übersetzt.
Nachdem alle Gewichte vorliegen, startet die Endsumme bei \(-\lceil N/2\rceil^2\). Danach werden nur gerade \(d\) betrachtet. Für jedes davon setzt die Implementierung \(m=\lfloor N/d\rfloor\), addiert \(a(d)\,m(m+1)/2\) und erhält so \(G(N)\), ohne die ursprüngliche Doppelsumme explizit auszuwerten.
Das lineare Sieb für den kleinsten Primfaktor ist \(O(N)\), und die Gewichtstabelle wird im selben linearen Durchlauf aufgebaut. Die abschließende Summe über gerade \(d\) ist ebenfalls \(O(N)\). Insgesamt ergibt sich also Laufzeit \(O(N)\) und Speicherbedarf \(O(N)\).
Tanımlar şunlardır:
$$g(n)=\sum_{i=1}^{n}(-1)^i\gcd(n,i^2),\qquad G(N)=\sum_{n=1}^{N} g(n).$$
Asıl problemde \(N=12{,}345{,}678\) alınır. Her \(n\) ve her \(i\) için \(\gcd(n,i^2)\) hesaplamak karesel maliyet doğurur. Bu yüzden çözüm, alternanslı toplamı bölenler üzerinden yazılan ve çarpımsal bir ağırlık fonksiyonu içeren kapalı bir biçime dönüştürür.
Ana fikir, iç toplamı önce \(n\)'nin bölenlerine göre ayırmak, sonra da ortaya çıkan katkıları çarpımsal bir aritmetik fonksiyonda toplamaktır.
Her pozitif \(u\) ve \(v\) için
$$\gcd(u,v)=\sum_{d\mid \gcd(u,v)} \varphi(d)$$
özdeşliği vardır. Bunu \(u=n\) ve \(v=i^2\) için uygularsak
$$g(n)=\sum_{i=1}^{n}(-1)^i\sum_{\substack{d\mid n\\ d\mid i^2}} \varphi(d)$$
elde edilir. Toplamların yerini değiştirince
$$g(n)=\sum_{d\mid n}\varphi(d)\,S_d(n)$$
olur; burada
$$S_d(n)=\sum_{\substack{1\le i\le n\\ d\mid i^2}} (-1)^i$$
ifadesi, karesi \(d\) ile bölünebilen \(i\)'lerin işaretli katkısını temsil eder.
\(d\)'yi
$$d=\prod_{p^{e_p}\parallel d} p^{e_p}$$
şeklinde asal çarpanlarına ayıralım. \(d\mid i^2\) koşulu, her asal için \(e_p\le 2v_p(i)\) demektir. Bu da
$$v_p(i)\ge \left\lceil \frac{e_p}{2}\right\rceil \quad \text{her } p\mid d \text{ için}$$
şeklinde yazılır. Şimdi
$$\rho(d)=\prod_{p^{e_p}\parallel d} p^{\lceil e_p/2\rceil}$$
tanımını yapalım. Bu sayı, karesi \(d\)'ye bölünebilen en küçük pozitif sayıdır. Böylece
$$d\mid i^2 \iff \rho(d)\mid i$$
olur. Ayrıca \(\rho(d)\mid d\mid n\) olduğu için
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^{\rho(d)k}$$
biçimine ineriz.
\(\rho(d)\)'nin paritesi \(d\)'nin paritesiyle aynıdır, dolayısıyla iki ayrı durum vardır.
\(d\) çiftse \(\rho(d)\) de çifttir; bu durumda bütün işaretler \(+1\) olur ve
$$S_d(n)=\frac{n}{\rho(d)}$$
elde edilir. \(d\) tekse \(\rho(d)\) de tektir; o zaman
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^k=\begin{cases} 0, & n \text{ çift},\\ -1, & n \text{ tek}. \end{cases}$$
Çünkü tek bir sayıya bölmek pariteyi değiştirmez. \(n\) tek olduğunda tüm bölenler de tek olduğu için
$$g(n)=-\sum_{d\mid n}\varphi(d)=-n$$
olur; burada \(\sum_{d\mid n}\varphi(d)=n\) özdeşliği kullanılır. \(n\) çift olduğunda ise tek bölenlerden gelen toplam sıfırdır. Sonuç olarak
$$g(n)= -n\,\mathbf{1}_{n\text{ tek}}+\sum_{\substack{d\mid n\\ d\text{ çift}}}\varphi(d)\frac{n}{\rho(d)}.$$
Şimdi
$$a(d)=\frac{\varphi(d)\,d}{\rho(d)}$$
tanımını yapalım. Böylece
$$\varphi(d)\frac{n}{\rho(d)}=a(d)\frac{n}{d}$$
olur ve formül
$$g(n)= -n\,\mathbf{1}_{n\text{ tek}}+\sum_{\substack{d\mid n\\ d\text{ çift}}} a(d)\frac{n}{d}$$
haline gelir. \(a\) çarpımsaldır. Bir asal kuvvet için
$$a(p^e)=\frac{\varphi(p^e)p^e}{p^{\lceil e/2\rceil}}=(p-1)p^{\lfloor 3e/2\rfloor-1}$$
olur. Eşdeğer biçimde
$$a\bigl(p^{2t-1}\bigr)=(p-1)p^{3t-3},\qquad a\bigl(p^{2t}\bigr)=(p-1)p^{3t-1}.$$
Buradan kodun kullandığı yineleme doğrudan çıkar: yeni bir asal ilk kez geliyorsa çarpan \(p-1\) olur; aynı asalın üssü büyüyorsa güncel üssün tek ya da çift olmasına göre ek çarpan \(p\) veya \(p^2\) olur.
Artık \(g(n)\) formülünü \(1\) ile \(N\) arasında toplarız. Tek sayılardan gelen taban katkı
$$\sum_{\substack{1\le n\le N\\ n\text{ tek}}} n = 1+3+\cdots +(2\lceil N/2\rceil-1)=\left\lceil \frac N2\right\rceil^2$$
olur. Sabit bir çift \(d\) için \(n=dm\) yazarsak
$$\sum_{\substack{1\le n\le N\\ d\mid n}} \frac{n}{d}=\sum_{m=1}^{\lfloor N/d\rfloor} m=\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}$$
elde edilir. Böylece kapalı form
$$\boxed{G(N)=-\left\lceil \frac N2\right\rceil^2+\sum_{\substack{2\le d\le N\\ d\text{ çift}}} a(d)\,\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.}$$
Uygulamanın hesapladığı toplam tam olarak budur.
Doğrudan tanımdan
$$g(4)=-\gcd(4,1)+\gcd(4,4)-\gcd(4,9)+\gcd(4,16)=-1+4-1+4=6$$
çıkar. Bölen formülü de aynı sonucu verir. \(4\)'ün çift bölenleri \(2\) ve \(4\)'tür:
$$\rho(2)=2,\quad a(2)=\frac{\varphi(2)\cdot 2}{2}=1,$$
$$\rho(4)=2,\quad a(4)=\frac{\varphi(4)\cdot 4}{2}=4.$$
\(4\) çift olduğu için tek taban terimi yoktur ve
$$g(4)=a(2)\frac{4}{2}+a(4)\frac{4}{4}=1\cdot 2+4\cdot 1=6$$
bulunur. Kümülatif toplam için
$$G(4)=g(1)+g(2)+g(3)+g(4)=-1+1-3+6=3$$
olur. Kapalı form de aynı değeri verir:
$$G(4)=-\left\lceil \frac 42\right\rceil^2+a(2)\frac{2\cdot 3}{2}+a(4)\frac{1\cdot 2}{2}=-4+3+4=3.$$
C++, Python ve Java uygulamaları aynı işlem hattını izler. Önce \(N\)'ye kadar her sayının en küçük asal bölenini veren doğrusal bir elek kurulur. Böylece yeni bir sayının çarpan yapısı, ondan bir en küçük asal bölen çıkarıldıktan sonra kalan bölümden yararlanılarak elde edilir.
Aynı geçişte her \(d\le N\) için \(a(d)\) ağırlığı hesaplanır. Eğer söz konusu asal o sayıda ilk kez görünüyorsa katkı \(p-1\) olur. Aynı asalın kuvveti büyüyorsa, yeni üssün paritesine göre çarpan \(p\) ya da \(p^2\) seçilir. Bu, yukarıdaki asal kuvvet formülünün artımlı biçimidir.
Ağırlıklar tamamlandıktan sonra son toplam \(-\lceil N/2\rceil^2\) değerinden başlatılır. Ardından yalnızca çift \(d\) değerleri dolaşılır, \(m=\lfloor N/d\rfloor\) hesaplanır, \(a(d)\,m(m+1)/2\) eklenir ve böylece orijinal çift toplam hiç açılmadan \(G(N)\) bulunur.
En küçük asal bölen eleği doğrusal zamanda kurulabilir; ağırlık tablosu da aynı doğrusal geçişte üretilir. Son kısımda çift \(d\) değerleri üzerinde yapılan toplama yine \(O(N)\) zamandır. Dolayısıyla toplam süre \(O(N)\), bellek kullanımı ise \(O(N)\)'dir.
Se definen
$$g(n)=\sum_{i=1}^{n}(-1)^i\gcd(n,i^2),\qquad G(N)=\sum_{n=1}^{N} g(n).$$
En el problema real, \(N=12{,}345{,}678\). Evaluar cada \(\gcd(n,i^2)\) de forma directa sería cuadrático y por tanto inviable. La solución rehace la suma alternante como una suma sobre divisores con un peso multiplicativo.
La idea central es reordenar la suma interior según los divisores de \(n\) y luego condensar esos aportes en una función aritmética multiplicativa.
Para enteros positivos \(u\) y \(v\),
$$\gcd(u,v)=\sum_{d\mid \gcd(u,v)} \varphi(d).$$
Aplicándolo con \(u=n\) y \(v=i^2\), obtenemos
$$g(n)=\sum_{i=1}^{n}(-1)^i\sum_{\substack{d\mid n\\ d\mid i^2}} \varphi(d).$$
Al intercambiar el orden de sumación resulta
$$g(n)=\sum_{d\mid n}\varphi(d)\,S_d(n),$$
donde
$$S_d(n)=\sum_{\substack{1\le i\le n\\ d\mid i^2}} (-1)^i.$$
Todo queda reducido a entender qué signo aportan los enteros \(i\) cuyo cuadrado es múltiplo de \(d\).
Escribimos
$$d=\prod_{p^{e_p}\parallel d} p^{e_p}.$$
La condición \(d\mid i^2\) equivale a \(e_p\le 2v_p(i)\) para todo primo \(p\), es decir,
$$v_p(i)\ge \left\lceil \frac{e_p}{2}\right\rceil \quad \text{para todo } p\mid d.$$
Definimos entonces
$$\rho(d)=\prod_{p^{e_p}\parallel d} p^{\lceil e_p/2\rceil}.$$
Este es el menor entero positivo cuyo cuadrado es divisible por \(d\). Con esta notación,
$$d\mid i^2 \iff \rho(d)\mid i.$$
Además, como \(\rho(d)\mid d\mid n\), se tiene
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^{\rho(d)k}.$$
La paridad de \(\rho(d)\) coincide con la de \(d\), así que aparecen dos casos distintos.
Si \(d\) es par, entonces \(\rho(d)\) también es par, todos los signos valen \(+1\), y por tanto
$$S_d(n)=\frac{n}{\rho(d)}.$$
Si \(d\) es impar, entonces \(\rho(d)\) es impar y
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^k=\begin{cases} 0, & n \text{ par},\\ -1, & n \text{ impar}. \end{cases}$$
Dividir por un número impar no cambia la paridad. Cuando \(n\) es impar, todos sus divisores también lo son, así que
$$g(n)=-\sum_{d\mid n}\varphi(d)=-n,$$
usando \(\sum_{d\mid n}\varphi(d)=n\). Cuando \(n\) es par, la contribución de los divisores impares desaparece. En consecuencia,
$$g(n)= -n\,\mathbf{1}_{n\text{ impar}}+\sum_{\substack{d\mid n\\ d\text{ par}}}\varphi(d)\frac{n}{\rho(d)}.$$
Definimos
$$a(d)=\frac{\varphi(d)\,d}{\rho(d)}.$$
Entonces
$$\varphi(d)\frac{n}{\rho(d)}=a(d)\frac{n}{d},$$
y la fórmula toma la forma
$$g(n)= -n\,\mathbf{1}_{n\text{ impar}}+\sum_{\substack{d\mid n\\ d\text{ par}}} a(d)\frac{n}{d}.$$
La función \(a\) es multiplicativa. Para una potencia prima \(p^e\),
$$a(p^e)=\frac{\varphi(p^e)p^e}{p^{\lceil e/2\rceil}}=(p-1)p^{\lfloor 3e/2\rfloor-1}.$$
Equivalentemente,
$$a\bigl(p^{2t-1}\bigr)=(p-1)p^{3t-3},\qquad a\bigl(p^{2t}\bigr)=(p-1)p^{3t-1}.$$
De aquí sale exactamente la recurrencia usada por la implementación: cuando aparece un primo nuevo se multiplica por \(p-1\); cuando continúa la misma potencia prima, la nueva paridad del exponente decide si el factor adicional es \(p\) o \(p^2\).
Ahora sumamos la fórmula de \(g(n)\) desde \(1\) hasta \(N\). La parte base de los impares aporta
$$\sum_{\substack{1\le n\le N\\ n\text{ impar}}} n = 1+3+\cdots +(2\lceil N/2\rceil-1)=\left\lceil \frac N2\right\rceil^2.$$
Para un divisor par fijo \(d\), escribimos \(n=dm\). Entonces
$$\sum_{\substack{1\le n\le N\\ d\mid n}} \frac{n}{d}=\sum_{m=1}^{\lfloor N/d\rfloor} m=\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.$$
Por lo tanto,
$$\boxed{G(N)=-\left\lceil \frac N2\right\rceil^2+\sum_{\substack{2\le d\le N\\ d\text{ par}}} a(d)\,\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.}$$
Esa es exactamente la expresión que calculan los programas.
Desde la definición original,
$$g(4)=-\gcd(4,1)+\gcd(4,4)-\gcd(4,9)+\gcd(4,16)=-1+4-1+4=6.$$
La fórmula por divisores da lo mismo. Los divisores pares de \(4\) son \(2\) y \(4\), y
$$\rho(2)=2,\quad a(2)=\frac{\varphi(2)\cdot 2}{2}=1,$$
$$\rho(4)=2,\quad a(4)=\frac{\varphi(4)\cdot 4}{2}=4.$$
Como \(4\) es par, no hay término base impar, así que
$$g(4)=a(2)\frac{4}{2}+a(4)\frac{4}{4}=1\cdot 2+4\cdot 1=6.$$
Para la suma acumulada,
$$G(4)=g(1)+g(2)+g(3)+g(4)=-1+1-3+6=3.$$
La forma cerrada coincide:
$$G(4)=-\left\lceil \frac 42\right\rceil^2+a(2)\frac{2\cdot 3}{2}+a(4)\frac{1\cdot 2}{2}=-4+3+4=3.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Primero construyen una criba lineal que guarda el menor factor primo de cada entero hasta \(N\). Eso permite deducir la factorización de cada número nuevo a partir del cociente que queda al eliminar uno de esos factores primos mínimos.
En la misma pasada se calcula el peso multiplicativo \(a(d)\) para todo \(d\le N\). Si el factor primo mínimo aparece por primera vez, el nuevo aporte es \(p-1\). Si ese primo prolonga una potencia ya existente, la paridad del exponente actualizado determina si el multiplicador extra es \(p\) o \(p^2\). Así, la ley en potencias primas se convierte en una recurrencia lineal.
Una vez completada la tabla de pesos, la suma final comienza en \(-\lceil N/2\rceil^2\). Después solo se recorren los valores pares de \(d\); para cada uno se calcula \(m=\lfloor N/d\rfloor\), se añade \(a(d)\,m(m+1)/2\) y se obtiene \(G(N)\) sin evaluar explícitamente la doble suma original.
La criba del menor factor primo es lineal y la tabla de pesos se rellena en esa misma pasada, así que el preprocesamiento cuesta \(O(N)\). La suma final sobre los \(d\) pares también es \(O(N)\). En conjunto, el tiempo total es \(O(N)\) y la memoria utilizada es \(O(N)\).
定义
$$g(n)=\sum_{i=1}^{n}(-1)^i\gcd(n,i^2),\qquad G(N)=\sum_{n=1}^{N} g(n).$$
本题实际要求的是 \(N=12{,}345{,}678\) 时的 \(G(N)\)。如果直接对每个 \(n\) 和每个 \(i\) 计算一次 \(\gcd(n,i^2)\)，时间复杂度会是平方级，显然不可行。实现采用的思路是把交错的 gcd 求和改写成按除数汇总的形式，再把这些除数贡献压缩成一个乘法函数。
核心步骤有两层：先把内层求和改写为关于 \(n\) 的各个除数的求和，再把偶数除数部分整理成一个可以线性筛递推的权重函数。
对任意正整数 \(u,v\)，都有
$$\gcd(u,v)=\sum_{d\mid \gcd(u,v)} \varphi(d).$$
把 \(u=n\)、\(v=i^2\) 代入，得到
$$g(n)=\sum_{i=1}^{n}(-1)^i\sum_{\substack{d\mid n\\ d\mid i^2}} \varphi(d).$$
交换求和顺序后，变成
$$g(n)=\sum_{d\mid n}\varphi(d)\,S_d(n),$$
其中
$$S_d(n)=\sum_{\substack{1\le i\le n\\ d\mid i^2}} (-1)^i.$$
因此问题转化为：固定一个除数 \(d\) 之后，所有满足 \(d\mid i^2\) 的 \(i\) 在交错符号下总共贡献多少。
将 \(d\) 写成素因子分解
$$d=\prod_{p^{e_p}\parallel d} p^{e_p}.$$
条件 \(d\mid i^2\) 等价于对每个素数 \(p\) 都满足 \(e_p\le 2v_p(i)\)，也就是
$$v_p(i)\ge \left\lceil \frac{e_p}{2}\right\rceil \quad \text{对所有 } p\mid d.$$
定义
$$\rho(d)=\prod_{p^{e_p}\parallel d} p^{\lceil e_p/2\rceil}.$$
\(\rho(d)\) 是满足“其平方能被 \(d\) 整除”的最小正整数。于是有一个非常关键的等价关系：
$$d\mid i^2 \iff \rho(d)\mid i.$$
又因为 \(\rho(d)\mid d\mid n\)，所以可把满足条件的 \(i\) 全部写成 \(i=\rho(d)k\)，从而
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^{\rho(d)k}.$$
\(\rho(d)\) 的奇偶性与 \(d\) 完全相同，所以这里自然分成两类。
如果 \(d\) 是偶数，那么 \(\rho(d)\) 也是偶数，于是 \((-1)^{\rho(d)k}=1\)，因此
$$S_d(n)=\frac{n}{\rho(d)}.$$
如果 \(d\) 是奇数，那么 \(\rho(d)\) 也是奇数，此时
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^k=\begin{cases} 0, & n \text{ 为偶数},\\ -1, & n \text{ 为奇数}. \end{cases}$$
原因是：被奇数整除不会改变奇偶性，所以 \(n/\rho(d)\) 与 \(n\) 同奇偶。
若 \(n\) 为奇数，则它的所有除数都为奇数，于是
$$g(n)=-\sum_{d\mid n}\varphi(d)=-n,$$
这里用到了标准恒等式 \(\sum_{d\mid n}\varphi(d)=n\)。若 \(n\) 为偶数，则所有奇除数的交错和都抵消为 \(0\)。因此总公式变成
$$g(n)= -n\,\mathbf{1}_{n\text{ 为奇数}}+\sum_{\substack{d\mid n\\ d\text{ 为偶数}}}\varphi(d)\frac{n}{\rho(d)}.$$
为了让最终公式更适合筛法，定义权重函数
$$a(d)=\frac{\varphi(d)\,d}{\rho(d)}.$$
这样就有
$$\varphi(d)\frac{n}{\rho(d)}=a(d)\frac{n}{d},$$
从而
$$g(n)= -n\,\mathbf{1}_{n\text{ 为奇数}}+\sum_{\substack{d\mid n\\ d\text{ 为偶数}}} a(d)\frac{n}{d}.$$
这个 \(a(d)\) 是乘法函数，因为 \(\varphi(d)\) 与 \(d/\rho(d)\) 都是乘法性的。对素数幂 \(p^e\)，有
$$a(p^e)=\frac{\varphi(p^e)p^e}{p^{\lceil e/2\rceil}}=(p-1)p^{\lfloor 3e/2\rfloor-1}.$$
也可以分奇偶指数写成
$$a\bigl(p^{2t-1}\bigr)=(p-1)p^{3t-3},\qquad a\bigl(p^{2t}\bigr)=(p-1)p^{3t-1}.$$
这正好解释了实现中的递推规则：如果加入的是一个全新的素因子，乘上 \(p-1\)；如果是在原有最小素因子的幂次上继续增加，那么新指数为奇数时乘 \(p\)，新指数为偶数时乘 \(p^2\)。
现在把上式从 \(n=1\) 加到 \(N\)。奇数基线部分给出
$$\sum_{\substack{1\le n\le N\\ n\text{ 为奇数}}} n = 1+3+\cdots +(2\lceil N/2\rceil-1)=\left\lceil \frac N2\right\rceil^2.$$
对固定的偶数 \(d\)，令 \(n=dm\)，则
$$\sum_{\substack{1\le n\le N\\ d\mid n}} \frac{n}{d}=\sum_{m=1}^{\lfloor N/d\rfloor} m=\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.$$
于是得到最终闭式
$$\boxed{G(N)=-\left\lceil \frac N2\right\rceil^2+\sum_{\substack{2\le d\le N\\ d\text{ 为偶数}}} a(d)\,\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.}$$
这就是实现真正计算的表达式。
先看单点值。按照原始定义，
$$g(4)=-\gcd(4,1)+\gcd(4,4)-\gcd(4,9)+\gcd(4,16)=-1+4-1+4=6.$$
用除数公式也能得到同样的结果。\(4\) 的偶数除数是 \(2\) 和 \(4\)，并且
$$\rho(2)=2,\quad a(2)=\frac{\varphi(2)\cdot 2}{2}=1,$$
$$\rho(4)=2,\quad a(4)=\frac{\varphi(4)\cdot 4}{2}=4.$$
因为 \(4\) 本身是偶数，没有奇数基线项，所以
$$g(4)=a(2)\frac{4}{2}+a(4)\frac{4}{4}=1\cdot 2+4\cdot 1=6.$$
再看累计值：
$$G(4)=g(1)+g(2)+g(3)+g(4)=-1+1-3+6=3.$$
闭式公式完全一致：
$$G(4)=-\left\lceil \frac 42\right\rceil^2+a(2)\frac{2\cdot 3}{2}+a(4)\frac{1\cdot 2}{2}=-4+3+4=3.$$
C++、Python 和 Java 三个实现使用的是同一条计算路线。第一步是建立一个线性筛，为每个不超过 \(N\) 的整数记录其最小素因子。这样在按顺序处理整数时，就能利用“去掉一个最小素因子之后的商”来复用已经得到的分解信息。
在同一遍扫描中，实现同时构造所有 \(a(d)\) 的值。如果某个最小素因子在当前整数中第一次出现，就乘上 \(p-1\)；如果它延续的是同一个素数幂，那么只需要看更新后的指数奇偶性：奇数乘 \(p\)，偶数乘 \(p^2\)。这正是上面素数幂公式的增量版本。
权重表准备完成后，最后一步从基线 \(-\lceil N/2\rceil^2\) 开始，只遍历偶数 \(d\)。对每个 \(d\) 计算 \(m=\lfloor N/d\rfloor\)，加入 \(a(d)\,m(m+1)/2\)，就得到了 \(G(N)\)。整个过程完全避开了原始定义中的双重循环。
最小素因子线性筛是 \(O(N)\)，权重表也在同一线性过程中完成。最后对偶数 \(d\) 的累加仍然是 \(O(N)\)。因此总时间复杂度是 \(O(N)\)，空间复杂度是 \(O(N)\)。
Определены функции
$$g(n)=\sum_{i=1}^{n}(-1)^i\gcd(n,i^2),\qquad G(N)=\sum_{n=1}^{N} g(n).$$
В самой задаче нужно вычислить значение при \(N=12{,}345{,}678\). Прямой перебор всех \(\gcd(n,i^2)\) дал бы квадратичную сложность, поэтому решение перестраивает чередующуюся сумму в сумму по делителям с мультипликативным весом.
Основная идея состоит в том, чтобы сначала переписать внутреннюю сумму через делители числа \(n\), а затем объединить вклад чётных делителей в одну мультипликативную арифметическую функцию.
Для любых положительных целых \(u\) и \(v\) верно
$$\gcd(u,v)=\sum_{d\mid \gcd(u,v)} \varphi(d).$$
Подставляя \(u=n\) и \(v=i^2\), получаем
$$g(n)=\sum_{i=1}^{n}(-1)^i\sum_{\substack{d\mid n\\ d\mid i^2}} \varphi(d).$$
Меняя порядок суммирования, приходим к виду
$$g(n)=\sum_{d\mid n}\varphi(d)\,S_d(n),$$
где
$$S_d(n)=\sum_{\substack{1\le i\le n\\ d\mid i^2}} (-1)^i.$$
Значит, вся задача сводится к вычислению знакопеременной суммы по тем \(i\), квадраты которых кратны \(d\).
Разложим \(d\) на простые множители:
$$d=\prod_{p^{e_p}\parallel d} p^{e_p}.$$
Условие \(d\mid i^2\) эквивалентно неравенствам \(e_p\le 2v_p(i)\) для всех простых \(p\), то есть
$$v_p(i)\ge \left\lceil \frac{e_p}{2}\right\rceil \quad \text{для всех } p\mid d.$$
Введём обозначение
$$\rho(d)=\prod_{p^{e_p}\parallel d} p^{\lceil e_p/2\rceil}.$$
Это наименьшее положительное число, квадрат которого делится на \(d\). Тогда
$$d\mid i^2 \iff \rho(d)\mid i.$$
Так как \(\rho(d)\mid d\mid n\), можно записать
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^{\rho(d)k}.$$
Чётность \(\rho(d)\) совпадает с чётностью \(d\), поэтому возникают два случая.
Если \(d\) чётно, то \(\rho(d)\) тоже чётно, все знаки равны \(+1\), и
$$S_d(n)=\frac{n}{\rho(d)}.$$
Если \(d\) нечётно, то \(\rho(d)\) нечётно, и
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^k=\begin{cases} 0, & n \text{ чётно},\\ -1, & n \text{ нечётно}. \end{cases}$$
Деление на нечётное число не меняет чётность, поэтому \(n/\rho(d)\) имеет ту же чётность, что и \(n\).
Если \(n\) нечётно, то все его делители тоже нечётны, и потому
$$g(n)=-\sum_{d\mid n}\varphi(d)=-n,$$
так как \(\sum_{d\mid n}\varphi(d)=n\). Если \(n\) чётно, вклад нечётных делителей обнуляется. Следовательно,
$$g(n)= -n\,\mathbf{1}_{n\text{ нечётно}}+\sum_{\substack{d\mid n\\ d\text{ чётно}}}\varphi(d)\frac{n}{\rho(d)}.$$
Определим
$$a(d)=\frac{\varphi(d)\,d}{\rho(d)}.$$
Тогда
$$\varphi(d)\frac{n}{\rho(d)}=a(d)\frac{n}{d},$$
и формула принимает вид
$$g(n)= -n\,\mathbf{1}_{n\text{ нечётно}}+\sum_{\substack{d\mid n\\ d\text{ чётно}}} a(d)\frac{n}{d}.$$
Функция \(a\) мультипликативна. Для простой степени \(p^e\) имеем
$$a(p^e)=\frac{\varphi(p^e)p^e}{p^{\lceil e/2\rceil}}=(p-1)p^{\lfloor 3e/2\rfloor-1}.$$
То же можно переписать так:
$$a\bigl(p^{2t-1}\bigr)=(p-1)p^{3t-3},\qquad a\bigl(p^{2t}\bigr)=(p-1)p^{3t-1}.$$
Отсюда непосредственно следует рекуррентное правило реализации: если добавляется новый простой множитель, нужно умножить на \(p-1\); если растёт степень уже имеющегося наименьшего простого множителя, то новый показатель диктует множитель \(p\) или \(p^2\).
Теперь суммируем выражение для \(g(n)\) от \(1\) до \(N\). Базовая нечётная часть даёт
$$\sum_{\substack{1\le n\le N\\ n\text{ нечётно}}} n = 1+3+\cdots +(2\lceil N/2\rceil-1)=\left\lceil \frac N2\right\rceil^2.$$
Для фиксированного чётного \(d\) положим \(n=dm\). Тогда
$$\sum_{\substack{1\le n\le N\\ d\mid n}} \frac{n}{d}=\sum_{m=1}^{\lfloor N/d\rfloor} m=\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.$$
Итак, получаем окончательную формулу
$$\boxed{G(N)=-\left\lceil \frac N2\right\rceil^2+\sum_{\substack{2\le d\le N\\ d\text{ чётно}}} a(d)\,\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.}$$
Именно она вычисляется в программе.
По исходному определению
$$g(4)=-\gcd(4,1)+\gcd(4,4)-\gcd(4,9)+\gcd(4,16)=-1+4-1+4=6.$$
Та же величина получается и из формулы по делителям. Чётные делители числа \(4\) равны \(2\) и \(4\), причём
$$\rho(2)=2,\quad a(2)=\frac{\varphi(2)\cdot 2}{2}=1,$$
$$\rho(4)=2,\quad a(4)=\frac{\varphi(4)\cdot 4}{2}=4.$$
Так как \(4\) чётно, базового нечётного слагаемого нет, и
$$g(4)=a(2)\frac{4}{2}+a(4)\frac{4}{4}=1\cdot 2+4\cdot 1=6.$$
Для накопленной суммы получаем
$$G(4)=g(1)+g(2)+g(3)+g(4)=-1+1-3+6=3.$$
Закрытая формула даёт то же самое:
$$G(4)=-\left\lceil \frac 42\right\rceil^2+a(2)\frac{2\cdot 3}{2}+a(4)\frac{1\cdot 2}{2}=-4+3+4=3.$$
Реализации на C++, Python и Java используют один и тот же вычислительный конвейер. Сначала строится линейное решето, которое хранит наименьший простой делитель каждого числа до \(N\). Благодаря этому разложение очередного числа получается из уже обработанного частного, возникающего после удаления одного наименьшего простого множителя.
В этом же проходе для всех \(d\le N\) вычисляется вес \(a(d)\). Если наименьший простой множитель встречается впервые, новый вклад равен \(p-1\). Если же продолжается уже существующая простая степень, то по чётности обновлённого показателя выбирается множитель \(p\) или \(p^2\). Это ровно та же закономерность, что и в формуле для простой степени.
После построения таблицы весов итоговая сумма начинается с базового члена \(-\lceil N/2\rceil^2\). Затем перебираются только чётные \(d\); для каждого вычисляется \(m=\lfloor N/d\rfloor\), прибавляется \(a(d)\,m(m+1)/2\), и так получается \(G(N)\) без явного расчёта исходной двойной суммы.
Линейное решето по наименьшим простым делителям работает за \(O(N)\), и таблица весов заполняется в том же линейном проходе. Финальное суммирование по чётным \(d\) тоже имеет сложность \(O(N)\). Следовательно, полное время работы равно \(O(N)\), а объём памяти составляет \(O(N)\).
نعرف
$$g(n)=\sum_{i=1}^{n}(-1)^i\gcd(n,i^2),\qquad G(N)=\sum_{n=1}^{N} g(n).$$
في المسألة الفعلية نأخذ \(N=12{,}345{,}678\). الحساب المباشر لكل قيمة \(\gcd(n,i^2)\) يؤدي إلى كلفة تربيعية، ولذلك تعيد الخوارزمية صياغة المجموع المتناوب على صورة مجموع على القواسم مع وزن ضربي.
الفكرة الأساسية هي تفكيك المجموع الداخلي حسب قواسم \(n\)، ثم جمع مساهمات القواسم الزوجية داخل دالة حسابية ضربية يمكن بناؤها بخطية.
لكل عددين صحيحين موجبين \(u\) و\(v\) لدينا
$$\gcd(u,v)=\sum_{d\mid \gcd(u,v)} \varphi(d).$$
بتطبيق ذلك على \(u=n\) و\(v=i^2\) نحصل على
$$g(n)=\sum_{i=1}^{n}(-1)^i\sum_{\substack{d\mid n\\ d\mid i^2}} \varphi(d).$$
وبتبديل ترتيب الجمع يصبح
$$g(n)=\sum_{d\mid n}\varphi(d)\,S_d(n),$$
حيث
$$S_d(n)=\sum_{\substack{1\le i\le n\\ d\mid i^2}} (-1)^i.$$
إذن المسألة تختزل إلى فهم المساهمة المتناوبة للأعداد \(i\) التي يكون مربعها قابلاً للقسمة على \(d\).
نكتب تحليل \(d\) إلى عوامل أولية على الصورة
$$d=\prod_{p^{e_p}\parallel d} p^{e_p}.$$
الشرط \(d\mid i^2\) يكافئ \(e_p\le 2v_p(i)\) لكل عدد أولي \(p\)، أي
$$v_p(i)\ge \left\lceil \frac{e_p}{2}\right\rceil \quad (p\mid d).$$
لذلك نعرّف
$$\rho(d)=\prod_{p^{e_p}\parallel d} p^{\lceil e_p/2\rceil}.$$
وهذا هو أصغر عدد موجب مربعه يقبل القسمة على \(d\). وعندها
$$d\mid i^2 \iff \rho(d)\mid i.$$
وبما أن \(\rho(d)\mid d\mid n\)، يمكننا كتابة
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^{\rho(d)k}.$$
فردية أو زوجية \(\rho(d)\) هي نفسها فردية أو زوجية \(d\)، ولذلك يظهر حالتان واضحتان.
إذا كان \(d\) زوجياً فإن \(\rho(d)\) زوجي أيضاً، وجميع الإشارات تصبح \(+1\)، ومن ثم
$$S_d(n)=\frac{n}{\rho(d)}.$$
أما إذا كان \(d\) فردياً فإن \(\rho(d)\) فردي، وبالتالي
$$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^k=\begin{cases} 0, & 2\mid n,\\ -1, & 2\nmid n. \end{cases}$$
والسبب أن القسمة على عدد فردي لا تغيّر الزوجية. إذا كان \(n\) فردياً فكل قواسمه فردية أيضاً، وعندئذ
$$g(n)=-\sum_{d\mid n}\varphi(d)=-n,$$
باستخدام الهوية \(\sum_{d\mid n}\varphi(d)=n\). وإذا كان \(n\) زوجياً فإن مساهمة القواسم الفردية تساوي صفراً. لذا نحصل على
$$g(n)= -n\,\mathbf{1}_{2\nmid n}+\sum_{\substack{d\mid n\\ 2\mid d}}\varphi(d)\frac{n}{\rho(d)}.$$
نعرّف الوزن
$$a(d)=\frac{\varphi(d)\,d}{\rho(d)}.$$
وعندها
$$\varphi(d)\frac{n}{\rho(d)}=a(d)\frac{n}{d},$$
فتصبح الصيغة
$$g(n)= -n\,\mathbf{1}_{2\nmid n}+\sum_{\substack{d\mid n\\ 2\mid d}} a(d)\frac{n}{d}.$$
الدالة \(a\) ضربية. وللقوة الأولية \(p^e\) نحصل على
$$a(p^e)=\frac{\varphi(p^e)p^e}{p^{\lceil e/2\rceil}}=(p-1)p^{\lfloor 3e/2\rfloor-1}.$$
وبصورة مكافئة،
$$a\bigl(p^{2t-1}\bigr)=(p-1)p^{3t-3},\qquad a\bigl(p^{2t}\bigr)=(p-1)p^{3t-1}.$$
وهذا يفسر قاعدة التحديث في التنفيذ: إذا ظهر عامل أولي جديد نضرب في \(p-1\)، وإذا كنا نزيد أسّ العامل الأولي الحالي فإن الزوجية الجديدة للأس تحدد هل الضرب يكون في \(p\) أم في \(p^2\).
الآن نجمع صيغة \(g(n)\) من \(1\) إلى \(N\). الجزء الأساسي القادم من الأعداد الفردية يساوي
$$\sum_{\substack{1\le n\le N\\ 2\nmid n}} n = 1+3+\cdots +(2\lceil N/2\rceil-1)=\left\lceil \frac N2\right\rceil^2.$$
وبالنسبة إلى قاسم زوجي ثابت \(d\)، نكتب \(n=dm\)، فنحصل على
$$\sum_{\substack{1\le n\le N\\ d\mid n}} \frac{n}{d}=\sum_{m=1}^{\lfloor N/d\rfloor} m=\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.$$
إذن الصيغة النهائية هي
$$\boxed{G(N)=-\left\lceil \frac N2\right\rceil^2+\sum_{\substack{2\le d\le N\\ 2\mid d}} a(d)\,\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.}$$
وهذه هي الصيغة التي تعتمدها جميع التنفيذات.
من التعريف الأصلي مباشرة نحصل على
$$g(4)=-\gcd(4,1)+\gcd(4,4)-\gcd(4,9)+\gcd(4,16)=-1+4-1+4=6.$$
وصيغة القواسم تعطي النتيجة نفسها. القواسم الزوجية للعدد \(4\) هي \(2\) و\(4\)، ولدينا
$$\rho(2)=2,\quad a(2)=\frac{\varphi(2)\cdot 2}{2}=1,$$
$$\rho(4)=2,\quad a(4)=\frac{\varphi(4)\cdot 4}{2}=4.$$
ولأن \(4\) زوجي فلا يوجد حد أساسي فردي، وبالتالي
$$g(4)=a(2)\frac{4}{2}+a(4)\frac{4}{4}=1\cdot 2+4\cdot 1=6.$$
أما المجموع التراكمي فيكون
$$G(4)=g(1)+g(2)+g(3)+g(4)=-1+1-3+6=3.$$
والصيغة المغلقة تؤكد ذلك:
$$G(4)=-\left\lceil \frac 42\right\rceil^2+a(2)\frac{2\cdot 3}{2}+a(4)\frac{1\cdot 2}{2}=-4+3+4=3.$$
تنفيذات C++ وPython وJava تتبع المسار نفسه. أولاً تُبنى غربال خطية تحفظ أصغر عامل أولي لكل عدد حتى \(N\). هذا يسمح باشتقاق تحليل كل عدد جديد من تحليل خارج القسمة الناتج بعد إزالة عامل أولي أصغر واحد.
في المرور نفسه تُحسب قيم الوزن \(a(d)\) لكل \(d\le N\). إذا كان العامل الأولي الأصغر جديداً في هذا العدد فالمساهمة الجديدة هي \(p-1\). وإذا كان امتداداً لقوة أولية موجودة من قبل، فإن زوجية الأس بعد التحديث تحدد هل نضرب في \(p\) أم في \(p^2\). وهكذا تتحول صيغة القوى الأولية إلى تحديث تدريجي ملائم للغربال.
بعد اكتمال جدول الأوزان تبدأ عملية الجمع النهائي من الحد الأساسي \(-\lceil N/2\rceil^2\). ثم يمر التنفيذ على القيم الزوجية \(d\) فقط، ويحسب \(m=\lfloor N/d\rfloor\)، ويضيف \(a(d)\,m(m+1)/2\)، وبذلك يصل إلى \(G(N)\) من دون فك المجموع الأصلي المزدوج.
غربال أصغر عامل أولي يعمل في \(O(N)\)، كما أن بناء جدول الأوزان يتم في المرور الخطي نفسه. ثم تأتي عملية الجمع على القواسم الزوجية بكلفة \(O(N)\) أيضاً. لذلك يكون التعقيد الزمني الكلي \(O(N)\)، والتعقيد المكاني \(O(N)\).