Problem 883 asks for the value \(T(R_2)\) for remarkable triangles at \(R_2=2{,}000{,}000\). The implementations reduce the geometry to counting points in the triangular lattice, where a vector written in basis coordinates \((u,v)\) has squared length
$$Q(u,v)=u^2+uv+v^2.$$
The final answer is not obtained by one direct geometric count: it is a weighted sum over many scaled lattice counts, with Möbius inversion removing non-primitive overcounting.
The triangular-lattice geometry behind remarkable triangles is encoded by the quadratic form \(Q(u,v)=u^2+uv+v^2\). The problem therefore becomes an arithmetic-geometric counting problem built from this norm form.
For a threshold \(M\), define
$$A(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M\},$$
$$A_{\equiv}(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M,\ u\equiv v\pmod{3}\}.$$
The unrestricted count \(A(M)\) measures all admissible lattice vectors up to squared length \(M\). The restricted count \(A_{\equiv}(M)\) keeps only the congruence class needed when a factor of \(3\) has to be absorbed separately. The implementation evaluates these two families for many values of
$$M=\left\lfloor\frac{R_2^2}{t^2}\right\rfloor.$$
The key identity is
$$4Q(u,v)=(2v+u)^2+3u^2.$$
After fixing \(u\), the condition \(Q(u,v)\le M\) becomes
$$ (2v+u)^2\le 4M-3u^2. $$
So \(u\) only needs to range over
$$0\le u\le \left\lfloor\sqrt{\frac{4M}{3}}\right\rfloor.$$
If we set
$$s=\left\lfloor\sqrt{4M-3u^2}\right\rfloor,$$
then the admissible integers \(v\) satisfy
$$\left\lceil\frac{-u-s}{2}\right\rceil \le v \le \left\lfloor\frac{-u+s}{2}\right\rfloor.$$
The interval length gives the number of points for this \(u\). Because replacing \((u,v)\) by \((-u,-v)\) preserves \(Q\), the implementation loops over \(u\ge0\) and doubles the contribution whenever \(u>0\).
The restricted counter comes from the identity
$$Q(u,v)=u^2+uv+v^2=(u-v)^2+3uv,$$
which implies
$$Q(u,v)\equiv (u-v)^2 \pmod{3}.$$
Therefore
$$3\mid Q(u,v)\iff u\equiv v\pmod{3}.$$
This is why the second channel counts only those values of \(v\) in the interval above that satisfy \(v\equiv u\pmod{3}\). In Eisenstein-lattice language, the prime \(3\) is ramified, so multiples of \(3\) must be handled by a separate congruence condition rather than by the ordinary channel.
Let
$$n=3^{e_3}\prod_{p\equiv1\pmod{3}}p^{\alpha_p}\prod_{q\equiv2\pmod{3}}q^{\beta_q}.$$
The arithmetic part of the solution distinguishes the three Eisenstein prime types: split primes \(p\equiv1\pmod{3}\), inert primes \(q\equiv2\pmod{3}\), and the ramified prime \(3\). Define
$$\tau_2(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1)\prod_{q\equiv2\pmod{3}}(2\beta_q+1),$$
$$P_1(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1),\qquad \chi(n)=(-1)^{\sum_{q\equiv2\pmod{3}}\beta_q}.$$
The raw multiplicative weight used by the implementation is
$$f(n)= \begin{cases} \tau_2(n)\,(2e_3-1), & e_3\ge 1,\\[4pt] \dfrac{\tau_2(n)+\chi(n)P_1(n)}{2}, & e_3=0. \end{cases}$$
This formula comes directly from how the relevant similarity classes split according to the behavior of primes modulo \(3\). The factor \(3\) contributes differently from the other primes, which is why it is peeled off first.
The raw weight \(f(n)\) still counts configurations that share a nontrivial common divisor in the Eisenstein sense. To isolate the primitive contribution, the implementation applies Möbius inversion:
$$h(n)=(f*\mu)(n)=\sum_{d\mid n} f(d)\,\mu\!\left(\frac{n}{d}\right).$$
This Dirichlet convolution removes the contributions that come from scaling up a smaller primitive configuration.
For each \(n\le 3R_2\), the implementations attach a lattice count \(F_n\) to the weight \(h(n)\):
$$F_n= \begin{cases} A\!\left(\left\lfloor\frac{R_2^2}{n^2}\right\rfloor\right)-1, & 3\nmid n,\\[6pt] A_{\equiv}\!\left(\left\lfloor\frac{R_2^2}{(n/3)^2}\right\rfloor\right)-1, & 3\mid n. \end{cases}$$
The subtraction of \(1\) removes the origin. The main accumulated sum is
$$S(R_2)=\sum_{n=1}^{3R_2} h(n)\,F_n.$$
A final symmetry correction is then applied:
$$E(R_2)=\frac{A(R_2^2)-1}{3},\qquad \boxed{T(R_2)=S(R_2)-2E(R_2).}$$
The division by \(3\) is valid for the unrestricted nonzero lattice count and reflects the threefold rotational symmetry that would otherwise be counted too many times.
This is the smallest checkpoint used by the implementations, and it already shows every moving part. First, \(Q(u,v)\le1\) gives the origin plus the six unit directions, so
$$A(1)=7,\qquad A_{\equiv}(1)=1.$$
Hence
$$F_1=A(1)-1=6,\qquad F_3=A_{\equiv}(1)-1=0.$$
Next, compute the raw weights:
$$f(1)=1,\qquad f(2)=\frac{3+(-1)\cdot1}{2}=1,\qquad f(3)=1.$$
Using \(\mu(1)=1\), \(\mu(2)=-1\), and \(\mu(3)=-1\), Möbius inversion gives
$$h(1)=1,\qquad h(2)=f(1)\mu(2)+f(2)\mu(1)=0,\qquad h(3)=f(1)\mu(3)+f(3)\mu(1)=0.$$
Therefore only \(n=1\) contributes:
$$S(1)=1\cdot 6=6,\qquad E(1)=\frac{7-1}{3}=2,$$
so the final value is
$$T(1)=6-2\cdot2=2,$$
matching the validation output.
The C++, Python, and Java implementations follow the same pipeline. They first build a smallest-prime-factor table and the Möbius function up to \(3R_2\). That data is enough to factor every integer \(n\), evaluate the multiplicative weight \(f(n)\), and then form the primitive weight \(h(n)\) by Dirichlet convolution.
Separately, the implementation precomputes the geometric tables for every \(1\le t\le R_2\): the unrestricted lattice count and the congruence-restricted lattice count at \(M=\left\lfloor R_2^2/t^2\right\rfloor\). The C++ version parallelizes this heavy phase; the Java version performs the same logic directly; the Python version delegates to the compiled computation so that the arithmetic and geometric steps stay identical. Once those tables exist, the program performs one final pass over \(n\le 3R_2\), chooses the correct channel according to divisibility by \(3\), accumulates \(h(n)F_n\), and finally applies the symmetry correction \(2E(R_2)\).
For one threshold \(M\), the lattice counter runs through \(u=0,1,\dots,\left\lfloor\sqrt{4M/3}\right\rfloor\), so a single evaluation costs \(O(\sqrt{M})\) time and \(O(1)\) extra memory. Summed over all \(t\le R_2\), this becomes
$$\sum_{t=1}^{R_2} O\!\left(\sqrt{\frac{R_2^2}{t^2}}\right)=\sum_{t=1}^{R_2} O\!\left(\frac{R_2}{t}\right)=O(R_2\log R_2).$$
The sieve stage is linear or near-linear in \(3R_2\), and the Dirichlet-convolution pass costs \(O(R_2\log R_2)\) overall. Memory usage is \(O(R_2)\): the arithmetic arrays have length \(3R_2+1\), and the geometric tables have length \(R_2+1\). Parallel execution improves wall-clock time for the geometric phase but does not change the asymptotic bounds.
Problem 883 verlangt den Wert \(T(R_2)\) für bemerkenswerte Dreiecke bei \(R_2=2{,}000{,}000\). Die Implementierungen reduzieren die Geometrie auf Gitterpunktzählungen im Dreiecksgitter, wobei ein Vektor in Basis-Koordinaten \((u,v)\) die quadratische Länge
$$Q(u,v)=u^2+uv+v^2$$
besitzt. Die Endantwort entsteht nicht aus einer einzigen direkten Zählung, sondern aus einer gewichteten Summe vieler skalierter Gitterzählungen, wobei die Möbius-Inversion nichtprimitive Mehrfachzählungen entfernt.
Die Geometrie hinter den bemerkenswerten Dreiecken wird durch die quadratische Form \(Q(u,v)=u^2+uv+v^2\) beschrieben. Das Problem wird damit zu einer arithmetisch-geometrischen Zählaufgabe auf Basis dieser Normform.
Für einen Schwellwert \(M\) definieren wir
$$A(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M\},$$
$$A_{\equiv}(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M,\ u\equiv v\pmod{3}\}.$$
Die uneingeschränkte Funktion \(A(M)\) zählt alle zulässigen Gittervektoren bis zur quadratischen Länge \(M\). Die eingeschränkte Funktion \(A_{\equiv}(M)\) behält nur die Kongruenzklasse, die gebraucht wird, wenn ein Faktor \(3\) separat absorbiert werden muss. Die Implementierung wertet diese beiden Familien für viele Werte
$$M=\left\lfloor\frac{R_2^2}{t^2}\right\rfloor$$
aus.
Die Schlüsselidentität lautet
$$4Q(u,v)=(2v+u)^2+3u^2.$$
Für festes \(u\) wird die Bedingung \(Q(u,v)\le M\) also zu
$$ (2v+u)^2\le 4M-3u^2. $$
Daraus folgt sofort, dass nur
$$0\le u\le \left\lfloor\sqrt{\frac{4M}{3}}\right\rfloor$$
durchlaufen werden muss. Setzt man
$$s=\left\lfloor\sqrt{4M-3u^2}\right\rfloor,$$
dann erfüllen die zulässigen ganzzahligen \(v\) die Schranken
$$\left\lceil\frac{-u-s}{2}\right\rceil \le v \le \left\lfloor\frac{-u+s}{2}\right\rfloor.$$
Die Intervalllänge liefert die Punktzahl für dieses \(u\). Weil \((u,v)\mapsto(-u,-v)\) die Form \(Q\) unverändert lässt, iteriert die Implementierung nur über \(u\ge0\) und verdoppelt den Beitrag für \(u>0\).
Der eingeschränkte Zähler folgt aus
$$Q(u,v)=u^2+uv+v^2=(u-v)^2+3uv,$$
also
$$Q(u,v)\equiv (u-v)^2 \pmod{3}.$$
Damit gilt
$$3\mid Q(u,v)\iff u\equiv v\pmod{3}.$$
Genau deshalb zählt der zweite Kanal nur die Werte \(v\) im obigen Intervall mit \(v\equiv u\pmod{3}\). In der Sprache der Eisenstein-Ganzzahlen ist die Primzahl \(3\) ramifiziert; Vielfache von \(3\) werden deshalb nicht über den normalen Kanal, sondern über eine gesonderte Kongruenzbedingung behandelt.
Sei
$$n=3^{e_3}\prod_{p\equiv1\pmod{3}}p^{\alpha_p}\prod_{q\equiv2\pmod{3}}q^{\beta_q}.$$
Der arithmetische Teil der Lösung unterscheidet die drei Eisenstein-Primtypen: zerfallende Primzahlen \(p\equiv1\pmod{3}\), träge Primzahlen \(q\equiv2\pmod{3}\) und die ramifizierte Primzahl \(3\). Definiere
$$\tau_2(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1)\prod_{q\equiv2\pmod{3}}(2\beta_q+1),$$
$$P_1(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1),\qquad \chi(n)=(-1)^{\sum_{q\equiv2\pmod{3}}\beta_q}.$$
Das rohe multiplikative Gewicht lautet in der Implementierung
$$f(n)= \begin{cases} \tau_2(n)\,(2e_3-1), & e_3\ge 1,\\[4pt] \dfrac{\tau_2(n)+\chi(n)P_1(n)}{2}, & e_3=0. \end{cases}$$
Diese Formel spiegelt direkt wider, wie sich die relevanten Ähnlichkeitsklassen nach dem Verhalten der Primzahlen modulo \(3\) aufspalten. Der Faktor \(3\) trägt anders bei als die übrigen Primzahlen und wird deshalb zuerst herausgezogen.
Das rohe Gewicht \(f(n)\) zählt noch Konfigurationen mit einem nichttrivialen gemeinsamen Teiler im Eisenstein-Sinn. Um nur primitive Beiträge zu behalten, verwendet die Implementierung die Möbius-Inversion:
$$h(n)=(f*\mu)(n)=\sum_{d\mid n} f(d)\,\mu\!\left(\frac{n}{d}\right).$$
Diese Dirichlet-Faltung entfernt genau die Beiträge, die nur durch Aufskalieren einer kleineren primitiven Konfiguration entstehen.
Für jedes \(n\le 3R_2\) koppeln die Implementierungen an das Gewicht \(h(n)\) einen Gitterzähler \(F_n\):
$$F_n= \begin{cases} A\!\left(\left\lfloor\frac{R_2^2}{n^2}\right\rfloor\right)-1, & 3\nmid n,\\[6pt] A_{\equiv}\!\left(\left\lfloor\frac{R_2^2}{(n/3)^2}\right\rfloor\right)-1, & 3\mid n. \end{cases}$$
Die Subtraktion von \(1\) entfernt den Ursprung. Die Hauptsumme ist
$$S(R_2)=\sum_{n=1}^{3R_2} h(n)\,F_n.$$
Danach folgt noch eine Symmetrie-Korrektur:
$$E(R_2)=\frac{A(R_2^2)-1}{3},\qquad \boxed{T(R_2)=S(R_2)-2E(R_2).}$$
Die Division durch \(3\) ist für die uneingeschränkte nichtnullige Gitterpunktzahl zulässig und spiegelt eine dreifache Rotationssymmetrie wider, die sonst zu oft gezählt würde.
Dies ist der kleinste Prüfwert der Implementierungen und zeigt bereits alle wesentlichen Bausteine. Aus \(Q(u,v)\le1\) erhält man den Ursprung und die sechs Einheitsrichtungen, also
$$A(1)=7,\qquad A_{\equiv}(1)=1.$$
Daher gilt
$$F_1=A(1)-1=6,\qquad F_3=A_{\equiv}(1)-1=0.$$
Nun die rohen Gewichte:
$$f(1)=1,\qquad f(2)=\frac{3+(-1)\cdot1}{2}=1,\qquad f(3)=1.$$
Mit \(\mu(1)=1\), \(\mu(2)=-1\) und \(\mu(3)=-1\) ergibt die Möbius-Inversion
$$h(1)=1,\qquad h(2)=f(1)\mu(2)+f(2)\mu(1)=0,\qquad h(3)=f(1)\mu(3)+f(3)\mu(1)=0.$$
Also trägt nur \(n=1\) bei:
$$S(1)=1\cdot 6=6,\qquad E(1)=\frac{7-1}{3}=2,$$
und damit
$$T(1)=6-2\cdot2=2,$$
genau wie im Validierungslauf.
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst bauen sie eine Tabelle der kleinsten Primfaktoren und die Möbius-Funktion bis \(3R_2\) auf. Diese Daten genügen, um jedes \(n\) zu faktorisieren, das multiplikative Gewicht \(f(n)\) auszuwerten und anschließend per Dirichlet-Faltung das primitive Gewicht \(h(n)\) zu bilden.
Unabhängig davon berechnet die Implementierung für jedes \(1\le t\le R_2\) die geometrischen Tabellen vor: den uneingeschränkten Gitterzähler und den kongruenzbeschränkten Gitterzähler bei \(M=\left\lfloor R_2^2/t^2\right\rfloor\). Die C++-Version parallelisiert diese aufwendige Phase; die Java-Version führt dieselbe Logik direkt aus; die Python-Version delegiert an dieselbe kompilierte Berechnung, sodass Arithmetik und Geometrie identisch bleiben. Sind diese Tabellen aufgebaut, genügt ein letzter Durchlauf über \(n\le 3R_2\), um abhängig von der Teilbarkeit durch \(3\) den richtigen Kanal zu wählen, \(h(n)F_n\) zu akkumulieren und schließlich die Korrektur \(2E(R_2)\) anzuwenden.
Für einen einzelnen Schwellwert \(M\) läuft der Gitterzähler über \(u=0,1,\dots,\left\lfloor\sqrt{4M/3}\right\rfloor\); eine Auswertung kostet also \(O(\sqrt{M})\) Zeit und \(O(1)\) zusätzlichen Speicher. Über alle \(t\le R_2\) summiert sich das zu
$$\sum_{t=1}^{R_2} O\!\left(\sqrt{\frac{R_2^2}{t^2}}\right)=\sum_{t=1}^{R_2} O\!\left(\frac{R_2}{t}\right)=O(R_2\log R_2).$$
Der Siebteil ist linear oder nahezu linear in \(3R_2\), und der Dirichlet-Faltungsdurchlauf kostet insgesamt \(O(R_2\log R_2)\). Der Speicherbedarf ist \(O(R_2)\): die arithmetischen Arrays haben Länge \(3R_2+1\), die geometrischen Tabellen Länge \(R_2+1\). Parallelisierung verbessert die Laufzeit in der Geometriephase, ändert aber nicht die asymptotische Schranke.
Problem 883, \(R_2=2{,}000{,}000\) için dikkat çekici üçgenlerin sayımından türeyen \(T(R_2)\) değerini ister. Uygulamalar geometriyi üçgensel örgü üzerindeki nokta sayımına indirger; bu örgüde baz koordinatları \((u,v)\) olan bir vektörün karesel uzunluğu
$$Q(u,v)=u^2+uv+v^2$$
şeklindedir. Nihai sonuç tek bir doğrudan sayımdan gelmez; çok sayıda ölçeklenmiş örgü sayımı ağırlıklı olarak toplanır ve Möbius terslemesi ilkel olmayan tekrarları temizler.
Dikkat çekici üçgenlerin arkasındaki üçgensel örgü geometrisi \(Q(u,v)=u^2+uv+v^2\) kuadratik formuyla kodlanır. Böylece problem bu norm formu üzerinden kurulan aritmetik-geometrik bir sayım problemine dönüşür.
Bir \(M\) eşiği için
$$A(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M\},$$
$$A_{\equiv}(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M,\ u\equiv v\pmod{3}\}$$
tanımlarını yapalım. \(A(M)\), karesel uzunluğu \(M\)'yi aşmayan tüm örgü vektörlerini sayar. \(A_{\equiv}(M)\) ise, \(3\) faktörü ayrı ele alınırken gereken özel kongruens sınıfını korur. Uygulama bu iki fonksiyonu birçok
$$M=\left\lfloor\frac{R_2^2}{t^2}\right\rfloor$$
değeri için hesaplar.
Ana özdeşlik
$$4Q(u,v)=(2v+u)^2+3u^2$$
şeklindedir. Bu nedenle \(u\) sabitken \(Q(u,v)\le M\) koşulu
$$ (2v+u)^2\le 4M-3u^2 $$
olur. Buradan yalnızca
$$0\le u\le \left\lfloor\sqrt{\frac{4M}{3}}\right\rfloor$$
aralığının taranması gerektiği hemen görülür. Eğer
$$s=\left\lfloor\sqrt{4M-3u^2}\right\rfloor$$
alınırsa uygun tam sayı \(v\) değerleri
$$\left\lceil\frac{-u-s}{2}\right\rceil \le v \le \left\lfloor\frac{-u+s}{2}\right\rfloor$$
eşitsizliğini sağlar. Bu aralığın uzunluğu, ilgili \(u\) için nokta sayısını verir. \((u,v)\mapsto(-u,-v)\) dönüşümü \(Q\)'yu değiştirmediği için uygulama \(u\ge0\) üzerinden döner ve \(u>0\) olduğunda katkıyı ikiyle çarpar.
Kısıtlı sayaç rastgele seçilmez. Çünkü
$$Q(u,v)=u^2+uv+v^2=(u-v)^2+3uv,$$
dolayısıyla
$$Q(u,v)\equiv (u-v)^2 \pmod{3}.$$
Bundan
$$3\mid Q(u,v)\iff u\equiv v\pmod{3}$$
çıkar. İşte bu yüzden ikinci kanal, yukarıdaki aralıkta yalnızca \(v\equiv u\pmod{3}\) olan değerleri sayar. Eisenstein örgüsü açısından bakıldığında \(3\) ramifiye asaldır; bu nedenle \(3\)'ün katları normal kanalla değil, ayrı bir kongruens koşuluyla ele alınır.
Şimdi
$$n=3^{e_3}\prod_{p\equiv1\pmod{3}}p^{\alpha_p}\prod_{q\equiv2\pmod{3}}q^{\beta_q}$$
olsun. Çözümün aritmetik tarafı üç Eisenstein asal tipini ayırır: ayrışan asallar \(p\equiv1\pmod{3}\), inert kalan asallar \(q\equiv2\pmod{3}\) ve ramifiye asal \(3\). Şunları tanımlayalım:
$$\tau_2(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1)\prod_{q\equiv2\pmod{3}}(2\beta_q+1),$$
$$P_1(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1),\qquad \chi(n)=(-1)^{\sum_{q\equiv2\pmod{3}}\beta_q}.$$
Uygulamanın kullandığı ham çarpımsal ağırlık
$$f(n)= \begin{cases} \tau_2(n)\,(2e_3-1), & e_3\ge 1,\\[4pt] \dfrac{\tau_2(n)+\chi(n)P_1(n)}{2}, & e_3=0 \end{cases}$$
şeklindedir. Bu formül, ilgili benzerlik sınıflarının asalların mod \(3\) davranışına göre nasıl ayrıldığını doğrudan yansıtır. \(3\) faktörü diğer asallardan farklı katkı verdiği için önce ayrılır.
Ham ağırlık \(f(n)\) hâlâ Eisenstein anlamında ortak böleni olan konfigürasyonları içerir. İlkel katkıyı ayırmak için uygulama Möbius terslemesi uygular:
$$h(n)=(f*\mu)(n)=\sum_{d\mid n} f(d)\,\mu\!\left(\frac{n}{d}\right).$$
Bu Dirichlet konvolüsyonu, daha küçük bir ilkel konfigürasyonun büyütülmüş kopyalarından gelen katkıları çıkarır.
Her \(n\le 3R_2\) için uygulamalar, \(h(n)\) ağırlığına bir örgü sayımı \(F_n\) bağlar:
$$F_n= \begin{cases} A\!\left(\left\lfloor\frac{R_2^2}{n^2}\right\rfloor\right)-1, & 3\nmid n,\\[6pt] A_{\equiv}\!\left(\left\lfloor\frac{R_2^2}{(n/3)^2}\right\rfloor\right)-1, & 3\mid n. \end{cases}$$
Buradaki \(1\) çıkarımı orijini siler. Ana toplam
$$S(R_2)=\sum_{n=1}^{3R_2} h(n)\,F_n$$
olur. Sonra bir simetri düzeltmesi uygulanır:
$$E(R_2)=\frac{A(R_2^2)-1}{3},\qquad \boxed{T(R_2)=S(R_2)-2E(R_2).}$$
\(3\)'e bölme, sıfır dışı serbest örgü nokta sayımı için geçerlidir ve aksi halde fazla sayılacak üçlü dönme simetrisini düzeltir.
Bu, uygulamaların kullandığı en küçük doğrulama örneğidir ve bütün parçaları gösterir. Önce \(Q(u,v)\le1\) eşitsizliği orijin ile altı birim yönü verir:
$$A(1)=7,\qquad A_{\equiv}(1)=1.$$
Dolayısıyla
$$F_1=A(1)-1=6,\qquad F_3=A_{\equiv}(1)-1=0.$$
Ham ağırlıklar ise
$$f(1)=1,\qquad f(2)=\frac{3+(-1)\cdot1}{2}=1,\qquad f(3)=1$$
olur. \(\mu(1)=1\), \(\mu(2)=-1\) ve \(\mu(3)=-1\) ile Möbius terslemesi
$$h(1)=1,\qquad h(2)=f(1)\mu(2)+f(2)\mu(1)=0,\qquad h(3)=f(1)\mu(3)+f(3)\mu(1)=0$$
sonucunu verir. Böylece yalnızca \(n=1\) katkı yapar:
$$S(1)=1\cdot 6=6,\qquad E(1)=\frac{7-1}{3}=2,$$
ve nihai değer
$$T(1)=6-2\cdot2=2$$
olur; bu da doğrulama çıktısıyla aynıdır.
C++, Python ve Java uygulamaları aynı işlem hattını izler. Önce \(3R_2\)'ye kadar en küçük asal bölen tablosu ve Möbius fonksiyonu kurulur. Bu bilgi, her \(n\)'yi çarpanlarına ayırmak, çarpımsal ağırlık \(f(n)\)'yi hesaplamak ve ardından Dirichlet konvolüsyonu ile ilkel ağırlık \(h(n)\)'yi üretmek için yeterlidir.
Bundan bağımsız olarak uygulama, her \(1\le t\le R_2\) için geometrik tabloları önceden hesaplar: \(M=\left\lfloor R_2^2/t^2\right\rfloor\) noktasındaki serbest örgü sayımı ve kongruens kısıtlı örgü sayımı. C++ sürümü bu ağır aşamayı paralelleştirir; Java sürümü aynı mantığı doğrudan uygular; Python sürümü ise aynı derlenmiş hesabı çağırır, böylece aritmetik ve geometrik adımlar birebir korunur. Bu tablolar hazır olunca program \(n\le 3R_2\) üzerinde son bir geçiş yapar, \(3\)'e bölünebilirliğe göre doğru kanalı seçer, \(h(n)F_n\) toplamını oluşturur ve en sonda \(2E(R_2)\) düzeltmesini uygular.
Tek bir \(M\) eşiği için örgü sayacı \(u=0,1,\dots,\left\lfloor\sqrt{4M/3}\right\rfloor\) üzerinden gider; dolayısıyla tek değerlendirme \(O(\sqrt{M})\) zaman ve \(O(1)\) ek bellek gerektirir. Tüm \(t\le R_2\) için bu toplam
$$\sum_{t=1}^{R_2} O\!\left(\sqrt{\frac{R_2^2}{t^2}}\right)=\sum_{t=1}^{R_2} O\!\left(\frac{R_2}{t}\right)=O(R_2\log R_2)$$
olur. Elek aşaması \(3R_2\) içinde lineer ya da lineere yakın davranır; Dirichlet konvolüsyon geçişi toplamda \(O(R_2\log R_2)\) maliyetlidir. Bellek kullanımı \(O(R_2)\)'dir: aritmetik diziler \(3R_2+1\), geometrik tablolar \(R_2+1\) uzunluğundadır. Paralel yürütme, geometrik aşamanın duvar saati süresini düşürür ama asimptotik sınırları değiştirmez.
El problema 883 pide el valor \(T(R_2)\) para los triángulos notables cuando \(R_2=2{,}000{,}000\). Las implementaciones reducen la geometría a un conteo de puntos en la retícula triangular, donde un vector con coordenadas de base \((u,v)\) tiene longitud cuadrática
$$Q(u,v)=u^2+uv+v^2.$$
La respuesta final no sale de un único conteo geométrico directo: es una suma ponderada de muchos conteos escalados de retícula, y la inversión de Möbius elimina las sobrecuentas no primitivas.
La geometría de los triángulos notables queda codificada por la forma cuadrática \(Q(u,v)=u^2+uv+v^2\). Por eso el problema se transforma en una tarea de conteo aritmético-geométrico construida a partir de esta forma normada.
Para un umbral \(M\), definimos
$$A(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M\},$$
$$A_{\equiv}(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M,\ u\equiv v\pmod{3}\}.$$
La función \(A(M)\) cuenta todos los vectores admisibles de la retícula con longitud cuadrática a lo sumo \(M\). La función \(A_{\equiv}(M)\) conserva sólo la clase de congruencia necesaria cuando un factor \(3\) debe tratarse por separado. La implementación evalúa ambas familias para muchos valores de
$$M=\left\lfloor\frac{R_2^2}{t^2}\right\rfloor.$$
La identidad clave es
$$4Q(u,v)=(2v+u)^2+3u^2.$$
Entonces, al fijar \(u\), la condición \(Q(u,v)\le M\) se convierte en
$$ (2v+u)^2\le 4M-3u^2. $$
Eso implica que basta recorrer
$$0\le u\le \left\lfloor\sqrt{\frac{4M}{3}}\right\rfloor.$$
Si definimos
$$s=\left\lfloor\sqrt{4M-3u^2}\right\rfloor,$$
entonces los enteros \(v\) admisibles satisfacen
$$\left\lceil\frac{-u-s}{2}\right\rceil \le v \le \left\lfloor\frac{-u+s}{2}\right\rfloor.$$
La longitud de ese intervalo da el número de puntos para este valor de \(u\). Como la transformación \((u,v)\mapsto(-u,-v)\) preserva \(Q\), la implementación recorre sólo \(u\ge0\) y duplica la contribución cuando \(u>0\).
El contador restringido sale de
$$Q(u,v)=u^2+uv+v^2=(u-v)^2+3uv,$$
de donde se obtiene
$$Q(u,v)\equiv (u-v)^2 \pmod{3}.$$
Por tanto,
$$3\mid Q(u,v)\iff u\equiv v\pmod{3}.$$
Ésa es la razón exacta por la que el segundo canal cuenta sólo los valores de \(v\) del intervalo anterior con \(v\equiv u\pmod{3}\). En el lenguaje de los enteros de Eisenstein, el primo \(3\) es ramificado, así que sus múltiplos necesitan una condición de congruencia separada.
Sea
$$n=3^{e_3}\prod_{p\equiv1\pmod{3}}p^{\alpha_p}\prod_{q\equiv2\pmod{3}}q^{\beta_q}.$$
La parte aritmética distingue los tres tipos de primos de Eisenstein: los primos escindidos \(p\equiv1\pmod{3}\), los primos inertes \(q\equiv2\pmod{3}\) y el primo ramificado \(3\). Definimos
$$\tau_2(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1)\prod_{q\equiv2\pmod{3}}(2\beta_q+1),$$
$$P_1(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1),\qquad \chi(n)=(-1)^{\sum_{q\equiv2\pmod{3}}\beta_q}.$$
El peso multiplicativo bruto que usa la implementación es
$$f(n)= \begin{cases} \tau_2(n)\,(2e_3-1), & e_3\ge 1,\\[4pt] \dfrac{\tau_2(n)+\chi(n)P_1(n)}{2}, & e_3=0. \end{cases}$$
Esta fórmula refleja directamente cómo se descomponen las clases de semejanza relevantes según el comportamiento de los primos módulo \(3\). El factor \(3\) aporta de manera distinta y por eso se separa primero.
El peso bruto \(f(n)\) todavía cuenta configuraciones que comparten un divisor común no trivial en el sentido de Eisenstein. Para aislar la contribución primitiva, la implementación aplica la inversión de Möbius:
$$h(n)=(f*\mu)(n)=\sum_{d\mid n} f(d)\,\mu\!\left(\frac{n}{d}\right).$$
Esta convolución de Dirichlet elimina exactamente las contribuciones que provienen de ampliar una configuración primitiva más pequeña.
Para cada \(n\le 3R_2\), las implementaciones asocian al peso \(h(n)\) un conteo de retícula \(F_n\):
$$F_n= \begin{cases} A\!\left(\left\lfloor\frac{R_2^2}{n^2}\right\rfloor\right)-1, & 3\nmid n,\\[6pt] A_{\equiv}\!\left(\left\lfloor\frac{R_2^2}{(n/3)^2}\right\rfloor\right)-1, & 3\mid n. \end{cases}$$
La resta de \(1\) elimina el origen. La suma principal es
$$S(R_2)=\sum_{n=1}^{3R_2} h(n)\,F_n.$$
Después se aplica una corrección final de simetría:
$$E(R_2)=\frac{A(R_2^2)-1}{3},\qquad \boxed{T(R_2)=S(R_2)-2E(R_2).}$$
La división entre \(3\) es válida para el conteo no nulo sin restricción y corrige una simetría rotacional triple que, de otro modo, quedaría contada de más.
Éste es el punto de control más pequeño usado por las implementaciones y ya muestra todos los componentes. Primero, \(Q(u,v)\le1\) da el origen más las seis direcciones unitarias, de modo que
$$A(1)=7,\qquad A_{\equiv}(1)=1.$$
Así,
$$F_1=A(1)-1=6,\qquad F_3=A_{\equiv}(1)-1=0.$$
Ahora calculemos los pesos brutos:
$$f(1)=1,\qquad f(2)=\frac{3+(-1)\cdot1}{2}=1,\qquad f(3)=1.$$
Usando \(\mu(1)=1\), \(\mu(2)=-1\) y \(\mu(3)=-1\), la inversión de Möbius produce
$$h(1)=1,\qquad h(2)=f(1)\mu(2)+f(2)\mu(1)=0,\qquad h(3)=f(1)\mu(3)+f(3)\mu(1)=0.$$
Por tanto, sólo contribuye \(n=1\):
$$S(1)=1\cdot 6=6,\qquad E(1)=\frac{7-1}{3}=2,$$
y el valor final es
$$T(1)=6-2\cdot2=2,$$
en acuerdo con la validación.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero construyen la tabla del menor factor primo y la función de Möbius hasta \(3R_2\). Eso basta para factorizar cada entero \(n\), evaluar el peso multiplicativo \(f(n)\) y luego obtener el peso primitivo \(h(n)\) mediante convolución de Dirichlet.
Por separado, la implementación precalcula para todo \(1\le t\le R_2\) las tablas geométricas: el conteo irrestricto de retícula y el conteo con restricción de congruencia en \(M=\left\lfloor R_2^2/t^2\right\rfloor\). La versión en C++ paraleliza esta fase costosa; la versión en Java ejecuta la misma lógica de forma directa; la versión en Python delega el cálculo pesado a la misma rutina compilada, de modo que los pasos aritméticos y geométricos se mantengan idénticos. Una vez construidas esas tablas, el programa hace un único recorrido final sobre \(n\le 3R_2\), elige el canal correcto según la divisibilidad por \(3\), acumula \(h(n)F_n\) y al final aplica la corrección \(2E(R_2)\).
Para un solo umbral \(M\), el contador de retícula recorre \(u=0,1,\dots,\left\lfloor\sqrt{4M/3}\right\rfloor\), así que una evaluación cuesta \(O(\sqrt{M})\) tiempo y \(O(1)\) memoria extra. Sumado sobre todos los \(t\le R_2\), esto se convierte en
$$\sum_{t=1}^{R_2} O\!\left(\sqrt{\frac{R_2^2}{t^2}}\right)=\sum_{t=1}^{R_2} O\!\left(\frac{R_2}{t}\right)=O(R_2\log R_2).$$
La etapa de criba es lineal o casi lineal en \(3R_2\), y el paso de convolución de Dirichlet cuesta \(O(R_2\log R_2)\) en total. El uso de memoria es \(O(R_2)\): los arreglos aritméticos tienen longitud \(3R_2+1\) y las tablas geométricas tienen longitud \(R_2+1\). La paralelización mejora el tiempo real de la fase geométrica, pero no cambia las cotas asintóticas.
第 883 题要求在 \(R_2=2{,}000{,}000\) 时求出与“Remarkable Triangles”对应的 \(T(R_2)\)。实现并不是直接枚举三角形，而是先把几何问题改写成三角晶格上的格点计数问题。在这套基底下，坐标为 \((u,v)\) 的向量平方长度是
$$Q(u,v)=u^2+uv+v^2.$$
最终答案来自许多不同尺度上的格点计数，再用数论权重做加权求和，并用 Möbius 反演去掉非原始对象的重复贡献。
“Remarkable Triangles”背后的几何结构由二元二次型 \(Q(u,v)=u^2+uv+v^2\) 编码。于是整个问题可以理解为：先研究这个范数形式下的格点分布，再把它和按素因子结构构造的算术权函数结合起来。
对任意阈值 \(M\)，定义两个基础计数函数：
$$A(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M\},$$
$$A_{\equiv}(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M,\ u\equiv v\pmod{3}\}.$$
\(A(M)\) 统计所有平方长度不超过 \(M\) 的晶格向量；\(A_{\equiv}(M)\) 则只保留满足 \(u\equiv v\pmod{3}\) 的那一部分。第二个计数并不是额外的人为限制，而是专门用来处理素数 \(3\) 的特殊行为。实现需要对很多
$$M=\left\lfloor\frac{R_2^2}{t^2}\right\rfloor$$
的取值同时求出这两类计数。
核心恒等式是
$$4Q(u,v)=(2v+u)^2+3u^2.$$
因此当 \(u\) 固定时，不等式 \(Q(u,v)\le M\) 等价于
$$ (2v+u)^2\le 4M-3u^2. $$
这马上给出 \(u\) 的范围：
$$0\le u\le \left\lfloor\sqrt{\frac{4M}{3}}\right\rfloor.$$
再令
$$s=\left\lfloor\sqrt{4M-3u^2}\right\rfloor,$$
那么所有可行的整数 \(v\) 恰好落在区间
$$\left\lceil\frac{-u-s}{2}\right\rceil \le v \le \left\lfloor\frac{-u+s}{2}\right\rfloor$$
内。区间长度就是这个 \(u\) 对总计数的贡献。由于变换 \((u,v)\mapsto(-u,-v)\) 不改变 \(Q\)，实现只遍历 \(u\ge0\)，并在 \(u>0\) 时把贡献翻倍。
二次型还可以写成
$$Q(u,v)=u^2+uv+v^2=(u-v)^2+3uv,$$
所以在模 \(3\) 下有
$$Q(u,v)\equiv (u-v)^2 \pmod{3}.$$
于是得到一个非常关键的判别：
$$3\mid Q(u,v)\iff u\equiv v\pmod{3}.$$
这正是第二个计数函数 \(A_{\equiv}(M)\) 的来源。它统计的并不是“任意一个方便的子集”，而是恰好对应于范数被 \(3\) 整除的那些点。在 Eisenstein 整数的语言里，素数 \(3\) 是 ramified prime，所以它不能和其他素数一样简单地走普通通道，必须单独分出一个模 \(3\) 条件。
设
$$n=3^{e_3}\prod_{p\equiv1\pmod{3}}p^{\alpha_p}\prod_{q\equiv2\pmod{3}}q^{\beta_q}.$$
实现中的算术部分会区分三类 Eisenstein 素数行为：
\(p\equiv1\pmod{3}\) 的素数在 Eisenstein 整数中分裂，\(q\equiv2\pmod{3}\) 的素数保持惰性，而 \(3\) 是分歧素数。接着定义
$$\tau_2(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1)\prod_{q\equiv2\pmod{3}}(2\beta_q+1),$$
$$P_1(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1),\qquad \chi(n)=(-1)^{\sum_{q\equiv2\pmod{3}}\beta_q}.$$
实现实际使用的原始乘法权函数是
$$f(n)= \begin{cases} \tau_2(n)\,(2e_3-1), & e_3\ge 1,\\[4pt] \dfrac{\tau_2(n)+\chi(n)P_1(n)}{2}, & e_3=0. \end{cases}$$
这个公式直接反映了相关相似类在模 \(3\) 的不同素数类型下如何分裂。尤其是 \(3\) 的贡献规则与其他素数不同，所以代码会先把 \(3\) 的指数单独剥离出来。
原始权函数 \(f(n)\) 仍然包含了带有共同 Eisenstein 因子的配置，也就是同一个原始对象被整体放大后的重复项。为了只保留 primitive contribution，实现使用 Möbius 反演：
$$h(n)=(f*\mu)(n)=\sum_{d\mid n} f(d)\,\mu\!\left(\frac{n}{d}\right).$$
这里的 \(*\) 是 Dirichlet 卷积。它的作用就是通过包含排除，把那些只是更小原始配置的整数倍放大版全部扣掉。
对每个 \(n\le 3R_2\)，实现都会把一个格点计数 \(F_n\) 乘到权重 \(h(n)\) 上：
$$F_n= \begin{cases} A\!\left(\left\lfloor\frac{R_2^2}{n^2}\right\rfloor\right)-1, & 3\nmid n,\\[6pt] A_{\equiv}\!\left(\left\lfloor\frac{R_2^2}{(n/3)^2}\right\rfloor\right)-1, & 3\mid n. \end{cases}$$
减去 \(1\) 的原因是要去掉原点。于是主和式为
$$S(R_2)=\sum_{n=1}^{3R_2} h(n)\,F_n.$$
最后还要再做一次对称性修正：
$$E(R_2)=\frac{A(R_2^2)-1}{3},\qquad \boxed{T(R_2)=S(R_2)-2E(R_2).}$$
这里除以 \(3\) 是成立的，因为无原点的总格点数天然按三重旋转对称分组。若不减去这部分修正，同一类方向会被多算。
这是实现里最小的校验点，而且足以展示整套机制。先看几何部分：不等式 \(Q(u,v)\le1\) 给出原点和六个单位方向，所以
$$A(1)=7,\qquad A_{\equiv}(1)=1.$$
于是
$$F_1=A(1)-1=6,\qquad F_3=A_{\equiv}(1)-1=0.$$
再算原始权重：
$$f(1)=1,\qquad f(2)=\frac{3+(-1)\cdot1}{2}=1,\qquad f(3)=1.$$
利用 \(\mu(1)=1\)、\(\mu(2)=-1\)、\(\mu(3)=-1\)，Möbius 反演得到
$$h(1)=1,\qquad h(2)=f(1)\mu(2)+f(2)\mu(1)=0,\qquad h(3)=f(1)\mu(3)+f(3)\mu(1)=0.$$
因此只有 \(n=1\) 有贡献：
$$S(1)=1\cdot 6=6,\qquad E(1)=\frac{7-1}{3}=2,$$
从而
$$T(1)=6-2\cdot2=2,$$
与实现中的校验结果完全一致。
C++、Python 和 Java 三个实现遵循同一条计算流水线。首先建立到 \(3R_2\) 为止的最小素因子表和 Möbius 函数。有了这些数据，就可以快速分解每个 \(n\)，求出乘法权函数 \(f(n)\)，再通过 Dirichlet 卷积得到原始对象对应的权函数 \(h(n)\)。
另一方面，实现会对所有 \(1\le t\le R_2\) 预计算几何表：也就是在 \(M=\left\lfloor R_2^2/t^2\right\rfloor\) 下的无约束格点计数与模 \(3\) 受限格点计数。C++ 版本把这一步并行化；Java 版本直接按同样逻辑执行；Python 版本则把重计算委托给编译后的核心实现，因此三种语言在数学流程上保持一致。最后程序只需再遍历一次 \(n\le 3R_2\)，按是否被 \(3\) 整除选择对应通道，累加 \(h(n)F_n\)，再减去修正项 \(2E(R_2)\) 即可。
对于单个阈值 \(M\)，格点计数器只需要遍历 \(u=0,1,\dots,\left\lfloor\sqrt{4M/3}\right\rfloor\)，所以单次计算耗时 \(O(\sqrt{M})\)，额外空间 \(O(1)\)。把所有 \(t\le R_2\) 的工作加起来，得到
$$\sum_{t=1}^{R_2} O\!\left(\sqrt{\frac{R_2^2}{t^2}}\right)=\sum_{t=1}^{R_2} O\!\left(\frac{R_2}{t}\right)=O(R_2\log R_2).$$
筛法部分对 \(3R_2\) 来说是线性或接近线性的；Dirichlet 卷积总体为 \(O(R_2\log R_2)\)。空间复杂度是 \(O(R_2)\)：算术数组长度约为 \(3R_2+1\)，几何表长度约为 \(R_2+1\)。并行只会改善几何阶段的实际运行时间，不会改变渐近复杂度。
В задаче 883 требуется вычислить значение \(T(R_2)\) для remarkable triangles при \(R_2=2{,}000{,}000\). Реализации не перебирают треугольники напрямую, а сводят геометрию к подсчёту точек треугольной решётки. В выбранном базисе вектор с координатами \((u,v)\) имеет квадрат длины
$$Q(u,v)=u^2+uv+v^2.$$
Итоговый ответ получается как взвешенная сумма многих масштабированных решёточных подсчётов, а инверсия Мёбиуса удаляет вклады непервичных объектов.
Геометрия, лежащая в основе remarkable triangles, кодируется квадратичной формой \(Q(u,v)=u^2+uv+v^2\). Поэтому вся задача превращается в арифметико-геометрический подсчёт, построенный вокруг этой нормы.
Для порога \(M\) введём
$$A(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M\},$$
$$A_{\equiv}(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M,\ u\equiv v\pmod{3}\}.$$
Функция \(A(M)\) считает все допустимые решёточные векторы с квадратом длины не больше \(M\). Функция \(A_{\equiv}(M)\) оставляет только ту класс-конгруэнцию, которая нужна для отдельной обработки множителя \(3\). Реализация вычисляет обе функции для многих значений
$$M=\left\lfloor\frac{R_2^2}{t^2}\right\rfloor.$$
Ключевое тождество имеет вид
$$4Q(u,v)=(2v+u)^2+3u^2.$$
Поэтому при фиксированном \(u\) условие \(Q(u,v)\le M\) переписывается как
$$ (2v+u)^2\le 4M-3u^2. $$
Сразу видно, что достаточно перебирать
$$0\le u\le \left\lfloor\sqrt{\frac{4M}{3}}\right\rfloor.$$
Если положить
$$s=\left\lfloor\sqrt{4M-3u^2}\right\rfloor,$$
то допустимые целые \(v\) удовлетворяют неравенствам
$$\left\lceil\frac{-u-s}{2}\right\rceil \le v \le \left\lfloor\frac{-u+s}{2}\right\rfloor.$$
Длина этого интервала и есть число точек для данного \(u\). Так как преобразование \((u,v)\mapsto(-u,-v)\) сохраняет \(Q\), реализация проходит только по \(u\ge0\) и удваивает вклад при \(u>0\).
Ограниченный счётчик возникает из равенства
$$Q(u,v)=u^2+uv+v^2=(u-v)^2+3uv,$$
откуда следует
$$Q(u,v)\equiv (u-v)^2 \pmod{3}.$$
Следовательно,
$$3\mid Q(u,v)\iff u\equiv v\pmod{3}.$$
Именно поэтому второй канал считает только те значения \(v\) из найденного интервала, которые удовлетворяют \(v\equiv u\pmod{3}\). В терминах целых Эйзенштейна простое число \(3\) является разветвлённым, поэтому его вклады нельзя обрабатывать тем же способом, что и остальные простые.
Пусть
$$n=3^{e_3}\prod_{p\equiv1\pmod{3}}p^{\alpha_p}\prod_{q\equiv2\pmod{3}}q^{\beta_q}.$$
Арифметическая часть решения различает три типа простых в кольце Эйзенштейна: расщепляющиеся \(p\equiv1\pmod{3}\), инертные \(q\equiv2\pmod{3}\) и разветвлённое простое \(3\). Введём
$$\tau_2(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1)\prod_{q\equiv2\pmod{3}}(2\beta_q+1),$$
$$P_1(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1),\qquad \chi(n)=(-1)^{\sum_{q\equiv2\pmod{3}}\beta_q}.$$
Используемый реализацией исходный мультипликативный вес равен
$$f(n)= \begin{cases} \tau_2(n)\,(2e_3-1), & e_3\ge 1,\\[4pt] \dfrac{\tau_2(n)+\chi(n)P_1(n)}{2}, & e_3=0. \end{cases}$$
Эта формула напрямую отражает то, как нужные классы подобия раскладываются в зависимости от поведения простых чисел по модулю \(3\). Множитель \(3\) вносит особый вклад, поэтому его степень выделяется отдельно.
Сырой вес \(f(n)\) всё ещё считает конфигурации с нетривиальным общим делителем в смысле Эйзенштейна. Чтобы оставить только примитивную часть, реализация использует инверсию Мёбиуса:
$$h(n)=(f*\mu)(n)=\sum_{d\mid n} f(d)\,\mu\!\left(\frac{n}{d}\right).$$
Это свёртка Дирихле, которая убирает вклады, возникающие лишь как увеличенные копии меньшей примитивной конфигурации.
Для каждого \(n\le 3R_2\) реализация сопоставляет весу \(h(n)\) решёточный счётчик \(F_n\):
$$F_n= \begin{cases} A\!\left(\left\lfloor\frac{R_2^2}{n^2}\right\rfloor\right)-1, & 3\nmid n,\\[6pt] A_{\equiv}\!\left(\left\lfloor\frac{R_2^2}{(n/3)^2}\right\rfloor\right)-1, & 3\mid n. \end{cases}$$
Вычитание \(1\) убирает начало координат. Основная сумма имеет вид
$$S(R_2)=\sum_{n=1}^{3R_2} h(n)\,F_n.$$
После этого применяется финальная симметрийная поправка:
$$E(R_2)=\frac{A(R_2^2)-1}{3},\qquad \boxed{T(R_2)=S(R_2)-2E(R_2).}$$
Деление на \(3\) корректно для общего числа ненулевых решёточных точек и компенсирует тройную вращательную симметрию, которая иначе была бы пересчитана несколько раз.
Это самый маленький контрольный пример, используемый в реализациях, и он уже показывает все основные механизмы. Из условия \(Q(u,v)\le1\) получаются начало координат и шесть единичных направлений, поэтому
$$A(1)=7,\qquad A_{\equiv}(1)=1.$$
Следовательно,
$$F_1=A(1)-1=6,\qquad F_3=A_{\equiv}(1)-1=0.$$
Теперь вычислим сырые веса:
$$f(1)=1,\qquad f(2)=\frac{3+(-1)\cdot1}{2}=1,\qquad f(3)=1.$$
Используя \(\mu(1)=1\), \(\mu(2)=-1\) и \(\mu(3)=-1\), получаем по инверсии Мёбиуса
$$h(1)=1,\qquad h(2)=f(1)\mu(2)+f(2)\mu(1)=0,\qquad h(3)=f(1)\mu(3)+f(3)\mu(1)=0.$$
Значит, вклад даёт только \(n=1\):
$$S(1)=1\cdot 6=6,\qquad E(1)=\frac{7-1}{3}=2,$$
и итоговое значение равно
$$T(1)=6-2\cdot2=2,$$
что совпадает с результатом проверки.
Реализации на C++, Python и Java следуют одной и той же вычислительной схеме. Сначала они строят таблицу наименьших простых делителей и функцию Мёбиуса до \(3R_2\). Этого достаточно, чтобы разложить каждое число \(n\), вычислить мультипликативный вес \(f(n)\), а затем через свёртку Дирихле получить примитивный вес \(h(n)\).
Независимо от этого реализация заранее считает геометрические таблицы для всех \(1\le t\le R_2\): полный решёточный счётчик и счётчик с условием по конгруэнции при \(M=\left\lfloor R_2^2/t^2\right\rfloor\). Версия на C++ распараллеливает эту тяжёлую стадию; версия на Java выполняет ту же логику напрямую; версия на Python делегирует тяжёлое вычисление скомпилированному ядру, так что арифметическая и геометрическая части совпадают. После построения таблиц остаётся один проход по \(n\le 3R_2\): выбрать правильный канал по делимости на \(3\), накопить \(h(n)F_n\) и затем применить поправку \(2E(R_2)\).
Для одного порога \(M\) решёточный счётчик проходит по \(u=0,1,\dots,\left\lfloor\sqrt{4M/3}\right\rfloor\), поэтому одна оценка стоит \(O(\sqrt{M})\) времени и \(O(1)\) дополнительной памяти. Суммирование по всем \(t\le R_2\) даёт
$$\sum_{t=1}^{R_2} O\!\left(\sqrt{\frac{R_2^2}{t^2}}\right)=\sum_{t=1}^{R_2} O\!\left(\frac{R_2}{t}\right)=O(R_2\log R_2).$$
Этап решета является линейным или почти линейным по \(3R_2\), а проход со свёрткой Дирихле в сумме стоит \(O(R_2\log R_2)\). Память имеет порядок \(O(R_2)\): арифметические массивы имеют длину \(3R_2+1\), а геометрические таблицы длину \(R_2+1\). Параллелизация уменьшает реальное время геометрического этапа, но не меняет асимптотику.
تطلب المسألة 883 حساب القيمة \(T(R_2)\) الخاصة بالمثلثات المميّزة عندما يكون \(R_2=2{,}000{,}000\). لا تعتمد التطبيقات على تعداد المثلثات مباشرة، بل تختزل الهندسة إلى عدّ نقاط في شبكة مثلثية، حيث تكون مربعات الأطوال في الإحداثيات \((u,v)\) معطاة بالصيغة
$$Q(u,v)=u^2+uv+v^2.$$
الجواب النهائي لا يأتي من عدّ هندسي واحد، بل من مجموع موزون لكثير من العدادات المقيّسة، ثم تُستخدم معكوسة Möbius لإزالة التكرارات غير الأولية.
الهندسة الكامنة وراء المثلثات المميّزة تُشفَّر بواسطة الصيغة التربيعية \(Q(u,v)=u^2+uv+v^2\). لذلك تصبح المسألة كلها مسألة عدّ تجمع بين الهندسة ونظرية الأعداد بالاعتماد على هذه الدالة المعيارية.
من أجل حدّ \(M\)، نعرّف
$$A(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M\},$$
$$A_{\equiv}(M)=\#\{(u,v)\in \mathbb{Z}^2:Q(u,v)\le M,\ u\equiv v\pmod{3}\}.$$
العدد \(A(M)\) يحصي كل المتجهات المسموح بها في الشبكة حتى مربع طول \(M\). أما \(A_{\equiv}(M)\) فيحتفظ فقط بطبقة التطابق المطلوبة عندما يجب التعامل مع العامل \(3\) على نحو منفصل. تقوم التطبيقات بحساب هاتين الدالتين لكثير من القيم
$$M=\left\lfloor\frac{R_2^2}{t^2}\right\rfloor.$$
الهوية الأساسية هي
$$4Q(u,v)=(2v+u)^2+3u^2.$$
وعند تثبيت \(u\)، يصبح الشرط \(Q(u,v)\le M\) على الصورة
$$ (2v+u)^2\le 4M-3u^2. $$
ومن هنا نرى فورًا أن المجال المطلوب لـ \(u\) هو
$$0\le u\le \left\lfloor\sqrt{\frac{4M}{3}}\right\rfloor.$$
وإذا أخذنا
$$s=\left\lfloor\sqrt{4M-3u^2}\right\rfloor,$$
فإن القيم الصحيحة المسموح بها لـ \(v\) تحقق
$$\left\lceil\frac{-u-s}{2}\right\rceil \le v \le \left\lfloor\frac{-u+s}{2}\right\rfloor.$$
طول هذا المجال يعطي عدد النقاط عند هذا \(u\). وبما أن التحويل \((u,v)\mapsto(-u,-v)\) يحافظ على \(Q\)، فإن التنفيذ يمر فقط على \(u\ge0\) ويضاعف المساهمة عندما يكون \(u>0\).
مصدر العداد المقيّد هو العلاقة
$$Q(u,v)=u^2+uv+v^2=(u-v)^2+3uv,$$
ومنها نحصل على
$$Q(u,v)\equiv (u-v)^2 \pmod{3}.$$
إذن
$$3\mid Q(u,v)\iff u\equiv v\pmod{3}.$$
ولهذا بالضبط تعدّ القناة الثانية فقط تلك القيم \(v\) من المجال السابق التي تحقق \(v\equiv u\pmod{3}\). وفي لغة أعداد Eisenstein يكون العدد الأولي \(3\) متشعّبًا، ولذلك يحتاج إلى معالجة منفصلة بدل المرور عبر القناة العادية.
لنكتب
$$n=3^{e_3}\prod_{p\equiv1\pmod{3}}p^{\alpha_p}\prod_{q\equiv2\pmod{3}}q^{\beta_q}.$$
الجزء العددي من الحل يميّز بين ثلاثة أنماط من الأعداد الأولية في حساب Eisenstein: الأعداد الأولية المتفككة \(p\equiv1\pmod{3}\)، والخاملة \(q\equiv2\pmod{3}\)، والعدد الأولي المتشعّب \(3\). نعرّف
$$\tau_2(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1)\prod_{q\equiv2\pmod{3}}(2\beta_q+1),$$
$$P_1(n)=\prod_{p\equiv1\pmod{3}}(2\alpha_p+1),\qquad \chi(n)=(-1)^{\sum_{q\equiv2\pmod{3}}\beta_q}.$$
والوزن الضربي الخام الذي تستخدمه التطبيقات هو
$$f(n)= \begin{cases} \tau_2(n)\,(2e_3-1), & e_3\ge 1,\\[4pt] \dfrac{\tau_2(n)+\chi(n)P_1(n)}{2}, & e_3=0. \end{cases}$$
هذه الصيغة تعبّر مباشرة عن كيفية انقسام أصناف التشابه المطلوبة بحسب سلوك الأعداد الأولية modulo \(3\). ويسهم العامل \(3\) بطريقة تختلف عن بقية الأعداد الأولية، لذلك يُفصل منذ البداية.
الوزن الخام \(f(n)\) ما يزال يحسب تشكيلات لها قاسم مشترك غير تافه في معنى Eisenstein. ولعزل المساهمة الأولية، تستخدم التطبيقات معكوسة Möbius:
$$h(n)=(f*\mu)(n)=\sum_{d\mid n} f(d)\,\mu\!\left(\frac{n}{d}\right).$$
هذا التفاف Dirichlet يزيل الإسهامات التي لا تنشأ إلا من تكبير تشكيل أولي أصغر.
لكل \(n\le 3R_2\)، تُسنِد التطبيقات إلى الوزن \(h(n)\) عدادًا شبكيًا \(F_n\):
$$F_n= \begin{cases} A\!\left(\left\lfloor\frac{R_2^2}{n^2}\right\rfloor\right)-1, & 3\nmid n,\\[6pt] A_{\equiv}\!\left(\left\lfloor\frac{R_2^2}{(n/3)^2}\right\rfloor\right)-1, & 3\mid n. \end{cases}$$
طرح \(1\) هنا يزيل نقطة الأصل. ومن ثم يكون المجموع الرئيسي
$$S(R_2)=\sum_{n=1}^{3R_2} h(n)\,F_n.$$
ثم تُطبَّق في النهاية تسوية تتعلق بالتناظر:
$$E(R_2)=\frac{A(R_2^2)-1}{3},\qquad \boxed{T(R_2)=S(R_2)-2E(R_2).}$$
القسمة على \(3\) صحيحة لعدد النقاط غير الصفرية في العدّ الحر، وهي تعالج تناظرًا دورانيًا ثلاثيًّا كان سيؤدي إلى عدّ بعض الاتجاهات أكثر من مرة.
هذا أصغر اختبار تحقق تستخدمه التطبيقات، ومع ذلك فهو يُظهر كل الأجزاء الأساسية. من الشرط \(Q(u,v)\le1\) نحصل على نقطة الأصل وستة اتجاهات وحيدة، ومن ثم
$$A(1)=7,\qquad A_{\equiv}(1)=1.$$
وبالتالي
$$F_1=A(1)-1=6,\qquad F_3=A_{\equiv}(1)-1=0.$$
ثم نحسب الأوزان الخام:
$$f(1)=1,\qquad f(2)=\frac{3+(-1)\cdot1}{2}=1,\qquad f(3)=1.$$
وباستخدام \(\mu(1)=1\) و\(\mu(2)=-1\) و\(\mu(3)=-1\)، تعطينا معكوسة Möbius
$$h(1)=1,\qquad h(2)=f(1)\mu(2)+f(2)\mu(1)=0,\qquad h(3)=f(1)\mu(3)+f(3)\mu(1)=0.$$
إذن لا يساهم إلا الحد \(n=1\):
$$S(1)=1\cdot 6=6,\qquad E(1)=\frac{7-1}{3}=2,$$
ومن ثم
$$T(1)=6-2\cdot2=2,$$
وهو تمامًا ناتج التحقق.
تتبع تطبيقات C++ وPython وJava المسار الحسابي نفسه. فهي تبدأ ببناء جدول أصغر عامل أولي ودالة Möbius حتى \(3R_2\). وهذا يكفي لتحليل كل عدد \(n\) إلى عوامله، وتقييم الوزن الضربي \(f(n)\)، ثم تكوين الوزن الأولي \(h(n)\) عبر التفاف Dirichlet.
وبصورة مستقلة، تقوم التطبيقات بتهيئة الجداول الهندسية مسبقًا لكل \(1\le t\le R_2\): أي عدّ الشبكة غير المقيّد وعدّ الشبكة المقيّد بشرط التطابق عند \(M=\left\lfloor R_2^2/t^2\right\rfloor\). نسخة C++ توازي هذه المرحلة الثقيلة؛ ونسخة Java تنفّذ المنطق نفسه مباشرة؛ أما نسخة Python فتعتمد على التنفيذ المترجَم نفسه حتى تبقى الخطوات الحسابية والهندسية متطابقة. وبعد تجهيز هذه الجداول لا يبقى إلا المرور مرة واحدة على \(n\le 3R_2\)، واختيار القناة الصحيحة وفق قابلية القسمة على \(3\)، وتجميع \(h(n)F_n\)، ثم تطبيق التصحيح \(2E(R_2)\).
عند حدّ واحد \(M\)، يمرّ عداد الشبكة على القيم \(u=0,1,\dots,\left\lfloor\sqrt{4M/3}\right\rfloor\)، لذا فإن التقييم الواحد يكلف \(O(\sqrt{M})\) زمنًا و\(O(1)\) ذاكرة إضافية. وبجمع ذلك على كل \(t\le R_2\) نحصل على
$$\sum_{t=1}^{R_2} O\!\left(\sqrt{\frac{R_2^2}{t^2}}\right)=\sum_{t=1}^{R_2} O\!\left(\frac{R_2}{t}\right)=O(R_2\log R_2).$$
مرحلة المنخل خطية أو شبه خطية في \(3R_2\)، وتمرير التفاف Dirichlet يكلف إجمالًا \(O(R_2\log R_2)\). أما الذاكرة فهي \(O(R_2)\): إذ إن المصفوفات العددية طولها \(3R_2+1\)، والجداول الهندسية طولها \(R_2+1\). التنفيذ المتوازي يحسن الزمن الفعلي للمرحلة الهندسية، لكنه لا يغيّر المرتبة التقاربية.