Define \(R(k)\) to be the number of representations of \(k\) in the form
$$k=a^2+3ab+b^2,\qquad a \gt b \gt 0.$$
The problem asks for
$$f(n,r)=\#\{k\le n : R(k)=r\},$$
and in particular for \(f(10^{15},40)\). A brute-force search over pairs \((a,b)\) is hopeless, so the solution classifies represented integers by their prime-factor structure in the quadratic field of discriminant \(5\).
The key observation is that the form behaves like a norm. Once that structure is exposed, the exact representation count depends only on the primes that split modulo \(5\), while the factors \(5^t\) and inert squares merely scale the represented integer without changing its multiplicity.
Let
$$\alpha=\frac{3+\sqrt5}{2},\qquad \bar{\alpha}=\frac{3-\sqrt5}{2}.$$
Then
$$a^2+3ab+b^2=(a+b\alpha)(a+b\bar{\alpha}).$$
So the quadratic form is the norm of the algebraic integer \(a+b\alpha\) in the field \(\mathbb{Q}(\sqrt5)\). This is why prime splitting modulo \(5\) controls representability: the discriminant of the form is \(5\), and the arithmetic reduces to how rational primes factor in that field.
For primes \(p\neq 5\), the splitting behavior is:
$$p\equiv 1,4\pmod5 \quad \text{split},\qquad p\equiv 2,3\pmod5 \quad \text{inert}.$$
Therefore a represented integer has the shape
$$k=5^t\left(\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}\right)\left(\prod_{q\equiv 2,3\!\!\!\pmod5} q^{2f_q}\right).$$
The inert primes may appear only with even exponent, while the ramified prime \(5\) may appear with any exponent. It is convenient to separate this as
$$k=x\cdot 5^t\cdot u^2,$$
where
$$x=\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}$$
is the split core, and every prime factor of \(u\) satisfies \(q\equiv 2,3\pmod5\). The important point is that the exact number of representations depends only on \(x\).
For the split core \(x=\prod p^{e_p}\), each split prime \(p\) contributes \(e_p+1\) choices when the factorization is distributed between the two conjugate algebraic factors. Multiplying over all split primes gives
$$\tau(x)=\prod_{p\mid x}(e_p+1),$$
which is exactly the ordinary divisor function of \(x\).
After restricting to the chamber \(a \gt b \gt 0\), conjugate factorizations are paired, and the middle symmetric case does not create a second interior solution. Hence
$$R(k)=\left\lfloor\frac{\tau(x)}{2}\right\rfloor.$$
This explains the condition used by the implementations: \(k\) has exactly \(r\) representations if and only if
$$\tau(x)\in\{2r,\,2r+1\}.$$
Suppose \(\tau(x)=T\), where \(T\) is either \(2r\) or \(2r+1\). Since
$$\tau(x)=\prod_{j=1}^s (e_j+1),$$
every multiplicative partition
$$T=f_1f_2\cdots f_s,\qquad f_j\ge 2,$$
produces an exponent pattern
$$e_j=f_j-1.$$
For example, when \(r=40\), the target values are \(80\) and \(81\). A factorization \(80=5\cdot 4\cdot 4\) yields exponents \((4,3,3)\), corresponding to split cores of the form
$$x=p_1^4p_2^3p_3^3,\qquad p_i\equiv 1,4\pmod5,\quad p_i\ \text{distinct}.$$
So the first stage of the algorithm is purely combinatorial: generate all exponent multisets whose \((e_j+1)\)-product is \(2r\) or \(2r+1\).
Fix one split core \(x\). Any represented number with that same representation count is
$$k=x\cdot 5^t\cdot u^2,$$
with \(u\) composed only of inert primes. Thus for
$$q=\left\lfloor\frac{n}{x}\right\rfloor,$$
the number of admissible multipliers is
$$G(q)=\#\{5^t u^2\le q : u \text{ uses only inert primes}\}.$$
If we define
$$I(y)=\#\{u\le y : \text{every prime factor of }u\text{ is }2\text{ or }3\pmod5\},$$
then
$$G(q)=\sum_{t\ge 0} I\!\left(\left\lfloor\sqrt{\frac{q}{5^t}}\right\rfloor\right),$$
where the sum is finite because \(5^t\le q\). This is exactly the table-driven multiplier count built by the implementations.
For each exponent pattern, the solver assigns those exponents to distinct split primes \(p\equiv 1,4\pmod5\). Because the bound \(x\le n\) matters, different permutations of the same exponent multiset can lead to different feasible products, so distinct orderings must be explored.
The search is pruned aggressively. Two facts are especially useful:
$$\text{largest exponents should be paired with the smallest split primes to get the minimal possible product},$$
and
$$\text{if even that minimal remaining tail already exceeds }n,\text{ the whole branch can be discarded.}$$
After all feasible split cores are generated, the final answer is
$$f(n,r)=\sum_{x\in \mathcal{X}_{n,r}} G\!\left(\left\lfloor\frac{n}{x}\right\rfloor\right),$$
where \(\mathcal{X}_{n,r}\) is the set of split cores satisfying \(\tau(x)\in\{2r,2r+1\}\) and \(x\le n\).
Take
$$209=11\cdot 19.$$
Both primes are split because \(11\equiv 1\pmod5\) and \(19\equiv 4\pmod5\). Hence the split core is \(x=209\) and
$$\tau(x)=(1+1)(1+1)=4,$$
so
$$R(209)=\left\lfloor\frac{4}{2}\right\rfloor=2.$$
Indeed, the two admissible representations are
$$209=13^2+3\cdot 13\cdot 1+1^2=8^2+3\cdot 8\cdot 5+5^2.$$
For an odd divisor count, consider
$$121=11^2,\qquad \tau(121)=3.$$
which gives
$$R(121)=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
and indeed
$$121=7^2+3\cdot 7\cdot 3+3^2.$$
This is exactly why the target condition is \(\tau(x)\in\{2r,2r+1\}\) rather than only \(2r\).
The C++, Python, and Java implementations all follow the same decomposition.
First, they generate every exponent multiset whose \((e_j+1)\)-product equals \(2r\) or \(2r+1\), and they immediately discard any pattern whose smallest possible split core already exceeds \(n\). Next, they estimate how large a split prime could ever be in a feasible core, sieve all split primes up to that bound, and precompute the powers needed for every exponent appearing in the surviving patterns.
Separately, they count inert-only integers up to a square-root bound, turn that prefix information into the multiplier table \(G(q)\), and then perform a depth-first search over increasing split primes. Every completed split core \(x\) contributes \(G(\lfloor n/x\rfloor)\). The C++ implementation also evaluates independent pattern-ordering tasks in parallel, while the Python and Java implementations keep the same mathematical structure with lighter orchestration.
Let \(x_{\min}\) be the smallest feasible split core and let \(M=\lfloor n/x_{\min}\rfloor\). Building the inert-only prefix up to \(\lfloor\sqrt{M}\rfloor\) takes sieve-like time near \(O(\sqrt{M}\log\log M)\), and filling the multiplier table costs \(O(M\log M)\) in the loose bound coming from the powers of \(5\). The remaining cost is the DFS over feasible split cores.
In the worst case that search is combinatorial, but for this problem it stays practical because only exponent patterns arising from \(2r\) and \(2r+1\) are considered, the number of distinct exponents is small, and the minimal-tail pruning removes impossible branches very early. Memory usage is dominated by the multiplier table, the inert-only prefix, and the split-prime power tables.
Sei \(R(k)\) die Anzahl der Darstellungen von \(k\) in der Form
$$k=a^2+3ab+b^2,\qquad a \gt b \gt 0.$$
Gesucht ist
$$f(n,r)=\#\{k\le n : R(k)=r\},$$
insbesondere also \(f(10^{15},40)\). Eine direkte Enumeration aller Paare \((a,b)\) ist viel zu teuer. Die Lösung nutzt stattdessen die Primfaktorstruktur der dargestellten Zahlen in der quadratischen Zahlkörperarithmetik mit Diskriminante \(5\).
Die zentrale Beobachtung ist, dass die Form als Norm geschrieben werden kann. Danach hängt die exakte Darstellungsanzahl nur noch von den Primzahlen ab, die modulo \(5\) zerfallen; Faktoren \(5^t\) und Quadrate aus inertem Anteil verändern die Multiplizität nicht.
Setze
$$\alpha=\frac{3+\sqrt5}{2},\qquad \bar{\alpha}=\frac{3-\sqrt5}{2}.$$
Dann gilt
$$a^2+3ab+b^2=(a+b\alpha)(a+b\bar{\alpha}).$$
Die Form ist also die Norm des algebraischen Integers \(a+b\alpha\) in \(\mathbb{Q}(\sqrt5)\). Genau deshalb wird Darstellbarkeit durch das Zerlegungsverhalten rationaler Primzahlen modulo \(5\) gesteuert.
Für Primzahlen \(p\neq 5\) gilt:
$$p\equiv 1,4\pmod5 \quad \text{split},\qquad p\equiv 2,3\pmod5 \quad \text{inert}.$$
Jede dargestellte Zahl hat daher die Form
$$k=5^t\left(\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}\right)\left(\prod_{q\equiv 2,3\!\!\!\pmod5} q^{2f_q}\right).$$
Inerte Primzahlen dürfen nur mit geradem Exponenten auftreten, während die verzweigte Primzahl \(5\) beliebige Exponenten haben darf. Es ist praktisch, dies als
$$k=x\cdot 5^t\cdot u^2$$
zu schreiben, wobei
$$x=\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}$$
der split-Kern ist und alle Primteiler von \(u\) inert sind. Die Anzahl der Darstellungen hängt nur von \(x\) ab.
Für den split-Kern \(x=\prod p^{e_p}\) liefert jede split-Primzahl \(p\) genau \(e_p+1\) Möglichkeiten, wie ihre Potenz auf die beiden konjugierten algebraischen Faktoren verteilt werden kann. Insgesamt ergibt das
$$\tau(x)=\prod_{p\mid x}(e_p+1),$$
also die gewöhnliche Teilerfunktion von \(x\).
Nach der Einschränkung auf den Bereich \(a \gt b \gt 0\) werden konjugierte Faktorisierungen paarweise identifiziert, und der symmetrische Mittelwertfall erzeugt keine zweite innere Lösung. Deshalb gilt
$$R(k)=\left\lfloor\frac{\tau(x)}{2}\right\rfloor.$$
Somit hat \(k\) genau \(r\) Darstellungen genau dann, wenn
$$\tau(x)\in\{2r,\,2r+1\}.$$
Sei \(\tau(x)=T\) mit \(T\in\{2r,2r+1\}\). Wegen
$$\tau(x)=\prod_{j=1}^s (e_j+1)$$
liefert jede multiplikative Zerlegung
$$T=f_1f_2\cdots f_s,\qquad f_j\ge 2,$$
das Exponentenmuster
$$e_j=f_j-1.$$
Für \(r=40\) sind die Zielwerte also \(80\) und \(81\). Die Zerlegung \(80=5\cdot 4\cdot 4\) führt beispielsweise zu \((4,3,3)\), also zu split-Kernen der Form
$$x=p_1^4p_2^3p_3^3,\qquad p_i\equiv 1,4\pmod5,\quad p_i\ \text{paarweise verschieden}.$$
Der erste algorithmische Schritt besteht folglich darin, alle Exponentenmultimengen zu erzeugen, deren \((e_j+1)\)-Produkt \(2r\) oder \(2r+1\) ist.
Fixiere einen split-Kern \(x\). Dann haben alle Zahlen mit derselben Darstellungsanzahl die Form
$$k=x\cdot 5^t\cdot u^2,$$
wobei \(u\) nur inerte Primzahlen enthält. Für
$$q=\left\lfloor\frac{n}{x}\right\rfloor$$
ist die Anzahl zulässiger Multiplikatoren
$$G(q)=\#\{5^t u^2\le q : u \text{ besteht nur aus inertem Anteil}\}.$$
Definiert man
$$I(y)=\#\{u\le y : \text{alle Primfaktoren von }u\text{ sind }2\text{ oder }3\pmod5\},$$
so folgt
$$G(q)=\sum_{t\ge 0} I\!\left(\left\lfloor\sqrt{\frac{q}{5^t}}\right\rfloor\right).$$
Diese Summe ist endlich, weil nur \(5^t\le q\) beitragen. Genau diese tabellierte Zählung verwendet die Implementierung.
Für jedes Exponentenmuster werden die Exponenten verschiedenen split-Primzahlen \(p\equiv 1,4\pmod5\) zugeordnet. Wegen der Schranke \(x\le n\) können unterschiedliche Permutationen derselben Exponentenmultimenge zu unterschiedlichen zulässigen Produkten führen, daher müssen alle verschiedenen Reihenfolgen betrachtet werden.
Die Tiefensuche wird stark beschnitten. Besonders wichtig sind zwei Beobachtungen:
Das minimale Produkt entsteht, wenn die größten Exponenten den kleinsten split-Primzahlen zugeordnet werden.
Wenn schon dieser minimale Restschwanz \(n\) überschreitet, kann der ganze Ast sofort verworfen werden.
Am Ende ergibt sich
$$f(n,r)=\sum_{x\in \mathcal{X}_{n,r}} G\!\left(\left\lfloor\frac{n}{x}\right\rfloor\right),$$
wobei \(\mathcal{X}_{n,r}\) die Menge aller split-Kerne mit \(\tau(x)\in\{2r,2r+1\}\) und \(x\le n\) bezeichnet.
Betrachte
$$209=11\cdot 19.$$
Beide Primzahlen sind split, denn \(11\equiv 1\pmod5\) und \(19\equiv 4\pmod5\). Also ist der split-Kern \(x=209\) und
$$\tau(x)=(1+1)(1+1)=4,$$
damit
$$R(209)=\left\lfloor\frac{4}{2}\right\rfloor=2.$$
Tatsächlich gibt es genau zwei zulässige Darstellungen:
$$209=13^2+3\cdot 13\cdot 1+1^2=8^2+3\cdot 8\cdot 5+5^2.$$
Für einen ungeraden Teilerwert nehme
$$121=11^2,\qquad \tau(121)=3,$$
also
$$R(121)=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
und tatsächlich
$$121=7^2+3\cdot 7\cdot 3+3^2.$$
Gerade dieses Beispiel erklärt, warum die Zielmenge \(\{2r,2r+1\}\) und nicht nur \(2r\) ist.
Die C++-, Python- und Java-Implementierungen benutzen alle dieselbe Zerlegung.
Zuerst erzeugen sie sämtliche Exponentenmultimengen, deren \((e_j+1)\)-Produkt \(2r\) oder \(2r+1\) ist, und verwerfen sofort jedes Muster, dessen kleinstmöglicher split-Kern bereits größer als \(n\) wäre. Danach schätzen sie eine obere Grenze für relevante split-Primzahlen, sieben alle solchen Primzahlen bis dorthin und berechnen die benötigten Primzahlpotenzen für die vorkommenden Exponenten vor.
Unabhängig davon zählen sie inert-only-Zahlen bis zu einer Quadratwurzelgrenze, bauen daraus die Tabelle \(G(q)\) auf und starten dann eine Tiefensuche über streng wachsende split-Primzahlen. Jeder vollständig erzeugte split-Kern \(x\) trägt \(G(\lfloor n/x\rfloor)\) bei. Die C++-Version verteilt unabhängige Muster- und Permutationsaufgaben zusätzlich auf mehrere Threads; die Python- und Java-Versionen behalten dieselbe mathematische Struktur mit leichterer Ausführungsschicht bei.
Sei \(x_{\min}\) der kleinste zulässige split-Kern und \(M=\lfloor n/x_{\min}\rfloor\). Das Erzeugen des inert-only-Präfixes bis \(\lfloor\sqrt{M}\rfloor\) kostet siebartig ungefähr \(O(\sqrt{M}\log\log M)\), und das Füllen der Tabelle \(G(q)\) benötigt in grober Schranke \(O(M\log M)\), weil für jedes \(q\) über Potenzen von \(5\) summiert wird. Der restliche Aufwand steckt in der Tiefensuche über alle zulässigen split-Kerne.
Im Worst Case ist diese Suche kombinatorisch, in dieser Aufgabe bleibt sie aber handhabbar: Es werden nur Muster aus \(2r\) und \(2r+1\) betrachtet, die Zahl verschiedener Exponenten ist klein, und die Minimalrest-Prüfung schneidet unmögliche Äste sehr früh ab. Der Speicher wird hauptsächlich von der Tabelle \(G\), dem inert-only-Präfix und den Potenztabellen für split-Primzahlen bestimmt.
\(R(k)\),
$$k=a^2+3ab+b^2,\qquad a \gt b \gt 0$$
şeklindeki gösterimlerin sayısı olsun. İstenen değer
$$f(n,r)=\#\{k\le n : R(k)=r\}$$
olup özellikle \(f(10^{15},40)\) hesaplanır. \((a,b)\) çiftlerini doğrudan taramak mümkün değildir; çözüm, temsil edilebilir sayıların asal çarpan yapısını diskriminantı \(5\) olan kuadratik alan üzerinden sınıflandırır.
Ana fikir, formu bir norm olarak yazmaktır. Bunu yaptıktan sonra tam gösterim sayısı yalnızca \(5\) modunda split olan asallara bağlı kalır; \(5^t\) çarpanı ile inert asalların kare katkıları ise sayının büyüklüğünü değiştirir ama gösterim çokluğunu değiştirmez.
Şunu tanımlayalım:
$$\alpha=\frac{3+\sqrt5}{2},\qquad \bar{\alpha}=\frac{3-\sqrt5}{2}.$$
O zaman
$$a^2+3ab+b^2=(a+b\alpha)(a+b\bar{\alpha})$$
olur. Yani bu ifade, \(\mathbb{Q}(\sqrt5)\) alanında \(a+b\alpha\) cebirsel tam sayısının normudur. Bu yüzden temsil edilebilirlik, rasyonel asalların bu alanda nasıl ayrıştığına bağlıdır.
\(p\neq 5\) için ayrışma davranışı şöyledir:
$$p\equiv 1,4\pmod5 \quad \text{split},\qquad p\equiv 2,3\pmod5 \quad \text{inert}.$$
Buna göre temsil edilen her sayı
$$k=5^t\left(\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}\right)\left(\prod_{q\equiv 2,3\!\!\!\pmod5} q^{2f_q}\right)$$
biçimindedir. İnert asallar yalnızca çift üslerle gelebilir; ramifiye olan \(5\) ise herhangi bir üs taşıyabilir. Bunu daha kullanışlı biçimde
$$k=x\cdot 5^t\cdot u^2$$
olarak ayırırız. Burada
$$x=\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}$$
split çekirdektir; \(u\)'nun tüm asal çarpanları inert sınıftandır. Gösterim sayısını belirleyen kısım yalnızca \(x\)'tir.
Split çekirdek \(x=\prod p^{e_p}\) için her split asal \(p\), eşlenik iki cebirsel çarpan arasında \(e_p+1\) farklı dağıtım seçeneği verir. Tüm split asallar çarpılınca
$$\tau(x)=\prod_{p\mid x}(e_p+1)$$
elde edilir; bu, \(x\)'in standart bölen sayısı fonksiyonudur.
\(a \gt b \gt 0\) bölgesine geçtiğimizde eşlenik çarpanlaşmalar çiftler halinde aynı iç çözüm ailesine karşılık gelir; ortadaki simetrik durum ise ikinci bir iç çözüm üretmez. Bu nedenle
$$R(k)=\left\lfloor\frac{\tau(x)}{2}\right\rfloor$$
olur. Dolayısıyla tam olarak \(r\) gösterimi olan sayılar için gerekli ve yeterli koşul
$$\tau(x)\in\{2r,\,2r+1\}$$
şeklindedir.
\(\tau(x)=T\) olsun; burada \(T\), \(2r\) veya \(2r+1\)'den biridir. Çünkü
$$\tau(x)=\prod_{j=1}^s (e_j+1),$$
her
$$T=f_1f_2\cdots f_s,\qquad f_j\ge 2$$
çarpımsal parçalanışı,
$$e_j=f_j-1$$
üs desenini verir. Örneğin \(r=40\) için hedef değerler \(80\) ve \(81\)'dir. \(80=5\cdot 4\cdot 4\) ayrışımı \((4,3,3)\) üslerine karşılık gelir ve split çekirdekler
$$x=p_1^4p_2^3p_3^3,\qquad p_i\equiv 1,4\pmod5.$$
Burada \(p_i\) değerleri birbirinden farklı split asallardır.
şeklinde olur. Bu yüzden algoritmanın ilk işi, \((e_j+1)\) çarpımı \(2r\) veya \(2r+1\) olan tüm üs çokluklarını üretmektir.
Bir split çekirdek \(x\) sabit olsun. Aynı gösterim sayısını veren tüm sayılar
$$k=x\cdot 5^t\cdot u^2$$
biçimindedir; burada \(u\) yalnızca inert asallardan oluşur. Şimdi
$$q=\left\lfloor\frac{n}{x}\right\rfloor$$
için uygun çarpan sayısı
\(\mathcal{I}\), tüm asal çarpanları inert sınıfta olan pozitif tamsayılar kümesi olsun. O zaman
$$G(q)=\#\{5^t u^2\le q : u\in \mathcal{I}\}$$
olur. Eğer
$$I(y)=\#\{u\le y : u\in \mathcal{I}\}$$
tanımlanırsa,
$$G(q)=\sum_{t\ge 0} I\!\left(\left\lfloor\sqrt{\frac{q}{5^t}}\right\rfloor\right)$$
elde edilir. Çünkü \(u^2\le q/5^t\) olması gerekir. Uygulama tam olarak bu tabloyu önceden hesaplar.
Her üs deseni için bu üsler, farklı split asallara \(p\equiv 1,4\pmod5\) atanır. \(x\le n\) sınırı nedeniyle, aynı üs çokluğunun farklı permütasyonları farklı geçerli çarpımlar verebilir; bu yüzden tüm farklı sıralar dikkate alınır.
Derinlik öncelikli arama güçlü biçimde budanır. İki önemli fikir şudur:
En küçük mümkün çarpım, en büyük üsler en küçük split asallara verildiğinde elde edilir.
Bu en küçük kalan kuyruk bile \(n\)'yi aşıyorsa, ilgili dalın tamamı imkansızdır.
Böylece son toplam
$$f(n,r)=\sum_{x\in \mathcal{X}_{n,r}} G\!\left(\left\lfloor\frac{n}{x}\right\rfloor\right)$$
olur; burada \(\mathcal{X}_{n,r}\), \(\tau(x)\in\{2r,2r+1\}\) koşulunu sağlayan ve \(x\le n\) olan tüm split çekirdekler kümesidir.
Şu sayıyı ele alalım:
$$209=11\cdot 19.$$
\(11\equiv 1\pmod5\) ve \(19\equiv 4\pmod5\) olduğundan iki asal da split sınıfındadır. O halde split çekirdek \(x=209\) ve
$$\tau(x)=(1+1)(1+1)=4$$
olur. Buradan
$$R(209)=\left\lfloor\frac{4}{2}\right\rfloor=2$$
çıkar. Gerçekten de iki gösterim vardır:
$$209=13^2+3\cdot 13\cdot 1+1^2=8^2+3\cdot 8\cdot 5+5^2.$$
Tek sayılı bölen durumuna örnek olarak
$$121=11^2,\qquad \tau(121)=3$$
alınır. Bu kez
$$R(121)=\left\lfloor\frac{3}{2}\right\rfloor=1$$
ve gerçekten
$$121=7^2+3\cdot 7\cdot 3+3^2.$$
Bu örnek, neden yalnızca \(2r\) değil \(\{2r,2r+1\}\) hedeflendiğini açıkça gösterir.
C++, Python ve Java uygulamalarının hepsi aynı matematiksel ayrışmayı izler.
Önce \((e_j+1)\) çarpımı \(2r\) ya da \(2r+1\) olan tüm üs çoklukları üretilir; mümkün olan en küçük split çekirdek bile \(n\)'yi geçiyorsa ilgili desen hemen atılır. Sonra gerekli split asal üst sınırı tahmin edilir, bu sınıra kadar tüm split asallar elenir ve kullanılan üsler için gerekli kuvvet tabloları hazırlanır.
Ayrı olarak, karekök ölçeğine kadar inert-only sayılar sayılır, bunlardan \(G(q)\) tablosu üretilir ve ardından artan split asallar üzerinde derinlik öncelikli arama yapılır. Tamamlanan her split çekirdek \(x\), toplama \(G(\lfloor n/x\rfloor)\) kadar katkı verir. C++ sürümü bağımsız desen-permütasyon işlerini çok iş parçacıklı çalıştırabilir; Python ve Java sürümleri ise aynı sayım mantığını daha hafif bir yürütümle uygular.
\(x_{\min}\) en küçük uygun split çekirdek ve \(M=\lfloor n/x_{\min}\rfloor\) olsun. İnert-only önek sayımını \(\lfloor\sqrt{M}\rfloor\) seviyesine kadar üretmek, elek benzeri olarak yaklaşık \(O(\sqrt{M}\log\log M)\) zaman alır. Çarpan tablosu \(G(q)\)'nun doldurulması da, her \(q\) için \(5\) kuvvetleri üzerinden dönüldüğü için kaba sınırla \(O(M\log M)\) düzeyindedir. Kalan maliyet, uygun split çekirdeklerin DFS ile üretimidir.
Bu arama en kötü durumda kombinatoriktir; ancak bu problemde pratik kalır. Çünkü yalnızca \(2r\) ve \(2r+1\)'den gelen desenler kullanılır, farklı üs değerlerinin sayısı küçüktür ve minimal kuyruk kontrolü imkansız dalları çok erken keser. Bellek kullanımı esas olarak \(G\) tablosu, inert-only önek dizisi ve split asal kuvvet tabloları tarafından belirlenir.
Sea \(R(k)\) el número de representaciones de \(k\) de la forma
$$k=a^2+3ab+b^2,\qquad a \gt b \gt 0.$$
La función pedida es
$$f(n,r)=\#\{k\le n : R(k)=r\},$$
y en particular interesa \(f(10^{15},40)\). Un barrido directo de todos los pares \((a,b)\) es inviable, así que la solución reorganiza el problema mediante la factorización prima de los enteros representables en el campo cuadrático de discriminante \(5\).
La idea central es escribir la forma como una norma. Una vez hecho eso, la multiplicidad exacta de representaciones depende solo de los primos que se descomponen módulo \(5\), mientras que el factor \(5^t\) y los cuadrados formados por primos inertes no cambian esa multiplicidad.
Definamos
$$\alpha=\frac{3+\sqrt5}{2},\qquad \bar{\alpha}=\frac{3-\sqrt5}{2}.$$
Entonces
$$a^2+3ab+b^2=(a+b\alpha)(a+b\bar{\alpha}).$$
Por tanto, la forma cuadrática es la norma del entero algebraico \(a+b\alpha\) en \(\mathbb{Q}(\sqrt5)\). Eso explica por qué la aritmética de los primos módulo \(5\) gobierna las representaciones.
Para \(p\neq 5\), el comportamiento es
$$p\equiv 1,4\pmod5 \quad \text{split},\qquad p\equiv 2,3\pmod5 \quad \text{inert}.$$
Así, todo entero representable tiene la forma
$$k=5^t\left(\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}\right)\left(\prod_{q\equiv 2,3\!\!\!\pmod5} q^{2f_q}\right).$$
Los primos inertes solo pueden aparecer con exponente par, mientras que el primo ramificado \(5\) puede aparecer con cualquier exponente. Conviene separar esto como
$$k=x\cdot 5^t\cdot u^2,$$
donde
$$x=\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}$$
es el núcleo split, y todos los factores primos de \(u\) son inertes. El número exacto de representaciones depende únicamente de \(x\).
Si \(x=\prod p^{e_p}\), cada primo split aporta \(e_p+1\) maneras de repartir su potencia entre los dos factores algebraicos conjugados. Al multiplicar todas esas elecciones se obtiene
$$\tau(x)=\prod_{p\mid x}(e_p+1),$$
que es exactamente la función divisor de \(x\).
Al restringirnos a la región \(a \gt b \gt 0\), las factorizaciones conjugadas quedan emparejadas, y el caso central simétrico no produce una segunda solución interior. Por eso
$$R(k)=\left\lfloor\frac{\tau(x)}{2}\right\rfloor.$$
En consecuencia, \(k\) tiene exactamente \(r\) representaciones si y solo si
$$\tau(x)\in\{2r,\,2r+1\}.$$
Sea \(\tau(x)=T\), con \(T\in\{2r,2r+1\}\). Como
$$\tau(x)=\prod_{j=1}^s (e_j+1),$$
cada partición multiplicativa
$$T=f_1f_2\cdots f_s,\qquad f_j\ge 2$$
produce el patrón
$$e_j=f_j-1.$$
Por ejemplo, para \(r=40\) los objetivos son \(80\) y \(81\). La descomposición \(80=5\cdot 4\cdot 4\) da los exponentes \((4,3,3)\), así que los núcleos split correspondientes tienen la forma
$$x=p_1^4p_2^3p_3^3,\qquad p_i\equiv 1,4\pmod5,\quad p_i\ \text{distintos}.$$
De este modo, la primera fase del algoritmo consiste en enumerar todos los multiconjuntos de exponentes cuyo producto \((e_j+1)\) vale \(2r\) o \(2r+1\).
Fijemos un núcleo split \(x\). Todos los enteros con la misma multiplicidad de representación son de la forma
$$k=x\cdot 5^t\cdot u^2,$$
con \(u\) compuesto solo por primos inertes. Si
$$q=\left\lfloor\frac{n}{x}\right\rfloor,$$
el número de multiplicadores válidos es
$$G(q)=\#\{5^t u^2\le q : u \text{ usa solo primos inertes}\}.$$
Definiendo
$$I(y)=\#\{u\le y : \text{todo primo de }u\text{ es }2\text{ o }3\pmod5\},$$
se obtiene
$$G(q)=\sum_{t\ge 0} I\!\left(\left\lfloor\sqrt{\frac{q}{5^t}}\right\rfloor\right).$$
La suma es finita porque solo contribuyen los valores con \(5^t\le q\). Esa es exactamente la tabla previa que construye la implementación.
Para cada patrón de exponentes, el algoritmo asigna esos exponentes a primos split distintos \(p\equiv 1,4\pmod5\). Como existe la restricción \(x\le n\), distintas permutaciones del mismo multiconjunto pueden producir productos factibles diferentes; por eso se exploran todas las ordenaciones distintas.
La búsqueda en profundidad aplica podas fuertes. Dos observaciones son esenciales:
$$\text{para minimizar el producto conviene emparejar los mayores exponentes con los menores primos split},$$
y
Si incluso esa cola mínima ya supera \(n\), toda la rama se descarta.
Al final, la respuesta queda como
$$f(n,r)=\sum_{x\in \mathcal{X}_{n,r}} G\!\left(\left\lfloor\frac{n}{x}\right\rfloor\right),$$
donde \(\mathcal{X}_{n,r}\) es el conjunto de núcleos split con \(\tau(x)\in\{2r,2r+1\}\) y \(x\le n\).
Tomemos
$$209=11\cdot 19.$$
Ambos primos son split, porque \(11\equiv 1\pmod5\) y \(19\equiv 4\pmod5\). Entonces el núcleo split es \(x=209\) y
$$\tau(x)=(1+1)(1+1)=4,$$
de modo que
$$R(209)=\left\lfloor\frac{4}{2}\right\rfloor=2.$$
En efecto, hay exactamente dos representaciones admisibles:
$$209=13^2+3\cdot 13\cdot 1+1^2=8^2+3\cdot 8\cdot 5+5^2.$$
Para ver el caso impar, consideremos
$$121=11^2,\qquad \tau(121)=3.$$
Entonces
$$R(121)=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
y realmente
$$121=7^2+3\cdot 7\cdot 3+3^2.$$
Eso muestra por qué el criterio correcto es \(\{2r,2r+1\}\) y no solo \(2r\).
Las implementaciones en C++, Python y Java siguen exactamente la misma descomposición matemática.
Primero generan todos los multiconjuntos de exponentes cuyo producto \((e_j+1)\) es \(2r\) o \(2r+1\), y descartan en seguida cualquier patrón cuyo menor núcleo split posible ya supere \(n\). Después estiman hasta qué tamaño hace falta considerar primos split, cribando todos esos primos y precalculando las potencias necesarias para cada exponente que aparece en los patrones supervivientes.
En paralelo lógico, cuentan los enteros formados solo por primos inertes hasta una cota de raíz cuadrada, convierten esa información prefija en la tabla \(G(q)\) y realizan luego una búsqueda en profundidad sobre primos split crecientes. Cada núcleo split completo \(x\) añade \(G(\lfloor n/x\rfloor)\). La versión en C++ además reparte tareas independientes entre varios hilos, mientras que las versiones en Python y Java conservan la misma lógica de conteo con una capa de ejecución más ligera.
Sea \(x_{\min}\) el menor núcleo split factible y \(M=\lfloor n/x_{\min}\rfloor\). Construir el prefijo de enteros inertes hasta \(\lfloor\sqrt{M}\rfloor\) cuesta un tiempo tipo criba cercano a \(O(\sqrt{M}\log\log M)\), y rellenar la tabla \(G(q)\) requiere una cota amplia \(O(M\log M)\) porque para cada \(q\) se recorren potencias de \(5\). El coste restante viene de la búsqueda DFS sobre los núcleos split válidos.
En el peor caso esa búsqueda es combinatoria, pero aquí se mantiene controlada: solo se exploran patrones derivados de \(2r\) y \(2r+1\), el número de exponentes distintos es pequeño y la poda por cola mínima elimina ramas imposibles muy pronto. La memoria queda dominada por la tabla \(G\), el prefijo inert-only y las tablas de potencias de primos split.
设 \(R(k)\) 表示整数 \(k\) 可以写成
$$k=a^2+3ab+b^2,\qquad a \gt b \gt 0$$
这种形式的表示个数。题目要求计算
$$f(n,r)=\#\{k\le n : R(k)=r\},$$
特别是 \(f(10^{15},40)\)。如果直接枚举所有 \((a,b)\)，规模会完全失控。真正可行的方法，是先弄清楚这种二元二次型在判别式为 \(5\) 的二次数域中对应怎样的范数分解，然后把问题转化为对素因子结构的计数。
核心思想是把这个二次型改写成一个范数。这样一来，表示次数只由那些在模 \(5\) 意义下分裂的素数决定；而 \(5\) 的幂次以及 inert 素数形成的平方因子只会放大数值大小，不会改变表示的个数。
令
$$\alpha=\frac{3+\sqrt5}{2},\qquad \bar{\alpha}=\frac{3-\sqrt5}{2}.$$
那么有
$$a^2+3ab+b^2=(a+b\alpha)(a+b\bar{\alpha}).$$
这说明该形式正是 \(\mathbb{Q}(\sqrt5)\) 中代数整数 \(a+b\alpha\) 的范数。于是，哪些整数能够被表示，取决于有理素数在这个二次数域里的分解方式；这也正是实现中按模 \(5\) 分类素数的理论来源。
对 \(p\neq 5\) 的素数，分解类型为
$$p\equiv 1,4\pmod5 \quad \text{split},\qquad p\equiv 2,3\pmod5 \quad \text{inert}.$$
因此，一个可表示整数一定形如
$$k=5^t\left(\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}\right)\left(\prod_{q\equiv 2,3\!\!\!\pmod5} q^{2f_q}\right).$$
其中 inert 素数只能以偶数指数出现，而被 \(5\) 分歧的素数 \(5\) 可以带任意指数。把它重新整理成
$$k=x\cdot 5^t\cdot u^2$$
更方便，其中
$$x=\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}$$
称为 split 核心，而 \(u\) 的所有素因子都满足 \(q\equiv 2,3\pmod5\)。最重要的一点是：表示个数完全由 \(x\) 决定，与 \(5^t\) 和 inert 平方部分无关。
设 split 核心为 \(x=\prod p^{e_p}\)。对每个 split 素数 \(p\)，其幂 \(p^{e_p}\) 在两个共轭代数因子之间有 \(e_p+1\) 种分配方式。把所有 split 素数的选择相乘，就得到
$$\tau(x)=\prod_{p\mid x}(e_p+1),$$
这恰好就是 \(x\) 的约数个数函数。
但是题目并不是统计所有代数分解，而是只统计满足 \(a \gt b \gt 0\) 的那一部分。共轭分解会两两配对，对应同一个正区域中的表示；当 \(\tau(x)\) 为奇数时，中间那个对称情形不会额外产生第二个内部解。因此有
$$R(k)=\left\lfloor\frac{\tau(x)}{2}\right\rfloor.$$
于是，整数 \(k\) 恰好有 \(r\) 个表示，当且仅当
$$\tau(x)\in\{2r,\,2r+1\}.$$
这正是实现中为什么要同时处理 \(2r\) 和 \(2r+1\) 的根本原因。
设 \(\tau(x)=T\)，其中 \(T\) 只能是 \(2r\) 或 \(2r+1\)。由于
$$\tau(x)=\prod_{j=1}^s (e_j+1),$$
所以 \(T\) 的每一个乘法拆分
$$T=f_1f_2\cdots f_s,\qquad f_j\ge 2$$
都会对应一个指数模式
$$e_j=f_j-1.$$
例如在本题 \(r=40\) 时，目标值是 \(80\) 和 \(81\)。如果把 \(80\) 分解成
$$80=5\cdot 4\cdot 4,$$
那么得到的指数模式就是 \((4,3,3)\)，对应的 split 核心形如
$$x=p_1^4p_2^3p_3^3,\qquad p_i\equiv 1,4\pmod5.$$
这里的 \(p_i\) 彼此不同，且都属于 split 素数。
因此，算法的第一步其实是一个纯组合问题：枚举所有满足 \(\prod (e_j+1)\in\{2r,2r+1\}\) 的指数多重集。
现在固定一个 split 核心 \(x\)。所有与它具有相同表示次数的整数都可以写成
$$k=x\cdot 5^t\cdot u^2,$$
其中 \(u\) 只含 inert 素数。若记
$$q=\left\lfloor\frac{n}{x}\right\rfloor,$$
那么允许的乘子个数就是
记 \(\mathcal{I}\) 为所有素因子都属于 inert 类的正整数集合，则
$$G(q)=\#\{5^t u^2\le q : u\in \mathcal{I}\}.$$
再定义
$$I(y)=\#\{u\le y : u\in \mathcal{I}\},$$
因为 \(u^2\le q/5^t\)，于是
$$G(q)=\sum_{t\ge 0} I\!\left(\left\lfloor\sqrt{\frac{q}{5^t}}\right\rfloor\right).$$
求和当然是有限的，因为只有 \(5^t\le q\) 时才会有贡献。实现中先预处理 inert-only 数的前缀计数，再把这一公式变成整张查表数组。
对每一个指数模式，算法都要把这些指数分配给不同的 split 素数 \(p\equiv 1,4\pmod5\)。由于存在 \(x\le n\) 的上界，同一个指数多重集的不同排列可能对应不同的可行乘积，所以不能只看排序后的唯一形式，而要检查所有不同排列。
搜索采用深度优先方式，并配合强力剪枝。最关键的两条是：
若想得到当前模式下的最小可能乘积，就应把最大的指数配给最小的 split 素数。
如果连这个最小可能的剩余尾部都已经超过 \(n\)，那么整棵分支都可以直接丢弃。
因此最终答案写成
$$f(n,r)=\sum_{x\in \mathcal{X}_{n,r}} G\!\left(\left\lfloor\frac{n}{x}\right\rfloor\right),$$
其中 \(\mathcal{X}_{n,r}\) 表示所有满足 \(\tau(x)\in\{2r,2r+1\}\) 且 \(x\le n\) 的 split 核心集合。
先看
$$209=11\cdot 19.$$
因为 \(11\equiv 1\pmod5\)，\(19\equiv 4\pmod5\)，所以两个素数都是 split。于是 split 核心就是 \(x=209\)，并且
$$\tau(x)=(1+1)(1+1)=4.$$
因此
$$R(209)=\left\lfloor\frac{4}{2}\right\rfloor=2.$$
实际确实有两种满足 \(a \gt b \gt 0\) 的表示：
$$209=13^2+3\cdot 13\cdot 1+1^2=8^2+3\cdot 8\cdot 5+5^2.$$
再看一个奇数约数个数的例子：
$$121=11^2,\qquad \tau(121)=3.$$
这时
$$R(121)=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
并且确实有
$$121=7^2+3\cdot 7\cdot 3+3^2.$$
这个例子很直观地说明了为什么条件必须写成 \(\{2r,2r+1\}\)，而不是只写成 \(2r\)。
C++、Python 和 Java 实现都遵循完全相同的数学拆分。
第一步是生成所有满足 \(\prod(e_j+1)=2r\) 或 \(2r+1\) 的指数多重集，并立即丢弃那些最小可能 split 核心已经超过 \(n\) 的模式。随后，程序估计需要筛到多大的 split 素数上界，在该范围内筛出所有 split 素数，并为所有出现过的指数预计算相应的素数幂。
与此同时，程序统计到平方根量级为止的 inert-only 整数，把前缀信息转换成乘子表 \(G(q)\)，然后在递增的 split 素数序列上做深度优先搜索。每构造出一个完整的 split 核心 \(x\)，就向总和加入 \(G(\lfloor n/x\rfloor)\)。C++ 版本还会把彼此独立的模式排列任务并行执行；Python 和 Java 版本保留同一套计数逻辑，只是调度方式更轻一些。
设 \(x_{\min}\) 为最小可行 split 核心，\(M=\lfloor n/x_{\min}\rfloor\)。构造到 \(\lfloor\sqrt{M}\rfloor\) 的 inert-only 前缀计数，大致是一次筛法级别的 \(O(\sqrt{M}\log\log M)\) 工作；建立整张 \(G(q)\) 表，在宽松估计下为 \(O(M\log M)\)，因为每个 \(q\) 都要遍历若干个 \(5\) 的幂次。剩余成本主要就是 split 核心的 DFS 枚举。
从最坏情况看，这部分搜索具有组合爆炸的潜在风险；但在本题中它仍然可控，因为只考虑来自 \(2r\) 和 \(2r+1\) 的模式，不同指数的种类很少，而且“最小尾部乘积”剪枝会非常早地砍掉不可能的分支。内存主要消耗在乘子表、inert-only 前缀数组以及 split 素数幂表上。
Обозначим через \(R(k)\) число представлений числа \(k\) в виде
$$k=a^2+3ab+b^2,\qquad a \gt b \gt 0.$$
Требуется вычислить
$$f(n,r)=\#\{k\le n : R(k)=r\},$$
а в самой задаче интересует \(f(10^{15},40)\). Прямой перебор всех пар \((a,b)\) здесь бесполезен. Рабочий подход основан на том, что эта форма связана с нормой в квадратическом поле дискриминанта \(5\), и потому количество представлений определяется структурой простых делителей.
Главная идея состоит в том, чтобы переписать форму как норму. После этого точная кратность представлений зависит только от простых, которые расщепляются по модулю \(5\); множитель \(5^t\) и квадрат из inert-простых изменяют величину числа, но не меняют число представлений.
Положим
$$\alpha=\frac{3+\sqrt5}{2},\qquad \bar{\alpha}=\frac{3-\sqrt5}{2}.$$
Тогда
$$a^2+3ab+b^2=(a+b\alpha)(a+b\bar{\alpha}).$$
Значит, данная бинарная квадратичная форма является нормой алгебраического целого \(a+b\alpha\) в поле \(\mathbb{Q}(\sqrt5)\). Именно поэтому классификация простых по классам modulo \(5\) полностью контролирует представимость.
Для простых \(p\neq 5\) справедливо:
$$p\equiv 1,4\pmod5 \quad \text{split},\qquad p\equiv 2,3\pmod5 \quad \text{inert}.$$
Следовательно, любое представимое число имеет вид
$$k=5^t\left(\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}\right)\left(\prod_{q\equiv 2,3\!\!\!\pmod5} q^{2f_q}\right).$$
Инертные простые могут входить только с чётными показателями, а разветвлённое простое \(5\) может входить с любым показателем. Удобно отделить это так:
$$k=x\cdot 5^t\cdot u^2,$$
где
$$x=\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}$$
есть split-ядро, а все простые делители \(u\) инертны. Важнейший факт: число представлений зависит только от \(x\).
Пусть \(x=\prod p^{e_p}\). Для каждого split-простого \(p\) степень \(p^{e_p}\) можно распределить между двумя сопряжёнными алгебраическими множителями \(e_p+1\) способами. Перемножая эти количества, получаем
$$\tau(x)=\prod_{p\mid x}(e_p+1),$$
то есть обычную функцию числа делителей.
Но задача считает только представления в области \(a \gt b \gt 0\). Сопряжённые факторизации объединяются в пары, а средний симметричный случай не даёт второго внутреннего решения. Поэтому
$$R(k)=\left\lfloor\frac{\tau(x)}{2}\right\rfloor.$$
Значит, число \(k\) имеет ровно \(r\) представлений тогда и только тогда, когда
$$\tau(x)\in\{2r,\,2r+1\}.$$
Пусть \(\tau(x)=T\), где \(T\) равно либо \(2r\), либо \(2r+1\). Так как
$$\tau(x)=\prod_{j=1}^s (e_j+1),$$
каждое мультипликативное разбиение
$$T=f_1f_2\cdots f_s,\qquad f_j\ge 2$$
порождает шаблон показателей
$$e_j=f_j-1.$$
Например, при \(r=40\) нужно рассматривать значения \(80\) и \(81\). Разложение \(80=5\cdot 4\cdot 4\) приводит к показателям \((4,3,3)\), то есть к split-ядрам вида
$$x=p_1^4p_2^3p_3^3,\qquad p_i\equiv 1,4\pmod5.$$
Здесь числа \(p_i\) попарно различны и все они являются split-простыми.
Таким образом, первая фаза алгоритма чисто комбинаторна: перечислить все мультимножества показателей, для которых \(\prod(e_j+1)\) равно \(2r\) или \(2r+1\).
Зафиксируем split-ядро \(x\). Все числа с тем же количеством представлений имеют вид
$$k=x\cdot 5^t\cdot u^2,$$
где \(u\) состоит только из inert-простых. Если
$$q=\left\lfloor\frac{n}{x}\right\rfloor,$$
то число допустимых множителей равно
Обозначим через \(\mathcal{I}\) множество положительных чисел, все простые делители которых inert. Тогда
$$G(q)=\#\{5^t u^2\le q : u\in \mathcal{I}\}.$$
Определим
$$I(y)=\#\{u\le y : u\in \mathcal{I}\}.$$
Тогда, поскольку \(u^2\le q/5^t\), имеем
$$G(q)=\sum_{t\ge 0} I\!\left(\left\lfloor\sqrt{\frac{q}{5^t}}\right\rfloor\right).$$
Сумма конечна, потому что вклад возможен только при \(5^t\le q\). Именно такую таблицу предварительно строят реализации.
Для каждого шаблона показателей алгоритм назначает эти показатели различным split-простым \(p\equiv 1,4\pmod5\). Из-за ограничения \(x\le n\) разные перестановки одного и того же мультимножества могут давать разные допустимые произведения, поэтому нужно просматривать все различные порядки.
Поиск в глубину сильно отсекается. Ключевые наблюдения таковы:
Минимальный продукт получается, когда наименьшим split-простым сопоставляются наибольшие показатели.
Если даже такой минимальный остаточный хвост уже превышает \(n\), то вся ветвь невозможна.
После перечисления всех допустимых ядёр получаем
$$f(n,r)=\sum_{x\in \mathcal{X}_{n,r}} G\!\left(\left\lfloor\frac{n}{x}\right\rfloor\right),$$
где \(\mathcal{X}_{n,r}\) обозначает множество split-ядер, для которых \(\tau(x)\in\{2r,2r+1\}\) и \(x\le n\).
Рассмотрим
$$209=11\cdot 19.$$
Оба простых являются split, поскольку \(11\equiv 1\pmod5\) и \(19\equiv 4\pmod5\). Значит, split-ядро равно \(x=209\), а
$$\tau(x)=(1+1)(1+1)=4.$$
Следовательно,
$$R(209)=\left\lfloor\frac{4}{2}\right\rfloor=2.$$
И действительно, существуют ровно два допустимых представления:
$$209=13^2+3\cdot 13\cdot 1+1^2=8^2+3\cdot 8\cdot 5+5^2.$$
Для нечётного значения функции делителей возьмём
$$121=11^2,\qquad \tau(121)=3.$$
Тогда
$$R(121)=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
и действительно
$$121=7^2+3\cdot 7\cdot 3+3^2.$$
Этот пример наглядно показывает, почему нужно рассматривать множество \(\{2r,2r+1\}\), а не только \(2r\).
Реализации на C++, Python и Java используют одну и ту же математическую схему.
Сначала они генерируют все мультимножества показателей, для которых произведение \((e_j+1)\) равно \(2r\) или \(2r+1\), и сразу отбрасывают те шаблоны, у которых даже наименьшее возможное split-ядро уже больше \(n\). Затем оценивается верхняя граница для нужных split-простых, просеиваются все такие простые до этой границы и заранее вычисляются необходимые степени для каждого встречающегося показателя.
Независимо от этого строится префиксный счётчик inert-only чисел до корневой границы, на его основе создаётся таблица \(G(q)\), а затем запускается DFS по возрастающим split-простым. Каждый полностью построенный split-ядро \(x\) даёт вклад \(G(\lfloor n/x\rfloor)\). В версии на C++ независимые задачи по шаблонам и перестановкам дополнительно распараллеливаются; версии на Python и Java сохраняют ту же логику подсчёта при более лёгкой организации выполнения.
Пусть \(x_{\min}\) — наименьшее допустимое split-ядро, а \(M=\lfloor n/x_{\min}\rfloor\). Построение префикса inert-only чисел до \(\lfloor\sqrt{M}\rfloor\) требует времени порядка \(O(\sqrt{M}\log\log M)\), как в решете. Заполнение таблицы \(G(q)\) в грубой оценке занимает \(O(M\log M)\), потому что для каждого \(q\) перебираются степени числа \(5\). Оставшаяся стоимость определяется поиском по всем допустимым split-ядрам.
В худшем случае этот поиск комбинаторен, но здесь остаётся практичным: рассматриваются только шаблоны, возникающие из \(2r\) и \(2r+1\), число различных показателей мало, а отсечение по минимально возможному хвосту очень рано убирает невозможные ветви. Память в основном уходит на таблицу \(G\), inert-only префикс и таблицы степеней split-простых.
لنرمز بـ \(R(k)\) إلى عدد تمثيلات العدد \(k\) على الصورة
$$k=a^2+3ab+b^2,\qquad a \gt b \gt 0.$$
المطلوب هو حساب
$$f(n,r)=\#\{k\le n : R(k)=r\},$$
وبصورة خاصة \(f(10^{15},40)\). التعداد المباشر لكل الأزواج \((a,b)\) غير عملي تمامًا. الحل الفعلي يعتمد على إعادة تفسير هذا الشكل التربيعي بوصفه معيارًا في حقل تربيعي ذي مميّز \(5\)، ثم عدّ الأعداد القابلة للتمثيل بحسب بنيتها الأولية.
الفكرة الأساسية هي كتابة الشكل على هيئة معيار. عندها يصبح عدد التمثيلات متعلقًا فقط بالأوليات التي تنشطر modulo \(5\)، بينما العامل \(5^t\) ومربعات الأوليات inert يغيّران حجم العدد من دون أن يغيّرا عدد تمثيلاته.
لنعرّف
$$\alpha=\frac{3+\sqrt5}{2},\qquad \bar{\alpha}=\frac{3-\sqrt5}{2}.$$
عندئذٍ
$$a^2+3ab+b^2=(a+b\alpha)(a+b\bar{\alpha}).$$
وهذا يعني أن الشكل المعطى هو معيار العدد الجبري \(a+b\alpha\) في الحقل \(\mathbb{Q}(\sqrt5)\). لذلك فإن سلوك الأوليات في هذا الحقل هو الذي يحكم قابلية التمثيل وعدده.
بالنسبة إلى كل أولي \(p\neq 5\) لدينا
$$p\equiv 1,4\pmod5 \quad \text{split},\qquad p\equiv 2,3\pmod5 \quad \text{inert}.$$
ومن ثم فإن أي عدد قابل للتمثيل يجب أن يكون على الصورة
$$k=5^t\left(\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}\right)\left(\prod_{q\equiv 2,3\!\!\!\pmod5} q^{2f_q}\right).$$
أي إن الأوليات inert لا تظهر إلا بأسس زوجية، بينما الأولي المتشعب \(5\) يمكن أن يظهر بأي أس. ومن المناسب فصل ذلك كما يلي:
$$k=x\cdot 5^t\cdot u^2,$$
حيث
$$x=\prod_{p\equiv 1,4\!\!\!\pmod5} p^{e_p}$$
هو النواة split، وكل أوليات \(u\) من النوع inert. النقطة الحاسمة هنا هي أن عدد التمثيلات يعتمد فقط على \(x\).
إذا كانت \(x=\prod p^{e_p}\)، فإن كل أولي split يساهم بعدد \(e_p+1\) من طرق توزيع قوته بين العاملين الجبريين المترافقين. وبضرب هذه الخيارات نحصل على
$$\tau(x)=\prod_{p\mid x}(e_p+1),$$
وهي بالضبط دالة عدد القواسم العادية.
لكننا لا نعدّ كل التحليلات الجبرية، بل فقط التمثيلات التي تحقق \(a \gt b \gt 0\). التحليلات المترافقة تأتي في أزواج، والحالة الوسطية المتماثلة لا تعطي تمثيلًا داخليًا ثانيًا. لذلك يكون
$$R(k)=\left\lfloor\frac{\tau(x)}{2}\right\rfloor.$$
وعليه فإن العدد \(k\) يملك بالضبط \(r\) تمثيلات إذا وفقط إذا
$$\tau(x)\in\{2r,\,2r+1\}.$$
لنفرض أن \(\tau(x)=T\)، حيث \(T\) يساوي \(2r\) أو \(2r+1\). بما أن
$$\tau(x)=\prod_{j=1}^s (e_j+1),$$
فإن كل تحليل ضربي
$$T=f_1f_2\cdots f_s,\qquad f_j\ge 2$$
يعطي نمط الأسس
$$e_j=f_j-1.$$
في هذه المسألة بالذات، عندما \(r=40\)، تكون القيم المستهدفة هي \(80\) و\(81\). مثلًا التحليل
$$80=5\cdot 4\cdot 4$$
يعطي النمط \((4,3,3)\)، أي نوى split من الشكل
$$x=p_1^4p_2^3p_3^3,\qquad p_i\equiv 1,4\pmod5.$$
وجميع القيم \(p_i\) مختلفة وتنتمي إلى أوليات split.
إذن المرحلة الأولى من الخوارزمية هي توليد كل المجموعات المتعددة للأسس التي تحقق \(\prod(e_j+1)\in\{2r,2r+1\}\).
لنثبت نواة split واحدة \(x\). كل عدد يملك نفس عدد التمثيلات يمكن كتابته بالشكل
$$k=x\cdot 5^t\cdot u^2,$$
حيث \(u\) لا يحتوي إلا على أوليات inert. إذا وضعنا
$$q=\left\lfloor\frac{n}{x}\right\rfloor,$$
فإن عدد المضاعفات المسموح بها هو
ولنرمز بـ \(\mathcal{I}\) إلى مجموعة الأعداد الموجبة التي تكون كل قواسمها الأولية من النوع inert. عندئذٍ
$$G(q)=\#\{5^t u^2\le q : u\in \mathcal{I}\}.$$
ولذلك إذا عرّفنا
$$I(y)=\#\{u\le y : u\in \mathcal{I}\},$$
فإن الشرط \(u^2\le q/5^t\) يعطينا
$$G(q)=\sum_{t\ge 0} I\!\left(\left\lfloor\sqrt{\frac{q}{5^t}}\right\rfloor\right).$$
وهذا الجمع منتهٍ لأن الحد \(5^t\le q\) فقط هو الذي يساهم. التطبيق البرمجي يبني هذه القيم مقدمًا في جدول سريع.
لكل نمط أسس، يجب إسناد هذه الأسس إلى أوليات split مختلفة تحقق \(p\equiv 1,4\pmod5\). وبسبب القيد \(x\le n\)، فإن تبديلات مختلفة لنفس المجموعة المتعددة من الأسس قد تعطي نواتج صالحة مختلفة، لذلك لا بد من فحص كل ترتيب مختلف.
يستخدم الحل بحثًا عمقيًا مع تقليم قوي. ومن أهم الحقائق المستخدمة:
أصغر حاصل ممكن ينتج عندما تُسند أكبر الأسس إلى أصغر أوليات split.
إذا كان حتى هذا الذيل الأدنى يتجاوز \(n\)، فكل الفرع مستحيل ويمكن حذفه فورًا.
وبعد تعداد كل النوى الممكنة نحصل على الصيغة النهائية
$$f(n,r)=\sum_{x\in \mathcal{X}_{n,r}} G\!\left(\left\lfloor\frac{n}{x}\right\rfloor\right),$$
حيث \(\mathcal{X}_{n,r}\) هي مجموعة نوى split التي تحقق \(\tau(x)\in\{2r,2r+1\}\) مع \(x\le n\).
لنأخذ
$$209=11\cdot 19.$$
العددان \(11\) و\(19\) من النوع split لأن
$$11\equiv 1\pmod5,\qquad 19\equiv 4\pmod5.$$
إذن النواة split هي \(x=209\)، ومن ثم
$$\tau(x)=(1+1)(1+1)=4.$$
وبالتالي
$$R(209)=\left\lfloor\frac{4}{2}\right\rfloor=2.$$
وفعلًا يوجد تمثيلان مقبولان:
$$209=13^2+3\cdot 13\cdot 1+1^2=8^2+3\cdot 8\cdot 5+5^2.$$
ولرؤية الحالة الفردية خذ
$$121=11^2,\qquad \tau(121)=3.$$
عندئذٍ
$$R(121)=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
وبالفعل
$$121=7^2+3\cdot 7\cdot 3+3^2.$$
هذا يوضح مباشرة لماذا الشرط الصحيح هو \(\{2r,2r+1\}\) وليس \(2r\) فقط.
تتبع تطبيقات C++ وPython وJava نفس التفكيك الرياضي تمامًا.
في البداية تُولَّد كل أنماط الأسس التي يساوي فيها حاصل \((e_j+1)\) أحد العددين \(2r\) أو \(2r+1\)، ثم يُستبعد فورًا أي نمط يكون أصغر حاصل split ممكن له أكبر من \(n\). بعد ذلك تُقدَّر أكبر قيمة لازمة لأوليات split، وتُجرى غربلة لهذه الأوليات حتى هذا الحد، وتُحسب مسبقًا القوى المطلوبة لكل أس يظهر في الأنماط الباقية.
بالتوازي المنطقي مع ذلك، يُبنى عدّ تراكمي للأعداد inert-only حتى حد من رتبة الجذر التربيعي، ثم يتحول هذا العد إلى جدول \(G(q)\)، وبعدها يبدأ بحث عمقي على أوليات split المتزايدة. كل نواة split مكتملة \(x\) تضيف المقدار \(G(\lfloor n/x\rfloor)\) إلى الجواب. إصدار C++ يوزع أيضًا المهام المستقلة على عدة خيوط، بينما يحافظ إصدارا Python وJava على البنية الحسابية نفسها مع تنظيم تنفيذ أخف.
إذا كانت \(x_{\min}\) أصغر نواة split ممكنة و\(M=\lfloor n/x_{\min}\rfloor\)، فإن بناء البادئة الخاصة بالأعداد inert-only حتى \(\lfloor\sqrt{M}\rfloor\) يأخذ زمنًا قريبًا من \(O(\sqrt{M}\log\log M)\) على طريقة الغربلة. أما ملء جدول \(G(q)\) فيأخذ حدًا خشنًا من رتبة \(O(M\log M)\) لأن كل \(q\) يجمع على قوى للعدد \(5\). وما تبقى من الكلفة الحسابية يتركز في DFS الذي يولد نوى split الممكنة.
أسوأ حالة لهذا البحث هي حالة تركيبية، لكنه يبقى عمليًا هنا لأن الأنماط لا تأتي إلا من \(2r\) و\(2r+1\)، وعدد الأسس المختلفة صغير، واختبار الذيل الأدنى يزيل الفروع المستحيلة في وقت مبكر جدًا. أما الذاكرة فتسيطر عليها بصورة أساسية جداول \(G\)، وبادئة inert-only، وجداول قوى أوليات split.