The geometry of the incenter and circumcenter can be reduced to a primitive arithmetic parameterization. After that reduction, the quantity computed by the implementations is
$$F(L)=\sum_{\substack{1\le r<s<2r\\ \gcd(r,s)=1\\ t\ge 1,\ rst\le L}} rst.$$
Here \((r,s)\) describes a primitive configuration and \(t\) is the scaling factor. A direct scan over all admissible triples \((r,s,t)\) is too slow for \(L=10^9\), so the solution turns the sum into divisor-based range queries and batches equal floor values.
The arithmetic form above is the key step. Once the geometry has been compressed into coprime integer parameters, the rest of the problem becomes a careful summation problem in elementary number theory.
The reduced parameterization gives the conditions
$$1\le r,\qquad r+1\le s\le 2r-1,\qquad \gcd(r,s)=1,\qquad rst\le L.$$
For fixed \(r\) and \(s\), the scaling factor \(t\) can range from \(1\) up to \(\left\lfloor L/(rs)\right\rfloor\). Also, if \(r>\sqrt{L}\), then even the smallest allowed value \(s=r+1\) gives \(rs>r^2>L\), so no triple can contribute. Therefore the outer loop only needs
$$1\le r\le R=\left\lfloor\sqrt{L}\right\rfloor.$$
For each such \(r\), the valid interval for \(s\) is
$$r+1\le s\le U_r=\min\!\left(2r-1,\left\lfloor\frac{L}{r}\right\rfloor\right).$$
For one fixed coprime pair \((r,s)\), the total contribution of all admissible scales is
$$\sum_{t=1}^{\lfloor L/(rs)\rfloor} rst=rs\sum_{t=1}^{\lfloor L/(rs)\rfloor} t.$$
Introduce the triangular-number function
$$T(n)=\frac{n(n+1)}{2}.$$
Then the whole problem becomes
$$F(L)=\sum_{r=1}^{R} r\sum_{\substack{r+1\le s\le U_r\\ \gcd(r,s)=1}} s\,T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
This is already a major simplification: the implementations never iterate over \(t\) explicitly.
For a fixed \(r\), define the weighted coprime prefix sum
$$C_r(x)=\sum_{\substack{1\le s\le x\\ \gcd(r,s)=1}} s.$$
Using the standard identity
$$\mathbf{1}_{\gcd(r,s)=1}=\sum_{d\mid \gcd(r,s)} \mu(d),$$
we obtain
$$\begin{aligned} C_r(x) &=\sum_{1\le s\le x} s\sum_{d\mid \gcd(r,s)}\mu(d)\\ &=\sum_{d\mid r}\mu(d)\sum_{\substack{1\le s\le x\\ d\mid s}} s\\ &=\sum_{d\mid r}\mu(d)\,d\,T\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right). \end{aligned}$$
Only squarefree divisors matter, because \(\mu(d)=0\) for every non-squarefree \(d\). This is why the implementations precompute, for each \(r\), the squarefree divisors together with their Möbius signs.
Once \(C_r(x)\) is available, any weighted coprime range sum follows immediately:
$$\sum_{\substack{a\le s\le b\\ \gcd(r,s)=1}} s=C_r(b)-C_r(a-1).$$
So the remaining challenge is not coprimality anymore. It is the changing floor value inside
$$T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
Fix \(r\) and suppose the current left endpoint in the \(s\)-interval is \(a\). Set
$$m=\left\lfloor\frac{L}{ra}\right\rfloor.$$
As \(s\) increases, the quantity \(\left\lfloor L/(rs)\right\rfloor\) stays equal to \(m\) on the whole block
$$a\le s\le b=\min\!\left(U_r,\left\lfloor\frac{L}{rm}\right\rfloor\right).$$
Therefore that entire block contributes
$$r\,T(m)\left(C_r(b)-C_r(a-1)\right).$$
Then the next block starts at \(b+1\). This is the same floor-grouping principle used in hyperbola-style divisor summation: one maximal interval replaces many identical floor evaluations.
Here
$$R=\left\lfloor\sqrt{15}\right\rfloor=3.$$
For \(r=1\), the interval \(r+1\le s\le U_r\) is empty, so there is no contribution.
For \(r=2\), the only admissible value is \(s=3\), and \(\gcd(2,3)=1\). Then
$$\left\lfloor\frac{15}{2\cdot 3}\right\rfloor=2,$$
so the contribution is
$$2\cdot 3\cdot T(2)=6\cdot 3=18.$$
For \(r=3\), the admissible values are \(s=4\) and \(s=5\). Both are coprime to \(3\), and both satisfy
$$\left\lfloor\frac{15}{3s}\right\rfloor=1.$$
Hence their contributions are
$$3\cdot 4\cdot T(1)=12,\qquad 3\cdot 5\cdot T(1)=15.$$
Adding everything gives
$$18+12+15=45,$$
which matches the checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same structure. They first compute \(R=\lfloor\sqrt{L}\rfloor\), because no larger \(r\) can appear. Next they build a smallest-prime-factor sieve up to \(R\), which lets them factor every \(r\) quickly.
From those factorizations they generate, for each \(r\), the list of squarefree divisors and the corresponding Möbius sign. A coprime prefix query \(C_r(x)\) is then evaluated by summing \(d\,T(\lfloor x/d\rfloor)\) over that divisor list with the correct sign.
The main loop runs over \(r\). For each \(r\), it scans the valid \(s\)-interval in maximal blocks on which \(\left\lfloor L/(rs)\right\rfloor\) is constant. On each block, the implementation asks for one coprime interval sum, multiplies it by \(r\) and the corresponding triangular number, and adds the result to the total.
The numeric types are chosen to avoid overflow: the Python version uses arbitrary-precision integers automatically, the Java version uses big integers for the accumulated total, and the C++ version uses 128-bit arithmetic for the same reason.
Let \(R=\lfloor\sqrt{L}\rfloor\). The smallest-prime-factor sieve costs \(O(R\log\log R)\) time and \(O(R)\) memory. Building the squarefree-divisor tables costs additional work proportional to the total number of stored squarefree divisors, namely
$$O\!\left(\sum_{r\le R} 2^{\omega(r)}\right),$$
where \(\omega(r)\) is the number of distinct prime factors of \(r\).
During the main summation, each floor-constant block for a given \(r\) needs two coprime prefix evaluations, and each such evaluation iterates over the same squarefree-divisor list. If \(B(r)\) denotes the number of blocks for that \(r\), then the main-loop cost is
$$O\!\left(\sum_{r\le R} B(r)\,2^{\omega(r)}\right).$$
This is far smaller in practice than iterating over every admissible triple \((r,s,t)\), because the \(t\)-sum has been collapsed into a triangular number and the \(s\)-loop is processed in batches rather than one value at a time.
Die Geometrie von Inkreismittelpunkt und Umkreismittelpunkt wird in der Lösung auf eine primitive arithmetische Parametrisierung zurückgeführt. Nach dieser Reduktion berechnen die Implementierungen die Größe
$$F(L)=\sum_{\substack{1\le r<s<2r\\ \gcd(r,s)=1\\ t\ge 1,\ rst\le L}} rst.$$
Dabei beschreibt \((r,s)\) eine primitive Konfiguration und \(t\) den Skalierungsfaktor. Eine direkte Enumeration aller zulässigen Tripel \((r,s,t)\) wäre für \(L=10^9\) viel zu langsam; deshalb formt die Lösung die Summe in Bereichsabfragen über Teiler und konstante Floor-Blöcke um.
Sobald die Geometrie in koprime Ganzzahlparameter übersetzt ist, bleibt ein reines Summationsproblem aus der elementaren Zahlentheorie übrig. Genau diese Umformung treibt den gesamten Algorithmus.
Aus der reduzierten Parametrisierung folgen die Bedingungen
$$1\le r,\qquad r+1\le s\le 2r-1,\qquad \gcd(r,s)=1,\qquad rst\le L.$$
Für feste \(r\) und \(s\) läuft der Skalierungsparameter \(t\) von \(1\) bis \(\left\lfloor L/(rs)\right\rfloor\). Außerdem gilt: Wenn \(r>\sqrt{L}\), dann liefert schon der kleinste zulässige Wert \(s=r+1\) die Ungleichung \(rs>r^2>L\); dann kann also kein Beitrag mehr auftreten. Deshalb genügt für die äußere Schleife
$$1\le r\le R=\left\lfloor\sqrt{L}\right\rfloor.$$
Für jedes solche \(r\) ist das gültige Intervall für \(s\)
$$r+1\le s\le U_r=\min\!\left(2r-1,\left\lfloor\frac{L}{r}\right\rfloor\right).$$
Für ein festes koprimes Paar \((r,s)\) ist der Gesamtbeitrag aller zulässigen Skalierungen
$$\sum_{t=1}^{\lfloor L/(rs)\rfloor} rst=rs\sum_{t=1}^{\lfloor L/(rs)\rfloor} t.$$
Wir führen die Dreieckszahlfunktion ein:
$$T(n)=\frac{n(n+1)}{2}.$$
Damit wird das gesamte Problem zu
$$F(L)=\sum_{r=1}^{R} r\sum_{\substack{r+1\le s\le U_r\\ \gcd(r,s)=1}} s\,T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
Das ist bereits eine entscheidende Vereinfachung: Die Implementierungen iterieren nie explizit über \(t\).
Für festes \(r\) definieren wir die gewichtete koprime Präfixsumme
$$C_r(x)=\sum_{\substack{1\le s\le x\\ \gcd(r,s)=1}} s.$$
Mit der Identität
$$\mathbf{1}_{\gcd(r,s)=1}=\sum_{d\mid \gcd(r,s)} \mu(d).$$
erhält man
$$\begin{aligned} C_r(x) &=\sum_{1\le s\le x} s\sum_{d\mid \gcd(r,s)}\mu(d)\\ &=\sum_{d\mid r}\mu(d)\sum_{\substack{1\le s\le x\\ d\mid s}} s\\ &=\sum_{d\mid r}\mu(d)\,d\,T\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right). \end{aligned}$$
Nur quadratfreie Teiler tragen etwas bei, denn für jeden nicht quadratfreien Teiler gilt \(\mu(d)=0\). Genau deshalb speichern die Implementierungen zu jedem \(r\) die quadratfreien Teiler zusammen mit ihrem Möbius-Vorzeichen vorab.
Sobald \(C_r(x)\) verfügbar ist, folgt jede gewichtete koprime Bereichssumme sofort:
$$\sum_{\substack{a\le s\le b\\ \gcd(r,s)=1}} s=C_r(b)-C_r(a-1).$$
Damit ist die Koprimalitätsbedingung erledigt. Übrig bleibt nur noch der wechselnde Floor-Ausdruck in
$$T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
Fixiere \(r\) und sei \(a\) der aktuelle linke Rand im \(s\)-Intervall. Setze
$$m=\left\lfloor\frac{L}{ra}\right\rfloor.$$
Wenn \(s\) wächst, bleibt \(\left\lfloor L/(rs)\right\rfloor\) auf dem gesamten Block
$$a\le s\le b=\min\!\left(U_r,\left\lfloor\frac{L}{rm}\right\rfloor\right).$$
konstant gleich \(m\). Der ganze Block trägt also
$$r\,T(m)\left(C_r(b)-C_r(a-1)\right).$$
bei. Danach beginnt der nächste Block bei \(b+1\). Das ist dieselbe Floor-Gruppierung, die man aus hyperbelartigen Teilersummen kennt: Ein maximales Intervall ersetzt viele identische Floor-Auswertungen.
Hier ist
$$R=\left\lfloor\sqrt{15}\right\rfloor=3.$$
Für \(r=1\) ist das Intervall \(r+1\le s\le U_r\) leer, also gibt es keinen Beitrag.
Für \(r=2\) ist nur \(s=3\) zulässig, und \(\gcd(2,3)=1\). Dann gilt
$$\left\lfloor\frac{15}{2\cdot 3}\right\rfloor=2,$$
also ist der Beitrag
$$2\cdot 3\cdot T(2)=6\cdot 3=18.$$
Für \(r=3\) sind die zulässigen Werte \(s=4\) und \(s=5\). Beide sind zu \(3\) teilerfremd und beide erfüllen
$$\left\lfloor\frac{15}{3s}\right\rfloor=1.$$
Ihre Beiträge lauten daher
$$3\cdot 4\cdot T(1)=12,\qquad 3\cdot 5\cdot T(1)=15.$$
Insgesamt ergibt sich
$$18+12+15=45,$$
genau der Kontrollwert aus den Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst berechnen sie \(R=\lfloor\sqrt{L}\rfloor\), weil kein größeres \(r\) auftreten kann. Danach wird ein Sieb der kleinsten Primteiler bis \(R\) aufgebaut, sodass sich jedes \(r\) schnell faktorisieren lässt.
Aus diesen Faktorisierungen wird für jedes \(r\) die Liste der quadratfreien Teiler zusammen mit dem passenden Möbius-Vorzeichen erzeugt. Eine koprime Präfixabfrage \(C_r(x)\) wird dann als Summe von \(d\,T(\lfloor x/d\rfloor)\) über genau diese Teilerliste mit korrektem Vorzeichen ausgewertet.
Die Hauptschleife läuft über \(r\). Für jedes \(r\) wird das gültige \(s\)-Intervall in maximale Blöcke zerlegt, auf denen \(\left\lfloor L/(rs)\right\rfloor\) konstant ist. Pro Block braucht die Implementierung nur eine koprime Intervallsumme, multipliziert sie mit \(r\) und der zugehörigen Dreieckszahl und addiert alles zum Gesamtergebnis.
Die Zahlentypen sind so gewählt, dass kein Überlauf entsteht: Python verwendet automatisch Ganzzahlen beliebiger Größe, Java nutzt große Ganzzahlen für die aufsummierte Antwort, und C++ verwendet 128-Bit-Arithmetik aus demselben Grund.
Sei \(R=\lfloor\sqrt{L}\rfloor\). Das Sieb der kleinsten Primteiler benötigt \(O(R\log\log R)\) Zeit und \(O(R)\) Speicher. Der Aufbau der Tabellen quadratfreier Teiler kostet zusätzliche Arbeit proportional zur Gesamtzahl dieser gespeicherten Teiler, also
$$O\!\left(\sum_{r\le R} 2^{\omega(r)}\right),$$
wobei \(\omega(r)\) die Anzahl verschiedener Primfaktoren von \(r\) bezeichnet.
In der Hauptsumme braucht jeder Floor-konstante Block für ein festes \(r\) zwei koprime Präfixabfragen, und jede dieser Abfragen läuft über dieselbe quadratfreie Teilerliste. Bezeichnet \(B(r)\) die Anzahl solcher Blöcke für dieses \(r\), so ist der Aufwand der Hauptschleife
$$O\!\left(\sum_{r\le R} B(r)\,2^{\omega(r)}\right).$$
Das ist in der Praxis deutlich kleiner als die Iteration über alle zulässigen Tripel \((r,s,t)\), weil die \(t\)-Summe bereits zu einer Dreieckszahl zusammengezogen wurde und die \(s\)-Werte blockweise statt einzeln verarbeitet werden.
İçmerkez ve çevrel merkez geometrisi çözümde ilkel bir aritmetik parametrelemeye indirgenir. Bu indirgeme yapıldıktan sonra uygulamaların hesapladığı büyüklük
$$F(L)=\sum_{\substack{1\le r<s<2r\\ \gcd(r,s)=1\\ t\ge 1,\ rst\le L}} rst.$$
şeklindedir. Burada \((r,s)\) ilkel bir konfigürasyonu, \(t\) ise ölçekleme katsayısını temsil eder. \(L=10^9\) için tüm uygun \((r,s,t)\) üçlülerini doğrudan gezmek çok pahalı olacağından çözüm, toplamı bölen tabanlı aralık sorgularına ve aynı floor değerlerini birlikte işleyen bloklara dönüştürür.
Geometri, aralarında asal tamsayı parametrelere sıkıştırıldıktan sonra geriye saf bir sayı teorisi toplamı kalır. Çözümün bütün gücü bu aritmetik yeniden yazımdan gelir.
İndirgenmiş parametreleme şu koşulları verir:
$$1\le r,\qquad r+1\le s\le 2r-1,\qquad \gcd(r,s)=1,\qquad rst\le L.$$
Sabit \(r\) ve \(s\) için ölçekleme parametresi \(t\), \(1\) ile \(\left\lfloor L/(rs)\right\rfloor\) arasında değişir. Ayrıca \(r>\sqrt{L}\) ise en küçük izinli değer olan \(s=r+1\) bile \(rs>r^2>L\) verir; dolayısıyla katkı gelmez. Bu yüzden dış döngü sadece
$$1\le r\le R=\left\lfloor\sqrt{L}\right\rfloor.$$
aralığında çalışır. Her böyle \(r\) için geçerli \(s\) aralığı
$$r+1\le s\le U_r=\min\!\left(2r-1,\left\lfloor\frac{L}{r}\right\rfloor\right).$$
olur.
Sabit bir aralarında asal \((r,s)\) çifti için tüm ölçeklerin toplam katkısı
$$\sum_{t=1}^{\lfloor L/(rs)\rfloor} rst=rs\sum_{t=1}^{\lfloor L/(rs)\rfloor} t.$$
şeklindedir. Şimdi üçgensel sayı fonksiyonunu tanımlayalım:
$$T(n)=\frac{n(n+1)}{2}.$$
Böylece tüm problem
$$F(L)=\sum_{r=1}^{R} r\sum_{\substack{r+1\le s\le U_r\\ \gcd(r,s)=1}} s\,T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
biçimine iner. Bu büyük bir sadeleşmedir; uygulamalar \(t\) üzerinden hiç açık döngü kurmaz.
Sabit \(r\) için ağırlıklı aralarında asal önek toplamını
$$C_r(x)=\sum_{\substack{1\le s\le x\\ \gcd(r,s)=1}} s.$$
olarak tanımlayalım. Standart özdeşlik
$$\mathbf{1}_{\gcd(r,s)=1}=\sum_{d\mid \gcd(r,s)} \mu(d).$$
kullanılırsa
$$\begin{aligned} C_r(x) &=\sum_{1\le s\le x} s\sum_{d\mid \gcd(r,s)}\mu(d)\\ &=\sum_{d\mid r}\mu(d)\sum_{\substack{1\le s\le x\\ d\mid s}} s\\ &=\sum_{d\mid r}\mu(d)\,d\,T\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right). \end{aligned}$$
elde edilir. Kareden arınmış olmayan bölenler katkı yapmaz; çünkü onlar için \(\mu(d)=0\) olur. Bu yüzden uygulamalar her \(r\) için kareden arınmış bölenleri ve ilgili Möbius işaretlerini önceden çıkarır.
\(C_r(x)\) bilindiğinde herhangi bir ağırlıklı aralarında asal aralık toplamı hemen bulunur:
$$\sum_{\substack{a\le s\le b\\ \gcd(r,s)=1}} s=C_r(b)-C_r(a-1).$$
Böylece aralarında asallık engeli ortadan kalkar. Geriye sadece
$$T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
ifadesindeki değişen floor değeri kalır.
\(r\) sabit olsun ve \(s\) aralığındaki mevcut sol uç \(a\) olsun. Şunu tanımlayalım:
$$m=\left\lfloor\frac{L}{ra}\right\rfloor.$$
\(s\) arttıkça \(\left\lfloor L/(rs)\right\rfloor\) değeri
$$a\le s\le b=\min\!\left(U_r,\left\lfloor\frac{L}{rm}\right\rfloor\right).$$
bloğunun tamamında sabit olarak \(m\) kalır. O halde bu bloğun toplam katkısı
$$r\,T(m)\left(C_r(b)-C_r(a-1)\right).$$
olur. Sonraki blok \(b+1\)'den başlar. Bu, hiperbollü bölen toplamlarında görülen floor-gruplama fikrinin aynısıdır: aynı değeri veren çok sayıda nokta yerine tek bir maksimum aralık işlenir.
Burada
$$R=\left\lfloor\sqrt{15}\right\rfloor=3.$$
olur. \(r=1\) için \(r+1\le s\le U_r\) aralığı boştur; katkı yoktur.
\(r=2\) için tek uygun değer \(s=3\)'tür ve \(\gcd(2,3)=1\). Bu durumda
$$\left\lfloor\frac{15}{2\cdot 3}\right\rfloor=2.$$
olduğu için katkı
$$2\cdot 3\cdot T(2)=6\cdot 3=18.$$
çıkar. \(r=3\) için uygun değerler \(s=4\) ve \(s=5\)'tir. Her ikisi de \(3\) ile aralarında asaldır ve her ikisi için de
$$\left\lfloor\frac{15}{3s}\right\rfloor=1.$$
geçerlidir. Dolayısıyla katkılar
$$3\cdot 4\cdot T(1)=12,\qquad 3\cdot 5\cdot T(1)=15.$$
olur. Toplam
$$18+12+15=45.$$
çıkar; bu da uygulamalardaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı iskeleti izler. Önce \(R=\lfloor\sqrt{L}\rfloor\) hesaplanır; çünkü bundan büyük hiçbir \(r\) katkı veremez. Sonra \(R\)'ye kadar en küçük asal bölen süzgeci kurulur ve böylece her \(r\) hızlıca asal çarpanlarına ayrılır.
Bu ayrışımlardan hareketle her \(r\) için kareden arınmış bölenler listesi ve bunların Möbius işaretleri üretilir. Bir önek sorgusu \(C_r(x)\), doğru işaretlerle ağırlıklandırılmış \(d\,T(\lfloor x/d\rfloor)\) terimlerinin toplamı olarak değerlendirilir.
Ana döngü \(r\) üzerinde ilerler. Her \(r\) için geçerli \(s\) aralığı, \(\left\lfloor L/(rs)\right\rfloor\) değerinin sabit kaldığı en büyük bloklara ayrılır. Her blokta uygulama bir aralarında asal aralık toplamı hesaplar, bunu \(r\) ve uygun üçgensel sayı ile çarpar, sonra da genel sonuca ekler.
Sayı türleri taşmayı önleyecek şekilde seçilmiştir: Python sürümü doğal olarak keyfi büyüklükte tamsayılar kullanır, Java sürümü birikimli sonuç için büyük tamsayılar kullanır, C++ sürümü ise aynı sebeple 128 bit aritmetik kullanır.
\(R=\lfloor\sqrt{L}\rfloor\) olsun. En küçük asal bölen süzgeci \(O(R\log\log R)\) zaman ve \(O(R)\) bellek kullanır. Kareden arınmış bölen tablolarını oluşturmanın ek maliyeti, depolanan toplam kareden arınmış bölen sayısıyla orantılıdır:
$$O\!\left(\sum_{r\le R} 2^{\omega(r)}\right),$$
burada \(\omega(r)\), \(r\)'nin farklı asal çarpan sayısıdır.
Ana toplam sırasında sabit bir \(r\) için her floor-sabit blok iki önek sorgusu gerektirir ve bu sorgular aynı kareden arınmış bölen listesi üzerinden dolaşır. Eğer \(B(r)\), bu \(r\) için blok sayısıysa ana döngünün maliyeti
$$O\!\left(\sum_{r\le R} B(r)\,2^{\omega(r)}\right).$$
olur. Bu, pratikte tüm uygun \((r,s,t)\) üçlülerini gezmekten çok daha küçüktür; çünkü \(t\) toplamı üçgensel sayıya indirgenmiştir ve \(s\) değerleri tek tek değil bloklar halinde işlenir.
La geometría del incentro y del circuncentro se reduce en la solución a una parametrización aritmética primitiva. Después de esa reducción, la cantidad que calculan las implementaciones es
$$F(L)=\sum_{\substack{1\le r<s<2r\\ \gcd(r,s)=1\\ t\ge 1,\ rst\le L}} rst.$$
Aquí \((r,s)\) describe una configuración primitiva y \(t\) es el factor de escala. Recorrer directamente todos los ternas admisibles \((r,s,t)\) sería demasiado lento para \(L=10^9\), así que la solución reorganiza la suma en consultas por divisores y bloques donde el valor del piso permanece constante.
Una vez que la parte geométrica se ha comprimido en parámetros enteros coprimos, el problema pasa a ser una suma de teoría de números elemental. Toda la aceleración viene de explotar bien esa forma aritmética.
La parametrización reducida impone
$$1\le r,\qquad r+1\le s\le 2r-1,\qquad \gcd(r,s)=1,\qquad rst\le L.$$
Para \(r\) y \(s\) fijos, el factor de escala \(t\) puede tomar valores desde \(1\) hasta \(\left\lfloor L/(rs)\right\rfloor\). Además, si \(r>\sqrt{L}\), incluso el menor valor permitido \(s=r+1\) produce \(rs>r^2>L\), de modo que ya no puede haber contribución. Por eso el bucle exterior solo necesita
$$1\le r\le R=\left\lfloor\sqrt{L}\right\rfloor.$$
Para cada uno de esos \(r\), el intervalo válido para \(s\) es
$$r+1\le s\le U_r=\min\!\left(2r-1,\left\lfloor\frac{L}{r}\right\rfloor\right).$$
Para un par coprimo fijo \((r,s)\), la contribución total de todas las escalas admisibles es
$$\sum_{t=1}^{\lfloor L/(rs)\rfloor} rst=rs\sum_{t=1}^{\lfloor L/(rs)\rfloor} t.$$
Introducimos la función triangular
$$T(n)=\frac{n(n+1)}{2}.$$
Entonces todo el problema se convierte en
$$F(L)=\sum_{r=1}^{R} r\sum_{\substack{r+1\le s\le U_r\\ \gcd(r,s)=1}} s\,T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
Esto ya supone una gran reducción: las implementaciones nunca iteran de forma explícita sobre \(t\).
Para un \(r\) fijo, definimos la suma prefijo ponderada
$$C_r(x)=\sum_{\substack{1\le s\le x\\ \gcd(r,s)=1}} s.$$
Usando la identidad
$$\mathbf{1}_{\gcd(r,s)=1}=\sum_{d\mid \gcd(r,s)} \mu(d),$$
se obtiene
$$\begin{aligned} C_r(x) &=\sum_{1\le s\le x} s\sum_{d\mid \gcd(r,s)}\mu(d)\\ &=\sum_{d\mid r}\mu(d)\sum_{\substack{1\le s\le x\\ d\mid s}} s\\ &=\sum_{d\mid r}\mu(d)\,d\,T\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right). \end{aligned}$$
Solo importan los divisores libres de cuadrados, porque \(\mu(d)=0\) para cualquier divisor que no lo sea. Por eso las implementaciones precalculan, para cada \(r\), la lista de divisores libres de cuadrados junto con su signo de Möbius.
Una vez conocida \(C_r(x)\), cualquier suma ponderada sobre un intervalo se obtiene como
$$\sum_{\substack{a\le s\le b\\ \gcd(r,s)=1}} s=C_r(b)-C_r(a-1).$$
Así, la condición de coprimalidad deja de ser el problema principal. Lo que queda por controlar es el valor cambiante del piso en
$$T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
Fijemos \(r\) y sea \(a\) el extremo izquierdo actual del intervalo de \(s\). Definimos
$$m=\left\lfloor\frac{L}{ra}\right\rfloor.$$
Al aumentar \(s\), la cantidad \(\left\lfloor L/(rs)\right\rfloor\) sigue siendo igual a \(m\) en todo el bloque
$$a\le s\le b=\min\!\left(U_r,\left\lfloor\frac{L}{rm}\right\rfloor\right).$$
Por tanto, el bloque completo aporta
$$r\,T(m)\left(C_r(b)-C_r(a-1)\right).$$
Luego el siguiente bloque empieza en \(b+1\). Esta es la misma idea de agrupación por valores constantes que aparece en el método hiperbólico de sumas sobre divisores: un intervalo máximo sustituye muchas evaluaciones idénticas del piso.
Aquí
$$R=\left\lfloor\sqrt{15}\right\rfloor=3.$$
Para \(r=1\), el intervalo \(r+1\le s\le U_r\) está vacío y no hay contribución.
Para \(r=2\), el único valor admisible es \(s=3\), con \(\gcd(2,3)=1\). Entonces
$$\left\lfloor\frac{15}{2\cdot 3}\right\rfloor=2,$$
de modo que la contribución es
$$2\cdot 3\cdot T(2)=6\cdot 3=18.$$
Para \(r=3\), los valores admisibles son \(s=4\) y \(s=5\). Ambos son coprimos con \(3\) y ambos cumplen
$$\left\lfloor\frac{15}{3s}\right\rfloor=1.$$
Sus contribuciones son
$$3\cdot 4\cdot T(1)=12,\qquad 3\cdot 5\cdot T(1)=15.$$
La suma total es
$$18+12+15=45,$$
exactamente el valor de comprobación usado por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma estructura. Primero calculan \(R=\lfloor\sqrt{L}\rfloor\), porque ningún \(r\) mayor puede contribuir. Después construyen una criba de menor factor primo hasta \(R\), lo que permite factorizar cada \(r\) con rapidez.
A partir de esas factorizaciones generan, para cada \(r\), la lista de divisores libres de cuadrados y el signo de Möbius correspondiente. Una consulta de prefijo \(C_r(x)\) se evalúa entonces sumando \(d\,T(\lfloor x/d\rfloor)\) sobre esa lista con el signo adecuado.
El bucle principal recorre \(r\). Para cada \(r\), el intervalo válido de \(s\) se procesa en bloques máximos donde \(\left\lfloor L/(rs)\right\rfloor\) permanece constante. En cada bloque, la implementación calcula una suma coprima por intervalo, la multiplica por \(r\) y por la cifra triangular adecuada, y añade el resultado al total.
Los tipos numéricos se eligen para evitar desbordamientos: Python usa enteros de precisión arbitraria de forma natural, Java usa enteros grandes para la suma acumulada y C++ usa aritmética de 128 bits con el mismo objetivo.
Sea \(R=\lfloor\sqrt{L}\rfloor\). La criba de menor factor primo cuesta \(O(R\log\log R)\) tiempo y \(O(R)\) memoria. Construir las tablas de divisores libres de cuadrados añade un trabajo proporcional al número total de esos divisores almacenados, es decir,
$$O\!\left(\sum_{r\le R} 2^{\omega(r)}\right),$$
donde \(\omega(r)\) es el número de factores primos distintos de \(r\).
Durante la suma principal, cada bloque de piso constante para un \(r\) fijo necesita dos evaluaciones de prefijo coprimo, y cada una de ellas recorre la misma lista de divisores libres de cuadrados. Si \(B(r)\) denota el número de bloques para ese \(r\), el coste del bucle principal es
$$O\!\left(\sum_{r\le R} B(r)\,2^{\omega(r)}\right).$$
En la práctica, esto es mucho menor que iterar sobre todas las ternas admisibles \((r,s,t)\), porque la suma sobre \(t\) ya se redujo a un número triangular y los valores de \(s\) se procesan por bloques en lugar de uno por uno.
题目中关于内心与外心的几何条件，在解法里先被压缩成一个原始的整数参数化。完成这一步之后，程序真正计算的是
$$F(L)=\sum_{\substack{1\le r<s<2r\\ \gcd(r,s)=1\\ t\ge 1,\ rst\le L}} rst.$$
这里 \((r,s)\) 表示一个原始构型，\(t\) 表示缩放因子。若对所有可行三元组 \((r,s,t)\) 直接暴力枚举，在 \(L=10^9\) 时会非常慢，所以实现把它改写成“按除数求前缀和，再按相同 floor 值分块”的数论求和问题。
一旦几何部分已经被翻译成互素整数参数，剩下的就是一个纯粹的求和与筛法问题。整个算法的关键不在于继续做几何推导，而在于如何高效地重组这个和式。
参数化后的限制条件是
$$1\le r,\qquad r+1\le s\le 2r-1,\qquad \gcd(r,s)=1,\qquad rst\le L$$
对固定的 \(r\) 和 \(s\)，缩放参数 \(t\) 可以从 \(1\) 取到 \(\left\lfloor L/(rs)\right\rfloor\)。另外，如果 \(r>\sqrt{L}\)，那么即使取最小允许值 \(s=r+1\)，也有 \(rs>r^2>L\)，因此不可能再有贡献。所以外层循环只需要处理
$$1\le r\le R=\left\lfloor\sqrt{L}\right\rfloor.$$
对每个这样的 \(r\)，\(s\) 的有效区间就是
$$r+1\le s\le U_r=\min\!\left(2r-1,\left\lfloor\frac{L}{r}\right\rfloor\right).$$
对一个固定的互素对 \((r,s)\)，所有允许的缩放贡献之和为
$$\sum_{t=1}^{\lfloor L/(rs)\rfloor} rst=rs\sum_{t=1}^{\lfloor L/(rs)\rfloor} t.$$
定义三角数函数
$$T(n)=\frac{n(n+1)}{2}.$$
那么总和可以写成
$$F(L)=\sum_{r=1}^{R} r\sum_{\substack{r+1\le s\le U_r\\ \gcd(r,s)=1}} s\,T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
这一步的意义非常大，因为它把原本显式的第三重循环完全折叠掉了。程序不再逐个遍历 \(t\)，而是一次性用三角数吸收所有缩放贡献。
对固定的 \(r\)，定义带权互素前缀和
$$C_r(x)=\sum_{\substack{1\le s\le x\\ \gcd(r,s)=1}} s.$$
利用恒等式
$$\mathbf{1}_{\gcd(r,s)=1}=\sum_{d\mid \gcd(r,s)} \mu(d).$$
可以推出
$$\begin{aligned} C_r(x) &=\sum_{1\le s\le x} s\sum_{d\mid \gcd(r,s)}\mu(d)\\ &=\sum_{d\mid r}\mu(d)\sum_{\substack{1\le s\le x\\ d\mid s}} s\\ &=\sum_{d\mid r}\mu(d)\,d\,T\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right). \end{aligned}$$
这里为什么只需要关心平方自由除数？因为一旦 \(d\) 含有平方因子，就有 \(\mu(d)=0\)，对应项自动消失。所以实现里会预先为每个 \(r\) 构造“平方自由除数及其 Möbius 符号”的列表，后续查询直接遍历这张表即可。
有了 \(C_r(x)\) 之后，任意区间内的带权互素和都能写成
$$\sum_{\substack{a\le s\le b\\ \gcd(r,s)=1}} s=C_r(b)-C_r(a-1)$$
这样一来，互素筛选已经不再是主要难点。剩下需要加速的是
$$T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
中的 floor 值会随着 \(s\) 改变而跳跃。
固定 \(r\)，设当前 \(s\) 区间的左端点为 \(a\)。令
$$m=\left\lfloor\frac{L}{ra}\right\rfloor.$$
随着 \(s\) 增大，\(\left\lfloor L/(rs)\right\rfloor\) 会在整段
$$a\le s\le b=\min\!\left(U_r,\left\lfloor\frac{L}{rm}\right\rfloor\right).$$
上都保持等于 \(m\)。因此整块的贡献可以一次性写成
$$r\,T(m)\left(C_r(b)-C_r(a-1)\right).$$
然后把下一个块的左端点设为 \(b+1\) 即可。这与 Dirichlet 双曲线法中常见的 floor 分块思想完全一致：不是逐个点重复计算同一个商值，而是一次处理一个最大常值区间。
此时
$$R=\left\lfloor\sqrt{15}\right\rfloor=3.$$
当 \(r=1\) 时，区间 \(r+1\le s\le U_r\) 为空，所以没有贡献。
当 \(r=2\) 时，唯一可行的 \(s\) 是 \(3\)，而且 \(\gcd(2,3)=1\)。这时
$$\left\lfloor\frac{15}{2\cdot 3}\right\rfloor=2.$$
所以贡献为
$$2\cdot 3\cdot T(2)=6\cdot 3=18.$$
当 \(r=3\) 时，可行的 \(s\) 为 \(4\) 和 \(5\)。它们都与 \(3\) 互素，并且都满足
$$\left\lfloor\frac{15}{3s}\right\rfloor=1.$$
于是两项贡献分别是
$$3\cdot 4\cdot T(1)=12,\qquad 3\cdot 5\cdot T(1)=15.$$
总和为
$$18+12+15=45.$$
这与实现中使用的校验值完全一致。
C++、Python 和 Java 三个实现遵循同一套流程。首先计算 \(R=\lfloor\sqrt{L}\rfloor\)，因为更大的 \(r\) 不可能产生有效项。接着构造到 \(R\) 为止的最小质因子筛，从而能够快速分解每个 \(r\)。
在这些分解结果的基础上，程序为每个 \(r\) 生成平方自由除数列表，并记录对应的 Möbius 符号。于是一次前缀查询 \(C_r(x)\) 就可以通过遍历这张除数表、累加带符号的 \(d\,T(\lfloor x/d\rfloor)\) 来完成。
主循环枚举 \(r\)。对每个 \(r\)，程序不会逐个尝试所有 \(s\)，而是把合法区间切分成若干个“\(\left\lfloor L/(rs)\right\rfloor\) 常值块”。每个块只需要一次互素区间和，再乘上 \(r\) 和对应的三角数，就能把整块的贡献加到答案中。
数值类型也做了相应安排以避免溢出：Python 版本天然支持任意精度整数，Java 版本在累积总和时使用大整数，C++ 版本则使用 128 位整数来容纳结果。
设 \(R=\lfloor\sqrt{L}\rfloor\)。最小质因子筛的时间复杂度为 \(O(R\log\log R)\)，空间复杂度为 \(O(R)\)。构造平方自由除数表还需要额外工作，其规模与存储的平方自由除数总数成正比，即
$$O\!\left(\sum_{r\le R} 2^{\omega(r)}\right).$$
其中 \(\omega(r)\) 表示 \(r\) 的不同质因子个数。
在主求和阶段，对于固定的 \(r\)，每个常值块都需要两次互素前缀查询，而每次查询都要遍历同一份平方自由除数列表。如果记 \(B(r)\) 为该 \(r\) 对应的分块数，那么主循环代价为
$$O\!\left(\sum_{r\le R} B(r)\,2^{\omega(r)}\right).$$
与朴素地遍历所有可行三元组 \((r,s,t)\) 相比，这个代价在实际中小得多，因为 \(t\) 已经被三角数求和吸收，而 \(s\) 也按块处理，不再逐个重复计算相同的 floor 值。
Геометрия, связанная с инцентром и циркумцентром, в решении сначала сводится к примитивной арифметической параметризации. После этого реализации фактически вычисляют величину
$$F(L)=\sum_{\substack{1\le r<s<2r\\ \gcd(r,s)=1\\ t\ge 1,\ rst\le L}} rst.$$
Здесь \((r,s)\) задаёт примитивную конфигурацию, а \(t\) играет роль масштаба. Прямой перебор всех допустимых троек \((r,s,t)\) слишком дорог уже при \(L=10^9\), поэтому решение переписывает сумму через запросы по делителям и обработку блоков с одинаковым значением целой части.
После перехода от геометрии к взаимно простым целым параметрам задача превращается в аккуратное суммирование из элементарной теории чисел. Именно это арифметическое переписывание и даёт весь выигрыш по времени.
Из сведённой параметризации получаем условия
$$1\le r,\qquad r+1\le s\le 2r-1,\qquad \gcd(r,s)=1,\qquad rst\le L.$$
При фиксированных \(r\) и \(s\) параметр масштаба \(t\) меняется от \(1\) до \(\left\lfloor L/(rs)\right\rfloor\). Кроме того, если \(r>\sqrt{L}\), то даже минимально возможное \(s=r+1\) даёт \(rs>r^2>L\), значит вкладов уже не будет. Поэтому внешний цикл нужен только для
$$1\le r\le R=\left\lfloor\sqrt{L}\right\rfloor.$$
Для каждого такого \(r\) допустимый интервал для \(s\) равен
$$r+1\le s\le U_r=\min\!\left(2r-1,\left\lfloor\frac{L}{r}\right\rfloor\right).$$
Для фиксированной взаимно простой пары \((r,s)\) суммарный вклад всех допустимых масштабов равен
$$\sum_{t=1}^{\lfloor L/(rs)\rfloor} rst=rs\sum_{t=1}^{\lfloor L/(rs)\rfloor} t.$$
Введём функцию треугольных чисел
$$T(n)=\frac{n(n+1)}{2}.$$
Тогда вся задача переписывается так:
$$F(L)=\sum_{r=1}^{R} r\sum_{\substack{r+1\le s\le U_r\\ \gcd(r,s)=1}} s\,T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
Это уже серьёзное упрощение: реализации никогда не перебирают \(t\) явно.
Для фиксированного \(r\) определим взвешенную префиксную сумму
$$C_r(x)=\sum_{\substack{1\le s\le x\\ \gcd(r,s)=1}} s.$$
Используем тождество
$$\mathbf{1}_{\gcd(r,s)=1}=\sum_{d\mid \gcd(r,s)} \mu(d).$$
Тогда
$$\begin{aligned} C_r(x) &=\sum_{1\le s\le x} s\sum_{d\mid \gcd(r,s)}\mu(d)\\ &=\sum_{d\mid r}\mu(d)\sum_{\substack{1\le s\le x\\ d\mid s}} s\\ &=\sum_{d\mid r}\mu(d)\,d\,T\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right). \end{aligned}$$
Здесь важны только квадратсвободные делители, поскольку для любого делителя с квадратным множителем \(\mu(d)=0\). Поэтому реализации заранее строят для каждого \(r\) список квадратсвободных делителей и соответствующих знаков Мёбиуса.
Когда \(C_r(x)\) уже доступна, любая взвешенная сумма по отрезку записывается как
$$\sum_{\substack{a\le s\le b\\ \gcd(r,s)=1}} s=C_r(b)-C_r(a-1).$$
После этого условие взаимной простоты перестаёт быть главной трудностью. Остаётся только быстро обработать меняющееся значение
$$T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
Зафиксируем \(r\) и пусть \(a\) — текущая левая граница интервала по \(s\). Положим
$$m=\left\lfloor\frac{L}{ra}\right\rfloor.$$
При увеличении \(s\) величина \(\left\lfloor L/(rs)\right\rfloor\) остаётся равной \(m\) на всём блоке
$$a\le s\le b=\min\!\left(U_r,\left\lfloor\frac{L}{rm}\right\rfloor\right).$$
Поэтому вклад всего блока равен
$$r\,T(m)\left(C_r(b)-C_r(a-1)\right).$$
Следующий блок начинается с \(b+1\). Это та же идея группировки по одинаковым значениям целой части, которая лежит в основе гиперболического метода для сумм по делителям: вместо множества одинаковых вычислений обрабатывается один максимальный интервал.
Здесь
$$R=\left\lfloor\sqrt{15}\right\rfloor=3.$$
Для \(r=1\) интервал \(r+1\le s\le U_r\) пуст, значит вклада нет.
Для \(r=2\) единственное допустимое значение — \(s=3\), причём \(\gcd(2,3)=1\). Тогда
$$\left\lfloor\frac{15}{2\cdot 3}\right\rfloor=2,$$
и вклад равен
$$2\cdot 3\cdot T(2)=6\cdot 3=18.$$
Для \(r=3\) допустимы \(s=4\) и \(s=5\). Оба числа взаимно просты с \(3\), и для обоих
$$\left\lfloor\frac{15}{3s}\right\rfloor=1.$$
Следовательно, получаем вклады
$$3\cdot 4\cdot T(1)=12,\qquad 3\cdot 5\cdot T(1)=15.$$
Итоговая сумма равна
$$18+12+15=45,$$
что в точности совпадает с контрольным значением из реализаций.
Реализации на C++, Python и Java построены одинаково. Сначала вычисляется \(R=\lfloor\sqrt{L}\rfloor\), потому что большие значения \(r\) всё равно не дадут вклад. Затем строится решето наименьших простых делителей до \(R\), что позволяет быстро разлагать каждое \(r\) на простые множители.
По этим разложениям для каждого \(r\) формируется список квадратсвободных делителей вместе со знаком Мёбиуса. После этого запрос вида \(C_r(x)\) считается как сумма величин \(d\,T(\lfloor x/d\rfloor)\) по этому списку с правильными знаками.
Главный цикл идёт по \(r\). Для каждого \(r\) допустимый интервал значений \(s\) разбивается на максимальные блоки, на которых \(\left\lfloor L/(rs)\right\rfloor\) постоянно. Для каждого блока программа вычисляет одну сумму по взаимно простым значениям на отрезке, умножает её на \(r\) и нужное треугольное число и добавляет результат к общему ответу.
Числовые типы выбраны так, чтобы избежать переполнения: Python использует целые произвольной длины, Java хранит накапливаемый итог в больших целых, а C++ применяет 128-битную арифметику с той же целью.
Пусть \(R=\lfloor\sqrt{L}\rfloor\). Решето наименьших простых делителей работает за \(O(R\log\log R)\) времени и требует \(O(R)\) памяти. Построение таблиц квадратсвободных делителей даёт дополнительную стоимость, пропорциональную общему числу сохранённых делителей такого вида:
$$O\!\left(\sum_{r\le R} 2^{\omega(r)}\right),$$
где \(\omega(r)\) — число различных простых делителей \(r\).
На этапе основного суммирования каждый блок с постоянным floor-значением для фиксированного \(r\) требует двух префиксных запросов по взаимно простым значениям, а каждый такой запрос проходит по тому же списку квадратсвободных делителей. Если \(B(r)\) обозначает количество блоков для данного \(r\), то стоимость главного цикла равна
$$O\!\left(\sum_{r\le R} B(r)\,2^{\omega(r)}\right).$$
На практике это значительно меньше, чем перебор всех допустимых троек \((r,s,t)\), потому что сумма по \(t\) уже заменена треугольным числом, а значения \(s\) обрабатываются блоками, а не по одному.
تُختزل هندسة المركز الداخلي والمركز الخارجي في الحل إلى بارامترية عددية أولية. بعد هذا الاختزال تصبح الكمية التي تحسبها التطبيقات هي
$$F(L)=\sum_{\substack{1\le r<s<2r\\ \gcd(r,s)=1\\ t\ge 1,\ rst\le L}} rst.$$
يمثل الزوج \((r,s)\) بنية أولية، ويمثل \(t\) عامل التكبير. التعداد المباشر لكل الثلاثيات المسموح بها \((r,s,t)\) يصبح بطيئًا جدًا عندما \(L=10^9\)، لذلك يعيد الحل كتابة المجموع على صورة استعلامات نطاق مبنية على القواسم مع تجميع القيم التي تشترك في نفس قيمة الجزء الصحيح.
بمجرد تحويل الجزء الهندسي إلى معاملات صحيحة متباينة نسبيًا، تتحول المسألة إلى مسألة جمع من نظرية الأعداد الابتدائية. جوهر الحل ليس تكرار الهندسة، بل إعادة تنظيم هذا المجموع بطريقة تسمح بالحساب السريع.
تعطي البارامترية المختزلة الشروط التالية:
$$1\le r,\qquad r+1\le s\le 2r-1,\qquad \gcd(r,s)=1,\qquad rst\le L.$$
عند تثبيت \(r\) و\(s\)، يمكن أن يأخذ عامل التكبير \(t\) القيم من \(1\) حتى \(\left\lfloor L/(rs)\right\rfloor\). كذلك إذا كان \(r>\sqrt{L}\)، فإن أصغر قيمة ممكنة وهي \(s=r+1\) تعطي \(rs>r^2>L\)، وبالتالي لا يبقى أي إسهام. لذلك يكفي أن يجري الدوران الخارجي على
$$1\le r\le R=\left\lfloor\sqrt{L}\right\rfloor.$$
ولكل قيمة من هذه القيم يكون مجال \(s\) الصحيح هو
$$r+1\le s\le U_r=\min\!\left(2r-1,\left\lfloor\frac{L}{r}\right\rfloor\right).$$
لزوج ثابت ومتباين نسبيًا \((r,s)\)، يكون مجموع مساهمات جميع قيم التكبير المسموح بها هو
$$\sum_{t=1}^{\lfloor L/(rs)\rfloor} rst=rs\sum_{t=1}^{\lfloor L/(rs)\rfloor} t.$$
لنعرّف دالة العدد المثلثي
$$T(n)=\frac{n(n+1)}{2}.$$
وبذلك تصبح المسألة كلها
$$F(L)=\sum_{r=1}^{R} r\sum_{\substack{r+1\le s\le U_r\\ \gcd(r,s)=1}} s\,T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
وهذه خطوة مهمة جدًا، لأن التنفيذ لا يحتاج بعد ذلك إلى الدوران الصريح على \(t\) إطلاقًا.
لـ \(r\) ثابت، نعرّف مجموع البادئة الموزون
$$C_r(x)=\sum_{\substack{1\le s\le x\\ \gcd(r,s)=1}} s.$$
وباستخدام الهوية
$$\mathbf{1}_{\gcd(r,s)=1}=\sum_{d\mid \gcd(r,s)} \mu(d),$$
نحصل على
$$\begin{aligned} C_r(x) &=\sum_{1\le s\le x} s\sum_{d\mid \gcd(r,s)}\mu(d)\\ &=\sum_{d\mid r}\mu(d)\sum_{\substack{1\le s\le x\\ d\mid s}} s\\ &=\sum_{d\mid r}\mu(d)\,d\,T\!\left(\left\lfloor\frac{x}{d}\right\rfloor\right). \end{aligned}$$
لا تهم إلا القواسم الخالية من المربعات، لأن \(\mu(d)=0\) لكل قاسم غير خالٍ من المربعات. ولهذا تبني التطبيقات مسبقًا، لكل \(r\)، قائمة بهذه القواسم مع إشارة Möbius الموافقة.
بعد معرفة \(C_r(x)\)، يصبح أي مجموع موزون على مجال محدود مساويًا لـ
$$\sum_{\substack{a\le s\le b\\ \gcd(r,s)=1}} s=C_r(b)-C_r(a-1).$$
وبهذا لا يعود شرط التباين النسبي هو العقبة الأساسية. ما يبقى هو التعامل مع تغير قيمة الجزء الصحيح داخل
$$T\!\left(\left\lfloor\frac{L}{rs}\right\rfloor\right).$$
ثبّت \(r\)، ولتكن \(a\) هي البداية الحالية في مجال \(s\). نضع
$$m=\left\lfloor\frac{L}{ra}\right\rfloor.$$
عندما تزداد \(s\)، تبقى القيمة \(\left\lfloor L/(rs)\right\rfloor\) مساوية لـ \(m\) على كامل الكتلة
$$a\le s\le b=\min\!\left(U_r,\left\lfloor\frac{L}{rm}\right\rfloor\right).$$
إذن تساهم هذه الكتلة كاملة بالمقدار
$$r\,T(m)\left(C_r(b)-C_r(a-1)\right).$$
ثم تبدأ الكتلة التالية عند \(b+1\). هذه هي الفكرة نفسها المستعملة في تجميع قيم القسمة الصحيحة في طريقة ديريشليه-هايبرولا: بدل إعادة حساب القيمة نفسها مرارًا، يُعالَج مجال أعظمي كامل دفعة واحدة.
لدينا هنا
$$R=\left\lfloor\sqrt{15}\right\rfloor=3.$$
عند \(r=1\) يكون المجال \(r+1\le s\le U_r\) فارغًا، فلا يوجد أي إسهام.
عند \(r=2\) تكون القيمة الوحيدة المسموح بها هي \(s=3\)، وهي متباينة نسبيًا مع \(2\). عندئذٍ
$$\left\lfloor\frac{15}{2\cdot 3}\right\rfloor=2,$$
فتصبح المساهمة
$$2\cdot 3\cdot T(2)=6\cdot 3=18.$$
وعند \(r=3\) تكون القيم المسموح بها \(s=4\) و\(s=5\). وكلتاهما متباينة نسبيًا مع \(3\)، وكلتاهما تحقق
$$\left\lfloor\frac{15}{3s}\right\rfloor=1.$$
إذًا المساهمتان هما
$$3\cdot 4\cdot T(1)=12,\qquad 3\cdot 5\cdot T(1)=15.$$
وبجمع الكل نحصل على
$$18+12+15=45,$$
وهو تمامًا مقدار التحقق المستخدم في التطبيقات.
تتبع تطبيقات C++ وPython وJava الهيكل نفسه. أولًا تحسب \(R=\lfloor\sqrt{L}\rfloor\)، لأن أي قيمة أكبر لـ \(r\) لا يمكن أن تنتج حدًا صالحًا. بعد ذلك تبني غربال أصغر عامل أولي حتى \(R\)، مما يسمح بتحليل كل \(r\) بسرعة.
ومن هذه التحليلات تُنشأ، لكل \(r\)، قائمة القواسم الخالية من المربعات مع إشارة Möbius الموافقة. وعند طلب بادئة من النوع \(C_r(x)\)، تجمع الشيفرة الحدود \(d\,T(\lfloor x/d\rfloor)\) على هذه القائمة مع الإشارات الصحيحة.
تسير الحلقة الرئيسية على قيم \(r\). ولكل \(r\)، لا تُفحَص قيم \(s\) واحدةً واحدة، بل يُقسَّم المجال المسموح إلى كتل عظمى تبقى فيها \(\left\lfloor L/(rs)\right\rfloor\) ثابتة. في كل كتلة تحسب الشيفرة مجموعًا واحدًا على مجال متباين نسبيًا، ثم تضربه في \(r\) وفي العدد المثلثي المناسب وتضيف النتيجة إلى المجموع الكلي.
أما الأنواع العددية فقد اختيرت لتجنب الفيض: نسخة Python تستخدم أعدادًا صحيحة ذات دقة غير محدودة تلقائيًا، ونسخة Java تستخدم أعدادًا صحيحة كبيرة للمجموع المتراكم، ونسخة C++ تستخدم حسابًا على 128 بت للسبب نفسه.
ليكن \(R=\lfloor\sqrt{L}\rfloor\). يحتاج غربال أصغر عامل أولي إلى زمن \(O(R\log\log R)\) وذاكرة \(O(R)\). كما أن بناء جداول القواسم الخالية من المربعات يتطلب عملًا إضافيًا يتناسب مع العدد الكلي لهذه القواسم المخزنة، أي
$$O\!\left(\sum_{r\le R} 2^{\omega(r)}\right),$$
حيث تمثل \(\omega(r)\) عدد العوامل الأولية المميزة للعدد \(r\).
أثناء الجمع الرئيسي، تحتاج كل كتلة ذات قيمة floor ثابتة لعدد \(r\) معين إلى استعلامي بادئة متباينين نسبيًا، وكل استعلام يمر على قائمة القواسم الخالية من المربعات نفسها. وإذا رمزنا بعدد الكتل الموافقة لـ \(r\) بالرمز \(B(r)\)، فإن تكلفة الحلقة الرئيسية هي
$$O\!\left(\sum_{r\le R} B(r)\,2^{\omega(r)}\right).$$
وهذا أصغر بكثير عمليًا من الدوران على كل ثلاثية مسموح بها \((r,s,t)\)، لأن مجموع \(t\) قد اختُزل مسبقًا إلى عدد مثلثي، ولأن قيم \(s\) تُعالَج على شكل كتل بدلًا من معالجتها فرادى.