Let \(s(n)\) denote the Gaussian-divisor sum defined in the problem, and let
$$S(N)=\sum_{n=1}^{N} s(n),\qquad N=10^8.$$
Ordinary positive divisors of \(n\) are also Gaussian divisors, purely imaginary divisors have real part \(0\), and genuinely complex divisors occur in conjugate pairs whose imaginary parts cancel. The task is therefore not to factor every \(n\) separately in \(\mathbb{Z}[i]\), but to count how often each possible Gaussian divisor appears among the integers up to \(N\).
The C++, Python, and Java implementations all exploit the same reorganization: isolate the ordinary divisor contribution, classify every non-real Gaussian divisor by a primitive direction and an integer scale, and evaluate the resulting sums through a fast summatory divisor routine.
The entire solution comes from turning a sum over integers \(n\) into a sum over Gaussian divisors that can divide some \(n\le N\).
The divisors on the real axis are exactly the ordinary positive divisors. Their total contribution to \(S(N)\) is
$$T(N)=\sum_{m=1}^{N}\sigma(m)=\sum_{d=1}^{N} d\left\lfloor\frac{N}{d}\right\rfloor,$$
because each positive integer \(d\) divides exactly \(\lfloor N/d\rfloor\) integers up to \(N\). This is the familiar summatory divisor function.
Purely imaginary divisors need no separate treatment: their real part is zero, so they do not affect the final total. The only additional work comes from Gaussian divisors with both real and imaginary parts nonzero.
Every contributing non-real Gaussian divisor can be represented uniquely in the form
\(d(a+bi)\) or \(d(a-bi)\).
where \(d\ge 1\), \(a,b\ge 1\), and \(\gcd(a,b)=1\). Any common factor of the real and imaginary parts is absorbed into the positive integer scale \(d\), so \((a,b)\) describes a primitive Gaussian direction.
For that primitive direction, define the norm
$$m=a^2+b^2.$$
This is exactly why the implementations loop only over coprime pairs \((a,b)\): non-primitive pairs would merely duplicate divisors already counted by a larger scale \(d\).
Fix a primitive direction \((a,b)\) and a scale \(d\). To determine when \(d(a+bi)\) divides an ordinary integer \(n\), multiply by the conjugate:
$$\frac{n}{d(a+bi)}=\frac{n(a-bi)}{d(a^2+b^2)}=\frac{n(a-bi)}{dm}.$$
Because \(\gcd(a,b)=1\), we also have \(\gcd(a,m)=\gcd(b,m)=1\). Therefore the real and imaginary parts of the quotient are integers exactly when \(dm\mid n\).
This is the crucial simplification. Divisibility by a Gaussian number is reduced to an ordinary divisibility condition involving the scale \(d\) and the primitive norm \(m=a^2+b^2\).
For fixed \((a,b)\) and \(d\), the conjugate pair \(d(a+bi)\) and \(d(a-bi)\) contributes the same real part \(da\), so together they contribute \(2da\) to every integer \(n\) divisible by \(dm\). There are exactly \(\left\lfloor N/(dm)\right\rfloor\) such integers up to \(N\).
Hence one primitive direction \((a,b)\) contributes
$$\sum_{d\ge 1} 2da\left\lfloor\frac{N}{dm}\right\rfloor=2a\sum_{d\le N/m} d\left\lfloor\frac{N/m}{d}\right\rfloor=2a\,T\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
Adding the ordinary divisor part gives the exact formula implemented by all three languages:
$$\boxed{S(N)=T(N)+\sum_{\substack{a,b\ge 1\\ \gcd(a,b)=1\\ a^2+b^2\le N}} 2a\,T\!\left(\left\lfloor\frac{N}{a^2+b^2}\right\rfloor\right).}$$
The condition \(a^2+b^2\le N\) is automatic: if the primitive norm already exceeds \(N\), then even the unscaled Gaussian divisor cannot divide any integer at most \(N\).
Take \(a=1\), \(b=2\), so \(m=1^2+2^2=5\). If \(N=20\), then the relevant scaled divisors are
$$1\pm 2i,\quad 2\pm 4i,\quad 3\pm 6i,\quad 4\pm 8i,$$
because \(d\le N/m=4\). The pair \(d(1\pm 2i)\) divides exactly the multiples of \(5d\), and its total real contribution is \(2d\cdot \lfloor 20/(5d)\rfloor\). Summing over \(d=1,2,3,4\) gives
$$2\bigl(1\cdot 4+2\cdot 2+3\cdot 1+4\cdot 1\bigr)=30.$$
This is precisely
$$2a\,T\!\left(\left\lfloor\frac{20}{5}\right\rfloor\right)=2\,T(4),$$
which shows on a small example how one primitive direction collapses to one summatory-divisor query.
The first ingredient is \(T(M)=\sum_{d\le M} d\lfloor M/d\rfloor\). The implementation does not iterate over all \(d\) one by one. Instead it groups together intervals on which the quotient \(\lfloor M/d\rfloor\) is constant.
If the current left endpoint is \(l\), then \(q=\lfloor M/l\rfloor\) stays unchanged up to \(r=\lfloor M/q\rfloor\). The whole block contributes
$$q\sum_{d=l}^{r} d=q\cdot \frac{(l+r)(r-l+1)}{2}.$$
This standard equal-quotient grouping reduces one prefix query from linear time to about \(O(\sqrt M)\).
The implementations start the answer with the ordinary divisor contribution \(T(N)\). They then scan all integer pairs \(a\ge 1\), \(b\ge 1\) satisfying \(a^2+b^2\le N\), and retain only the coprime pairs. Those are the primitive directions from the derivation above.
For each surviving pair, the norm \(a^2+b^2\) is computed, the value \(T\!\left(\left\lfloor N/(a^2+b^2)\right\rfloor\right)\) is queried, multiplied by \(2a\), and added to the running total.
Many different primitive pairs produce the same quotient \(\left\lfloor N/(a^2+b^2)\right\rfloor\). The C++ and Python implementations store previously computed divisor-prefix values so that repeated queries are answered immediately. The Java implementation applies the same formula directly without that memoization layer, but the mathematical accumulation is identical in all three languages.
The dominant scan is the enumeration of lattice points in the quarter-disk \(a^2+b^2\le N\), which contains \(O(N)\) integer pairs because the radius is \(\sqrt N\). The coprimality test changes only the constant factor.
Each distinct divisor-prefix query is evaluated in about \(O(\sqrt M)\) time by equal-quotient grouping. In the memoized variants, many queries reuse an earlier result because the same quotient occurs repeatedly. Memory usage is \(O(U)\) for the number \(U\) of cached prefix values; aside from that cache, the algorithm uses only constant extra loop state.
The real gain is structural rather than cosmetic: instead of factoring every integer up to \(10^8\) in \(\mathbb{Z}[i]\), the solution performs one global scan of primitive Gaussian directions and a manageable number of summatory-divisor evaluations.
Sei \(s(n)\) die in der Aufgabenstellung definierte Summe gaußscher Teiler, und sei
$$S(N)=\sum_{n=1}^{N} s(n),\qquad N=10^8.$$
Gewöhnliche positive Teiler von \(n\) sind zugleich gaußsche Teiler, rein imaginäre Teiler haben Realteil \(0\), und echte komplexe Teiler treten paarweise als Konjugierte auf, sodass sich ihre Imaginärteile wegheben. Man muss also nicht jedes \(n\) separat in \(\mathbb{Z}[i]\) faktorisieren, sondern nur zählen, wie oft ein möglicher gaußscher Teiler unter allen Zahlen bis \(N\) vorkommt.
Die Implementierungen in C++, Python und Java benutzen genau diese Umordnung: zuerst der gewöhnliche Teileranteil, dann eine Zerlegung jedes nichtreellen gaußschen Teilers in primitive Richtung und ganzzahligen Skalierungsfaktor, schließlich eine schnelle Auswertung einer summatorischen Teilerfunktion.
Die gesamte Lösung entsteht, indem man die Summe über die ganzen Zahlen \(n\) in eine Summe über alle gaußschen Teiler umschreibt, die überhaupt ein \(n\le N\) teilen können.
Die Teiler auf der reellen Achse sind genau die gewöhnlichen positiven Teiler. Ihr Gesamtbeitrag zu \(S(N)\) ist
$$T(N)=\sum_{m=1}^{N}\sigma(m)=\sum_{d=1}^{N} d\left\lfloor\frac{N}{d}\right\rfloor,$$
denn jede positive ganze Zahl \(d\) teilt genau \(\lfloor N/d\rfloor\) Zahlen bis \(N\). Das ist die klassische summatorische Teilerfunktion.
Rein imaginäre Teiler brauchen keine eigene Behandlung: Ihr Realteil ist null. Übrig bleibt also nur der Beitrag der gaußschen Teiler mit nichtverschwindendem Real- und Imaginärteil.
Jeder beitragende nichtreelle gaußsche Teiler lässt sich eindeutig in der Form
\(d(a+bi)\) oder \(d(a-bi)\).
schreiben, wobei \(d\ge 1\), \(a,b\ge 1\) und \(\gcd(a,b)=1\) gilt. Jeder gemeinsame Faktor von Real- und Imaginärteil wird in den positiven ganzzahligen Faktor \(d\) gezogen, sodass \((a,b)\) eine primitive gaußsche Richtung beschreibt.
Zu dieser primitiven Richtung gehört die Norm
$$m=a^2+b^2.$$
Genau deshalb prüfen die Implementierungen nur teilerfremde Paare \((a,b)\): Nichtprimitive Paare würden lediglich Divisoren doppelt erfassen, die bereits über einen größeren Wert von \(d\) gezählt werden.
Fixiere nun eine primitive Richtung \((a,b)\) und einen Faktor \(d\). Um zu entscheiden, wann \(d(a+bi)\) eine gewöhnliche ganze Zahl \(n\) teilt, multipliziert man mit dem Konjugierten:
$$\frac{n}{d(a+bi)}=\frac{n(a-bi)}{d(a^2+b^2)}=\frac{n(a-bi)}{dm}.$$
Aus \(\gcd(a,b)=1\) folgt auch \(\gcd(a,m)=\gcd(b,m)=1\). Daher sind Real- und Imaginärteil dieses Quotienten genau dann ganzzahlig, wenn \(dm\mid n\) gilt.
Das ist die entscheidende Vereinfachung: Teilbarkeit durch eine gaußsche Zahl wird auf eine gewöhnliche Teilbarkeitsbedingung zurückgeführt, nämlich auf den Faktor \(d\) und die primitive Norm \(m=a^2+b^2\).
Für festes \((a,b)\) und \(d\) tragen die beiden konjugierten Teiler \(d(a+bi)\) und \(d(a-bi)\) denselben Realteil \(da\) bei. Zusammen liefern sie also \(2da\) für jede Zahl \(n\), die durch \(dm\) teilbar ist. Solche Zahlen gibt es bis \(N\) genau \(\left\lfloor N/(dm)\right\rfloor\).
Der Beitrag einer primitiven Richtung \((a,b)\) ist deshalb
$$\sum_{d\ge 1} 2da\left\lfloor\frac{N}{dm}\right\rfloor=2a\sum_{d\le N/m} d\left\lfloor\frac{N/m}{d}\right\rfloor=2a\,T\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
Mit dem rationalen Anteil ergibt sich genau die Formel, die in allen drei Sprachen implementiert wird:
$$\boxed{S(N)=T(N)+\sum_{\substack{a,b\ge 1\\ \gcd(a,b)=1\\ a^2+b^2\le N}} 2a\,T\!\left(\left\lfloor\frac{N}{a^2+b^2}\right\rfloor\right).}$$
Die Bedingung \(a^2+b^2\le N\) ist unvermeidlich: Wenn schon die primitive Norm größer als \(N\) ist, kann selbst der unskalierte gaußsche Teiler keine Zahl bis \(N\) teilen.
Nimm \(a=1\) und \(b=2\), also \(m=1^2+2^2=5\). Für \(N=20\) sind die relevanten skalierten Teiler
$$1\pm 2i,\quad 2\pm 4i,\quad 3\pm 6i,\quad 4\pm 8i,$$
denn \(d\le N/m=4\). Das Paar \(d(1\pm 2i)\) teilt genau die Vielfachen von \(5d\), und sein gesamter Realteilbeitrag ist \(2d\cdot \lfloor 20/(5d)\rfloor\). Für \(d=1,2,3,4\) erhält man
$$2\bigl(1\cdot 4+2\cdot 2+3\cdot 1+4\cdot 1\bigr)=30.$$
Das ist exakt
$$2a\,T\!\left(\left\lfloor\frac{20}{5}\right\rfloor\right)=2\,T(4),$$
und zeigt an einem kleinen Beispiel, wie eine primitive Richtung auf eine einzige Auswertung der summatorischen Teilerfunktion schrumpft.
Die erste Zutat ist \(T(M)=\sum_{d\le M} d\lfloor M/d\rfloor\). Die Implementierung läuft dabei nicht über alle \(d\) einzeln, sondern fasst Intervalle zusammen, auf denen der Quotient \(\lfloor M/d\rfloor\) konstant bleibt.
Wenn \(l\) der aktuelle linke Rand ist, dann bleibt \(q=\lfloor M/l\rfloor\) bis \(r=\lfloor M/q\rfloor\) unverändert. Der gesamte Block trägt
$$q\sum_{d=l}^{r} d=q\cdot \frac{(l+r)(r-l+1)}{2}$$
bei. Diese Standardtechnik senkt eine einzelne Präfixanfrage von linearer Laufzeit auf ungefähr \(O(\sqrt M)\).
Die Implementierungen starten mit dem gewöhnlichen Teileranteil \(T(N)\). Danach werden alle ganzzahligen Paare \(a\ge 1\), \(b\ge 1\) mit \(a^2+b^2\le N\) durchsucht, und nur teilerfremde Paare bleiben übrig. Genau diese Paare sind die primitiven Richtungen aus der Herleitung.
Für jedes solche Paar wird die Norm \(a^2+b^2\) berechnet, der Wert \(T\!\left(\left\lfloor N/(a^2+b^2)\right\rfloor\right)\) abgefragt, mit \(2a\) multipliziert und zum laufenden Ergebnis addiert.
Viele verschiedene primitive Paare erzeugen denselben Quotienten \(\left\lfloor N/(a^2+b^2)\right\rfloor\). Die C++- und Python-Implementierungen speichern bereits berechnete Präfixwerte und beantworten identische Anfragen sofort. Die Java-Implementierung verwendet dieselbe Formel direkt ohne diese Zwischenspeicherung, aber die mathematische Summation ist in allen drei Sprachen dieselbe.
Der dominierende Schritt ist die Enumeration der Gitterpunkte im Viertelkreis \(a^2+b^2\le N\). Da der Radius \(\sqrt N\) ist, enthält dieser Bereich \(O(N)\) ganzzahlige Paare; der Teilerfremdheitstest ändert nur den konstanten Faktor.
Jede unterschiedliche Präfixanfrage wird durch Quotientengruppierung in ungefähr \(O(\sqrt M)\) Zeit berechnet. In den Varianten mit Memoisierung werden viele Anfragen wiederverwendet, weil derselbe Quotient sehr oft vorkommt. Der Speicherbedarf beträgt \(O(U)\) für die Anzahl \(U\) der gespeicherten Präfixwerte; abgesehen davon wird nur konstanter zusätzlicher Schleifenzustand benötigt.
Der eigentliche Gewinn ist strukturell: Statt jede Zahl bis \(10^8\) einzeln in \(\mathbb{Z}[i]\) zu faktorisieren, genügt ein globaler Durchlauf über primitive gaußsche Richtungen plus eine handhabbare Zahl von Teilerpräfix-Abfragen.
\(s(n)\) soruda tanımlanan Gaussian bölen toplamı olsun ve
$$S(N)=\sum_{n=1}^{N} s(n),\qquad N=10^8$$
olarak tanımlansın. \(n\)'in sıradan pozitif bölenleri aynı zamanda Gaussian bölenlerdir, saf imajiner bölenlerin gerçel kısmı \(0\)'dır ve gerçekten karmaşık bölenler eşlenik çiftler halinde geldiği için imajiner kısımlar birbirini götürür. Bu yüzden amaç, her \(n\)'i ayrı ayrı \(\mathbb{Z}[i]\) içinde çarpanlara ayırmak değil, hangi Gaussian bölenin \(N\)'e kadar kaç kez ortaya çıktığını topluca saymaktır.
C++, Python ve Java uygulamalarının ortak fikri budur: önce sıradan bölen katkısını ayırmak, sonra her gerçel olmayan Gaussian böleni bir ilkel yön ve bir tamsayı ölçeğiyle sınıflandırmak, en sonunda da ortaya çıkan toplamları hızlı bir bölen-önek hesabıyla değerlendirmek.
Bütün çözüm, \(n\) üzerinden giden toplamı, \(n\le N\) için gerçekten bölen olabilecek Gaussian sayılar üzerinden giden bir toplama çevirmekten çıkıyor.
Gerçel eksen üzerindeki bölenler tam olarak sıradan pozitif bölenlerdir. Bunların \(S(N)\)'e toplam katkısı
$$T(N)=\sum_{m=1}^{N}\sigma(m)=\sum_{d=1}^{N} d\left\lfloor\frac{N}{d}\right\rfloor$$
olur; çünkü her pozitif tamsayı \(d\), \(N\)'e kadar tam olarak \(\lfloor N/d\rfloor\) sayı böler. Bu ifade klasik bölen-toplam önek fonksiyonudur.
Saf imajiner bölenleri ayrıca ele almaya gerek yoktur; gerçel katkıları sıfırdır. Geriye yalnızca hem gerçel hem imajiner kısmı sıfır olmayan Gaussian bölenler kalır.
Katkı yapan her gerçel olmayan Gaussian bölen benzersiz biçimde
\(d(a+bi)\) veya \(d(a-bi)\).
şeklinde yazılabilir; burada \(d\ge 1\), \(a,b\ge 1\) ve \(\gcd(a,b)=1\) olur. Gerçel ve imajiner kısımdaki ortak çarpanlar pozitif tamsayı ölçeği olan \(d\)'ye çekildiği için \((a,b)\) bir ilkel Gaussian yönü temsil eder.
Bu ilkel yönün normu
$$m=a^2+b^2$$
olarak tanımlanır. Uygulamaların yalnızca aralarında asal \((a,b)\) çiftlerini gezmesinin nedeni tam olarak budur: ilkel olmayan çiftler, daha büyük bir \(d\) ile zaten sayılmış bölenleri tekrar eder.
Şimdi ilkel bir \((a,b)\) yönünü ve bir \(d\) ölçeğini sabitleyelim. \(d(a+bi)\)'nin sıradan bir \(n\) tam sayısını ne zaman böldüğünü anlamak için eşleniğiyle çarparız:
$$\frac{n}{d(a+bi)}=\frac{n(a-bi)}{d(a^2+b^2)}=\frac{n(a-bi)}{dm}.$$
\(\gcd(a,b)=1\) olduğundan \(\gcd(a,m)=\gcd(b,m)=1\) da geçerlidir. Dolayısıyla bu bölümün hem gerçel hem imajiner kısmı ancak ve ancak \(dm\mid n\) iken tamsayı olur.
Asıl sadeleşme burada gerçekleşir. Bir Gaussian sayıya bölünebilme, yalnızca ölçek \(d\) ile ilkel norm \(m=a^2+b^2\) üzerinden yazılan sıradan bir bölünebilme koşuluna indirgenir.
Sabit \((a,b)\) ve \(d\) için, eşlenik çift \(d(a+bi)\) ile \(d(a-bi)\) aynı gerçel kısma, yani \(da\)'ya sahiptir. Bu yüzden \(dm\)'ye bölünen her \(n\) için birlikte \(2da\) katkı yaparlar. \(N\)'e kadar böyle sayıların sayısı tam olarak \(\left\lfloor N/(dm)\right\rfloor\)'dür.
Dolayısıyla tek bir ilkel yön \((a,b)\)'nin toplam katkısı
$$\sum_{d\ge 1} 2da\left\lfloor\frac{N}{dm}\right\rfloor=2a\sum_{d\le N/m} d\left\lfloor\frac{N/m}{d}\right\rfloor=2a\,T\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
olur. Bunu sıradan bölen katkısıyla birleştirince, üç uygulamanın da kullandığı tam formül ortaya çıkar:
$$\boxed{S(N)=T(N)+\sum_{\substack{a,b\ge 1\\ \gcd(a,b)=1\\ a^2+b^2\le N}} 2a\,T\!\left(\left\lfloor\frac{N}{a^2+b^2}\right\rfloor\right).}$$
\(a^2+b^2\le N\) koşulu zorunludur; çünkü ilkel norm daha baştan \(N\)'yi aşıyorsa, ölçeklenmemiş Gaussian bölen bile \(N\)'e kadar hiçbir tamsayıyı bölemez.
\(a=1\) ve \(b=2\) alalım; bu durumda \(m=1^2+2^2=5\) olur. \(N=20\) için ilgili ölçeklenmiş bölenler
$$1\pm 2i,\quad 2\pm 4i,\quad 3\pm 6i,\quad 4\pm 8i$$
şeklindedir; çünkü \(d\le N/m=4\) olmalıdır. \(d(1\pm 2i)\) çifti tam olarak \(5d\)'nin katlarını böler ve toplam gerçel katkısı \(2d\cdot \lfloor 20/(5d)\rfloor\) olur. \(d=1,2,3,4\) için toplarsak
$$2\bigl(1\cdot 4+2\cdot 2+3\cdot 1+4\cdot 1\bigr)=30$$
elde ederiz. Bu da tam olarak
$$2a\,T\!\left(\left\lfloor\frac{20}{5}\right\rfloor\right)=2\,T(4)$$
ifadesidir ve tek bir ilkel yönün nasıl tek bir bölen-önek sorgusuna dönüştüğünü somut biçimde gösterir.
İlk yapı taşı \(T(M)=\sum_{d\le M} d\lfloor M/d\rfloor\) ifadesidir. Uygulama bütün \(d\) değerlerini tek tek dolaşmaz; bunun yerine \(\lfloor M/d\rfloor\) bölümünün sabit kaldığı aralıkları gruplayarak toplar.
Güncel sol uç \(l\) ise, \(q=\lfloor M/l\rfloor\) değeri \(r=\lfloor M/q\rfloor\)'ye kadar değişmez. Bu bloğun katkısı
$$q\sum_{d=l}^{r} d=q\cdot \frac{(l+r)(r-l+1)}{2}$$
şeklindedir. Bu standart eşit-bölüm gruplaması, tek bir önek sorgusunu doğrusal zamandan yaklaşık \(O(\sqrt M)\) düzeyine indirir.
Uygulamalar cevabı önce sıradan bölen katkısı \(T(N)\) ile başlatır. Daha sonra \(a^2+b^2\le N\) şartını sağlayan tüm \(a\ge 1\), \(b\ge 1\) çiftleri taranır ve sadece aralarında asal olanlar tutulur. Bunlar türetimdeki ilkel yönlerdir.
Kalan her çift için norm \(a^2+b^2\) hesaplanır, \(T\!\left(\left\lfloor N/(a^2+b^2)\right\rfloor\right)\) değeri sorgulanır, \(2a\) ile çarpılır ve toplam cevaba eklenir.
Birçok farklı ilkel çift aynı \(\left\lfloor N/(a^2+b^2)\right\rfloor\) bölümünü üretir. C++ ve Python uygulamaları daha önce hesaplanan bölen-önek değerlerini saklayarak aynı sorguları anında yanıtlar. Java uygulaması aynı formülü bu önbellekleme katmanı olmadan doğrudan uygular; yine de üç dilde hesaplanan matematiksel toplam tamamen aynıdır.
Baskın adım, \(a^2+b^2\le N\) çeyrek-diskindeki kafes noktalarını taramaktır. Yarıçap \(\sqrt N\) olduğu için bu bölgede \(O(N)\) adet tamsayı çifti bulunur; aralarında asallık testi yalnızca sabit katsayıyı değiştirir.
Her farklı bölen-önek sorgusu, eşit-bölüm gruplaması sayesinde yaklaşık \(O(\sqrt M)\) zamanda hesaplanır. Önbellekli sürümlerde aynı bölüm tekrar tekrar ortaya çıktığından birçok sorgu yeniden kullanılabilir. Bellek kullanımı, saklanan önek değerlerinin sayısı \(U\) için \(O(U)\)'dur; bunun dışında yalnızca sabit büyüklükte döngü durumu tutulur.
Asıl kazanç yapısaldır: çözüm, \(10^8\)'e kadar tüm sayıları \(\mathbb{Z}[i]\) içinde ayrı ayrı çarpanlara ayırmak yerine, ilkel Gaussian yönler üzerinde tek bir küresel tarama ve yönetilebilir sayıda bölen-önek hesabı yapar.
Sea \(s(n)\) la suma de divisores gaussianos definida en el enunciado, y sea
$$S(N)=\sum_{n=1}^{N} s(n),\qquad N=10^8.$$
Los divisores positivos ordinarios de \(n\) también son divisores gaussianos, los divisores puramente imaginarios tienen parte real \(0\), y los divisores complejos no reales aparecen en pares conjugados cuyas partes imaginarias se cancelan. Por tanto, el objetivo no es factorizar cada \(n\) por separado en \(\mathbb{Z}[i]\), sino contar cuántas veces aparece cada posible divisor gaussiano entre todos los enteros hasta \(N\).
Las implementaciones en C++, Python y Java usan exactamente esa reorganización: separar primero la contribución de los divisores ordinarios, clasificar cada divisor gaussiano no real mediante una dirección primitiva y un factor entero, y evaluar después las sumas resultantes con una rutina rápida para la función sumatoria de divisores.
Toda la solución sale de sustituir una suma sobre los enteros \(n\) por una suma sobre todos los divisores gaussianos que realmente pueden dividir a algún \(n\le N\).
Los divisores situados sobre el eje real son exactamente los divisores positivos ordinarios. Su contribución total a \(S(N)\) es
$$T(N)=\sum_{m=1}^{N}\sigma(m)=\sum_{d=1}^{N} d\left\lfloor\frac{N}{d}\right\rfloor,$$
porque cada entero positivo \(d\) divide a exactamente \(\lfloor N/d\rfloor\) números hasta \(N\). Esta es la función sumatoria clásica de divisores.
Los divisores puramente imaginarios no necesitan tratamiento aparte: su parte real es nula. Así, el único trabajo adicional proviene de los divisores gaussianos con parte real e imaginaria no nulas.
Cada divisor gaussiano no real que aporta a la suma puede escribirse de forma única como
\(d(a+bi)\) o \(d(a-bi)\).
con \(d\ge 1\), \(a,b\ge 1\) y \(\gcd(a,b)=1\). Todo factor común de la parte real e imaginaria se absorbe en el entero positivo \(d\), de modo que \((a,b)\) describe una dirección gaussiana primitiva.
Para esa dirección primitiva definimos la norma
$$m=a^2+b^2.$$
Esta es exactamente la razón por la que el código solo recorre pares coprimos \((a,b)\): los pares no primitivos solo repetirían divisores ya contados mediante un valor mayor de \(d\).
Fijemos ahora una dirección primitiva \((a,b)\) y un factor \(d\). Para decidir cuándo \(d(a+bi)\) divide a un entero ordinario \(n\), multiplicamos por el conjugado:
$$\frac{n}{d(a+bi)}=\frac{n(a-bi)}{d(a^2+b^2)}=\frac{n(a-bi)}{dm}.$$
Como \(\gcd(a,b)=1\), también se cumple \(\gcd(a,m)=\gcd(b,m)=1\). Por tanto, la parte real y la parte imaginaria del cociente son enteras exactamente cuando \(dm\mid n\).
Ahí está la simplificación central. La divisibilidad por un número gaussiano se reduce a una condición ordinaria de divisibilidad que solo involucra el factor \(d\) y la norma primitiva \(m=a^2+b^2\).
Para un \((a,b)\) y un \(d\) fijos, el par conjugado \(d(a+bi)\) y \(d(a-bi)\) tiene la misma parte real \(da\). En conjunto aporta \(2da\) a cada entero \(n\) divisible por \(dm\). Hay exactamente \(\left\lfloor N/(dm)\right\rfloor\) de esos enteros hasta \(N\).
Así, la contribución de una sola dirección primitiva \((a,b)\) es
$$\sum_{d\ge 1} 2da\left\lfloor\frac{N}{dm}\right\rfloor=2a\sum_{d\le N/m} d\left\lfloor\frac{N/m}{d}\right\rfloor=2a\,T\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
Al añadir la parte racional se obtiene exactamente la fórmula usada por las implementaciones:
$$\boxed{S(N)=T(N)+\sum_{\substack{a,b\ge 1\\ \gcd(a,b)=1\\ a^2+b^2\le N}} 2a\,T\!\left(\left\lfloor\frac{N}{a^2+b^2}\right\rfloor\right).}$$
La condición \(a^2+b^2\le N\) es inevitable: si la norma primitiva ya supera \(N\), ni siquiera el divisor gaussiano sin escalar puede dividir a un entero menor o igual que \(N\).
Tomemos \(a=1\) y \(b=2\), de modo que \(m=1^2+2^2=5\). Para \(N=20\), los divisores escalados relevantes son
$$1\pm 2i,\quad 2\pm 4i,\quad 3\pm 6i,\quad 4\pm 8i,$$
porque \(d\le N/m=4\). El par \(d(1\pm 2i)\) divide exactamente a los múltiplos de \(5d\), y su contribución real total es \(2d\cdot \lfloor 20/(5d)\rfloor\). Sumando para \(d=1,2,3,4\) se obtiene
$$2\bigl(1\cdot 4+2\cdot 2+3\cdot 1+4\cdot 1\bigr)=30.$$
Eso es precisamente
$$2a\,T\!\left(\left\lfloor\frac{20}{5}\right\rfloor\right)=2\,T(4),$$
y muestra en un caso concreto cómo una dirección primitiva se reduce a una sola consulta de la función sumatoria de divisores.
El primer ingrediente es \(T(M)=\sum_{d\le M} d\lfloor M/d\rfloor\). La implementación no recorre todos los valores de \(d\) por separado. En su lugar, agrupa intervalos en los que el cociente \(\lfloor M/d\rfloor\) permanece constante.
Si el extremo izquierdo actual es \(l\), entonces \(q=\lfloor M/l\rfloor\) se mantiene hasta \(r=\lfloor M/q\rfloor\). Todo el bloque aporta
$$q\sum_{d=l}^{r} d=q\cdot \frac{(l+r)(r-l+1)}{2}.$$
Esta técnica estándar de agrupar por cocientes iguales reduce una consulta desde tiempo lineal hasta aproximadamente \(O(\sqrt M)\).
Las implementaciones arrancan el resultado con la contribución ordinaria \(T(N)\). Después recorren todos los pares enteros \(a\ge 1\), \(b\ge 1\) tales que \(a^2+b^2\le N\), y conservan solo los pares coprimos. Esos son exactamente los pares primitivos de la derivación.
Para cada par válido se calcula la norma \(a^2+b^2\), se consulta \(T\!\left(\left\lfloor N/(a^2+b^2)\right\rfloor\right)\), se multiplica por \(2a\) y se añade al acumulado.
Muchos pares primitivos distintos producen el mismo cociente \(\left\lfloor N/(a^2+b^2)\right\rfloor\). Las implementaciones en C++ y Python guardan los valores ya calculados de la función prefijo para responder instantáneamente a consultas repetidas. La implementación en Java aplica la misma fórmula de manera directa, sin esa capa de memoización, pero la suma matemática es idéntica en los tres lenguajes.
El recorrido dominante es la enumeración de puntos de la retícula en el cuarto de disco \(a^2+b^2\le N\). Como el radio es \(\sqrt N\), esa región contiene \(O(N)\) pares enteros; la prueba de coprimalidad solo altera el factor constante.
Cada consulta distinta de la función prefijo se evalúa en aproximadamente \(O(\sqrt M)\) gracias al agrupamiento por cocientes iguales. En las variantes con memoización, muchas consultas reutilizan un resultado previo porque el mismo cociente aparece una y otra vez. El uso de memoria es \(O(U)\), donde \(U\) es el número de valores prefijo almacenados; aparte de esa caché, solo se necesita estado constante para los bucles.
La verdadera ganancia es estructural: en vez de factorizar todos los enteros hasta \(10^8\) dentro de \(\mathbb{Z}[i]\), el método realiza un único barrido global sobre direcciones gaussianas primitivas y un número manejable de evaluaciones de la función sumatoria de divisores.
设 \(s(n)\) 为题目定义的高斯整数因子和，并记
$$S(N)=\sum_{n=1}^{N} s(n),\qquad N=10^8.$$
普通正因子本身就是高斯整数因子，纯虚因子的实部为 \(0\)，而真正的复高斯因子会以共轭成对出现，因此虚部最终会相互抵消。于是问题的核心不是把每个 \(n\) 都单独放到 \(\mathbb{Z}[i]\) 里分解，而是统计每一种可能的高斯因子在所有 \(n\le N\) 中出现了多少次。
C++、Python 和 Java 实现都遵循同一个重排思路：先分离普通因子的贡献，再把每个非实高斯因子写成“原始方向 + 整数倍数”的形式，最后用一个快速的约数求和前缀函数把总和算出来。
整套方法的本质，是把“对所有整数 \(n\) 求和”改写成“对所有可能整除某个 \(n\le N\) 的高斯因子求和”。
落在实轴上的因子，恰好就是普通的正因子。它们对 \(S(N)\) 的总贡献为
$$T(N)=\sum_{m=1}^{N}\sigma(m)=\sum_{d=1}^{N} d\left\lfloor\frac{N}{d}\right\rfloor,$$
因为每个正整数 \(d\) 恰好整除 \(\lfloor N/d\rfloor\) 个不超过 \(N\) 的整数。这就是经典的约数和前缀函数。
纯虚因子不需要单独处理，因为它们的实部为零，不会影响最终答案。于是剩下的工作只来自那些实部和虚部都不为零的高斯因子。
每个真正贡献到总和中的非实高斯因子，都可以唯一写成
\(d(a+bi)\) 或 \(d(a-bi)\)。
其中 \(d\ge 1\)、\(a,b\ge 1\)，并且 \(\gcd(a,b)=1\)。如果实部和虚部带有公共因子，就把它吸收到正整数倍数 \(d\) 中，因此 \((a,b)\) 描述的是一个原始高斯方向。
对于这个原始方向，定义其范数为
$$m=a^2+b^2.$$
这正是实现中只枚举互素对 \((a,b)\) 的原因：非原始对只会把已经通过更大倍数 \(d\) 统计过的因子重复一遍。
现在固定一个原始方向 \((a,b)\) 和一个倍数 \(d\)。要判断 \(d(a+bi)\) 何时整除普通整数 \(n\)，把分母乘上共轭即可：
$$\frac{n}{d(a+bi)}=\frac{n(a-bi)}{d(a^2+b^2)}=\frac{n(a-bi)}{dm}.$$
由于 \(\gcd(a,b)=1\)，还可以推出 \(\gcd(a,m)=\gcd(b,m)=1\)。因此，上式的实部和虚部同时为整数，当且仅当 \(dm\mid n\)。
这就是整道题的关键化简。一个高斯整数的整除条件，被完全化成了一个普通的整数整除条件，而且只依赖于倍数 \(d\) 与原始范数 \(m=a^2+b^2\)。
对固定的 \((a,b)\) 与 \(d\)，共轭对 \(d(a+bi)\) 和 \(d(a-bi)\) 具有相同的实部 \(da\)。因此，它们会给每个被 \(dm\) 整除的整数 \(n\) 带来 \(2da\) 的总实部贡献。而不超过 \(N\) 的这类整数一共有 \(\left\lfloor N/(dm)\right\rfloor\) 个。
于是，一个原始方向 \((a,b)\) 的总贡献就是
$$\sum_{d\ge 1} 2da\left\lfloor\frac{N}{dm}\right\rfloor=2a\sum_{d\le N/m} d\left\lfloor\frac{N/m}{d}\right\rfloor=2a\,T\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
再加上普通因子的部分，就得到实现真正使用的精确公式：
$$\boxed{S(N)=T(N)+\sum_{\substack{a,b\ge 1\\ \gcd(a,b)=1\\ a^2+b^2\le N}} 2a\,T\!\left(\left\lfloor\frac{N}{a^2+b^2}\right\rfloor\right).}$$
条件 \(a^2+b^2\le N\) 也是自然的：如果原始范数已经大于 \(N\)，那么连未经放大的那个高斯因子都不可能整除任何 \(n\le N\)。
取 \(a=1\)、\(b=2\)，则 \(m=1^2+2^2=5\)。如果 \(N=20\)，相关的倍数因子就是
$$1\pm 2i,\quad 2\pm 4i,\quad 3\pm 6i,\quad 4\pm 8i,$$
因为此时 \(d\le N/m=4\)。其中 \(d(1\pm 2i)\) 恰好整除所有 \(5d\) 的倍数，所以它带来的总实部贡献为 \(2d\cdot \lfloor 20/(5d)\rfloor\)。对 \(d=1,2,3,4\) 求和得到
$$2\bigl(1\cdot 4+2\cdot 2+3\cdot 1+4\cdot 1\bigr)=30.$$
这正好等于
$$2a\,T\!\left(\left\lfloor\frac{20}{5}\right\rfloor\right)=2\,T(4),$$
它清楚地展示了：一个原始方向的全部贡献，可以被压缩成一次约数和前缀查询。
第一块核心算术是 \(T(M)=\sum_{d\le M} d\lfloor M/d\rfloor\)。实现不会对所有 \(d\) 一个个累加，而是把那些使 \(\lfloor M/d\rfloor\) 取同一值的区间合并处理。
如果当前左端点是 \(l\)，那么商 \(q=\lfloor M/l\rfloor\) 会一直保持不变，直到 \(r=\lfloor M/q\rfloor\)。整个区间的贡献为
$$q\sum_{d=l}^{r} d=q\cdot \frac{(l+r)(r-l+1)}{2}.$$
这种“按相同商分组”的常见技巧，把一次前缀查询从线性时间降到了大约 \(O(\sqrt M)\)。
实现先用普通因子的贡献 \(T(N)\) 初始化答案。随后枚举所有满足 \(a^2+b^2\le N\) 的整数对 \(a\ge 1\)、\(b\ge 1\)，并且只保留互素的那些。它们正是上面推导中的原始方向。
对于每个合法方向，程序先计算范数 \(a^2+b^2\)，再查询 \(T\!\left(\left\lfloor N/(a^2+b^2)\right\rfloor\right)\)，乘上 \(2a\)，最后加入累计答案。
许多不同的原始对会产生相同的商 \(\left\lfloor N/(a^2+b^2)\right\rfloor\)。C++ 和 Python 实现会缓存已经算出的约数前缀值，因此重复查询几乎可以直接返回。Java 实现没有加这一层缓存，而是直接按同一公式重新计算，但三种语言的数学累加完全一致。
主导步骤是枚举四分之一圆盘 \(a^2+b^2\le N\) 中的格点。由于半径是 \(\sqrt N\)，这个区域包含 \(O(N)\) 个整数点；互素筛选只会改变常数因子，不会改变数量级。
每个不同的前缀查询通过按商分组可以在大约 \(O(\sqrt M)\) 时间内完成。在带缓存的版本里，很多查询都能复用此前的结果，因为同一个商会反复出现。内存使用量为 \(O(U)\)，其中 \(U\) 是缓存的前缀值个数；除缓存之外，算法只需要常数级的循环状态。
真正的优势在于结构重排：算法从未尝试把 \(1\) 到 \(10^8\) 的每个整数都在 \(\mathbb{Z}[i]\) 中单独分解，而是改成了“全局扫描原始高斯方向 + 可控数量的约数求和查询”。
Пусть \(s(n)\) обозначает сумму гауссовых делителей, определенную в условии, и пусть
$$S(N)=\sum_{n=1}^{N} s(n),\qquad N=10^8.$$
Обычные положительные делители числа \(n\) сами являются гауссовыми делителями, чисто мнимые делители имеют действительную часть \(0\), а настоящие комплексные делители возникают попарно вместе со своими сопряжениями, так что мнимые части взаимно уничтожаются. Поэтому задача состоит не в том, чтобы факторизовать каждое \(n\) по отдельности в \(\mathbb{Z}[i]\), а в том, чтобы посчитать, сколько раз каждый возможный гауссов делитель встречается среди всех чисел до \(N\).
Именно эту идею и используют реализации на C++, Python и Java: сначала выделяют вклад обычных делителей, затем описывают каждый невещественный гауссов делитель через примитивное направление и целочисленный масштаб, а потом вычисляют итог при помощи быстрой сумматорной функции делителей.
Вся конструкция решения возникает из замены суммы по целым числам \(n\) на сумму по всем гауссовым делителям, которые вообще могут делить некоторое \(n\le N\).
Делители на вещественной оси - это в точности обычные положительные делители. Их суммарный вклад в \(S(N)\) равен
$$T(N)=\sum_{m=1}^{N}\sigma(m)=\sum_{d=1}^{N} d\left\lfloor\frac{N}{d}\right\rfloor,$$
потому что каждое положительное целое \(d\) делит ровно \(\lfloor N/d\rfloor\) чисел, не превосходящих \(N\). Это стандартная сумматорная функция делителей.
Чисто мнимые делители можно не выделять отдельно: их действительная часть равна нулю. Значит, дополнительную работу создают только те гауссовы делители, у которых ненулевые и действительная, и мнимая части.
Каждый невещественный гауссов делитель, который дает вклад в сумму, единственным образом записывается в виде
\(d(a+bi)\) или \(d(a-bi)\).
где \(d\ge 1\), \(a,b\ge 1\) и \(\gcd(a,b)=1\). Любой общий множитель действительной и мнимой части поглощается положительным целым коэффициентом \(d\), так что пара \((a,b)\) задает примитивное гауссово направление.
Для такого направления вводится норма
$$m=a^2+b^2.$$
Именно поэтому реализации перебирают только взаимно простые пары \((a,b)\): непримитивные пары просто дублировали бы делители, уже учтенные при большем значении \(d\).
Теперь зафиксируем примитивное направление \((a,b)\) и масштаб \(d\). Чтобы понять, когда \(d(a+bi)\) делит обычное целое число \(n\), умножим на сопряженное:
$$\frac{n}{d(a+bi)}=\frac{n(a-bi)}{d(a^2+b^2)}=\frac{n(a-bi)}{dm}.$$
Из условия \(\gcd(a,b)=1\) также следует \(\gcd(a,m)=\gcd(b,m)=1\). Поэтому действительная и мнимая части частного являются целыми тогда и только тогда, когда \(dm\mid n\).
Это и есть главная редукция. Делимость на гауссово число заменяется обычной проверкой делимости, зависящей только от масштаба \(d\) и примитивной нормы \(m=a^2+b^2\).
Для фиксированных \((a,b)\) и \(d\) сопряженная пара \(d(a+bi)\) и \(d(a-bi)\) имеет одну и ту же действительную часть \(da\). Значит, вместе они дают вклад \(2da\) для каждого целого \(n\), делящегося на \(dm\). Таких чисел до \(N\) ровно \(\left\lfloor N/(dm)\right\rfloor\).
Следовательно, вклад одного примитивного направления \((a,b)\) равен
$$\sum_{d\ge 1} 2da\left\lfloor\frac{N}{dm}\right\rfloor=2a\sum_{d\le N/m} d\left\lfloor\frac{N/m}{d}\right\rfloor=2a\,T\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
После добавления рациональной части получается точная формула, которую используют все реализации:
$$\boxed{S(N)=T(N)+\sum_{\substack{a,b\ge 1\\ \gcd(a,b)=1\\ a^2+b^2\le N}} 2a\,T\!\left(\left\lfloor\frac{N}{a^2+b^2}\right\rfloor\right).}$$
Условие \(a^2+b^2\le N\) естественно: если примитивная норма уже больше \(N\), то даже нерастянутый гауссов делитель не сможет делить ни одного числа, не превосходящего \(N\).
Пусть \(a=1\) и \(b=2\), тогда \(m=1^2+2^2=5\). При \(N=20\) соответствующие масштабированные делители таковы:
$$1\pm 2i,\quad 2\pm 4i,\quad 3\pm 6i,\quad 4\pm 8i,$$
потому что \(d\le N/m=4\). Пара \(d(1\pm 2i)\) делит в точности кратные \(5d\), а ее общий действительный вклад равен \(2d\cdot \lfloor 20/(5d)\rfloor\). Суммирование по \(d=1,2,3,4\) дает
$$2\bigl(1\cdot 4+2\cdot 2+3\cdot 1+4\cdot 1\bigr)=30.$$
Это в точности
$$2a\,T\!\left(\left\lfloor\frac{20}{5}\right\rfloor\right)=2\,T(4),$$
что наглядно показывает, как полный вклад одного примитивного направления сворачивается в один запрос к сумматорной функции делителей.
Первая арифметическая заготовка - это \(T(M)=\sum_{d\le M} d\lfloor M/d\rfloor\). Реализация не проходит все значения \(d\) по одному, а объединяет интервалы, на которых частное \(\lfloor M/d\rfloor\) постоянно.
Если текущая левая граница равна \(l\), то значение \(q=\lfloor M/l\rfloor\) не меняется до \(r=\lfloor M/q\rfloor\). Весь блок дает вклад
$$q\sum_{d=l}^{r} d=q\cdot \frac{(l+r)(r-l+1)}{2}.$$
Эта стандартная группировка по равным частным уменьшает стоимость одного префиксного запроса с линейной до примерно \(O(\sqrt M)\).
Сначала реализации инициализируют ответ обычным вкладом \(T(N)\). Затем перебираются все пары целых \(a\ge 1\), \(b\ge 1\), удовлетворяющие \(a^2+b^2\le N\), и остаются только взаимно простые пары. Именно они и являются примитивными направлениями из доказательства.
Для каждой допустимой пары вычисляется норма \(a^2+b^2\), затем запрашивается \(T\!\left(\left\lfloor N/(a^2+b^2)\right\rfloor\right)\), результат умножается на \(2a\) и добавляется к общей сумме.
Многие разные примитивные пары дают одно и то же значение \(\left\lfloor N/(a^2+b^2)\right\rfloor\). Варианты на C++ и Python сохраняют уже вычисленные префиксные значения и мгновенно отвечают на повторные запросы. Версия на Java применяет ту же формулу напрямую, без слоя мемоизации, но математическое накопление во всех трех языках одинаково.
Главный проход - это перебор точек решетки в четверти диска \(a^2+b^2\le N\). Поскольку радиус равен \(\sqrt N\), в этой области находится \(O(N)\) целочисленных пар; проверка взаимной простоты меняет только константу.
Каждый различный префиксный запрос вычисляется примерно за \(O(\sqrt M)\) благодаря группировке по равным частным. В мемоизированных вариантах многие вызовы переиспользуют старый результат, потому что один и тот же частный встречается много раз. Память составляет \(O(U)\), где \(U\) - число сохраненных префиксных значений; кроме этого, алгоритму нужен лишь константный дополнительный циклевой контекст.
Качественное преимущество здесь важнее формального порядка: решение ни разу не пытается факторизовать все числа до \(10^8\) в \(\mathbb{Z}[i]\) по одному, а заменяет это одним глобальным перебором примитивных гауссовых направлений и умеренным числом запросов к сумматорной функции делителей.
لتكن \(s(n)\) هي دالة مجموع القواسم الغاوسية كما عرّفتها المسألة، ولنكتب
$$S(N)=\sum_{n=1}^{N} s(n),\qquad N=10^8.$$
القواسم الصحيحة الموجبة المعتادة هي أيضًا قواسم غاوسية، والقواسم التخيلية الصرفة جزءها الحقيقي يساوي \(0\)، أما القواسم الغاوسية غير الحقيقية فتظهر في أزواج مترافقة فتُلغى الأجزاء التخيلية عند جمعها. لذلك فالمطلوب ليس تحليل كل \(n\) على حدة داخل \(\mathbb{Z}[i]\)، بل إعادة ترتيب الجمع بحيث نعدّ كم مرة يظهر كل قاسم غاوسي ممكن بين جميع الأعداد حتى \(N\).
هذا بالضبط ما تفعله تطبيقات C++ وPython وJava: تعزل أولًا مساهمة القواسم الصحيحة المعتادة، ثم تصف كل قاسم غاوسي غير حقيقي بواسطة اتجاه بدائي ومقياس صحيح، وبعد ذلك تحسب المجموع بواسطة روتين سريع لدالة مجموع القواسم التراكمية.
جوهر الحل كله هو تحويل المجموع على الأعداد \(n\) إلى مجموع على جميع القواسم الغاوسية التي يمكنها أصلًا أن تقسم عددًا ما لا يتجاوز \(N\).
القواسم الواقعة على المحور الحقيقي هي بالضبط القواسم الصحيحة الموجبة المعتادة. ومساهمتها الكلية في \(S(N)\) تساوي
$$T(N)=\sum_{m=1}^{N}\sigma(m)=\sum_{d=1}^{N} d\left\lfloor\frac{N}{d}\right\rfloor,$$
لأن كل عدد صحيح موجب \(d\) يقسم بالضبط \(\lfloor N/d\rfloor\) عددًا من الأعداد حتى \(N\). وهذه هي دالة مجموع القواسم التراكمية المعروفة.
أما القواسم التخيلية الصرفة فلا تحتاج إلى معالجة منفصلة، لأن جزأها الحقيقي يساوي صفرًا. وهكذا لا يبقى إلا القواسم الغاوسية التي لها جزء حقيقي وجزء تخيلي غير صفريين معًا.
كل قاسم غاوسي غير حقيقي يساهم في المجموع يمكن كتابته بصورة وحيدة على الشكل
\(d(a+bi)\) أو \(d(a-bi)\).
حيث \(d\ge 1\)، و\(a,b\ge 1\)، و\(\gcd(a,b)=1\). أي عامل مشترك بين الجزأين الحقيقي والتخيلي يُسحب إلى المضاعف الصحيح الموجب \(d\)، فتصف الزوجية \((a,b)\) اتجاهًا غاوسيًا بدائيًا.
ولذلك الاتجاه البدائي نعرّف المعيار
$$m=a^2+b^2.$$
وهذا يفسر مباشرة لماذا تعدّ التطبيقات فقط الأزواج المتباينة نسبيًا \((a,b)\): الأزواج غير البدائية لا تضيف شيئًا جديدًا، بل تكرر قواسم سبق عدّها عند قيمة أكبر لـ \(d\).
لنثبت الآن اتجاهًا بدائيًا \((a,b)\) ومقياسًا \(d\). لمعرفة متى يكون \(d(a+bi)\) قاسمًا لعدد صحيح عادي \(n\)، نضرب في المترافق:
$$\frac{n}{d(a+bi)}=\frac{n(a-bi)}{d(a^2+b^2)}=\frac{n(a-bi)}{dm}.$$
وبما أن \(\gcd(a,b)=1\)، فإن \(\gcd(a,m)=\gcd(b,m)=1\) أيضًا. لذلك يكون الجزآن الحقيقي والتخيلي لهذا الناتج عددين صحيحين إذا وفقط إذا كان \(dm\mid n\).
هذه هي نقطة التبسيط الحاسمة. فشرط القسمة على عدد غاوسي يتحول بالكامل إلى شرط قسمة صحيح عادي يعتمد فقط على المقياس \(d\) وعلى المعيار البدائي \(m=a^2+b^2\).
بالنسبة إلى \((a,b)\) و\(d\) ثابتين، فإن الزوج المترافق \(d(a+bi)\) و\(d(a-bi)\) يملك الجزء الحقيقي نفسه وهو \(da\). لذلك فهما معًا يضيفان مقدار \(2da\) إلى كل عدد صحيح \(n\) يقبل القسمة على \(dm\). وعدد هذه الأعداد حتى \(N\) هو بالضبط \(\left\lfloor N/(dm)\right\rfloor\).
ومن ثم فإن مساهمة اتجاه بدائي واحد \((a,b)\) تساوي
$$\sum_{d\ge 1} 2da\left\lfloor\frac{N}{dm}\right\rfloor=2a\sum_{d\le N/m} d\left\lfloor\frac{N/m}{d}\right\rfloor=2a\,T\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
وبإضافة الجزء العقلاني نحصل على الصيغة الدقيقة التي تستعملها التطبيقات كلها:
$$\boxed{S(N)=T(N)+\sum_{\substack{a,b\ge 1\\ \gcd(a,b)=1\\ a^2+b^2\le N}} 2a\,T\!\left(\left\lfloor\frac{N}{a^2+b^2}\right\rfloor\right).}$$
والشرط \(a^2+b^2\le N\) طبيعي جدًا، لأنه إذا تجاوز المعيار البدائي \(N\) فلن يستطيع حتى القاسم غير المضروب في \(d\) أن يقسم أي عدد لا يتجاوز \(N\).
خذ \(a=1\) و\(b=2\)، فيكون \(m=1^2+2^2=5\). إذا كان \(N=20\)، فإن القواسم المضروبة ذات الصلة هي
$$1\pm 2i,\quad 2\pm 4i,\quad 3\pm 6i,\quad 4\pm 8i,$$
لأن \(d\le N/m=4\). والزوج \(d(1\pm 2i)\) يقسم بالضبط مضاعفات \(5d\)، ولذلك تكون مساهمته الحقيقية الكلية \(2d\cdot \lfloor 20/(5d)\rfloor\). وبالجمع على \(d=1,2,3,4\) نحصل على
$$2\bigl(1\cdot 4+2\cdot 2+3\cdot 1+4\cdot 1\bigr)=30.$$
وهذا يساوي تمامًا
$$2a\,T\!\left(\left\lfloor\frac{20}{5}\right\rfloor\right)=2\,T(4),$$
وهو مثال صغير يوضح كيف تنضغط مساهمة اتجاه بدائي كامل إلى استعلام واحد فقط عن دالة مجموع القواسم التراكمية.
أول لبنة حسابية هي \(T(M)=\sum_{d\le M} d\lfloor M/d\rfloor\). لا تمرّ الشيفرة على كل قيمة \(d\) على حدة، بل تجمع المقاطع التي يبقى فيها خارج القسمة \(\lfloor M/d\rfloor\) ثابتًا.
إذا كانت البداية الحالية للمقطع هي \(l\)، فإن \(q=\lfloor M/l\rfloor\) يبقى ثابتًا حتى \(r=\lfloor M/q\rfloor\). وتكون مساهمة هذا المقطع كله
$$q\sum_{d=l}^{r} d=q\cdot \frac{(l+r)(r-l+1)}{2}.$$
هذه الحيلة القياسية، أي التجميع بحسب القيم المتساوية للخارج، تخفض كلفة الاستعلام الواحد من زمن خطي إلى ما يقارب \(O(\sqrt M)\).
تبدأ التطبيقات الجواب بمساهمة القواسم العادية \(T(N)\). بعد ذلك تُعدّ جميع الأزواج الصحيحة \(a\ge 1\)، \(b\ge 1\) التي تحقق \(a^2+b^2\le N\)، ثم يُحتفَظ فقط بالأزواج المتباينة نسبيًا. هذه هي بالضبط الاتجاهات البدائية التي ظهرت في الاشتقاق.
لكل زوج صالح، يُحسب المعيار \(a^2+b^2\)، ثم تُستخرَج القيمة \(T\!\left(\left\lfloor N/(a^2+b^2)\right\rfloor\right)\)، وتُضرَب في \(2a\)، ثم تُضاف إلى المجموع الجاري.
كثير من الأزواج البدائية المختلفة تعطي نفس القيمة \(\left\lfloor N/(a^2+b^2)\right\rfloor\). تطبيقا C++ وPython يخزّنان قيم البادئة التي حُسبت مسبقًا، فتُجاب الاستعلامات المكررة فورًا. أما تطبيق Java فيستعمل الصيغة نفسها مباشرة من غير طبقة التخزين هذه، لكن المجموع الرياضي نفسه لا يتغير بين اللغات الثلاث.
المرحلة المهيمنة هي تعداد نقاط الشبكة داخل ربع القرص \(a^2+b^2\le N\). وبما أن نصف القطر هو \(\sqrt N\)، فإن هذه المنطقة تحتوي على \(O(N)\) زوج من الأعداد الصحيحة؛ وفحص التباين النسبي لا يغيّر إلا العامل الثابت.
كل استعلام مختلف عن دالة البادئة يُحسب في نحو \(O(\sqrt M)\) بفضل التجميع بحسب الخارج المتساوي. وفي النسخ التي تستخدم التخزين المؤقت، يُعاد استعمال كثير من النتائج لأن القيمة نفسها تتكرر مرات كثيرة. استهلاك الذاكرة هو \(O(U)\) حيث \(U\) عدد القيم المخزنة؛ وبخلاف هذا التخزين لا تحتاج الخوارزمية إلا إلى حالة حلقات ثابتة الحجم.
المكسب الحقيقي هنا بنيوي: الحل لا يحاول أبدًا تحليل جميع الأعداد حتى \(10^8\) داخل \(\mathbb{Z}[i]\) واحدًا واحدًا، بل يستبدل ذلك بمسح عالمي للاتجاهات الغاوسية البدائية وعدد قابل للإدارة من استعلامات مجموع القواسم.