The centers of the honeycomb cells form a triangular lattice. In axial coordinates, every displacement is described by two integers \(a,b\), and its squared Euclidean length is
$$L^2 = 3(a^2+ab+b^2).$$
Therefore the distance-counting function can be rewritten as
$$B(L)=\left|\left\{(a,b)\in\mathbb Z^2:3(a^2+ab+b^2)=L^2\right\}\right|.$$
If \(L^2/3\notin\mathbb Z\), then \(B(L)=0\). Otherwise, with
$$n=\frac{L^2}{3},$$
the problem reduces to the representation count
$$r(n)=\left|\left\{(a,b)\in\mathbb Z^2:a^2+ab+b^2=n\right\}\right|.$$
The local implementations count all \(n\le N\) with \(r(n)=450\), where the target repository limit is
$$N=\left\lfloor\frac{(5\cdot 10^{11})^2}{3}\right\rfloor.$$
Each such \(n\) corresponds to exactly one honeycomb distance \(L=\sqrt{3n}\), so this arithmetic reformulation is equivalent to the original geometric question.
The quadratic form
$$a^2+ab+b^2$$
is the norm form of the Eisenstein integers, since
$$a^2+ab+b^2=N(a-b\omega),\qquad \omega=e^{2\pi i/3}.$$
This is why the arithmetic of primes modulo \(3\) controls the number of lattice representations. The C++ function count_representations_formula implements exactly this standard norm-counting formula.
Write the prime factorization of \(n\) as
$$n=3^{e_0}\prod_{p\equiv 1 \pmod{3}}p^{e_p}\prod_{q\equiv 2 \pmod{3}}q^{f_q}.$$
Then the representation count is determined by the congruence class of each prime:
if some exponent \(f_q\) is odd, then
$$r(n)=0;$$
otherwise,
$$r(n)=6\prod_{p\equiv 1 \pmod{3}}(e_p+1).$$
The reason is structural. Primes \(p\equiv 1 \pmod{3}\) split in the Eisenstein integers and contribute a factor \(e_p+1\). Primes \(q\equiv 2 \pmod{3}\) are inert, so they can only appear with even exponent if the norm is to remain representable. The prime \(3\) is ramified, but it does not change the multiplicity factor beyond the universal leading constant \(6\).
Since
$$450=6\cdot 75,$$
we must have
$$\prod_{p\equiv 1 \pmod{3}}(e_p+1)=75.$$
Now factor \(75\) into integers greater than \(1\):
$$75,\qquad 25\cdot 3,\qquad 15\cdot 5,\qquad 5\cdot 5\cdot 3.$$
Subtracting \(1\) from each factor gives the only possible exponent multisets on primes \(p\equiv 1 \pmod{3}\):
$$[74],\qquad [24,2],\qquad [14,4],\qquad [4,4,2].$$
So every admissible core is of one of the forms
$$p^{74},\qquad p^{24}q^2,\qquad p^{14}q^4,\qquad p^4q^4r^2,$$
with distinct primes \(p,q,r\equiv 1 \pmod{3}\). Whenever the exponents are not all equal, their assignment to distinct primes matters. This explains the separate code paths for \([24,2]\) and \([2,24]\), for \([14,4]\) and \([4,14]\), and for the three ordered versions of \([4,4,2]\).
Every valid integer \(n\) can be written uniquely as
$$n=c\cdot t,$$
where \(c\) is a core carrying one of the exponent patterns above on primes \(p\equiv 1 \pmod{3}\), and \(t\) is a multiplier that does not change the value \(r(n)=450\).
The only neutral factors are powers of \(3\) and even powers of primes \(q\equiv 2 \pmod{3}\). Therefore
$$t=3^a u^2,$$
where every prime divisor of \(u\) satisfies
$$q\equiv 2 \pmod{3}.$$
No prime \(p\equiv 1 \pmod{3}\) may appear inside \(u\), even squared, because that would increase some exponent \(e_p\) and change the product \(\prod (e_p+1)\).
For \(s\ge 1\), define
$$G(s)=\left|\left\{u\le s:\forall q\mid u,\ q\equiv 2 \pmod{3}\right\}\right|.$$
If \(x\) is the remaining budget after fixing the core \(c\), then the number of admissible multipliers \(t\le x\) is
$$M(x)=\sum_{\substack{a\ge 0\\3^a\le x}} G\!\left(\left\lfloor\sqrt{\frac{x}{3^a}}\right\rfloor\right).$$
This formula is exactly what the C++ method NeutralCounter::count_multipliers and the Python helper count_mult compute. The prefix table is built from a smallest-prime-factor sieve. The boolean recurrence used by the code is simple:
$$\texttt{good}(1)=1,\qquad \texttt{good}(n)=1 \iff \left(\operatorname{spf}(n)\equiv 2 \pmod{3}\right)\land \texttt{good}\!\left(\frac{n}{\operatorname{spf}(n)}\right)=1.$$
After prefix sums, each evaluation of \(G(s)\) is \(O(1)\), so each call to \(M(x)\) only iterates over powers of \(3\).
The smallest possible core is obtained from the smallest three primes congruent to \(1 \pmod{3}\):
$$c_{\min}=7^4\cdot 13^4\cdot 19^2.$$
This is why the solver returns \(0\) immediately when \(N<c_{\min}\). It also explains the constants
$$7^4\cdot 13^4\cdot 19^2,\qquad 7^4\cdot 13^4$$
stored in the C++ source as lower structural bounds.
The program sieves primes \(p\equiv 1 \pmod{3}\), precomputes \(p^2\) and \(p^4\) for all such primes, and stores the much shorter lists of primes with
$$p^{14}\le N,\qquad p^{24}\le N,\qquad p^{74}\le N.$$
Then it runs the ordered families
$$[74],\ [24,2],\ [2,24],\ [14,4],\ [4,14],\ [4,4,2],\ [4,2,4],\ [2,4,4],$$
and for each admissible core \(c\) it adds
$$M\!\left(\left\lfloor\frac{N}{c}\right\rfloor\right).$$
This is the whole algorithm: enumerate the rare core patterns, then attach every neutral multiplier that still fits below the limit.
The C++ implementation validates the representation formula against brute-force lattice counting for every \(1\le n\le 120\). It also includes explicit problem checkpoints:
$$r(1)=6 \quad\Rightarrow\quad B(\sqrt{3})=6,$$
$$r(7)=12 \quad\Rightarrow\quad B(\sqrt{21})=12.$$
For the larger integer distance used in the validation block,
$$L=111111111,\qquad n=\frac{L^2}{3}=3^3\cdot 37^2\cdot 333667^2,$$
so the formula gives
$$B(L)=r(n)=6(2+1)(2+1)=54,$$
exactly matching the checkpoint in the repository.
The C++ file is the full reference implementation. It contains the number-theoretic formula, brute-force validators, the neutral-multiplier sieve, precomputed power tables, and the final core enumeration. The expensive three-prime families are parallelized with parallel_sum_indices, but the mathematics is unchanged.
The Python file is a direct arithmetic transcription of the same method: the same exponent families, the same neutral counter, and the same final sum. The Java file does not reimplement the mathematics independently; instead, it compiles and runs the C++ solver and returns the parsed final output. So all three local solution files encode the same argument, just with different engineering choices.
Let
$$N=\left\lfloor\frac{L_{\max}^2}{3}\right\rfloor,\qquad P=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4}}\right\rfloor,\qquad S=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4\cdot 19^2}}\right\rfloor.$$
Sieving primes \(p\equiv 1 \pmod{3}\) up to \(P\) costs near \(O(P\log\log P)\) time. Building the smallest-prime-factor table and the neutral prefix counts up to \(S\) also costs near \(O(S\log\log S)\) time. Both structures use linear memory in their respective limits.
After that preprocessing, each multiplier query \(M(x)\) uses only \(O(\log x)\) iterations over powers of \(3\), with \(O(1)\) prefix lookups inside. The family loops are heavily pruned because exponents \(74\), \(24\), \(14\), \(4\), and \(2\) make the core values grow very quickly. In practice the algorithm is dominated by the sieves and this pruned enumeration, not by any geometric search.
Die Mittelpunkte der Wabenzellen bilden ein Dreiecksgitter. In axialen Koordinaten wird jede Verschiebung durch zwei ganze Zahlen \(a,b\) beschrieben, und für die quadratische Distanz gilt
$$L^2 = 3(a^2+ab+b^2).$$
Damit lässt sich die Abstandsanzahl schreiben als
$$B(L)=\left|\left\{(a,b)\in\mathbb Z^2:3(a^2+ab+b^2)=L^2\right\}\right|.$$
Falls \(L^2/3\notin\mathbb Z\) ist, dann gilt sofort \(B(L)=0\). Andernfalls setzen wir
$$n=\frac{L^2}{3},$$
und das Problem wird zu einer reinen Darstellungszählung
$$r(n)=\left|\left\{(a,b)\in\mathbb Z^2:a^2+ab+b^2=n\right\}\right|.$$
Die lokalen Implementierungen zählen also alle \(n\le N\) mit \(r(n)=450\), wobei die Zielschranke im Repository
$$N=\left\lfloor\frac{(5\cdot 10^{11})^2}{3}\right\rfloor$$
ist. Jedes solche \(n\) entspricht genau einer Distanz \(L=\sqrt{3n}\), daher ist die arithmetische Formulierung exakt äquivalent zur geometrischen Aufgabenstellung.
Die quadratische Form
$$a^2+ab+b^2$$
ist die Normform der Eisenstein-Zahlen, denn
$$a^2+ab+b^2=N(a-b\omega),\qquad \omega=e^{2\pi i/3}.$$
Deshalb hängt die Anzahl der Gitterdarstellungen direkt vom Primzahlverhalten modulo \(3\) ab. Genau diese Standardformel implementiert die C++-Funktion count_representations_formula.
Schreibe die Primfaktorzerlegung von \(n\) als
$$n=3^{e_0}\prod_{p\equiv 1 \pmod{3}}p^{e_p}\prod_{q\equiv 2 \pmod{3}}q^{f_q}.$$
Dann entscheidet die Restklasse jeder Primzahl über die Zahl der Darstellungen:
Ist irgendein Exponent \(f_q\) ungerade, dann gilt
$$r(n)=0;$$
sonst
$$r(n)=6\prod_{p\equiv 1 \pmod{3}}(e_p+1).$$
Der Grund ist strukturell. Primzahlen \(p\equiv 1 \pmod{3}\) zerfallen in den Eisenstein-Zahlen und liefern jeweils den Faktor \(e_p+1\). Primzahlen \(q\equiv 2 \pmod{3}\) sind inert und dürfen nur mit geradem Exponenten auftreten. Die Primzahl \(3\) ist verzweigt, ändert aber die Vielfachheit nicht über den universellen Vorfaktor \(6\) hinaus.
Wegen
$$450=6\cdot 75$$
muss gelten
$$\prod_{p\equiv 1 \pmod{3}}(e_p+1)=75.$$
Nun zerlegen wir \(75\) in Faktoren größer als \(1\):
$$75,\qquad 25\cdot 3,\qquad 15\cdot 5,\qquad 5\cdot 5\cdot 3.$$
Nach Abzug von \(1\) entstehen genau die möglichen Exponentenmultimengen auf Primzahlen \(p\equiv 1 \pmod{3}\):
$$[74],\qquad [24,2],\qquad [14,4],\qquad [4,4,2].$$
Jeder zulässige Kern hat also eine der Formen
$$p^{74},\qquad p^{24}q^2,\qquad p^{14}q^4,\qquad p^4q^4r^2,$$
wobei \(p,q,r\equiv 1 \pmod{3}\) verschieden sind. Wenn die Exponenten nicht alle gleich sind, ist ihre Zuordnung zu verschiedenen Primzahlen relevant. Deshalb enumeriert der Code getrennt \([24,2]\) und \([2,24]\), ebenso \([14,4]\) und \([4,14]\) sowie die drei geordneten Varianten von \([4,4,2]\).
Jede gültige Zahl \(n\) lässt sich eindeutig schreiben als
$$n=c\cdot t,$$
wobei \(c\) ein Kern mit einem der obigen Exponentenmuster auf Primzahlen \(p\equiv 1 \pmod{3}\) ist, und \(t\) ein Faktor, der den Wert \(r(n)=450\) nicht verändert.
Neutral sind nur Potenzen von \(3\) und gerade Potenzen von Primzahlen \(q\equiv 2 \pmod{3}\). Daher gilt
$$t=3^a u^2,$$
wobei jeder Primteiler von \(u\) die Bedingung
$$q\equiv 2 \pmod{3}$$
erfüllt. Eine Primzahl \(p\equiv 1 \pmod{3}\) darf in \(u\) nicht einmal quadratisch vorkommen, denn sonst würde sich irgendein Exponent \(e_p\) erhöhen und damit das Produkt \(\prod (e_p+1)\) ändern.
Für \(s\ge 1\) definieren wir
$$G(s)=\left|\left\{u\le s:\forall q\mid u,\ q\equiv 2 \pmod{3}\right\}\right|.$$
Wenn \(x\) nach Wahl des Kerns \(c\) das verbleibende Budget ist, dann ist die Zahl der zulässigen Multiplikatoren \(t\le x\)
$$M(x)=\sum_{\substack{a\ge 0\\3^a\le x}} G\!\left(\left\lfloor\sqrt{\frac{x}{3^a}}\right\rfloor\right).$$
Genau diese Formel berechnen in den lokalen Dateien die C++-Methode NeutralCounter::count_multipliers und die Python-Hilfsfunktion count_mult. Die Präfixtabelle entsteht über ein SPF-Sieb. Die vom Code benutzte Rekursion lautet
$$\texttt{good}(1)=1,\qquad \texttt{good}(n)=1 \iff \left(\operatorname{spf}(n)\equiv 2 \pmod{3}\right)\land \texttt{good}\!\left(\frac{n}{\operatorname{spf}(n)}\right)=1.$$
Nach der Präfixsummierung ist jede Auswertung von \(G(s)\) \(O(1)\), sodass pro Anfrage \(M(x)\) nur noch über die Potenzen von \(3\) iteriert wird.
Der kleinste mögliche Kern entsteht aus den drei kleinsten Primzahlen \(1 \pmod{3}\):
$$c_{\min}=7^4\cdot 13^4\cdot 19^2.$$
Deshalb kann der Löser sofort \(0\) zurückgeben, falls \(N<c_{\min}\) gilt. Dieselbe Überlegung erklärt auch die beiden Konstanten
$$7^4\cdot 13^4\cdot 19^2,\qquad 7^4\cdot 13^4,$$
die im C++-Quelltext als strukturelle Schranken auftauchen.
Das Programm siebt Primzahlen \(p\equiv 1 \pmod{3}\), berechnet für alle diese Primzahlen \(p^2\) und \(p^4\) vor und speichert die viel kürzeren Listen mit
$$p^{14}\le N,\qquad p^{24}\le N,\qquad p^{74}\le N.$$
Danach werden die geordneten Familien
$$[74],\ [24,2],\ [2,24],\ [14,4],\ [4,14],\ [4,4,2],\ [4,2,4],\ [2,4,4]$$
durchlaufen, und für jeden zulässigen Kern \(c\) wird
$$M\!\left(\left\lfloor\frac{N}{c}\right\rfloor\right)$$
addiert. Genau darin besteht der gesamte Algorithmus: seltene Kernmuster auflisten und dann alle neutralen Faktoren anhängen, die noch unter der Schranke bleiben.
Die C++-Implementierung vergleicht die Formel zunächst für alle \(1\le n\le 120\) mit einer Brute-Force-Zählung im Gitter. Zusätzlich enthält sie explizite Prüfwerte aus der Aufgabe:
$$r(1)=6 \quad\Rightarrow\quad B(\sqrt{3})=6,$$
$$r(7)=12 \quad\Rightarrow\quad B(\sqrt{21})=12.$$
Für die große ganzzahlige Distanz aus dem Prüfblock gilt
$$L=111111111,\qquad n=\frac{L^2}{3}=3^3\cdot 37^2\cdot 333667^2,$$
und damit
$$B(L)=r(n)=6(2+1)(2+1)=54,$$
genau wie im Repository validiert.
Die C++-Datei ist die eigentliche Referenzimplementierung. Sie enthält die zahlentheoretische Formel, Brute-Force-Validierungen, das Sieb für neutrale Multiplikatoren, vorberechnete Potenztabellen und die finale Enumeration der Kerne. Die teuren Drei-Primzahl-Familien werden über parallel_sum_indices parallelisiert, aber mathematisch bleibt alles unverändert.
Die Python-Datei ist eine direkte arithmetische Übersetzung derselben Methode: dieselben Exponentenfamilien, derselbe neutrale Zähler, dieselbe Endsumme. Die Java-Datei implementiert die Mathematik nicht separat, sondern kompiliert und startet den C++-Löser und liefert dessen letzte Ausgabezeile zurück. Alle drei lokalen Lösungen beruhen also auf demselben Argument, nur mit unterschiedlichen technischen Entscheidungen.
Sei
$$N=\left\lfloor\frac{L_{\max}^2}{3}\right\rfloor,\qquad P=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4}}\right\rfloor,\qquad S=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4\cdot 19^2}}\right\rfloor.$$
Das Sieben der Primzahlen \(p\equiv 1 \pmod{3}\) bis \(P\) kostet näherungsweise \(O(P\log\log P)\) Zeit. Das SPF-Sieb und die Präfixzählung bis \(S\) kosten ebenfalls näherungsweise \(O(S\log\log S)\) Zeit. Beide Datenstrukturen benötigen linearen Speicher in ihrer jeweiligen Schranke.
Nach dieser Vorverarbeitung benötigt jede Anfrage \(M(x)\) nur \(O(\log x)\) Schritte über Potenzen von \(3\), mit \(O(1)\)-Präfixzugriffen im Inneren. Die Familien-Schleifen sind stark beschnitten, weil die Exponenten \(74\), \(24\), \(14\), \(4\) und \(2\) die Kernwerte sehr schnell wachsen lassen. In der Praxis dominiert deshalb die Kombination aus Sieben und beschnittener Kernauszählung, nicht irgendeine geometrische Brute-Force-Suche.
Petek hücrelerinin merkezleri üçgensel bir kafes oluşturur. Eksenel koordinatlarda her yer değiştirme iki tamsayı \(a,b\) ile ifade edilir ve Öklid uzaklığının karesi
$$L^2 = 3(a^2+ab+b^2)$$
şeklindedir. Böylece uzaklık sayma fonksiyonu
$$B(L)=\left|\left\{(a,b)\in\mathbb Z^2:3(a^2+ab+b^2)=L^2\right\}\right|$$
olarak yeniden yazılır. Eğer \(L^2/3\notin\mathbb Z\) ise doğrudan \(B(L)=0\) olur. Aksi halde
$$n=\frac{L^2}{3}$$
tanımıyla problem şu temsil sayısına indirgenir:
$$r(n)=\left|\left\{(a,b)\in\mathbb Z^2:a^2+ab+b^2=n\right\}\right|.$$
Yerel çözümler bu yüzden \(r(n)=450\) olan tüm \(n\le N\) değerlerini sayar; burada depo içindeki hedef sınır
$$N=\left\lfloor\frac{(5\cdot 10^{11})^2}{3}\right\rfloor$$
olarak alınır. Her böyle \(n\), tam olarak bir adet \(L=\sqrt{3n}\) uzaklığına karşılık gelir; dolayısıyla aritmetik model, özgün geometrik soruyla bire bir aynıdır.
Şu ikinci dereceden form
$$a^2+ab+b^2$$
Eisenstein tamsayılarının normudur; çünkü
$$a^2+ab+b^2=N(a-b\omega),\qquad \omega=e^{2\pi i/3}.$$
Bu yüzden kafes temsillerinin sayısı, asalların \(3\) moduna göre davranışıyla belirlenir. C++ dosyasındaki count_representations_formula fonksiyonu tam olarak bu standart norm sayma formülünü uygular.
\(n\)'in asal çarpanlara ayrılışını
$$n=3^{e_0}\prod_{p\equiv 1 \pmod{3}}p^{e_p}\prod_{q\equiv 2 \pmod{3}}q^{f_q}$$
şeklinde yazalım. O zaman temsil sayısı şu kurala uyar:
Eğer herhangi bir \(f_q\) tek ise
$$r(n)=0;$$
aksi halde
$$r(n)=6\prod_{p\equiv 1 \pmod{3}}(e_p+1).$$
Bunun nedeni yapısaldır. \(p\equiv 1 \pmod{3}\) asalları Eisenstein tamsayılarında ayrışır ve her biri \(e_p+1\) çarpanı getirir. \(q\equiv 2 \pmod{3}\) asalları inerttir; bu yüzden temsil edilebilirlik için üslerinin çift olması gerekir. \(3\) asalı ise ramified durumdadır, fakat evrensel \(6\) katsayısının ötesinde çarpan sayısını değiştirmez.
Şundan dolayı
$$450=6\cdot 75,$$
şu çarpım şartı gerekir:
$$\prod_{p\equiv 1 \pmod{3}}(e_p+1)=75.$$
Şimdi \(75\)'i \(1\)'den büyük çarpanlara ayıralım:
$$75,\qquad 25\cdot 3,\qquad 15\cdot 5,\qquad 5\cdot 5\cdot 3.$$
Her faktörden \(1\) çıkarınca, \(p\equiv 1 \pmod{3}\) asalları üzerindeki mümkün üs çoklukları tam olarak şunlardır:
$$[74],\qquad [24,2],\qquad [14,4],\qquad [4,4,2].$$
Yani her uygun çekirdek şu biçimlerden biridir:
$$p^{74},\qquad p^{24}q^2,\qquad p^{14}q^4,\qquad p^4q^4r^2,$$
burada \(p,q,r\equiv 1 \pmod{3}\) olan farklı asallardır. Üsler eşit olmadığında, bunların farklı asallara nasıl dağıtıldığı önemlidir. Kodun \([24,2]\) ile \([2,24]\), \([14,4]\) ile \([4,14]\), ayrıca \([4,4,2]\)'nin üç sıralı sürümü için ayrı döngüler kurmasının nedeni budur.
Her geçerli \(n\) sayısı tekil biçimde
$$n=c\cdot t$$
olarak yazılır. Burada \(c\), yukarıdaki üs desenlerinden birini taşıyan bir çekirdek; \(t\) ise \(r(n)=450\) değerini değiştirmeyen bir çarpandır.
Nötr kalabilen tek çarpanlar, \(3\)'ün kuvvetleri ile \(q\equiv 2 \pmod{3}\) asallarının çift kuvvetleridir. Bu yüzden
$$t=3^a u^2$$
yazabiliriz; burada \(u\)'nun her asal böleni
$$q\equiv 2 \pmod{3}$$
şartını sağlar. \(p\equiv 1 \pmod{3}\) sınıfındaki bir asal, kare olarak bile \(u\)'ya giremez; çünkü bu durumda ilgili bir \(e_p\) değeri büyür ve \(\prod (e_p+1)\) çarpımı değişir.
\(s\ge 1\) için
$$G(s)=\left|\left\{u\le s:\forall q\mid u,\ q\equiv 2 \pmod{3}\right\}\right|$$
tanımını yapalım. Çekirdek \(c\) seçildikten sonra kalan bütçe \(x\) ise, \(t\le x\) olan uygun nötr çarpanların sayısı
$$M(x)=\sum_{\substack{a\ge 0\\3^a\le x}} G\!\left(\left\lfloor\sqrt{\frac{x}{3^a}}\right\rfloor\right)$$
olur. C++ dosyasındaki NeutralCounter::count_multipliers ve Python dosyasındaki count_mult yardımcı fonksiyonu tam olarak bu formülü hesaplar. Ön ek tablosu, en küçük asal bölen süzgeci ile kurulur. Kodun kullandığı mantıksal bağıntı şudur:
$$\texttt{good}(1)=1,\qquad \texttt{good}(n)=1 \iff \left(\operatorname{spf}(n)\equiv 2 \pmod{3}\right)\land \texttt{good}\!\left(\frac{n}{\operatorname{spf}(n)}\right)=1.$$
Ön ek toplamlarından sonra \(G(s)\) sorgusu \(O(1)\) olur; böylece her \(M(x)\) çağrısı sadece \(3\)'ün kuvvetleri üzerinden dolaşır.
En küçük mümkün çekirdek, \(1 \pmod{3}\) sınıfındaki en küçük üç asaldan gelir:
$$c_{\min}=7^4\cdot 13^4\cdot 19^2.$$
Bu nedenle \(N<c_{\min}\) ise çözücü hemen \(0\) döndürebilir. Aynı düşünce, C++ kaynakta sabit olarak duran
$$7^4\cdot 13^4\cdot 19^2,\qquad 7^4\cdot 13^4$$
ifadelerini de açıklar.
Program önce \(p\equiv 1 \pmod{3}\) asallarını süzer, bunlar için \(p^2\) ve \(p^4\) değerlerini önceden hesaplar, sonra da çok daha kısa olan
$$p^{14}\le N,\qquad p^{24}\le N,\qquad p^{74}\le N$$
listelerini çıkarır. Daha sonra sıralı aileler
$$[74],\ [24,2],\ [2,24],\ [14,4],\ [4,14],\ [4,4,2],\ [4,2,4],\ [2,4,4]$$
dolaşılır ve her geçerli çekirdek \(c\) için
$$M\!\left(\left\lfloor\frac{N}{c}\right\rfloor\right)$$
toplama eklenir. Bütün algoritma bundan ibarettir: seyrek çekirdek desenlerini üret, sonra sınırın altında kalan tüm nötr çarpanları ekle.
C++ uygulaması önce \(1\le n\le 120\) aralığındaki her değer için formülü kafes üzerinde brute-force sayımı ile karşılaştırır. Ayrıca problemle ilgili açık kontrol değerleri de vardır:
$$r(1)=6 \quad\Rightarrow\quad B(\sqrt{3})=6,$$
$$r(7)=12 \quad\Rightarrow\quad B(\sqrt{21})=12.$$
Doğrulama bloğundaki büyük tamsayı uzaklık için
$$L=111111111,\qquad n=\frac{L^2}{3}=3^3\cdot 37^2\cdot 333667^2,$$
ve dolayısıyla
$$B(L)=r(n)=6(2+1)(2+1)=54,$$
elde edilir; bu da repodaki kontrolle bire bir aynıdır.
C++ dosyası tam referans uygulamadır. Sayı kuramı formülü, brute-force doğrulamaları, nötr çarpan süzgeci, önceden hesaplanmış üs tabloları ve son çekirdek enumerasyonu bu dosyada bulunur. En pahalı üç asal içeren aileler parallel_sum_indices ile paralelleştirilmiştir; fakat matematiksel içerik değişmez.
Python dosyası aynı yöntemin doğrudan aritmetik çevirisidir: aynı üs aileleri, aynı nötr sayaç, aynı son toplam. Java dosyası ise matematiği yeniden yazmaz; C++ çözücüsünü derleyip çalıştırır ve son çıktı satırını döndürür. Yani üç yerel çözüm dosyasının dayandığı matematiksel argüman aynıdır, sadece mühendislik tercihleri farklıdır.
Şunu tanımlayalım:
$$N=\left\lfloor\frac{L_{\max}^2}{3}\right\rfloor,\qquad P=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4}}\right\rfloor,\qquad S=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4\cdot 19^2}}\right\rfloor.$$
\(p\equiv 1 \pmod{3}\) asallarını \(P\)'ye kadar süzmek yaklaşık \(O(P\log\log P)\) zaman alır. \(S\)'ye kadar en küçük asal bölen tablosu ve ön ek sayacı kurmak da yaklaşık \(O(S\log\log S)\) zamandır. Her iki yapı da kendi sınırlarında doğrusal bellek kullanır.
Bu hazırlıktan sonra her \(M(x)\) sorgusu yalnızca \(3\)'ün kuvvetleri üzerinde \(O(\log x)\) adım gerektirir ve içerideki her ön ek erişimi \(O(1)\)'dir. Aile döngüleri çok güçlü biçimde budanır; çünkü \(74\), \(24\), \(14\), \(4\) ve \(2\) üsleri çekirdekleri çok hızlı büyütür. Pratikte maliyeti belirleyen kısım, geometrik brute-force değil, bu süzgeçler ve budanmış çekirdek enumerasyonudur.
Los centros de las celdas del panal forman una red triangular. En coordenadas axiales, cualquier desplazamiento se describe con dos enteros \(a,b\), y el cuadrado de la distancia euclídea es
$$L^2 = 3(a^2+ab+b^2).$$
Por tanto, la función de conteo de distancias puede escribirse como
$$B(L)=\left|\left\{(a,b)\in\mathbb Z^2:3(a^2+ab+b^2)=L^2\right\}\right|.$$
Si \(L^2/3\notin\mathbb Z\), entonces \(B(L)=0\). En caso contrario definimos
$$n=\frac{L^2}{3},$$
y el problema se reduce al número de representaciones
$$r(n)=\left|\left\{(a,b)\in\mathbb Z^2:a^2+ab+b^2=n\right\}\right|.$$
Las implementaciones locales cuentan, por tanto, todos los \(n\le N\) tales que \(r(n)=450\), donde el límite objetivo del repositorio es
$$N=\left\lfloor\frac{(5\cdot 10^{11})^2}{3}\right\rfloor.$$
Cada uno de esos valores de \(n\) corresponde exactamente a una distancia \(L=\sqrt{3n}\), así que la reformulación aritmética es completamente equivalente a la pregunta geométrica original.
La forma cuadrática
$$a^2+ab+b^2$$
es la norma de los enteros de Eisenstein, ya que
$$a^2+ab+b^2=N(a-b\omega),\qquad \omega=e^{2\pi i/3}.$$
Por eso el comportamiento de los primos módulo \(3\) determina el número de representaciones de la red. La función C++ count_representations_formula implementa exactamente esta fórmula estándar.
Escribamos la factorización prima de \(n\) como
$$n=3^{e_0}\prod_{p\equiv 1 \pmod{3}}p^{e_p}\prod_{q\equiv 2 \pmod{3}}q^{f_q}.$$
Entonces el número de representaciones queda determinado por la clase residual de cada primo:
si algún exponente \(f_q\) es impar, entonces
$$r(n)=0;$$
si no,
$$r(n)=6\prod_{p\equiv 1 \pmod{3}}(e_p+1).$$
La explicación es estructural. Los primos \(p\equiv 1 \pmod{3}\) se descomponen en los enteros de Eisenstein y cada uno aporta un factor \(e_p+1\). Los primos \(q\equiv 2 \pmod{3}\) son inertes, de modo que solo pueden aparecer con exponente par. El primo \(3\) es ramificado, pero no altera la multiplicidad salvo por la constante universal \(6\).
Como
$$450=6\cdot 75,$$
necesitamos
$$\prod_{p\equiv 1 \pmod{3}}(e_p+1)=75.$$
Ahora factorizamos \(75\) en enteros mayores que \(1\):
$$75,\qquad 25\cdot 3,\qquad 15\cdot 5,\qquad 5\cdot 5\cdot 3.$$
Restando \(1\) a cada factor, obtenemos los únicos multiconjuntos posibles de exponentes sobre los primos \(p\equiv 1 \pmod{3}\):
$$[74],\qquad [24,2],\qquad [14,4],\qquad [4,4,2].$$
Así, cualquier núcleo admisible tiene una de las formas
$$p^{74},\qquad p^{24}q^2,\qquad p^{14}q^4,\qquad p^4q^4r^2,$$
con primos distintos \(p,q,r\equiv 1 \pmod{3}\). Cuando los exponentes no son todos iguales, importa a qué primo se asigna cada uno. Esa es la razón de que el código enumere por separado \([24,2]\) y \([2,24]\), \([14,4]\) y \([4,14]\), y también las tres versiones ordenadas de \([4,4,2]\).
Cada entero válido \(n\) puede escribirse de manera única como
$$n=c\cdot t,$$
donde \(c\) es un núcleo que lleva uno de los patrones anteriores sobre los primos \(p\equiv 1 \pmod{3}\), y \(t\) es un factor que no modifica el valor \(r(n)=450\).
Los únicos factores neutros son las potencias de \(3\) y las potencias pares de primos \(q\equiv 2 \pmod{3}\). Por tanto,
$$t=3^a u^2,$$
donde todo divisor primo de \(u\) satisface
$$q\equiv 2 \pmod{3}.$$
Ningún primo \(p\equiv 1 \pmod{3}\) puede aparecer dentro de \(u\), ni siquiera al cuadrado, porque eso incrementaría alguno de los exponentes \(e_p\) y cambiaría el producto \(\prod (e_p+1)\).
Para \(s\ge 1\), definimos
$$G(s)=\left|\left\{u\le s:\forall q\mid u,\ q\equiv 2 \pmod{3}\right\}\right|.$$
Si \(x\) es el presupuesto restante tras fijar el núcleo \(c\), entonces el número de multiplicadores admisibles \(t\le x\) es
$$M(x)=\sum_{\substack{a\ge 0\\3^a\le x}} G\!\left(\left\lfloor\sqrt{\frac{x}{3^a}}\right\rfloor\right).$$
Esto es exactamente lo que calculan el método C++ NeutralCounter::count_multipliers y la función auxiliar de Python count_mult. La tabla prefijo se construye a partir de una criba de menor factor primo. La recurrencia booleana usada por el código es
$$\texttt{good}(1)=1,\qquad \texttt{good}(n)=1 \iff \left(\operatorname{spf}(n)\equiv 2 \pmod{3}\right)\land \texttt{good}\!\left(\frac{n}{\operatorname{spf}(n)}\right)=1.$$
Después de acumular prefijos, cada consulta \(G(s)\) cuesta \(O(1)\), así que cada evaluación de \(M(x)\) solo recorre las potencias de \(3\).
El menor núcleo posible se obtiene con los tres menores primos congruentes con \(1 \pmod{3}\):
$$c_{\min}=7^4\cdot 13^4\cdot 19^2.$$
Por eso el solver devuelve \(0\) inmediatamente cuando \(N<c_{\min}\). La misma observación explica las constantes
$$7^4\cdot 13^4\cdot 19^2,\qquad 7^4\cdot 13^4$$
que aparecen en el código C++ como cotas estructurales.
El programa criba los primos \(p\equiv 1 \pmod{3}\), precalcula \(p^2\) y \(p^4\) para todos ellos y guarda además las listas mucho más cortas con
$$p^{14}\le N,\qquad p^{24}\le N,\qquad p^{74}\le N.$$
Luego recorre las familias ordenadas
$$[74],\ [24,2],\ [2,24],\ [14,4],\ [4,14],\ [4,4,2],\ [4,2,4],\ [2,4,4]$$
y, para cada núcleo admisible \(c\), añade
$$M\!\left(\left\lfloor\frac{N}{c}\right\rfloor\right).$$
Ese es todo el algoritmo: enumerar los patrones raros del núcleo y adjuntar luego todos los multiplicadores neutros que aún caben bajo el límite.
La implementación en C++ valida primero la fórmula contra un conteo bruto de la red para todos los \(1\le n\le 120\). También incluye comprobaciones explícitas de la propia tarea:
$$r(1)=6 \quad\Rightarrow\quad B(\sqrt{3})=6,$$
$$r(7)=12 \quad\Rightarrow\quad B(\sqrt{21})=12.$$
Para la gran distancia entera usada en el bloque de validación,
$$L=111111111,\qquad n=\frac{L^2}{3}=3^3\cdot 37^2\cdot 333667^2,$$
y por tanto
$$B(L)=r(n)=6(2+1)(2+1)=54,$$
que coincide exactamente con el checkpoint del repositorio.
El archivo C++ es la implementación de referencia completa. Contiene la fórmula aritmética, las validaciones por fuerza bruta, la criba de multiplicadores neutros, las tablas de potencias precalculadas y la enumeración final de núcleos. Las familias de tres primos, que son las más pesadas, se paralelizan mediante parallel_sum_indices, aunque la matemática es la misma.
El archivo Python es una transcripción aritmética directa del mismo método: las mismas familias de exponentes, el mismo contador neutro y la misma suma final. El archivo Java no reimplementa la matemática por separado; compila y ejecuta el solver C++ y devuelve la última línea interpretada. Así, los tres archivos locales codifican el mismo razonamiento con elecciones de ingeniería distintas.
Sea
$$N=\left\lfloor\frac{L_{\max}^2}{3}\right\rfloor,\qquad P=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4}}\right\rfloor,\qquad S=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4\cdot 19^2}}\right\rfloor.$$
Cribar los primos \(p\equiv 1 \pmod{3}\) hasta \(P\) cuesta aproximadamente \(O(P\log\log P)\) tiempo. Construir la tabla de menor factor primo y el prefijo neutro hasta \(S\) cuesta aproximadamente \(O(S\log\log S)\) tiempo. Ambas estructuras usan memoria lineal en su respectivo límite.
Tras ese preprocesamiento, cada consulta \(M(x)\) solo necesita \(O(\log x)\) iteraciones sobre potencias de \(3\), con accesos de prefijo \(O(1)\) en el interior. Los bucles de familias están muy podados porque los exponentes \(74\), \(24\), \(14\), \(4\) y \(2\) hacen crecer los núcleos muy deprisa. En la práctica domina la combinación de cribas y enumeración podada, no una búsqueda geométrica por fuerza bruta.
蜂窝中六边形单元的中心构成一个三角晶格。用轴坐标表示时，任意位移都可写成两个整数 \(a,b\) 的组合，其欧氏距离平方满足
$$L^2 = 3(a^2+ab+b^2).$$
因此距离计数函数可以改写为
$$B(L)=\left|\left\{(a,b)\in\mathbb Z^2:3(a^2+ab+b^2)=L^2\right\}\right|.$$
如果 \(L^2/3\notin\mathbb Z\)，那么必有 \(B(L)=0\)。否则令
$$n=\frac{L^2}{3},$$
问题就变成二次型
$$r(n)=\left|\left\{(a,b)\in\mathbb Z^2:a^2+ab+b^2=n\right\}\right|$$
的表示次数问题。仓库中的本地实现实际上是在统计所有满足 \(r(n)=450\) 且 \(n\le N\) 的整数，其中目标上界是
$$N=\left\lfloor\frac{(5\cdot 10^{11})^2}{3}\right\rfloor.$$
每个这样的 \(n\) 都唯一对应一个距离 \(L=\sqrt{3n}\)，所以这一步算术化改写与原始几何问题完全等价。
二次型
$$a^2+ab+b^2$$
正是 Eisenstein 整数中的范数，因为
$$a^2+ab+b^2=N(a-b\omega),\qquad \omega=e^{2\pi i/3}.$$
这说明表示个数由素数在模 \(3\) 意义下的类型控制。C++ 文件中的 count_representations_formula 就是这一标准表示公式的直接实现。
把 \(n\) 的素因数分解写成
$$n=3^{e_0}\prod_{p\equiv 1 \pmod{3}}p^{e_p}\prod_{q\equiv 2 \pmod{3}}q^{f_q}.$$
那么表示次数满足：
如果存在某个 \(f_q\) 为奇数，则
$$r(n)=0;$$
否则
$$r(n)=6\prod_{p\equiv 1 \pmod{3}}(e_p+1).$$
原因是：\(p\equiv 1 \pmod{3}\) 的素数在 Eisenstein 整数中分裂，因此带来一个 \(e_p+1\) 因子；\(q\equiv 2 \pmod{3}\) 的素数是惰性的，所以若要可表示，其指数必须是偶数；素数 \(3\) 是分歧的，但除了统一前因子 \(6\) 之外不会额外改变表示重数。
因为
$$450=6\cdot 75,$$
所以必须满足
$$\prod_{p\equiv 1 \pmod{3}}(e_p+1)=75.$$
把 \(75\) 分解成大于 \(1\) 的因子：
$$75,\qquad 25\cdot 3,\qquad 15\cdot 5,\qquad 5\cdot 5\cdot 3.$$
每个因子减去 \(1\)，便得到所有可能的指数多重集合：
$$[74],\qquad [24,2],\qquad [14,4],\qquad [4,4,2].$$
因此任意可行核心都只能是下列四种类型之一：
$$p^{74},\qquad p^{24}q^2,\qquad p^{14}q^4,\qquad p^4q^4r^2,$$
其中 \(p,q,r\equiv 1 \pmod{3}\) 且互不相同。当指数不全相同时，哪个素数拿哪个指数会影响枚举过程，所以代码才会把 \([24,2]\) 与 \([2,24]\)、\([14,4]\) 与 \([4,14]\)、以及 \([4,4,2]\) 的三个有序版本分别处理。
每个合法的 \(n\) 都能唯一写成
$$n=c\cdot t,$$
其中 \(c\) 是承载上述指数模式的核心，只涉及 \(p\equiv 1 \pmod{3}\) 的素数；而 \(t\) 是不会改变 \(r(n)=450\) 的中性乘子。
真正中性的因子只有 \(3\) 的幂和 \(q\equiv 2 \pmod{3}\) 的偶次幂，因此
$$t=3^a u^2,$$
并且 \(u\) 的每个素因子都满足
$$q\equiv 2 \pmod{3}.$$
任何 \(p\equiv 1 \pmod{3}\) 的素数都不能出现在 \(u\) 中，哪怕只以平方形式出现也不行，因为那会改变某个 \(e_p\)，从而改变 \(\prod (e_p+1)\) 的值。
对 \(s\ge 1\)，定义
$$G(s)=\left|\left\{u\le s:\forall q\mid u,\ q\equiv 2 \pmod{3}\right\}\right|.$$
若固定核心 \(c\) 后剩余预算为 \(x\)，则满足 \(t\le x\) 的中性乘子个数为
$$M(x)=\sum_{\substack{a\ge 0\\3^a\le x}} G\!\left(\left\lfloor\sqrt{\frac{x}{3^a}}\right\rfloor\right).$$
这正是 C++ 中 NeutralCounter::count_multipliers 和 Python 中 count_mult 所做的事情。前缀表来自最小素因子筛。代码使用的布尔递推非常直接：
$$\texttt{good}(1)=1,\qquad \texttt{good}(n)=1 \iff \left(\operatorname{spf}(n)\equiv 2 \pmod{3}\right)\land \texttt{good}\!\left(\frac{n}{\operatorname{spf}(n)}\right)=1.$$
做完前缀和之后，\(G(s)\) 查询就是 \(O(1)\)，因此每次 \(M(x)\) 只需枚举 \(3\) 的各个幂次。
最小的可行核心由最小的三个 \(1 \pmod{3}\) 素数组成：
$$c_{\min}=7^4\cdot 13^4\cdot 19^2.$$
所以当 \(N<c_{\min}\) 时，求解器可以立刻返回 \(0\)。这也解释了 C++ 源码中出现的两个结构常量
$$7^4\cdot 13^4\cdot 19^2,\qquad 7^4\cdot 13^4.$$
程序先筛出所有 \(p\equiv 1 \pmod{3}\) 的素数，预计算 \(p^2\) 与 \(p^4\)，再额外保存更短的列表：
$$p^{14}\le N,\qquad p^{24}\le N,\qquad p^{74}\le N.$$
随后枚举以下有序模式：
$$[74],\ [24,2],\ [2,24],\ [14,4],\ [4,14],\ [4,4,2],\ [4,2,4],\ [2,4,4].$$
对每个合法核心 \(c\)，都把
$$M\!\left(\left\lfloor\frac{N}{c}\right\rfloor\right)$$
加入答案。这就是完整算法：先枚举极少量的核心模式，再附加所有仍在上界内的中性乘子。
C++ 实现先对所有 \(1\le n\le 120\) 用暴力格点计数验证公式。它还包含题目本身的几个检查点：
$$r(1)=6 \quad\Rightarrow\quad B(\sqrt{3})=6,$$
$$r(7)=12 \quad\Rightarrow\quad B(\sqrt{21})=12.$$
对验证块里的大整数距离，
$$L=111111111,\qquad n=\frac{L^2}{3}=3^3\cdot 37^2\cdot 333667^2,$$
因此
$$B(L)=r(n)=6(2+1)(2+1)=54,$$
与仓库中的检查值完全一致。
C++ 文件是完整的参考实现。它包含数论公式、暴力验证器、中性乘子筛、幂表预处理以及最终的核心枚举。最重的三素数模式通过 parallel_sum_indices 并行化，但数学内容没有变化。
Python 文件是同一方法的直接算术翻译：相同的指数模式、相同的中性计数器、相同的最终求和。Java 文件并没有独立重写这套数学，而是负责编译并运行 C++ 求解器，再解析其最终输出。因此三个本地解文件本质上实现的是同一个论证，只是在工程层面做了不同取舍。
记
$$N=\left\lfloor\frac{L_{\max}^2}{3}\right\rfloor,\qquad P=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4}}\right\rfloor,\qquad S=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4\cdot 19^2}}\right\rfloor.$$
筛出所有 \(p\equiv 1 \pmod{3}\) 的素数到 \(P\) 的代价接近 \(O(P\log\log P)\)。构建到 \(S\) 的最小素因子表和中性前缀计数，代价也接近 \(O(S\log\log S)\)。这两部分都只需要线性级别的内存。
完成预处理后，每次 \(M(x)\) 查询只需沿着 \(3\) 的幂次做 \(O(\log x)\) 次循环，而每次循环内部只是 \(O(1)\) 的前缀访问。由于指数 \(74\)、\(24\)、\(14\)、\(4\)、\(2\) 让核心值增长极快，核心枚举被强力剪枝。实际运行中，瓶颈来自这些筛法与剪枝后的枚举，而不是几何上的暴力搜索。
Центры ячеек сот образуют треугольную решетку. В аксиальных координатах любое смещение задается двумя целыми числами \(a,b\), а квадрат евклидова расстояния равен
$$L^2 = 3(a^2+ab+b^2).$$
Поэтому функцию подсчета расстояний можно записать как
$$B(L)=\left|\left\{(a,b)\in\mathbb Z^2:3(a^2+ab+b^2)=L^2\right\}\right|.$$
Если \(L^2/3\notin\mathbb Z\), то сразу \(B(L)=0\). Иначе положим
$$n=\frac{L^2}{3},$$
и задача сводится к числу представлений
$$r(n)=\left|\left\{(a,b)\in\mathbb Z^2:a^2+ab+b^2=n\right\}\right|.$$
Локальные реализации фактически считают все \(n\le N\), для которых \(r(n)=450\), где целевая граница репозитория равна
$$N=\left\lfloor\frac{(5\cdot 10^{11})^2}{3}\right\rfloor.$$
Каждому такому \(n\) соответствует ровно одно расстояние \(L=\sqrt{3n}\), поэтому арифметическая формулировка полностью эквивалентна исходной геометрической.
Квадратичная форма
$$a^2+ab+b^2$$
является нормой в кольце целых Эйзенштейна, потому что
$$a^2+ab+b^2=N(a-b\omega),\qquad \omega=e^{2\pi i/3}.$$
Именно поэтому число решеточных представлений определяется поведением простых чисел по модулю \(3\). Функция count_representations_formula в C++ реализует ровно эту стандартную формулу.
Запишем разложение \(n\) на простые множители в виде
$$n=3^{e_0}\prod_{p\equiv 1 \pmod{3}}p^{e_p}\prod_{q\equiv 2 \pmod{3}}q^{f_q}.$$
Тогда количество представлений определяется так:
если хотя бы один показатель \(f_q\) нечетен, то
$$r(n)=0;$$
иначе
$$r(n)=6\prod_{p\equiv 1 \pmod{3}}(e_p+1).$$
Причина структурная. Простые \(p\equiv 1 \pmod{3}\) раскладываются в кольце Эйзенштейна и дают множитель \(e_p+1\). Простые \(q\equiv 2 \pmod{3}\) инертны, поэтому должны входить только с четными степенями. Простое число \(3\) является разветвленным, но не меняет кратность сверх универсального множителя \(6\).
Так как
$$450=6\cdot 75,$$
необходимо, чтобы
$$\prod_{p\equiv 1 \pmod{3}}(e_p+1)=75.$$
Разложим \(75\) на множители, большие \(1\):
$$75,\qquad 25\cdot 3,\qquad 15\cdot 5,\qquad 5\cdot 5\cdot 3.$$
Вычитая из каждого множителя единицу, получаем все возможные мультимножества показателей для простых \(p\equiv 1 \pmod{3}\):
$$[74],\qquad [24,2],\qquad [14,4],\qquad [4,4,2].$$
Значит, любой допустимый ядровой множитель имеет один из видов
$$p^{74},\qquad p^{24}q^2,\qquad p^{14}q^4,\qquad p^4q^4r^2,$$
где \(p,q,r\equiv 1 \pmod{3}\) и различны. Когда показатели различны, важно, как именно они распределены по простым. Поэтому в коде отдельно перечисляются \([24,2]\) и \([2,24]\), \([14,4]\) и \([4,14]\), а также три упорядоченные версии \([4,4,2]\).
Каждое подходящее число \(n\) единственным образом представляется как
$$n=c\cdot t,$$
где \(c\) является ядром с одним из указанных выше шаблонов показателей на простых \(p\equiv 1 \pmod{3}\), а \(t\) не изменяет значение \(r(n)=450\).
Нейтральными могут быть только степени числа \(3\) и четные степени простых \(q\equiv 2 \pmod{3}\). Поэтому
$$t=3^a u^2,$$
где каждый простой делитель числа \(u\) удовлетворяет
$$q\equiv 2 \pmod{3}.$$
Простые \(p\equiv 1 \pmod{3}\) не могут входить в \(u\) даже в квадрате, потому что тогда изменился бы какой-то показатель \(e_p\), а вместе с ним и произведение \(\prod (e_p+1)\).
Для \(s\ge 1\) введем
$$G(s)=\left|\left\{u\le s:\forall q\mid u,\ q\equiv 2 \pmod{3}\right\}\right|.$$
Если после выбора ядра \(c\) остается бюджет \(x\), то число допустимых множителей \(t\le x\) равно
$$M(x)=\sum_{\substack{a\ge 0\\3^a\le x}} G\!\left(\left\lfloor\sqrt{\frac{x}{3^a}}\right\rfloor\right).$$
Именно это вычисляют метод C++ NeutralCounter::count_multipliers и вспомогательная функция Python count_mult. Префиксная таблица строится по решету наименьшего простого делителя. Булева рекурсия в коде имеет вид
$$\texttt{good}(1)=1,\qquad \texttt{good}(n)=1 \iff \left(\operatorname{spf}(n)\equiv 2 \pmod{3}\right)\land \texttt{good}\!\left(\frac{n}{\operatorname{spf}(n)}\right)=1.$$
После накопления префиксных сумм запрос \(G(s)\) выполняется за \(O(1)\), поэтому каждый вызов \(M(x)\) просто перебирает степени тройки.
Минимальное возможное ядро получается из трех наименьших простых чисел \(1 \pmod{3}\):
$$c_{\min}=7^4\cdot 13^4\cdot 19^2.$$
Именно поэтому решатель сразу возвращает \(0\), если \(N<c_{\min}\). Эта же идея объясняет константы
$$7^4\cdot 13^4\cdot 19^2,\qquad 7^4\cdot 13^4,$$
которые хранятся в исходнике C++ как нижние структурные границы.
Программа сначала строит решето по простым \(p\equiv 1 \pmod{3}\), предварительно вычисляет \(p^2\) и \(p^4\), а затем сохраняет более короткие списки, удовлетворяющие
$$p^{14}\le N,\qquad p^{24}\le N,\qquad p^{74}\le N.$$
После этого она перебирает упорядоченные семейства
$$[74],\ [24,2],\ [2,24],\ [14,4],\ [4,14],\ [4,4,2],\ [4,2,4],\ [2,4,4]$$
и для каждого допустимого ядра \(c\) добавляет величину
$$M\!\left(\left\lfloor\frac{N}{c}\right\rfloor\right).$$
В этом и состоит весь алгоритм: перечислить редкие ядровые шаблоны, а затем присоединить все нейтральные множители, которые еще помещаются под ограничение.
Реализация на C++ сначала сверяет формулу с грубым подсчетом по решетке для всех \(1\le n\le 120\). Кроме того, в коде зашиты контрольные значения из задачи:
$$r(1)=6 \quad\Rightarrow\quad B(\sqrt{3})=6,$$
$$r(7)=12 \quad\Rightarrow\quad B(\sqrt{21})=12.$$
Для большого целого расстояния из блока проверки имеем
$$L=111111111,\qquad n=\frac{L^2}{3}=3^3\cdot 37^2\cdot 333667^2,$$
и потому
$$B(L)=r(n)=6(2+1)(2+1)=54,$$
что в точности совпадает с контрольной проверкой в репозитории.
Файл C++ является полной эталонной реализацией. В нем находятся числовая формула, брутфорс-валидаторы, решето нейтральных множителей, таблицы степеней и финальное перечисление ядер. Самые тяжелые семейства с тремя простыми числами распараллеливаются через parallel_sum_indices, но математическая схема не меняется.
Файл Python представляет собой прямую арифметическую запись того же метода: те же семейства показателей, тот же счетчик нейтральных множителей и та же итоговая сумма. Файл Java не реализует математику отдельно, а компилирует и запускает C++-решатель, после чего извлекает финальную строку вывода. Значит, все три локальных решения основаны на одном и том же доказательстве, различаясь только инженерной оболочкой.
Обозначим
$$N=\left\lfloor\frac{L_{\max}^2}{3}\right\rfloor,\qquad P=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4}}\right\rfloor,\qquad S=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4\cdot 19^2}}\right\rfloor.$$
Построение решета по простым \(p\equiv 1 \pmod{3}\) до \(P\) требует примерно \(O(P\log\log P)\) времени. Построение таблицы наименьшего простого делителя и префиксного счетчика до \(S\) также требует примерно \(O(S\log\log S)\) времени. Обе структуры используют линейную память относительно своих пределов.
После предварительной обработки каждый запрос \(M(x)\) делает лишь \(O(\log x)\) шагов по степеням числа \(3\), а внутри каждого шага выполняется \(O(1)\) префиксный доступ. Семейства ядер сильно прорежены, потому что показатели \(74\), \(24\), \(14\), \(4\) и \(2\) очень быстро увеличивают значение ядра. На практике алгоритм определяется именно решетами и этим сильно отсеченным перебором, а не какой-либо геометрической грубой силой.
مراكز خلايا قرص العسل تشكّل شبكة مثلثية. في الإحداثيات المحورية يمكن وصف أي إزاحة بعددين صحيحين \(a,b\)، ويكون مربع المسافة الإقليدية
$$L^2 = 3(a^2+ab+b^2).$$
ومن ثم يمكن كتابة دالة العدّ على الصورة
$$B(L)=\left|\left\{(a,b)\in\mathbb Z^2:3(a^2+ab+b^2)=L^2\right\}\right|.$$
إذا كان \(L^2/3\notin\mathbb Z\) فلدينا مباشرة \(B(L)=0\). أما إذا كان
$$n=\frac{L^2}{3},$$
عدداً صحيحاً، فإن المسألة تتحول إلى عدّ تمثيلات الشكل
$$r(n)=\left|\left\{(a,b)\in\mathbb Z^2:a^2+ab+b^2=n\right\}\right|.$$
ولهذا فإن الملفات المحلية تعدّ جميع القيم \(n\le N\) التي تحقق \(r(n)=450\)، حيث حدّ المسألة في المستودع هو
$$N=\left\lfloor\frac{(5\cdot 10^{11})^2}{3}\right\rfloor.$$
وكل قيمة من هذه القيم تقابل مسافة وحيدة \(L=\sqrt{3n}\)، لذا فالصياغة الحسابية مكافئة تماماً للصياغة الهندسية الأصلية.
الشكل التربيعي
$$a^2+ab+b^2$$
هو معيار في أعداد Eisenstein، لأن
$$a^2+ab+b^2=N(a-b\omega),\qquad \omega=e^{2\pi i/3}.$$
ولهذا يتحكم سلوك الأعداد الأولية بترديد \(3\) في عدد التمثيلات الشبكية. الدالة count_representations_formula في ملف C++ تطبق هذه الصيغة القياسية مباشرة.
لنكتب التحليل الأولي للعدد \(n\) بالشكل
$$n=3^{e_0}\prod_{p\equiv 1 \pmod{3}}p^{e_p}\prod_{q\equiv 2 \pmod{3}}q^{f_q}.$$
عندئذ يتحدد عدد التمثيلات كما يلي:
إذا كان أحد الأسس \(f_q\) فردياً فإن
$$r(n)=0;$$
وإلا فإن
$$r(n)=6\prod_{p\equiv 1 \pmod{3}}(e_p+1).$$
السبب بنيوي. فالأعداد الأولية \(p\equiv 1 \pmod{3}\) تنشطر في أعداد Eisenstein وتضيف عاملاً من الشكل \(e_p+1\). أما الأعداد \(q\equiv 2 \pmod{3}\) فهي خاملة، ولذلك لا بد أن تظهر بأسس زوجية حتى يبقى العدد قابلاً للتمثيل. والعدد الأولي \(3\) متشعب، لكنه لا يغيّر المضاعفية إلا من خلال العامل الثابت \(6\).
بما أن
$$450=6\cdot 75,$$
فلا بد من تحقق
$$\prod_{p\equiv 1 \pmod{3}}(e_p+1)=75.$$
نفكك \(75\) إلى عوامل أكبر من \(1\):
$$75,\qquad 25\cdot 3,\qquad 15\cdot 5,\qquad 5\cdot 5\cdot 3.$$
وبطرح \(1\) من كل عامل نحصل على جميع أنماط الأسس الممكنة على الأعداد الأولية \(p\equiv 1 \pmod{3}\):
$$[74],\qquad [24,2],\qquad [14,4],\qquad [4,4,2].$$
إذن كل نواة صالحة لا بد أن تكون من أحد الأشكال
$$p^{74},\qquad p^{24}q^2,\qquad p^{14}q^4,\qquad p^4q^4r^2,$$
حيث \(p,q,r\equiv 1 \pmod{3}\) أعداد أولية مختلفة. وعندما لا تكون الأسس متساوية، يصبح ترتيب إسنادها إلى الأوليات مهماً، ولهذا يعالج الكود \([24,2]\) و\([2,24]\) كلّاً على حدة، وكذلك \([14,4]\) و\([4,14]\)، إضافة إلى الصور الثلاث المرتبة للنمط \([4,4,2]\).
كل عدد صالح \(n\) يكتب بصورة وحيدة على الشكل
$$n=c\cdot t,$$
حيث تمثل \(c\) النواة التي تحمل واحداً من أنماط الأسس السابقة على الأوليات \(p\equiv 1 \pmod{3}\)، بينما \(t\) هو عامل لا يغيّر القيمة \(r(n)=450\).
العوامل المحايدة الوحيدة هي قوى \(3\) والقوى الزوجية للأوليات \(q\equiv 2 \pmod{3}\). لذلك
$$t=3^a u^2,$$
بحيث يحقق كل قاسم أولي للعدد \(u\) الشرط
$$q\equiv 2 \pmod{3}.$$
ولا يجوز أن يظهر أي أولي من الفئة \(p\equiv 1 \pmod{3}\) داخل \(u\)، حتى ولو ظهر على صورة مربع، لأن ذلك سيزيد أحد الأسس \(e_p\) ويغيّر بالتالي حاصل الضرب \(\prod (e_p+1)\).
لكل \(s\ge 1\) نعرّف
$$G(s)=\left|\left\{u\le s:\forall q\mid u,\ q\equiv 2 \pmod{3}\right\}\right|.$$
إذا كان \(x\) هو الهامش المتبقي بعد تثبيت النواة \(c\)، فإن عدد المضاعفات المحايدة \(t\le x\) يساوي
$$M(x)=\sum_{\substack{a\ge 0\\3^a\le x}} G\!\left(\left\lfloor\sqrt{\frac{x}{3^a}}\right\rfloor\right).$$
وهذا بالضبط ما تحسبه الدالة NeutralCounter::count_multipliers في C++ والمساعد count_mult في Python. يُبنى جدول السوابق باستعمال غربال أصغر عامل أولي. والعلاقة المنطقية التي يستخدمها الكود هي
$$\texttt{good}(1)=1,\qquad \texttt{good}(n)=1 \iff \left(\operatorname{spf}(n)\equiv 2 \pmod{3}\right)\land \texttt{good}\!\left(\frac{n}{\operatorname{spf}(n)}\right)=1.$$
وبعد تكوين المجاميع التراكمية يصبح الاستعلام عن \(G(s)\) ذا كلفة \(O(1)\)، ومن ثم لا يحتاج كل استدعاء لـ \(M(x)\) إلا إلى المرور على قوى العدد \(3\).
أصغر نواة ممكنة تنتج من أصغر ثلاثة أعداد أولية توافق \(1 \pmod{3}\):
$$c_{\min}=7^4\cdot 13^4\cdot 19^2.$$
ولهذا يرجع الحل مباشرة القيمة \(0\) إذا كان \(N<c_{\min}\). كما يفسر هذا أيضاً الثابتين
$$7^4\cdot 13^4\cdot 19^2,\qquad 7^4\cdot 13^4$$
الموجودين في ملف C++ على أنهما حدود بنيوية دنيا.
يبني البرنامج أولاً غربالاً للأوليات \(p\equiv 1 \pmod{3}\)، ثم يحسب مسبقاً \(p^2\) و\(p^4\)، ثم يحتفظ بالقوائم الأقصر التي تحقق
$$p^{14}\le N,\qquad p^{24}\le N,\qquad p^{74}\le N.$$
بعد ذلك يمر على العائلات المرتبة
$$[74],\ [24,2],\ [2,24],\ [14,4],\ [4,14],\ [4,4,2],\ [4,2,4],\ [2,4,4]$$
ولكل نواة صالحة \(c\) يضيف المقدار
$$M\!\left(\left\lfloor\frac{N}{c}\right\rfloor\right).$$
وهذه هي الخوارزمية كلها: نعدّ الأنماط النادرة للنواة، ثم نلحق بها كل المضاعفات المحايدة التي تبقى تحت الحد المطلوب.
تتحقق نسخة C++ أولاً من صحة الصيغة بمقارنتها مع عدّ شبكي مباشر لكل \(1\le n\le 120\). كما تحتوي على نقاط فحص صريحة من المسألة نفسها:
$$r(1)=6 \quad\Rightarrow\quad B(\sqrt{3})=6,$$
$$r(7)=12 \quad\Rightarrow\quad B(\sqrt{21})=12.$$
وبالنسبة للمسافة الصحيحة الكبيرة المستخدمة في التحقق، لدينا
$$L=111111111,\qquad n=\frac{L^2}{3}=3^3\cdot 37^2\cdot 333667^2,$$
ومن ثم
$$B(L)=r(n)=6(2+1)(2+1)=54,$$
وهو بالضبط الرقم الذي يفحصه المستودع.
ملف C++ هو التنفيذ المرجعي الكامل. فهو يحتوي على الصيغة العددية، وفحوص القوة الغاشمة، وغربال المضاعفات المحايدة، وجداول القوى المسبقة، ثم تعداد النوى في النهاية. أما العائلات الأثقل التي تتضمن ثلاثة أوليات فتُوازى بواسطة parallel_sum_indices، لكن البنية الرياضية نفسها لا تتغير.
ملف Python هو ترجمة حسابية مباشرة للطريقة نفسها: الأنماط نفسها، والعداد المحايد نفسه، والمجموع النهائي نفسه. أما ملف Java فلا يعيد تنفيذ الرياضيات من الصفر، بل يقوم بترجمة مشغل C++ وتشغيله ثم تحليل السطر الأخير من الخرج. لذلك فكل الملفات المحلية الثلاثة تعتمد البرهان نفسه، مع اختلاف في القرارات الهندسية فقط.
لنعرّف
$$N=\left\lfloor\frac{L_{\max}^2}{3}\right\rfloor,\qquad P=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4}}\right\rfloor,\qquad S=\left\lfloor\sqrt{\frac{N}{7^4\cdot 13^4\cdot 19^2}}\right\rfloor.$$
بناء غربال للأوليات \(p\equiv 1 \pmod{3}\) حتى \(P\) يكلف تقريباً \(O(P\log\log P)\) زمناً. كما أن بناء جدول أصغر عامل أولي وعدّاد السوابق حتى \(S\) يكلف تقريباً \(O(S\log\log S)\) زمناً. وكلتا البنيتين تحتاجان إلى ذاكرة خطية في حدودهما.
بعد هذا التحضير، يحتاج كل استعلام \(M(x)\) فقط إلى \(O(\log x)\) خطوة عبر قوى \(3\)، مع وصول من نوع \(O(1)\) إلى الجداول في الداخل. أما حلقات العائلات فهي مقصوصة بقوة لأن الأسس \(74\) و\(24\) و\(14\) و\(4\) و\(2\) تجعل قيم النوى تنمو بسرعة شديدة. ولذلك فإن التكلفة العملية تهيمن عليها الغربلة وتعداد النوى بعد القص، لا البحث الهندسي الخام.