The task is to count primitive integral-median configurations whose size parameter is at most \(n\). A naive scan over geometric candidates would be far too slow. The implementations therefore replace the geometry by an arithmetic parametrization, count the resulting integer lattice points inside rational trapezoids, and only at the end remove the nonprimitive configurations produced by odd rescaling.
Write \(G(n)\) for the number of admissible parameter tuples before primitive filtering, and \(C(n)\) for the primitive count required by the problem. The method has two layers: first evaluate \(G(n)\) exactly by lattice-point counting, then recover \(C(n)\) by subtracting odd dilations of smaller primitive objects.
In the parametrization used by the implementations, each admissible configuration is encoded by two positive integer pairs \((\alpha,\beta)\) and \((p,q)\). The admissibility conditions become
$$\alpha \gt \sqrt{3}\,\beta,\qquad \beta p \le \alpha q,\qquad (\alpha+\beta)p \gt (\alpha+3\beta)q,\qquad \alpha p-\beta q \le n.$$
There are also parity restrictions. The auxiliary pair \((p,q)\) may lie only in the residue classes
$$ (p,q)\equiv (0,1),\ (1,0),\ (1,1)\pmod 2, $$
because the all-even class would represent a nonprimitive encoding. The generating pair \((\alpha,\beta)\) must then follow the compatible even/odd progression for the chosen class, so the implementation advances through these parameters in steps of \(2\) instead of testing every integer.
Fix the generating pair \((\alpha,\beta)\). Rearranging the inequalities gives the allowed range for \(p\) as a function of \(q\):
$$\frac{\alpha+3\beta}{\alpha+\beta}q \lt p \le \min\left(\frac{\alpha}{\beta}q,\frac{\beta q+n}{\alpha}\right).$$
So for each positive integer \(q\), the admissible values of \(p\) lie above one open line and below the smaller of two closed lines. The two upper bounds cross at
$$q_{\mathrm{sw}}=\left\lfloor\frac{\beta n}{\alpha^2-\beta^2}\right\rfloor,$$
and the whole region disappears after
$$q_{\max}=\left\lfloor\frac{n(\alpha+\beta)}{\alpha^2+2\alpha\beta-\beta^2}\right\rfloor.$$
Therefore the contribution for fixed \((\alpha,\beta)\) is counted as
$$\text{two closed trapezoids} - \text{one open trapezoid}.$$
This is the geometric core of the solution.
For a chosen residue class, write
$$q=2q'+\varepsilon_q,\qquad p=2p'+\varepsilon_p,\qquad \varepsilon_p,\varepsilon_q\in\{0,1\}.$$
After this affine change of variables, each parity-restricted trapezoid turns into an ordinary lattice count with doubled denominator. Closed edges are counted with a usual floor, while open edges are handled by shifting the numerator down by \(1\). In that way every residue class is reduced to the same numerical primitive: summing values of a floor of a linear expression.
For integers \(A,B,M\) and an interval \(L \lt x \le U\), define
$$T(A,B,M;L,U)=\sum_{x=L+1}^{U}\left\lfloor\frac{Ax+B}{M}\right\rfloor.$$
This counts lattice points under the rational line \(y=(Ax+B)/M\). For a strict upper boundary one instead uses \(\lfloor (Ax+B-1)/M\rfloor\). The implementations evaluate these sums exactly by Euclidean-style reduction: first remove the whole-number parts of \(A/M\) and \(B/M\), then swap slope and denominator on the reduced problem. Once the interval becomes tiny, direct summation finishes the job. Because every admissible region from Step 2 is trapezoidal, \(G(n)\) is obtained entirely from a small number of such exact floor-sums.
Iterating over every possible generating pair would waste work when \(\alpha\) is large. The implementations therefore split at
$$R=\left\lfloor\sqrt{\frac{3n}{2}}\right\rfloor.$$
For \(\alpha \lt R\), the code fixes \((\alpha,\beta)\) and counts \((p,q)\) directly. For the complementary range it reverses the viewpoint: fix \((p,q)\) and count admissible \((\alpha,\beta)\). Transposing the inequalities from Step 1 gives
$$\beta \le \min\left(\frac{q}{p}\alpha,\frac{p-q}{3q-p}\alpha\right),\qquad \beta \gt \frac{p\alpha-n}{q}.$$
The active upper slope changes exactly when
$$p^2=3q^2,$$
which explains the two-case split in the second major loop. This is a classic hyperbola-style decomposition: one pass is efficient for small generators, the transposed pass is efficient for large generators.
After the parity normalization, every nonprimitive configuration is an odd dilation of a primitive one. Therefore
$$C(n)=G(n)-\sum_{\substack{d\ge 3\\ d\text{ odd}}} C\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
The same quotient \(\lfloor n/d\rfloor\) appears for many consecutive odd values of \(d\), so the implementations group equal quotients into blocks and subtract one cached subproblem multiplied by the number of odd dilations in that block. This is why the primitive filtering stays fast.
For \(n=10\), the odd dilations \(d\ge 3\) produce
$$\left\lfloor\frac{10}{3}\right\rfloor=3,\qquad \left\lfloor\frac{10}{5}\right\rfloor=2,\qquad \left\lfloor\frac{10}{7}\right\rfloor=\left\lfloor\frac{10}{9}\right\rfloor=1.$$
So the recursion becomes
$$C(10)=G(10)-C(3)-C(2)-2C(1).$$
Two different odd scales collapse to the same subproblem \(C(1)\), which is exactly the optimization exploited by quotient grouping. The checkpoint used by the implementations is \(C(10)=3\).
The C++, Python, and Java implementations all follow the same plan. They first compute \(R=\lfloor\sqrt{3n/2}\rfloor\) and then evaluate the raw count \(G(n)\) across the three admissible parity classes. The first pass iterates over the small generating range and adds the two closed trapezoids minus the open trapezoid from Step 2. The second pass handles the complementary range by fixing the auxiliary pair and counting the transposed trapezoids from Step 5. In both passes, parity is enforced by stepping through the correct congruence classes and by applying affine parity shifts inside the floor-sum evaluator.
After \(G(n)\) is known, the implementation computes the primitive total \(C(n)\) with memoized recursion. Cached values avoid repeated work, and the subtraction over odd dilations is grouped by equal quotients \(\lfloor n/d\rfloor\), so the same smaller argument is solved only once. The three language versions are mathematically identical.
The geometric part of one distinct subproblem is organized as a hyperbola decomposition. The direct and transposed passes together create about \(O(n)\) trapezoid evaluations for an argument of size \(n\), and each trapezoid evaluation is reduced by Euclidean floor-sum transformations, giving roughly logarithmic work per call. The primitive-filter recursion is much cheaper than subtracting every odd scale independently because memoization and quotient grouping collapse many scales to the same smaller argument. The overall method is comfortably subquadratic in practice and far faster than direct enumeration of candidate triangles.
Gesucht ist die Anzahl primitiver Integral-Median-Konfigurationen mit Größenparameter höchstens \(n\). Eine naive Durchmusterung aller geometrischen Kandidaten wäre viel zu langsam. Deshalb ersetzen die Implementierungen die Geometrie durch eine arithmetische Parametrisierung, zählen die entstehenden Gitterpunkte in rationalen Trapezen exakt und entfernen erst am Ende die nichtprimitiven Konfigurationen, die durch ungerade Skalierung entstehen.
Sei \(G(n)\) die Anzahl aller zulässigen Parametertupel vor der Primitivitätsfilterung und \(C(n)\) die tatsächlich gesuchte primitive Anzahl. Das Verfahren hat also zwei Schichten: Zuerst wird \(G(n)\) exakt per Gitterpunktzählung berechnet, danach gewinnt man \(C(n)\), indem man die ungeraden Vielfachen kleinerer primitiver Objekte subtrahiert.
In der von den Implementierungen verwendeten Parametrisierung wird jede zulässige Konfiguration durch zwei positive Zahlenpaare \((\alpha,\beta)\) und \((p,q)\) beschrieben. Die Bedingungen lauten dann
$$\alpha \gt \sqrt{3}\,\beta,\qquad \beta p \le \alpha q,\qquad (\alpha+\beta)p \gt (\alpha+3\beta)q,\qquad \alpha p-\beta q \le n.$$
Dazu kommen Paritätsauflagen. Das Hilfspaar \((p,q)\) darf nur in den Klassen
$$ (p,q)\equiv (0,1),\ (1,0),\ (1,1)\pmod 2 $$
liegen, denn die komplett gerade Klasse würde eine nichtprimitive Kodierung darstellen. Das erzeugende Paar \((\alpha,\beta)\) muss dann die dazu kompatible Gerade/Ungerade-Folge erfüllen, weshalb die Implementierung diese Parameter direkt in Zweierschritten durchläuft.
Fixiere das erzeugende Paar \((\alpha,\beta)\). Dann lassen sich die Bedingungen zu einem erlaubten Bereich für \(p\) in Abhängigkeit von \(q\) umformen:
$$\frac{\alpha+3\beta}{\alpha+\beta}q \lt p \le \min\left(\frac{\alpha}{\beta}q,\frac{\beta q+n}{\alpha}\right).$$
Für jedes positive \(q\) liegen die zulässigen Werte von \(p\) also oberhalb einer offenen Geraden und unterhalb des kleineren von zwei geschlossenen oberen Rändern. Die beiden oberen Schranken schneiden sich bei
$$q_{\mathrm{sw}}=\left\lfloor\frac{\beta n}{\alpha^2-\beta^2}\right\rfloor,$$
und nach
$$q_{\max}=\left\lfloor\frac{n(\alpha+\beta)}{\alpha^2+2\alpha\beta-\beta^2}\right\rfloor$$
gibt es überhaupt keine Punkte mehr. Der Beitrag für festes \((\alpha,\beta)\) ist damit
$$\text{zwei geschlossene Trapeze} - \text{ein offenes Trapez}.$$
Für eine feste Restklasse schreiben wir
$$q=2q'+\varepsilon_q,\qquad p=2p'+\varepsilon_p,\qquad \varepsilon_p,\varepsilon_q\in\{0,1\}.$$
Nach dieser affinen Variablentransformation wird jedes paritätsbeschränkte Trapez zu einer gewöhnlichen Gitterpunktzählung mit verdoppeltem Nenner. Geschlossene Kanten werden mit der normalen Floor-Funktion gezählt; für offene Kanten verschiebt man den Zähler um \(1\) nach unten. Auf diese Weise reduzieren sich alle drei zulässigen Restklassen auf dieselbe numerische Kernoperation: die Summe von Floors linearer Ausdrücke.
Für ganze Zahlen \(A,B,M\) und ein Intervall \(L \lt x \le U\) definieren wir
$$T(A,B,M;L,U)=\sum_{x=L+1}^{U}\left\lfloor\frac{Ax+B}{M}\right\rfloor.$$
Diese Summe zählt Gitterpunkte unter der rationalen Geraden \(y=(Ax+B)/M\). Für eine strenge obere Grenze verwendet man stattdessen \(\lfloor(Ax+B-1)/M\rfloor\). Die Implementierungen berechnen diese Summen exakt mit einer euklidischen Reduktion: Zuerst werden die ganzzahligen Anteile von \(A/M\) und \(B/M\) abgespalten, dann werden Steigung und Nenner im reduzierten Problem vertauscht. Sobald das Intervall klein genug ist, genügt direkte Summation. Weil alle zulässigen Bereiche aus Schritt 2 trapezförmig sind, erhält man \(G(n)\) vollständig aus wenigen solchen exakten Floor-Sums.
Ein einfaches Durchlaufen aller möglichen erzeugenden Paare wäre für große \(\alpha\) unnötig teuer. Deshalb teilen die Implementierungen bei
$$R=\left\lfloor\sqrt{\frac{3n}{2}}\right\rfloor$$
auf. Für \(\alpha \lt R\) wird \((\alpha,\beta)\) fixiert und \((p,q)\) direkt gezählt. Für den komplementären Bereich wird die Perspektive umgedreht: Man fixiert \((p,q)\) und zählt die zulässigen \((\alpha,\beta)\). Aus den Bedingungen aus Schritt 1 folgt dann
$$\beta \le \min\left(\frac{q}{p}\alpha,\frac{p-q}{3q-p}\alpha\right),\qquad \beta \gt \frac{p\alpha-n}{q}.$$
Die aktive obere Schranke wechselt genau bei
$$p^2=3q^2,$$
und genau daraus entsteht die Zweifallunterscheidung in der zweiten Hauptschleife. Das ist eine klassische Hyperbelzerlegung: ein Durchlauf ist für kleine Erzeuger günstig, der transponierte Durchlauf für große.
Nach der Paritätsnormalisierung ist jedes nichtprimitive Objekt ein ungerades Vielfaches eines primitiven Objekts. Daher gilt
$$C(n)=G(n)-\sum_{\substack{d\ge 3\\ d\text{ ungerade}}} C\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
Derselbe Quotient \(\lfloor n/d\rfloor\) tritt für viele aufeinanderfolgende ungerade Werte von \(d\) auf. Deshalb fasst die Implementierung gleiche Quotienten zu Blöcken zusammen und subtrahiert ein zwischengespeichertes Teilproblem mit der Anzahl der ungeraden Skalierungen in diesem Block.
Für \(n=10\) liefern die ungeraden Skalierungen \(d\ge 3\)
$$\left\lfloor\frac{10}{3}\right\rfloor=3,\qquad \left\lfloor\frac{10}{5}\right\rfloor=2,\qquad \left\lfloor\frac{10}{7}\right\rfloor=\left\lfloor\frac{10}{9}\right\rfloor=1.$$
Damit reduziert sich die Rekursion auf
$$C(10)=G(10)-C(3)-C(2)-2C(1).$$
Zwei verschiedene ungerade Skalen führen also zum selben Teilproblem \(C(1)\). Genau diesen Effekt nutzt die Quotientenblockung aus. Der in den Implementierungen verwendete Kontrollwert ist \(C(10)=3\).
Die Implementierungen in C++, Python und Java folgen demselben Plan. Zuerst wird \(R=\lfloor\sqrt{3n/2}\rfloor\) berechnet, danach der rohe Wert \(G(n)\) über die drei zulässigen Paritätsklassen aufsummiert. Der erste Durchlauf behandelt den kleinen Erzeugerbereich und addiert die zwei geschlossenen Trapeze minus das offene Trapez aus Schritt 2. Der zweite Durchlauf deckt den komplementären Bereich ab, indem das Hilfspaar fixiert und die transponierten Trapeze aus Schritt 5 gezählt werden. In beiden Durchläufen wird die Parität durch passende Schrittweiten und affine Verschiebungen innerhalb des Floor-Sum-Kerns erzwungen.
Nachdem \(G(n)\) bekannt ist, berechnet die Implementierung die primitive Gesamtzahl \(C(n)\) mit memoisierten Rekursionsaufrufen. Bereits berechnete Werte werden aus dem Cache gelesen, und die Subtraktion über ungerade Skalierungen wird nach gleichen Quotienten \(\lfloor n/d\rfloor\) gruppiert. Dadurch wird jedes kleinere Teilproblem nur einmal gelöst.
Der geometrische Teil eines einzelnen Teilproblems ist als Hyperbelzerlegung organisiert. Die direkten und transponierten Durchläufe erzeugen zusammen ungefähr \(O(n)\) Trapezauswertungen für ein Argument der Größe \(n\), und jede solche Auswertung benötigt dank euklidischer Floor-Sum-Reduktion nur ungefähr logarithmische Zeit. Die Rekursion zur Primitivitätsfilterung ist deutlich billiger als eine separate Behandlung jeder ungeraden Skalierung, weil Memoisierung und Quotientenblockung viele Skalen auf dieselben kleineren Argumente zusammenziehen. Das Gesamtverfahren ist in der Praxis klar subquadratisch und dramatisch schneller als direkte Enumeration.
Amaç, boyut parametresi \(n\)'i aşmayan primitif integral-medyan konfigürasyonlarının sayısını bulmaktır. Geometrik adayları tek tek taramak çok yavaş olurdu. Bu yüzden implementasyonlar geometriyi aritmetik bir parametreleştirmeye dönüştürür, oluşan rasyonel trapezlerdeki örgü noktalarını tam olarak sayar ve en sonda tek sayılı ölçeklemelerden gelen primitif olmayan kopyaları çıkarır.
\(G(n)\), primitiflik filtresi uygulanmadan önceki uygun parametre dörtlülerinin sayısı olsun; \(C(n)\) ise sorunun istediği primitif toplam olsun. Yöntem iki katmanlıdır: önce \(G(n)\) örgü nokta sayımıyla tam hesaplanır, sonra daha küçük primitif çözümlerin tek katlı kopyaları çıkarılarak \(C(n)\) elde edilir.
İmplementasyonların kullandığı parametreleştirmede her uygun konfigürasyon iki pozitif tam sayı çiftiyle, yani \((\alpha,\beta)\) ve \((p,q)\) ile temsil edilir. Koşullar şu hale gelir:
$$\alpha \gt \sqrt{3}\,\beta,\qquad \beta p \le \alpha q,\qquad (\alpha+\beta)p \gt (\alpha+3\beta)q,\qquad \alpha p-\beta q \le n.$$
Bunlara ek olarak parity kısıtları vardır. Yardımcı çift \((p,q)\) yalnızca şu sınıflarda olabilir:
$$ (p,q)\equiv (0,1),\ (1,0),\ (1,1)\pmod 2, $$
çünkü tamamen çift sınıf primitif olmayan bir kodlamaya karşılık gelir. Üreten çift \((\alpha,\beta)\) de seçilen sınıfa uyumlu tek-çift ilerleyişi izlemek zorundadır; bu yüzden kod her tamsayıyı denemek yerine doğrudan \(2\)'şer adımlarla ilerler.
\((\alpha,\beta)\) sabit olsun. Eşitsizlikleri yeniden düzenlersek, \(q\)'ya bağlı olarak \(p\) için izin verilen aralık şudur:
$$\frac{\alpha+3\beta}{\alpha+\beta}q \lt p \le \min\left(\frac{\alpha}{\beta}q,\frac{\beta q+n}{\alpha}\right).$$
Demek ki her pozitif \(q\) için uygun \(p\) değerleri bir açık doğrunun üstünde ve iki kapalı üst sınırın küçüğünün altında kalır. İki üst sınır
$$q_{\mathrm{sw}}=\left\lfloor\frac{\beta n}{\alpha^2-\beta^2}\right\rfloor$$
noktasında yer değiştirir; bölge ise
$$q_{\max}=\left\lfloor\frac{n(\alpha+\beta)}{\alpha^2+2\alpha\beta-\beta^2}\right\rfloor$$
sonrasında tamamen biter. Böylece sabit \((\alpha,\beta)\) katkısı
$$\text{iki kapalı trapez} - \text{bir açık trapez}$$
şeklinde sayılır.
Seçilen bir kalıntı sınıfı için
$$q=2q'+\varepsilon_q,\qquad p=2p'+\varepsilon_p,\qquad \varepsilon_p,\varepsilon_q\in\{0,1\}$$
yazılır. Bu affine değişimden sonra parity kısıtlı her trapez, paydası iki katına çıkmış sıradan bir örgü nokta sayımına dönüşür. Kapalı kenarlar normal floor ile, açık kenarlar ise payın \(1\) azaltılmasıyla sayılır. Böylece üç geçerli kalıntı sınıfının hepsi aynı sayısal çekirdeğe, yani doğrusal bir ifadenin floor toplamına indirilmiş olur.
\(A,B,M\) tamsayıları ve \(L \lt x \le U\) aralığı için
$$T(A,B,M;L,U)=\sum_{x=L+1}^{U}\left\lfloor\frac{Ax+B}{M}\right\rfloor$$
tanımını yapalım. Bu ifade, \(y=(Ax+B)/M\) doğrusu altındaki örgü noktalarını sayar. Üst sınır sıkı ise \(\lfloor(Ax+B-1)/M\rfloor\) kullanılır. İmplementasyonlar bu toplamları Öklid benzeri bir indirgeme ile tam hesaplar: önce \(A/M\) ve \(B/M\)'nin tam sayı kısımları ayrılır, sonra indirgenmiş problemde eğim ile payda yer değiştirir. Aralık yeterince küçülünce doğrudan toplama yapılır. Adım 2'deki tüm bölgeler trapez olduğu için \(G(n)\) birkaç adet tam floor-sum hesabından oluşur.
Olası tüm üreten çiftleri doğrudan dolaşmak, \(\alpha\) büyüdüğünde gereksiz iş üretir. Bu nedenle implementasyonlar
$$R=\left\lfloor\sqrt{\frac{3n}{2}}\right\rfloor$$
eşik değerinde bölme yapar. \(\alpha \lt R\) iken \((\alpha,\beta)\) sabitlenir ve \((p,q)\) doğrudan sayılır. Tamamlayıcı bölgede bakış açısı ters çevrilir: \((p,q)\) sabitlenir ve uygun \((\alpha,\beta)\) çiftleri sayılır. Adım 1'deki eşitsizlikler bu durumda
$$\beta \le \min\left(\frac{q}{p}\alpha,\frac{p-q}{3q-p}\alpha\right),\qquad \beta \gt \frac{p\alpha-n}{q}$$
biçimine döner. Etkin üst eğim tam olarak
$$p^2=3q^2$$
noktasında değişir; ikinci büyük döngüdeki iki durum bundan gelir. Bu, klasik bir hiperbol ayrışımıdır: bir geçiş küçük üreteçlerde, öteki büyük üreteçlerde verimlidir.
Parity normalizasyonundan sonra primitif olmayan her konfigürasyon, bir primitif konfigürasyonun tek katlı ölçeklenmiş halidir. Bu yüzden
$$C(n)=G(n)-\sum_{\substack{d\ge 3\\ d\text{ tek}}} C\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right)$$
eşitliği geçerlidir. Aynı \(\lfloor n/d\rfloor\) bölümü art arda gelen birçok tek \(d\) için tekrarlandığından, implementasyonlar eşit bölümləri bloklar halinde sayar ve aynı alt problemi bir kez hesaplayıp bloktaki tek çarpan sayısıyla çarpar.
\(n=10\) olduğunda \(d\ge 3\) tek ölçekleri
$$\left\lfloor\frac{10}{3}\right\rfloor=3,\qquad \left\lfloor\frac{10}{5}\right\rfloor=2,\qquad \left\lfloor\frac{10}{7}\right\rfloor=\left\lfloor\frac{10}{9}\right\rfloor=1$$
değerlerini verir. Dolayısıyla rekürsiyon
$$C(10)=G(10)-C(3)-C(2)-2C(1)$$
şeklinde toplanır. İki farklı tek ölçek aynı \(C(1)\) alt problemine düşer; quotient blocking tam olarak bu kazancı kullanır. İmplementasyonların doğrulama noktası \(C(10)=3\)'tür.
C++, Python ve Java implementasyonları aynı matematiksel planı izler. Önce \(R=\lfloor\sqrt{3n/2}\rfloor\) hesaplanır, ardından ham sayı \(G(n)\) üç geçerli parity sınıfı üzerinden toplanır. İlk geçiş küçük üreteç bölgesini dolaşır ve Adım 2'deki iki kapalı trapezi ekleyip açık trapezi çıkarır. İkinci geçiş tamamlayıcı bölgeyi, yardımcı çifti sabitleyip Adım 5'teki ters çevrilmiş trapezleri sayarak işler. Her iki geçişte de parity, doğru mod sınıflarında adımlama ve floor-sum çekirdeğindeki affine kaydırmalarla uygulanır.
\(G(n)\) elde edildikten sonra implementasyon, primitif toplam \(C(n)\)'i memoization kullanan bir rekürsiyonla hesaplar. Önceden hesaplanan küçük argümanlar önbellekten alınır; tek sayılı ölçeklemeler üzerindeki çıkarma da aynı \(\lfloor n/d\rfloor\) değerlerine göre gruplanır. Böylece aynı alt problem tekrar tekrar çözülmez.
Geometrik kısım tek bir alt problem için hiperbol tarzı bir ayrışım olarak düzenlenmiştir. Doğrudan ve ters çevrilmiş geçişler birlikte, büyüklüğü \(n\) olan bir argüman için yaklaşık \(O(n)\) trapez değerlendirmesi üretir; her trapez değerlendirmesi de Öklid tipi floor-sum indirgemesi sayesinde yaklaşık logaritmik zamanda biter. Primitiflik filtresi, her tek ölçeği ayrı ayrı çıkarmaktan çok daha ucuzdur; çünkü memoization ve quotient blocking birçok ölçeği aynı küçük argümana indirger. Sonuç olarak yöntem pratikte rahatça subquadratic kalır ve doğrudan üçgen taramasından çok daha hızlıdır.
El objetivo es contar las configuraciones primitivas de mediana entera cuyo parámetro de tamaño no supera \(n\). Un barrido ingenuo sobre todos los candidatos geométricos sería demasiado lento. Por eso las implementaciones reemplazan la geometría por una parametrización aritmética, cuentan exactamente los puntos de retícula dentro de trapecios racionales y solo al final eliminan las configuraciones no primitivas que provienen de reescalados impares.
Sea \(G(n)\) el número de tuplas de parámetros admisibles antes del filtrado de primitividad y sea \(C(n)\) el conteo primitivo pedido por el problema. El método tiene dos capas: primero calcular \(G(n)\) exactamente mediante conteo de puntos de retícula, y después recuperar \(C(n)\) restando las dilataciones impares de objetos primitivos más pequeños.
En la parametrización usada por las implementaciones, cada configuración admisible se codifica por dos pares positivos \((\alpha,\beta)\) y \((p,q)\). Las condiciones se convierten en
$$\alpha \gt \sqrt{3}\,\beta,\qquad \beta p \le \alpha q,\qquad (\alpha+\beta)p \gt (\alpha+3\beta)q,\qquad \alpha p-\beta q \le n.$$
Además aparecen restricciones de paridad. El par auxiliar \((p,q)\) solo puede pertenecer a las clases
$$ (p,q)\equiv (0,1),\ (1,0),\ (1,1)\pmod 2, $$
porque la clase totalmente par representaría una codificación no primitiva. El par generador \((\alpha,\beta)\) debe seguir entonces la progresión par/impar compatible con la clase elegida, de modo que la implementación avanza de \(2\) en \(2\).
Fijemos \((\alpha,\beta)\). Al reorganizar las desigualdades, el rango permitido para \(p\) en función de \(q\) es
$$\frac{\alpha+3\beta}{\alpha+\beta}q \lt p \le \min\left(\frac{\alpha}{\beta}q,\frac{\beta q+n}{\alpha}\right).$$
Para cada entero positivo \(q\), los valores válidos de \(p\) quedan por encima de una recta abierta y por debajo del menor de dos techos cerrados. Los dos techos se cruzan en
$$q_{\mathrm{sw}}=\left\lfloor\frac{\beta n}{\alpha^2-\beta^2}\right\rfloor,$$
y la región se agota por completo después de
$$q_{\max}=\left\lfloor\frac{n(\alpha+\beta)}{\alpha^2+2\alpha\beta-\beta^2}\right\rfloor.$$
Así, la contribución para \((\alpha,\beta)\) fijo se cuenta como
$$\text{dos trapecios cerrados} - \text{un trapecio abierto}.$$
Para una clase residual concreta escribimos
$$q=2q'+\varepsilon_q,\qquad p=2p'+\varepsilon_p,\qquad \varepsilon_p,\varepsilon_q\in\{0,1\}.$$
Tras este cambio afín de variables, cada trapecio con restricción de paridad se convierte en un conteo ordinario de retícula con denominador duplicado. Los bordes cerrados se cuentan con el piso usual y los bordes abiertos se manejan desplazando el numerador una unidad hacia abajo. De ese modo, las tres clases residuales admisibles se reducen al mismo núcleo numérico: sumar pisos de expresiones lineales.
Para enteros \(A,B,M\) y un intervalo \(L \lt x \le U\), definimos
$$T(A,B,M;L,U)=\sum_{x=L+1}^{U}\left\lfloor\frac{Ax+B}{M}\right\rfloor.$$
Esta suma cuenta puntos de retícula por debajo de la recta racional \(y=(Ax+B)/M\). Para una cota superior estricta se usa \(\lfloor(Ax+B-1)/M\rfloor\). Las implementaciones evalúan estas sumas exactamente mediante una reducción de tipo euclidiano: primero separan las partes enteras de \(A/M\) y \(B/M\), y luego intercambian pendiente y denominador en el problema reducido. Cuando el intervalo ya es pequeño, se termina con suma directa. Como todas las regiones admisibles del paso 2 son trapecios, \(G(n)\) se obtiene por completo a partir de unas pocas floor-sums exactas.
Recorrer todos los pares generadores posibles sería un desperdicio cuando \(\alpha\) es grande. Por eso las implementaciones separan en
$$R=\left\lfloor\sqrt{\frac{3n}{2}}\right\rfloor.$$
Para \(\alpha \lt R\), se fija \((\alpha,\beta)\) y se cuentan directamente los pares \((p,q)\). En el rango complementario se invierte el punto de vista: se fija \((p,q)\) y se cuentan los \((\alpha,\beta)\) admisibles. Al transponer las desigualdades del paso 1 se obtiene
$$\beta \le \min\left(\frac{q}{p}\alpha,\frac{p-q}{3q-p}\alpha\right),\qquad \beta \gt \frac{p\alpha-n}{q}.$$
La pendiente superior activa cambia exactamente cuando
$$p^2=3q^2,$$
y eso explica la división en dos casos del segundo bucle principal. Es una descomposición clásica de tipo hipérbola: un barrido es eficiente para generadores pequeños y el barrido transpuesto lo es para generadores grandes.
Tras la normalización de paridad, toda configuración no primitiva es una dilatación impar de una configuración primitiva. Por tanto,
$$C(n)=G(n)-\sum_{\substack{d\ge 3\\ d\text{ impar}}} C\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
El mismo cociente \(\lfloor n/d\rfloor\) aparece para muchos valores impares consecutivos de \(d\), de modo que las implementaciones agrupan cocientes iguales y restan un único subproblema memorizado multiplicado por la cantidad de escalas impares del bloque.
Cuando \(n=10\), las escalas impares \(d\ge 3\) producen
$$\left\lfloor\frac{10}{3}\right\rfloor=3,\qquad \left\lfloor\frac{10}{5}\right\rfloor=2,\qquad \left\lfloor\frac{10}{7}\right\rfloor=\left\lfloor\frac{10}{9}\right\rfloor=1.$$
Entonces la recursión se reduce a
$$C(10)=G(10)-C(3)-C(2)-2C(1).$$
Dos escalas impares distintas colapsan al mismo subproblema \(C(1)\), que es exactamente la optimización explotada por la agrupación de cocientes. El punto de control usado por las implementaciones es \(C(10)=3\).
Las implementaciones en C++, Python y Java siguen exactamente el mismo plan. Primero calculan \(R=\lfloor\sqrt{3n/2}\rfloor\) y luego evalúan el conteo bruto \(G(n)\) recorriendo las tres clases de paridad admisibles. El primer barrido itera sobre la zona de generadores pequeños y suma los dos trapecios cerrados menos el trapecio abierto del paso 2. El segundo barrido cubre la zona complementaria fijando el par auxiliar y contando los trapecios transpuestos del paso 5. En ambos casos la paridad se impone con progresiones de paso \(2\) y con desplazamientos afines dentro del evaluador de floor-sums.
Una vez conocido \(G(n)\), la implementación calcula el total primitivo \(C(n)\) mediante recursión con memoización. Los valores ya resueltos se leen desde la caché, y la resta sobre dilataciones impares se agrupa por cocientes iguales \(\lfloor n/d\rfloor\). Así, cada argumento menor se resuelve una sola vez.
La parte geométrica de un subproblema distinto está organizada como una descomposición de tipo hipérbola. Los barridos directo y transpuesto generan conjuntamente unas \(O(n)\) evaluaciones de trapecios para un argumento de tamaño \(n\), y cada evaluación se reduce mediante transformaciones euclidianas de floor-sum, lo que da un coste aproximadamente logarítmico por llamada. La recursión de primitividad es mucho más barata que restar cada escala impar por separado, porque la memoización y la agrupación de cocientes colapsan muchas escalas al mismo argumento pequeño. En la práctica el método es claramente subcuadrático y muchísimo más rápido que enumerar triángulos directamente.
题目要求统计尺寸参数不超过 \(n\) 的原始整中线构型数量。直接从几何对象出发暴力枚举会非常慢。实现采用的做法是先把几何条件改写成一组整数参数不等式，再把计数问题变成若干有理梯形中的格点计数，最后再把由奇数倍缩放产生的非原始对象递归扣除。
记 \(G(n)\) 为尚未做原始性筛除之前的可行参数组总数，记 \(C(n)\) 为题目真正要求的原始计数。整个方法可以分成两层：先用精确格点计数求出 \(G(n)\)，再通过奇数倍缩放递归从 \(G(n)\) 中恢复出 \(C(n)\)。
在实现使用的参数化中，每一个可行构型都由两个正整数对 \((\alpha,\beta)\) 和 \((p,q)\) 来编码。可行条件写成
$$\alpha \gt \sqrt{3}\,\beta,\qquad \beta p \le \alpha q,\qquad (\alpha+\beta)p \gt (\alpha+3\beta)q,\qquad \alpha p-\beta q \le n.$$
除此以外还要满足奇偶限制。辅助参数对 \((p,q)\) 只能落在下面三种模 \(2\) 剩余类中：
$$ (p,q)\equiv (0,1),\ (1,0),\ (1,1)\pmod 2. $$
全偶类会对应到非原始编码，因此必须排除。与之配套的生成对 \((\alpha,\beta)\) 也只能按照兼容的奇偶步进前进，所以实现里不是逐个测试所有整数，而是直接按步长 \(2\) 枚举。
固定生成对 \((\alpha,\beta)\) 以后，把不等式整理成 \(p\) 关于 \(q\) 的范围，可得
$$\frac{\alpha+3\beta}{\alpha+\beta}q \lt p \le \min\left(\frac{\alpha}{\beta}q,\frac{\beta q+n}{\alpha}\right).$$
这说明对每个正整数 \(q\)，合法的 \(p\) 落在一条开边界直线之上，同时落在两条闭边界上界中的较小者之下。两条上界在
$$q_{\mathrm{sw}}=\left\lfloor\frac{\beta n}{\alpha^2-\beta^2}\right\rfloor$$
处发生切换，而整个区域在
$$q_{\max}=\left\lfloor\frac{n(\alpha+\beta)}{\alpha^2+2\alpha\beta-\beta^2}\right\rfloor$$
之后完全消失。因此，固定 \((\alpha,\beta)\) 的贡献可以拆成
$$\text{两个闭梯形} - \text{一个开梯形}.$$
这正是实现中几何计数的核心结构。
对某个给定的奇偶类，写成
$$q=2q'+\varepsilon_q,\qquad p=2p'+\varepsilon_p,\qquad \varepsilon_p,\varepsilon_q\in\{0,1\}.$$
做完这个仿射变量替换以后，每一个带奇偶约束的梯形都会变成一个分母翻倍的普通格点计数。闭边界可以直接用 floor 统计，开边界则通过把分子减去 \(1\) 来处理。这样一来，三个允许的剩余类都会归约成同一个数值核心：对线性表达式的 floor 值做求和。
对整数 \(A,B,M\) 和区间 \(L \lt x \le U\)，定义
$$T(A,B,M;L,U)=\sum_{x=L+1}^{U}\left\lfloor\frac{Ax+B}{M}\right\rfloor.$$
这个和正好统计位于有理直线 \(y=(Ax+B)/M\) 下方的格点数。若上界是严格不等式，则改用 \(\lfloor (Ax+B-1)/M\rfloor\)。实现并不是逐项累加这个和，而是使用欧几里得风格的 floor-sum 变换：先剥离 \(A/M\) 和 \(B/M\) 的整数部分，再在缩小后的问题中交换斜率和分母；当区间宽度足够小时，再回退到直接求和。由于步骤 2 中所有可行区域都是梯形，\(G(n)\) 的全部贡献都可以由少量这样的精确 floor-sum 得到。
如果对所有可能的生成对都直接枚举，那么当 \(\alpha\) 很大时会做很多无效工作。因此实现先在
$$R=\left\lfloor\sqrt{\frac{3n}{2}}\right\rfloor$$
处切开。对于 \(\alpha \lt R\)，直接固定 \((\alpha,\beta)\) 去计数 \((p,q)\)。对于补集区间，则反过来固定 \((p,q)\) 去计数可行的 \((\alpha,\beta)\)。把步骤 1 的不等式转置后得到
$$\beta \le \min\left(\frac{q}{p}\alpha,\frac{p-q}{3q-p}\alpha\right),\qquad \beta \gt \frac{p\alpha-n}{q}.$$
哪一条上界真正起作用，会在
$$p^2=3q^2$$
这个分界线上发生切换，这正是第二个主循环要分成两种情况的原因。这个结构本质上就是一种双曲线式拆分：小生成参数用一种枚举方向更高效，大生成参数则把角色对换后更高效。
经过奇偶标准化以后，每一个非原始构型都可以看成某个原始构型的奇数倍放大。因此有
$$C(n)=G(n)-\sum_{\substack{d\ge 3\\ d\text{ 为奇数}}} C\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
很多连续的奇数 \(d\) 会给出同一个商 \(\lfloor n/d\rfloor\)，所以实现不是逐个减，而是把相同商值合并成块。每一块只需要读取一次缓存中的子问题结果，再乘以该块中奇数缩放因子的个数即可。
当 \(n=10\) 时，所有满足 \(d\ge 3\) 的奇数缩放会产生
$$\left\lfloor\frac{10}{3}\right\rfloor=3,\qquad \left\lfloor\frac{10}{5}\right\rfloor=2,\qquad \left\lfloor\frac{10}{7}\right\rfloor=\left\lfloor\frac{10}{9}\right\rfloor=1.$$
于是递归可写成
$$C(10)=G(10)-C(3)-C(2)-2C(1).$$
可以看到，不同的奇数缩放 \(7\) 与 \(9\) 会落到同一个子问题 \(C(1)\) 上，这正是商值分块能够节省大量工作的原因。实现中的校验点给出 \(C(10)=3\)。
C++、Python 和 Java 三个实现遵循完全相同的数学流程。它们先计算 \(R=\lfloor\sqrt{3n/2}\rfloor\)，然后在三种允许的奇偶类上累加原始筛除之前的总数 \(G(n)\)。第一段循环处理较小的生成参数范围，对应步骤 2 中的两个闭梯形减去一个开梯形。第二段循环处理补集范围，它固定辅助参数对，再去统计步骤 5 中转置后的梯形区域。两段循环都会通过模 \(2\) 步进和仿射平移来强制奇偶约束，而实际的计数核心始终是同一个 floor-sum 例程。
在得到 \(G(n)\) 之后，实现再用带缓存的递归去求原始计数 \(C(n)\)。已经算过的小参数会直接从记忆化表中读取，奇数倍缩放的扣除则按照相同商值 \(\lfloor n/d\rfloor\) 成块处理，因此同一个子问题不会被反复求解。三种语言版本在数学上完全一致，只是语法不同。
每一个不同参数规模的几何子问题都被组织成一种双曲线式分解。直接枚举部分和转置枚举部分合在一起，对规模为 \(n\) 的参数大约会产生 \(O(n)\) 次梯形求值，而每一次梯形求值又会通过欧几里得式的 floor-sum 变换降到大致对数时间。原始性筛除的递归远比逐个处理所有奇数缩放便宜，因为记忆化和商值分块会把大量缩放合并到同一个较小参数上。实际运行中，这个方法显著低于平方复杂度，也远快于直接枚举候选三角形。
Нужно посчитать число примитивных конфигураций с целой медианой, у которых параметр размера не превосходит \(n\). Наивный перебор геометрических кандидатов был бы слишком медленным. Поэтому реализации сначала заменяют геометрию арифметической параметризацией, затем точно считают решётчатые точки внутри рациональных трапеций и только после этого рекурсивно вычитают непримитивные объекты, возникающие из нечётных масштабирований.
Обозначим через \(G(n)\) число допустимых наборов параметров до фильтрации по примитивности, а через \(C(n)\) итоговое примитивное количество, которое и требуется в задаче. Значит, решение состоит из двух слоёв: сначала точно вычислить \(G(n)\) как задачу подсчёта решётчатых точек, а затем восстановить \(C(n)\), вычитая нечётные растяжения меньших примитивных объектов.
В параметризации, используемой реализациями, каждая допустимая конфигурация кодируется двумя положительными парами \((\alpha,\beta)\) и \((p,q)\). Условия допустимости принимают вид
$$\alpha \gt \sqrt{3}\,\beta,\qquad \beta p \le \alpha q,\qquad (\alpha+\beta)p \gt (\alpha+3\beta)q,\qquad \alpha p-\beta q \le n.$$
Кроме того, присутствуют условия чётности. Вспомогательная пара \((p,q)\) может лежать только в классах
$$ (p,q)\equiv (0,1),\ (1,0),\ (1,1)\pmod 2, $$
потому что полностью чётный класс соответствовал бы непримитивному кодированию. Генерирующая пара \((\alpha,\beta)\) должна затем двигаться по совместимой чётно-нечётной прогрессии, поэтому в программе эти параметры перебираются с шагом \(2\).
Зафиксируем генерирующую пару \((\alpha,\beta)\). Тогда допустимый диапазон для \(p\) как функции от \(q\) можно записать так:
$$\frac{\alpha+3\beta}{\alpha+\beta}q \lt p \le \min\left(\frac{\alpha}{\beta}q,\frac{\beta q+n}{\alpha}\right).$$
Значит, для каждого положительного \(q\) допустимые значения \(p\) лежат выше одной открытой прямой и ниже меньшей из двух закрытых верхних границ. Эти две верхние границы меняются местами в точке
$$q_{\mathrm{sw}}=\left\lfloor\frac{\beta n}{\alpha^2-\beta^2}\right\rfloor,$$
а вся область исчезает после
$$q_{\max}=\left\lfloor\frac{n(\alpha+\beta)}{\alpha^2+2\alpha\beta-\beta^2}\right\rfloor.$$
Поэтому вклад фиксированной пары \((\alpha,\beta)\) считается как
$$\text{две закрытые трапеции} - \text{одна открытая трапеция}.$$
Для выбранного класса остатков пишем
$$q=2q'+\varepsilon_q,\qquad p=2p'+\varepsilon_p,\qquad \varepsilon_p,\varepsilon_q\in\{0,1\}.$$
После такой аффинной замены переменных каждая трапеция с условием на чётность превращается в обычный подсчёт решётчатых точек с удвоенным знаменателем. Закрытые границы считаются обычным floor, а открытые границы обрабатываются сдвигом числителя на \(1\) вниз. Тем самым все три допустимых класса остатков сводятся к одному и тому же численному ядру: сумме целых частей линейного выражения.
Для целых \(A,B,M\) и интервала \(L \lt x \le U\) введём
$$T(A,B,M;L,U)=\sum_{x=L+1}^{U}\left\lfloor\frac{Ax+B}{M}\right\rfloor.$$
Эта сумма считает решётчатые точки под рациональной прямой \(y=(Ax+B)/M\). Для строгой верхней границы используется \(\lfloor(Ax+B-1)/M\rfloor\). Реализации вычисляют такие суммы точно с помощью евклидова понижения: сначала отделяют целые части \(A/M\) и \(B/M\), затем в уменьшенной задаче меняют местами наклон и знаменатель. Когда ширина интервала становится маленькой, остаётся только прямое суммирование. Поскольку все допустимые области из шага 2 являются трапециями, весь \(G(n)\) складывается из небольшого числа таких точных floor-sum.
Если перебирать все возможные генерирующие пары напрямую, то при больших \(\alpha\) возникает много лишней работы. Поэтому реализации разделяют область по порогу
$$R=\left\lfloor\sqrt{\frac{3n}{2}}\right\rfloor.$$
При \(\alpha \lt R\) программа фиксирует \((\alpha,\beta)\) и напрямую считает пары \((p,q)\). В дополнительной области перспектива переворачивается: фиксируется \((p,q)\), а затем считаются допустимые \((\alpha,\beta)\). После транспонирования неравенств шага 1 получаем
$$\beta \le \min\left(\frac{q}{p}\alpha,\frac{p-q}{3q-p}\alpha\right),\qquad \beta \gt \frac{p\alpha-n}{q}.$$
Активная верхняя граница меняется ровно на линии
$$p^2=3q^2,$$
что и объясняет разбиение на два случая во втором большом цикле. Это классическая гиперболическая декомпозиция: один проход эффективен для малых генерирующих параметров, транспонированный проход эффективен для больших.
После нормализации по чётности каждый непримитивный объект является нечётным растяжением некоторого примитивного объекта. Поэтому
$$C(n)=G(n)-\sum_{\substack{d\ge 3\\ d\text{ нечётно}}} C\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
Один и тот же частный \(\lfloor n/d\rfloor\) возникает для многих последовательных нечётных значений \(d\), поэтому реализации группируют одинаковые частные в блоки и вычитают одно кэшированное подзадачное значение, умноженное на число нечётных масштабов в данном блоке.
Для \(n=10\) нечётные масштабы \(d\ge 3\) дают
$$\left\lfloor\frac{10}{3}\right\rfloor=3,\qquad \left\lfloor\frac{10}{5}\right\rfloor=2,\qquad \left\lfloor\frac{10}{7}\right\rfloor=\left\lfloor\frac{10}{9}\right\rfloor=1.$$
Значит, рекурсия принимает вид
$$C(10)=G(10)-C(3)-C(2)-2C(1).$$
Два разных нечётных масштаба сводятся к одному и тому же подзадачному значению \(C(1)\), и именно эту экономию использует группировка по частным. Контрольная точка реализаций даёт \(C(10)=3\).
Реализации на C++, Python и Java следуют одному и тому же плану. Сначала вычисляется \(R=\lfloor\sqrt{3n/2}\rfloor\), после чего суммируется сырое количество \(G(n)\) по трём допустимым классам чётности. Первый проход обрабатывает область малых генераторов и добавляет две закрытые трапеции, вычитая открытую трапецию из шага 2. Второй проход покрывает дополнительную область: он фиксирует вспомогательную пару и считает транспонированные трапеции из шага 5. В обоих проходах чётность обеспечивается шагом \(2\) по циклам и аффинными сдвигами внутри вычислителя floor-sum.
Когда \(G(n)\) уже найдено, реализация получает примитивный итог \(C(n)\) с помощью рекурсии с мемоизацией. Уже решённые меньшие аргументы берутся из кэша, а вычитание по нечётным масштабам группируется по одинаковым частным \(\lfloor n/d\rfloor\). Поэтому одна и та же подзадача не решается много раз.
Геометрическая часть одного различного подзадачного аргумента организована как гиперболическая декомпозиция. Прямой и транспонированный проходы вместе создают порядка \(O(n)\) вычислений трапеций для аргумента размера \(n\), а каждое такое вычисление благодаря евклидову понижению floor-sum стоит примерно логарифмическое время. Рекурсивная фильтрация по примитивности намного дешевле, чем отдельное вычитание каждого нечётного масштаба, потому что мемоизация и группировка частных сводят многие масштабы к одним и тем же меньшим аргументам. На практике алгоритм уверенно субквадратичен и намного быстрее прямого перебора треугольников.
المطلوب هو عدّ التراكيب الأولية ذات المتوسط الصحيح عندما لا يتجاوز معامل الحجم \(n\). الفحص المباشر لكل المرشحين الهندسيين بطيء جدًا. لذلك تعتمد التطبيقات على تحويل الوصف الهندسي إلى تمثيل حسابي، ثم تحسب نقاط الشبكة داخل أشباه منحرفات نسبية بدقة، وبعد ذلك فقط تطرح التراكيب غير الأولية الناتجة من التمديد بالعوامل الفردية.
لنكتب \(G(n)\) لعدد مجموعات المعلمات المقبولة قبل تصفية الأولية، ولتكن \(C(n)\) هي القيمة الأولية المطلوبة في المسألة. إذن الطريقة تعمل على طبقتين: أولًا نحسب \(G(n)\) بدقة كمسألة عدّ نقاط شبكة، ثم نستعيد \(C(n)\) بطرح التمديدات الفردية للأجسام الأولية الأصغر.
في التمثيل الذي تستخدمه التطبيقات، يُشفَّر كل تركيب مقبول بزوجين موجبين من الأعداد الصحيحة هما \((\alpha,\beta)\) و\((p,q)\). وتصبح الشروط
$$\alpha \gt \sqrt{3}\,\beta,\qquad \beta p \le \alpha q,\qquad (\alpha+\beta)p \gt (\alpha+3\beta)q,\qquad \alpha p-\beta q \le n.$$
وهناك أيضًا قيود على الزوجية. فالزوج المساعد \((p,q)\) لا يجوز أن ينتمي إلا إلى الفئات
$$ (p,q)\equiv (0,1),\ (1,0),\ (1,1)\pmod 2, $$
لأن الفئة الزوجية بالكامل تمثل ترميزًا غير أولي. وبعد اختيار هذه الفئة يجب أن يتحرك الزوج المولِّد \((\alpha,\beta)\) على التتابع الزوجي أو الفردي الموافق لها، ولهذا تسير الحلقات في التطبيق بخطوة مقدارها \(2\).
إذا ثبتنا الزوج المولِّد \((\alpha,\beta)\)، أمكن إعادة ترتيب المتباينات للحصول على المجال المسموح لـ \(p\) بدلالة \(q\):
$$\frac{\alpha+3\beta}{\alpha+\beta}q \lt p \le \min\left(\frac{\alpha}{\beta}q,\frac{\beta q+n}{\alpha}\right).$$
هذا يعني أن القيم الصحيحة المقبولة لـ \(p\) تقع فوق مستقيم مفتوح وتحت الأصغر من حدين علويين مغلقين. ويتبدل الحد العلوي الفعّال عند
$$q_{\mathrm{sw}}=\left\lfloor\frac{\beta n}{\alpha^2-\beta^2}\right\rfloor,$$
وتختفي المنطقة كلها بعد
$$q_{\max}=\left\lfloor\frac{n(\alpha+\beta)}{\alpha^2+2\alpha\beta-\beta^2}\right\rfloor.$$
إذن مساهمة كل \((\alpha,\beta)\) ثابتة تُحسب على صورة
$$\text{شبه منحرفين مغلقين} - \text{شبه منحرف مفتوح واحد}.$$
لفئة بواقي معينة نكتب
$$q=2q'+\varepsilon_q,\qquad p=2p'+\varepsilon_p,\qquad \varepsilon_p,\varepsilon_q\in\{0,1\}.$$
بعد هذا التحويل الأفيني، يتحول كل شبه منحرف مقيد بالزوجية إلى عدّ شبكة عادي لكن بمقام مضاعف. الحدود المغلقة تُحسب مباشرة باستعمال floor، أما الحدود المفتوحة فتُعالج بإنقاص البسط بمقدار \(1\). وهكذا تختزل الفئات الثلاث المسموح بها إلى نواة حسابية واحدة: جمع القيم الصحيحة الصغرى لتعابير خطية.
لأعداد صحيحة \(A,B,M\) ولفترة \(L \lt x \le U\)، نعرّف
$$T(A,B,M;L,U)=\sum_{x=L+1}^{U}\left\lfloor\frac{Ax+B}{M}\right\rfloor.$$
هذا المجموع يعد نقاط الشبكة الواقعة تحت المستقيم النسبي \(y=(Ax+B)/M\). وإذا كانت الحافة العليا مفتوحة استُخدم \(\lfloor(Ax+B-1)/M\rfloor\) بدلًا منه. تقوم التطبيقات بحساب هذه المجاميع بدقة عبر تخفيض من نمط خوارزمية إقليدس: تُفصل أولًا الأجزاء الصحيحة من \(A/M\) و\(B/M\)، ثم يُستبدل الميل بالمقام في المسألة المختزلة. وعندما يصبح عرض الفترة صغيرًا، يكفي الجمع المباشر. وبما أن كل المناطق المقبولة من الخطوة 2 هي أشباه منحرفات، فإن \(G(n)\) كله يُبنى من عدد صغير من هذه المجاميع الدقيقة.
المرور على كل الأزواج المولِّدة مباشرة يسبب عملاً زائدًا عندما تكون \(\alpha\) كبيرة. لذلك تقسم التطبيقات المجال عند
$$R=\left\lfloor\sqrt{\frac{3n}{2}}\right\rfloor.$$
عندما تكون \(\alpha \lt R\) يُثبَّت الزوج \((\alpha,\beta)\) وتُعد الأزواج \((p,q)\) مباشرة. أما في الجزء المتمم فيُعكس المنظور: نثبت \((p,q)\) ثم نعد الأزواج المقبولة \((\alpha,\beta)\). وبعد نقل متباينات الخطوة 1 نحصل على
$$\beta \le \min\left(\frac{q}{p}\alpha,\frac{p-q}{3q-p}\alpha\right),\qquad \beta \gt \frac{p\alpha-n}{q}.$$
ويتغير الحد العلوي الفعّال بالضبط عند
$$p^2=3q^2,$$
ومن هنا تأتي حالتا الحلقة الكبرى الثانية. هذه بنية كلاسيكية على نمط تقسيم القطع الزائد: مرور واحد مناسب للمولدات الصغيرة، والمرور المنقول مناسب للمولدات الكبيرة.
بعد التطبيع بحسب الزوجية، يصبح كل تركيب غير أولي مجرد تمديد فردي لتركيب أولي. لذلك
$$C(n)=G(n)-\sum_{\substack{d\ge 3\\ d\text{ فردي}}} C\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).$$
والقيمة نفسها \(\lfloor n/d\rfloor\) تتكرر لكثير من القيم الفردية المتتالية لـ \(d\)، ولهذا تجمع التطبيقات القيم المتساوية في كتل، ثم تطرح نتيجة فرعية واحدة محفوظة في الذاكرة مضروبة في عدد العوامل الفردية داخل تلك الكتلة.
عندما \(n=10\)، فإن العوامل الفردية \(d\ge 3\) تعطي
$$\left\lfloor\frac{10}{3}\right\rfloor=3,\qquad \left\lfloor\frac{10}{5}\right\rfloor=2,\qquad \left\lfloor\frac{10}{7}\right\rfloor=\left\lfloor\frac{10}{9}\right\rfloor=1.$$
ومن ثم تصبح العلاقة
$$C(10)=G(10)-C(3)-C(2)-2C(1).$$
أي إن عاملين فرديين مختلفين يهبطان إلى المسألة الفرعية نفسها \(C(1)\)، وهذا هو بالضبط السبب الذي يجعل تجميع الحواصل فعالًا. نقطة التحقق المستخدمة في التطبيقات هي \(C(10)=3\).
تتبع تطبيقات C++ وPython وJava الخطة الرياضية نفسها. فهي تبدأ بحساب \(R=\lfloor\sqrt{3n/2}\rfloor\)، ثم تجمع العدد الخام \(G(n)\) عبر فئات الزوجية الثلاث المسموح بها. المرور الأول يعالج المدى الصغير للمولدات ويضيف شبه المنحرفين المغلقين ثم يطرح شبه المنحرف المفتوح من الخطوة 2. والمرور الثاني يغطي المدى المتمم بتثبيت الزوج المساعد وعدّ أشباه المنحرفات المنقولة من الخطوة 5. وفي كلا المرورين تُفرض الزوجية عبر التقدم في فئات البواقي الصحيحة وعبر إزاحات أفينية داخل مقوم floor-sum.
بعد معرفة \(G(n)\)، يحسب التنفيذ القيمة الأولية \(C(n)\) باسترجاع ذي تخزين مؤقت. القيم الأصغر المحسوبة سابقًا تُقرأ من الذاكرة، وطرح المقاييس الفردية يُجمَّع حسب القيم المتساوية لـ \(\lfloor n/d\rfloor\)، ولذلك لا تُحل المسألة الفرعية نفسها أكثر من مرة.
الجزء الهندسي لكل مسألة فرعية مميزة منظم على شكل تقسيم من نمط القطع الزائد. والمروران المباشر والمنقول يولدان معًا نحو \(O(n)\) من تقييمات أشباه المنحرفات لوسيط حجمه \(n\)، وكل تقييم منها يُختزل بتحويلات floor-sum على النمط الإقليدي، ولذلك تكون كلفة النداء الواحد تقريبًا لوغاريتمية. أما استرجاع تصفية الأولية فهو أرخص بكثير من طرح كل مقياس فردي على حدة، لأن التخزين المؤقت وتجميع الحواصل يدمجان كثيرًا من المقاييس في الوسيط الأصغر نفسه. عمليًا تبقى الخوارزمية دون التربيعي بوضوح، وهي أسرع كثيرًا من تعداد المثلثات مباشرة.