Let \(T(N)\) denote the number of integer-sided triangles that contain a \(60^\circ\) angle and whose incircle radius does not exceed \(N\). The specific task is to evaluate \(T(1{,}053{,}779)\).
A brute-force search over side triples would be far too large, because the geometric condition mixes a Diophantine constraint from the \(60^\circ\) angle with a second constraint on the inradius. The implementations therefore replace direct triangle enumeration by a parametrization of primitive objects and then count all admissible integer scalings.
The key observation is that a \(60^\circ\) triangle can be converted into a \(120^\circ\) triangle with integer sides, and the latter has a classical coprime parametrization. Once that primitive parametrization is known, the inradius becomes a simple linear expression, so counting triangles reduces to summing the number of allowed scale factors.
Take a triangle whose \(60^\circ\) angle lies between the integer sides \(a\) and \(b\), and let \(c\) be the side opposite that angle. Without loss of generality order the adjacent sides so that \(a \le b\). The law of cosines gives
$$c^2=a^2+b^2-ab.$$
Now write \(x=a\) and \(y=b-a\), so \(b=x+y\). Substituting this into the cosine-law relation yields
$$c^2=x^2+(x+y)^2-x(x+y)=x^2+xy+y^2.$$
So every target triangle determines an integer triple \((x,y,z)\) with
$$z^2=x^2+xy+y^2.$$
This is exactly the side relation for a triangle with a \(120^\circ\) angle. Conversely, any positive integer solution of \(z^2=x^2+xy+y^2\) generates two \(60^\circ\) triangles:
$$ (x,\ x+y,\ z)\qquad\text{and}\qquad (y,\ x+y,\ z). $$
That is why the counting formula naturally splits into two families.
For primitive solutions of \(z^2=x^2+xy+y^2\), the implementations use the standard parametrization
$$x=m^2-n^2,\qquad y=2mn+n^2,\qquad z=m^2+mn+n^2,$$
where
$$m>n\ge 1,\qquad \gcd(m,n)=1,\qquad m\not\equiv n \pmod{3}.$$
The coprimality condition removes common factors, and the congruence restriction eliminates the redundant non-primitive cases. It is convenient to replace \(m\) by
$$t=m-n,$$
so that \(m=n+t\), \(\gcd(m,n)=\gcd(n,t)\), and the congruence condition becomes simply \(t\not\equiv 0\pmod 3\).
Family A uses the triangle \((x,\ x+y,\ z)\). Since \(x+y=m^2+2mn=m(m+2n)\), its area is
$$\Delta_A=\frac{\sqrt{3}}{4}\,x(x+y),$$
and its semiperimeter is
$$s_A=\frac{x+(x+y)+z}{2}=\frac{2x+y+z}{2}=\frac{3m(m+n)}{2}.$$
Therefore
$$r_A=\frac{\Delta_A}{s_A}=\frac{\sqrt{3}}{6}(m-n)(m+2n)=\frac{\sqrt{3}}{6}\,t(3n+t).$$
Family B uses the triangle \((y,\ x+y,\ z)\). Its area and semiperimeter are
$$\Delta_B=\frac{\sqrt{3}}{4}\,y(x+y),\qquad s_B=\frac{y+(x+y)+z}{2}=\frac{x+2y+z}{2}=\frac{(m+2n)(2m+n)}{2},$$
so its inradius becomes
$$r_B=\frac{\Delta_B}{s_B}=\frac{\sqrt{3}}{2}mn=\frac{\sqrt{3}}{2}\,n(n+t).$$
If a primitive triangle is scaled by an integer factor \(k\), all side lengths and the inradius scale by the same factor. Hence the two non-primitive families are counted through
$$r_A(k)=\frac{k\sqrt{3}}{6}\,q_A,\qquad q_A=t(3n+t),$$
$$r_B(k)=\frac{k\sqrt{3}}{2}\,q_B,\qquad q_B=n(n+t).$$
For a fixed primitive object, the only remaining question is how many positive integers \(k\) keep the inradius below \(N\). Family B requires
$$\frac{k\sqrt{3}}{2}\,q_B\le N,$$
so the number of valid scales is
$$\left\lfloor \frac{2N}{q_B\sqrt{3}} \right\rfloor.$$
Family A analogously contributes
$$\left\lfloor \frac{6N}{q_A\sqrt{3}} \right\rfloor.$$
This is the central invariant used by the code. If we define
$$M_C(q)=\left\lfloor \frac{C}{q\sqrt{3}} \right\rfloor,$$
then the total count is
$$T(N)=\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{2N}\!\bigl(n(n+t)\bigr)+\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{6N}\!\bigl(t(3n+t)\bigr),$$
with the understanding that only pairs satisfying \(q_B\le 2N/\sqrt3\) or \(q_A\le 6N/\sqrt3\) contribute at all. The two sums are finite because once \(q\) exceeds its threshold, even the primitive scale \(k=1\) is already too large.
Choose \(m=2\) and \(n=1\), so \(t=1\). The primitive \(120^\circ\) triple is
$$x=2^2-1^2=3,\qquad y=2\cdot2\cdot1+1^2=5,\qquad z=2^2+2\cdot1+1^2=7.$$
This generates the two primitive \(60^\circ\) triangles
$$ (3,8,7)\qquad\text{and}\qquad (5,8,7). $$
For Family A,
$$q_A=t(3n+t)=1\cdot(3+1)=4,\qquad r_A=\frac{\sqrt3}{6}\cdot 4=\frac{2\sqrt3}{3}.$$
For Family B,
$$q_B=n(n+t)=1\cdot2=2,\qquad r_B=\frac{\sqrt3}{2}\cdot 2=\sqrt3.$$
If, for illustration, \(N=10\), then the admissible scale counts would be
$$\left\lfloor \frac{60}{4\sqrt3}\right\rfloor=8\qquad\text{and}\qquad \left\lfloor \frac{20}{2\sqrt3}\right\rfloor=5.$$
The actual problem uses a much larger \(N\), but the counting mechanism is identical: each primitive parameter pair contributes exactly the number of legal integer scalings.
The implementations organize the computation around the function \(M_C(q)=\lfloor C/(q\sqrt3)\rfloor\). They build one table for \(C=2N\) and another for \(C=6N\), because the two triangle families differ only in that constant and in the definition of \(q\).
Each table entry stores the largest \(k\) such that \(qk\sqrt3\le C\). Instead of trusting floating-point arithmetic at the boundary, the code converts this to the exact integer inequality
$$3q^2k^2\le C^2.$$
A square-root estimate is used only as a starting guess; it is then corrected upward or downward until the inequality is exact. This prevents off-by-one errors near values where \(C/(q\sqrt3)\) lies extremely close to an integer.
After the tables are ready, the code loops over the primitive parameters \((n,t)\). For Family B it walks through \(n\) and then all \(t\) for which \(q_B=n(n+t)\) still fits under the table bound. For Family A it walks through \(t\) and then all \(n\) for which \(q_A=t(3n+t)\) fits. In both cases it enforces \(\gcd(n,t)=1\) and skips \(t\) divisible by 3.
Every valid pair contributes a single precomputed table lookup, so the total is just the sum of those entries across both families. The C++ implementation can distribute the outer parameter loop across several threads, while the Python and Java implementations perform the same arithmetic serially. The C++ version also checks the known values \(T(100)=1234\), \(T(1000)=22767\), and \(T(10000)=359912\) before evaluating the full target.
Let
$$Q_B=\left\lfloor\frac{2N}{\sqrt3}\right\rfloor,\qquad Q_A=\left\lfloor\frac{6N}{\sqrt3}\right\rfloor.$$
Building the two lookup tables costs \(O(Q_A+Q_B)=O(N)\) time and memory. The primitive enumeration for Family B visits
$$\sum_{n\le \sqrt{Q_B}} O\!\left(\frac{Q_B}{n}\right)=O(Q_B\log Q_B),$$
candidate pairs before the gcd filter, and Family A behaves similarly:
$$\sum_{t\le \sqrt{Q_A}} O\!\left(\frac{Q_A}{t}\right)=O(Q_A\log Q_A).$$
Hence the overall running time is \(O(N\log N)\), with \(O(N)\) memory for the scale tables. This is dramatically smaller than any direct search over side triples, because the geometry has already been compressed into two structured Diophantine families.
Sei \(T(N)\) die Anzahl der Dreiecke mit ganzzahligen Seiten, die einen Winkel von \(60^\circ\) besitzen und deren Inkreisradius höchstens \(N\) ist. Gesucht ist konkret \(T(1{,}053{,}779)\).
Ein naiver Suchlauf über alle möglichen Seitenlängen wäre viel zu groß. Die Bedingung für den \(60^\circ\)-Winkel liefert bereits eine diophantische Gleichung, und zusätzlich muss auch noch der Inkreisradius beschränkt werden. Deshalb arbeiten die Implementierungen nicht direkt mit Dreiecken, sondern mit einer primitiven Parametrisierung und zählen anschließend nur noch zulässige Skalierungen.
Der Kern der Lösung ist eine Umformung von \(60^\circ\)-Dreiecken in ganzzahlige \(120^\circ\)-Tripel. Für diese Tripel gibt es eine klassische Parametrisierung durch teilerfremde ganze Zahlen. Danach wird der Inkreisradius zu einem linearen Ausdruck, und das Zählen reduziert sich auf eine saubere Summation über ganzzahlige Vielfache.
Betrachte ein Dreieck, bei dem der \(60^\circ\)-Winkel zwischen den ganzzahligen Seiten \(a\) und \(b\) liegt; die gegenüberliegende Seite sei \(c\). Ohne Einschränkung gelte \(a\le b\). Aus dem Kosinussatz folgt
$$c^2=a^2+b^2-ab.$$
Setzt man nun \(x=a\) und \(y=b-a\), also \(b=x+y\), dann wird daraus
$$c^2=x^2+(x+y)^2-x(x+y)=x^2+xy+y^2.$$
Damit liefert jedes gesuchte Dreieck ein ganzzahliges Tripel \((x,y,z)\) mit
$$z^2=x^2+xy+y^2.$$
Das ist genau die Seitenbeziehung eines Dreiecks mit einem Winkel von \(120^\circ\). Umgekehrt erzeugt jedes positive ganzzahlige Tripel dieser Form zwei \(60^\circ\)-Dreiecke:
$$ (x,\ x+y,\ z)\qquad\text{und}\qquad (y,\ x+y,\ z). $$
Genau daraus entstehen in der Lösung die beiden Familien.
Für primitive Lösungen von \(z^2=x^2+xy+y^2\) benutzen die Implementierungen die Standardform
$$x=m^2-n^2,\qquad y=2mn+n^2,\qquad z=m^2+mn+n^2,$$
mit den Bedingungen
$$m>n\ge 1,\qquad \gcd(m,n)=1,\qquad m\not\equiv n \pmod{3}.$$
Die Teilerfremdheit stellt die Primitivität sicher; die Kongruenzbedingung entfernt die überzähligen nicht-primitiven Fälle. Für die Implementierung ist es günstiger, statt \(m\) die Differenz
$$t=m-n$$
zu verwenden. Dann gilt \(m=n+t\), außerdem \(\gcd(m,n)=\gcd(n,t)\), und die Bedingung modulo 3 vereinfacht sich zu \(t\not\equiv 0\pmod 3\).
Familie A verwendet das Dreieck \((x,\ x+y,\ z)\). Weil \(x+y=m^2+2mn=m(m+2n)\) ist, erhält man für die Fläche
$$\Delta_A=\frac{\sqrt{3}}{4}\,x(x+y),$$
und für den Halbumfang
$$s_A=\frac{x+(x+y)+z}{2}=\frac{2x+y+z}{2}=\frac{3m(m+n)}{2}.$$
Damit folgt
$$r_A=\frac{\Delta_A}{s_A}=\frac{\sqrt{3}}{6}(m-n)(m+2n)=\frac{\sqrt{3}}{6}\,t(3n+t).$$
Familie B verwendet das Dreieck \((y,\ x+y,\ z)\). Hier sind
$$\Delta_B=\frac{\sqrt{3}}{4}\,y(x+y),\qquad s_B=\frac{y+(x+y)+z}{2}=\frac{x+2y+z}{2}=\frac{(m+2n)(2m+n)}{2},$$
woraus
$$r_B=\frac{\Delta_B}{s_B}=\frac{\sqrt{3}}{2}mn=\frac{\sqrt{3}}{2}\,n(n+t)$$
folgt. Skaliert man ein primitives Dreieck mit einem ganzzahligen Faktor \(k\), dann skalieren alle Seiten und auch der Inkreisradius mit demselben Faktor. Deshalb werden die nicht-primitiven Fälle über
$$r_A(k)=\frac{k\sqrt{3}}{6}\,q_A,\qquad q_A=t(3n+t),$$
$$r_B(k)=\frac{k\sqrt{3}}{2}\,q_B,\qquad q_B=n(n+t)$$
gezählt.
Für ein festes primitives Dreieck bleibt nur noch die Frage, wie viele positive ganze Zahlen \(k\) den Radius unterhalb von \(N\) halten. Für Familie B gilt
$$\frac{k\sqrt{3}}{2}\,q_B\le N,$$
also gibt es
$$\left\lfloor \frac{2N}{q_B\sqrt{3}} \right\rfloor$$
zulässige Skalierungen. Für Familie A entsprechend
$$\left\lfloor \frac{6N}{q_A\sqrt{3}} \right\rfloor.$$
Genau diese Größe wird von der Implementierung tabelliert. Mit
$$M_C(q)=\left\lfloor \frac{C}{q\sqrt{3}} \right\rfloor$$
lautet die Gesamtzahl
$$T(N)=\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{2N}\!\bigl(n(n+t)\bigr)+\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{6N}\!\bigl(t(3n+t)\bigr).$$
Nur Parameterpaare mit \(q_B\le 2N/\sqrt3\) bzw. \(q_A\le 6N/\sqrt3\) tragen überhaupt bei, denn darüber ist schon der primitive Fall \(k=1\) zu groß.
Wähle \(m=2\) und \(n=1\), also \(t=1\). Dann ist das primitive \(120^\circ\)-Tripel
$$x=2^2-1^2=3,\qquad y=2\cdot2\cdot1+1^2=5,\qquad z=2^2+2\cdot1+1^2=7.$$
Daraus entstehen die beiden primitiven \(60^\circ\)-Dreiecke
$$ (3,8,7)\qquad\text{und}\qquad (5,8,7). $$
Für Familie A gilt
$$q_A=t(3n+t)=1\cdot(3+1)=4,\qquad r_A=\frac{\sqrt3}{6}\cdot4=\frac{2\sqrt3}{3}.$$
Für Familie B gilt
$$q_B=n(n+t)=1\cdot2=2,\qquad r_B=\frac{\sqrt3}{2}\cdot2=\sqrt3.$$
Nimmt man nur zur Illustration \(N=10\), dann sind die zulässigen Skalierungszahlen
$$\left\lfloor \frac{60}{4\sqrt3}\right\rfloor=8\qquad\text{und}\qquad \left\lfloor \frac{20}{2\sqrt3}\right\rfloor=5.$$
Für das eigentliche Problem ist \(N\) viel größer, aber genau dieselbe Logik gilt unverändert: Jedes primitive Parameterpaar trägt exakt die Anzahl seiner zulässigen ganzzahligen Skalierungen bei.
Die Implementierungen organisieren die gesamte Rechnung um die Funktion \(M_C(q)=\lfloor C/(q\sqrt3)\rfloor\). Es wird eine Tabelle für \(C=2N\) und eine zweite für \(C=6N\) aufgebaut, weil sich die beiden Dreiecksfamilien nur in dieser Konstante und in der Definition von \(q\) unterscheiden.
Jeder Tabelleneintrag speichert das größte \(k\) mit \(qk\sqrt3\le C\). Statt sich auf Fließkommawerte an der Grenze zu verlassen, formt die Implementierung das in die exakte Ungleichung
$$3q^2k^2\le C^2$$
um. Ein Wurzelwert dient nur als Startschätzer und wird danach mit ganzzahliger Kontrolle nach oben oder unten korrigiert. So entstehen keine Off-by-one-Fehler an kritischen Grenzen.
Danach werden die primitiven Parameter \((n,t)\) enumeriert. Für Familie B läuft der äußere Parameter über \(n\), und für jedes \(n\) werden alle \(t\) mit \(q_B=n(n+t)\) innerhalb der Tabellengrenze untersucht. Für Familie A läuft der äußere Parameter über \(t\), und dazu alle \(n\) mit \(q_A=t(3n+t)\) innerhalb der Grenze. In beiden Fällen wird \(\gcd(n,t)=1\) verlangt, und alle \(t\), die durch 3 teilbar sind, werden übersprungen.
Jedes zulässige Paar liefert genau einen vorberechneten Tabellenwert. Die Gesamtsumme ist daher nichts anderes als die Summe dieser Einträge über beide Familien. Die C++-Implementierung kann die äußeren Schleifen auf mehrere Threads verteilen; die Python- und Java-Implementierungen führen dieselben Rechnungen seriell aus. Zusätzlich prüft die C++-Version vor dem Hauptlauf die bekannten Werte \(T(100)=1234\), \(T(1000)=22767\) und \(T(10000)=359912\).
Setze
$$Q_B=\left\lfloor\frac{2N}{\sqrt3}\right\rfloor,\qquad Q_A=\left\lfloor\frac{6N}{\sqrt3}\right\rfloor.$$
Der Aufbau der beiden Nachschlagetabellen kostet \(O(Q_A+Q_B)=O(N)\) Zeit und Speicher. Die Enumeration der primitiven Paare für Familie B betrachtet vor dem ggT-Filter
$$\sum_{n\le \sqrt{Q_B}} O\!\left(\frac{Q_B}{n}\right)=O(Q_B\log Q_B)$$
Kandidaten, und Familie A verhält sich analog:
$$\sum_{t\le \sqrt{Q_A}} O\!\left(\frac{Q_A}{t}\right)=O(Q_A\log Q_A).$$
Insgesamt ergibt sich also \(O(N\log N)\) Laufzeit bei \(O(N)\) Speicherbedarf. Das ist um Größenordnungen besser als jede direkte Suche über Seitenlängen, weil die geometrische Struktur schon im Voraus in zwei geordnete diophantische Familien eingearbeitet wurde.
\(T(N)\), bir açısı \(60^\circ\) olan ve içteğet çember yarıçapı en fazla \(N\) olan tam kenarlı üçgenlerin sayısı olsun. Soruda istenen değer \(T(1{,}053{,}779)\)'dur.
Kenar üçlüleri üzerinde doğrudan arama yapmak verimli değildir. Çünkü hem \(60^\circ\) açı koşulu ayrı bir diofant denklemi üretir hem de içyarıçap için ikinci bir eşitsizlik gerekir. Bu yüzden uygulamalar üçgenleri tek tek taramak yerine, önce ilkel nesneleri parametrize eder, sonra da izin verilen tam sayı ölçeklerini sayar.
Temel fikir, \(60^\circ\) açılı bir üçgeni tam kenarlı bir \(120^\circ\) üçgenine dönüştürmektir. \(120^\circ\) üçgenleri için bilinen bir ilkel parametreleştirme vardır. Bu parametreleştirme kullanıldığında içyarıçap son derece basit, doğrusal bir ifadeye dönüşür; böylece sorun, uygun ölçek katsayılarını toplamaya indirgenir.
\(60^\circ\) açısı \(a\) ve \(b\) kenarları arasında bulunan bir üçgen alalım; bu açının karşısındaki kenar \(c\) olsun. Genelliği bozmadan \(a\le b\) diyelim. Kosinüs teoreminden
$$c^2=a^2+b^2-ab$$
gelir. Şimdi \(x=a\) ve \(y=b-a\) yazalım; böylece \(b=x+y\) olur. Yerine koyarsak
$$c^2=x^2+(x+y)^2-x(x+y)=x^2+xy+y^2$$
elde edilir. Yani her hedef üçgen,
$$z^2=x^2+xy+y^2$$
eşitliğini sağlayan bir tam sayı üçlüsüne karşılık gelir. Bu da tam olarak bir açısı \(120^\circ\) olan üçgenlerin kenar bağıntısıdır. Tersi yönde de her böyle üçlü iki tane \(60^\circ\) üçgen üretir:
$$ (x,\ x+y,\ z)\qquad\text{ve}\qquad (y,\ x+y,\ z). $$
Çözümdeki iki ailenin kaynağı budur.
\(z^2=x^2+xy+y^2\) denkleminin ilkel çözümleri için uygulamalar şu standart parametreleri kullanır:
$$x=m^2-n^2,\qquad y=2mn+n^2,\qquad z=m^2+mn+n^2,$$
burada
$$m>n\ge 1,\qquad \gcd(m,n)=1,\qquad m\not\equiv n \pmod{3}.$$
EBOB koşulu ortak çarpanları temizler; mod 3 koşulu ise ilkel olmayan tekrarları dışarıda bırakır. Uygulama açısından \(m\) yerine
$$t=m-n$$
farkını kullanmak daha elverişlidir. Böylece \(m=n+t\), ayrıca \(\gcd(m,n)=\gcd(n,t)\) olur ve mod 3 kısıtı da \(t\not\equiv0\pmod3\) biçimine iner.
A Tipi, \((x,\ x+y,\ z)\) üçgenini kullanır. \(x+y=m^2+2mn=m(m+2n)\) olduğundan alan
$$\Delta_A=\frac{\sqrt{3}}{4}\,x(x+y),$$
yarı çevre ise
$$s_A=\frac{x+(x+y)+z}{2}=\frac{2x+y+z}{2}=\frac{3m(m+n)}{2}$$
olur. Dolayısıyla
$$r_A=\frac{\Delta_A}{s_A}=\frac{\sqrt{3}}{6}(m-n)(m+2n)=\frac{\sqrt{3}}{6}\,t(3n+t).$$
B Tipi, \((y,\ x+y,\ z)\) üçgenidir. Burada
$$\Delta_B=\frac{\sqrt{3}}{4}\,y(x+y),\qquad s_B=\frac{y+(x+y)+z}{2}=\frac{x+2y+z}{2}=\frac{(m+2n)(2m+n)}{2},$$
ve sonuç olarak
$$r_B=\frac{\Delta_B}{s_B}=\frac{\sqrt{3}}{2}mn=\frac{\sqrt{3}}{2}\,n(n+t)$$
elde edilir. İlkel bir üçgen \(k\) ile ölçeklenirse bütün kenarlar ve içyarıçap da \(k\) ile çarpılır. Bu yüzden ilkel olmayan üçgenler şu biçimde sayılır:
$$r_A(k)=\frac{k\sqrt{3}}{6}\,q_A,\qquad q_A=t(3n+t),$$
$$r_B(k)=\frac{k\sqrt{3}}{2}\,q_B,\qquad q_B=n(n+t).$$
Sabit bir ilkel temel üçgen için geriye sadece, kaç farklı pozitif \(k\) değerinin içyarıçapı \(N\)'in altında tuttuğu sorusu kalır. B Tipinde
$$\frac{k\sqrt{3}}{2}\,q_B\le N$$
olduğundan geçerli ölçek sayısı
$$\left\lfloor \frac{2N}{q_B\sqrt{3}} \right\rfloor$$
olur. A Tipi için de benzer biçimde
$$\left\lfloor \frac{6N}{q_A\sqrt{3}} \right\rfloor$$
katkısı gelir. Kodun kullandığı temel değişmez budur. Eğer
$$M_C(q)=\left\lfloor \frac{C}{q\sqrt{3}} \right\rfloor$$
tanımlanırsa toplam sayı
$$T(N)=\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{2N}\!\bigl(n(n+t)\bigr)+\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{6N}\!\bigl(t(3n+t)\bigr)$$
şeklini alır. Yalnızca \(q_B\le 2N/\sqrt3\) veya \(q_A\le 6N/\sqrt3\) olan çiftler katkı yapar; çünkü daha büyük \(q\) değerlerinde ilkel ölçek \(k=1\) bile sınırı aşar.
\(m=2\) ve \(n=1\) seçelim; o halde \(t=1\). İlkel \(120^\circ\) üçlüsü
$$x=2^2-1^2=3,\qquad y=2\cdot2\cdot1+1^2=5,\qquad z=2^2+2\cdot1+1^2=7$$
olur. Buradan iki ilkel \(60^\circ\) üçgen gelir:
$$ (3,8,7)\qquad\text{ve}\qquad (5,8,7). $$
A Tipi için
$$q_A=t(3n+t)=1\cdot(3+1)=4,\qquad r_A=\frac{\sqrt3}{6}\cdot4=\frac{2\sqrt3}{3},$$
B Tipi için
$$q_B=n(n+t)=1\cdot2=2,\qquad r_B=\frac{\sqrt3}{2}\cdot2=\sqrt3$$
çıkar. Yalnızca örnek olsun diye \(N=10\) alınırsa geçerli ölçek sayıları
$$\left\lfloor \frac{60}{4\sqrt3}\right\rfloor=8\qquad\text{ve}\qquad \left\lfloor \frac{20}{2\sqrt3}\right\rfloor=5$$
olur. Gerçek problemde \(N\) çok daha büyüktür, fakat sayma mantığı birebir aynıdır.
Uygulamalar bütün hesabı \(M_C(q)=\lfloor C/(q\sqrt3)\rfloor\) fonksiyonu etrafında kurar. Bir tablo \(C=2N\) için, ikinci tablo \(C=6N\) için hazırlanır; çünkü iki ailenin farkı tam olarak bu sabit ve \(q\) ifadesidir.
Her tablo girişi, \(qk\sqrt3\le C\) eşitsizliğini sağlayan en büyük \(k\) değerini saklar. Sınır noktasında kayan noktalı hesaplara güvenmek yerine kod bunu
$$3q^2k^2\le C^2$$
şeklindeki tam sayı eşitsizliğine çevirir. Karekökten elde edilen ilk tahmin sadece başlangıç içindir; sonra eşitsizlik kesinleşene kadar yukarı ya da aşağı düzeltilir. Böylece sınırda oluşabilecek tek-adım hataları önlenir.
Tablolar hazırlandıktan sonra kod \((n,t)\) parametrelerini gezer. B Tipinde dış döngü \(n\) üzerindedir; her \(n\) için \(q_B=n(n+t)\) sınırın altında kaldığı sürece bütün \(t\) değerleri denenir. A Tipinde dış döngü \(t\) üzerindedir; bu kez \(q_A=t(3n+t)\) sınırın altında kaldığı sürece \(n\) değerleri dolaşılır. Her iki tarafta da \(\gcd(n,t)=1\) şartı uygulanır ve 3'e tam bölünen \(t\) değerleri atlanır.
Her geçerli parametre çifti yalnızca önceden hesaplanmış bir tablo değerini toplam sonuca ekler. C++ uygulaması isterse dış döngüleri birden fazla iş parçacığına bölebilir; Python ve Java uygulamaları aynı aritmetiği seri biçimde yürütür. C++ sürümü ayrıca ana hedefe geçmeden önce \(T(100)=1234\), \(T(1000)=22767\) ve \(T(10000)=359912\) değerlerini kontrol eder.
Şu kısaltmaları kullanalım:
$$Q_B=\left\lfloor\frac{2N}{\sqrt3}\right\rfloor,\qquad Q_A=\left\lfloor\frac{6N}{\sqrt3}\right\rfloor$$
olsun. İki tabloyu kurmanın maliyeti zaman ve bellek açısından \(O(Q_A+Q_B)=O(N)\)'dir. B Tipi için ilkel çiftleri tarama maliyeti, EBOB filtresinden önce,
$$\sum_{n\le \sqrt{Q_B}} O\!\left(\frac{Q_B}{n}\right)=O(Q_B\log Q_B)$$
şeklindedir. A Tipi de benzer davranır:
$$\sum_{t\le \sqrt{Q_A}} O\!\left(\frac{Q_A}{t}\right)=O(Q_A\log Q_A).$$
Dolayısıyla toplam çalışma süresi \(O(N\log N)\), bellek kullanımı ise \(O(N)\)'dir. Bu, kenar üçlülerini doğrudan brute-force aramaya göre çok daha küçüktür; çünkü geometrik yapı en başta iki düzenli diofant aileye indirgenmiştir.
Sea \(T(N)\) el numero de triangulos de lados enteros que contienen un angulo de \(60^\circ\) y cuyo inradio no supera \(N\). El problema pide en particular \(T(1{,}053{,}779)\).
Un barrido ingenuo sobre ternas de lados seria demasiado costoso. La condicion del angulo de \(60^\circ\) ya impone una ecuacion diofantica, y ademas hay que respetar una cota sobre el inradio. Por eso las implementaciones no enumeran triangulos directamente: parametrizan primero las configuraciones primitivas y despues cuentan todos los escalados enteros permitidos.
La idea central es transformar un triangulo con angulo de \(60^\circ\) en un triple entero asociado a un triangulo de \(120^\circ\). Ese triple admite una parametrizacion clasica por enteros coprimos. Una vez hecha esa reduccion, el inradio queda expresado de forma lineal y el conteo se convierte en una suma de factores de escala validos.
Consideremos un triangulo en el que el angulo de \(60^\circ\) esta entre los lados enteros \(a\) y \(b\), y sea \(c\) el lado opuesto. Sin perdida de generalidad, supongamos \(a\le b\). Por la ley de cosenos,
$$c^2=a^2+b^2-ab.$$
Si escribimos \(x=a\) e \(y=b-a\), entonces \(b=x+y\). Al sustituir se obtiene
$$c^2=x^2+(x+y)^2-x(x+y)=x^2+xy+y^2.$$
Por tanto, cada triangulo objetivo produce un triple entero \((x,y,z)\) con
$$z^2=x^2+xy+y^2.$$
Esa es exactamente la relacion de lados de un triangulo con un angulo de \(120^\circ\). A la inversa, cualquier solucion entera positiva de esa forma genera dos triangulos de \(60^\circ\):
$$ (x,\ x+y,\ z)\qquad\text{y}\qquad (y,\ x+y,\ z). $$
De ahi nace la division en dos familias que usa el algoritmo.
Para las soluciones primitivas de \(z^2=x^2+xy+y^2\), las implementaciones emplean la parametrizacion estandar
$$x=m^2-n^2,\qquad y=2mn+n^2,\qquad z=m^2+mn+n^2,$$
con
$$m>n\ge 1,\qquad \gcd(m,n)=1,\qquad m\not\equiv n \pmod{3}.$$
La condicion de coprimalidad elimina factores comunes, y la restriccion modulo 3 evita las repeticiones no primitivas. Resulta mas comodo reescribir el parametro mediante
$$t=m-n,$$
de modo que \(m=n+t\), \(\gcd(m,n)=\gcd(n,t)\) y la condicion de congruencia se convierte en \(t\not\equiv 0\pmod 3\).
La Familia A usa el triangulo \((x,\ x+y,\ z)\). Como \(x+y=m^2+2mn=m(m+2n)\), su area vale
$$\Delta_A=\frac{\sqrt{3}}{4}\,x(x+y),$$
mientras que el semiperimetro es
$$s_A=\frac{x+(x+y)+z}{2}=\frac{2x+y+z}{2}=\frac{3m(m+n)}{2}.$$
Por tanto,
$$r_A=\frac{\Delta_A}{s_A}=\frac{\sqrt{3}}{6}(m-n)(m+2n)=\frac{\sqrt{3}}{6}\,t(3n+t).$$
La Familia B usa \((y,\ x+y,\ z)\). En este caso
$$\Delta_B=\frac{\sqrt{3}}{4}\,y(x+y),\qquad s_B=\frac{y+(x+y)+z}{2}=\frac{x+2y+z}{2}=\frac{(m+2n)(2m+n)}{2},$$
y entonces
$$r_B=\frac{\Delta_B}{s_B}=\frac{\sqrt{3}}{2}mn=\frac{\sqrt{3}}{2}\,n(n+t).$$
Si un triangulo primitivo se multiplica por un factor entero \(k\), todos los lados y el inradio tambien se multiplican por \(k\). Por eso los casos no primitivos se cuentan mediante
$$r_A(k)=\frac{k\sqrt{3}}{6}\,q_A,\qquad q_A=t(3n+t),$$
$$r_B(k)=\frac{k\sqrt{3}}{2}\,q_B,\qquad q_B=n(n+t).$$
Fijado un triangulo primitivo, solo queda contar cuantos enteros positivos \(k\) mantienen el inradio por debajo de \(N\). Para la Familia B,
$$\frac{k\sqrt{3}}{2}\,q_B\le N,$$
de modo que el numero de escalados validos es
$$\left\lfloor \frac{2N}{q_B\sqrt{3}} \right\rfloor.$$
Para la Familia A se obtiene de forma analoga
$$\left\lfloor \frac{6N}{q_A\sqrt{3}} \right\rfloor.$$
Esta es la cantidad central del algoritmo. Si definimos
$$M_C(q)=\left\lfloor \frac{C}{q\sqrt{3}} \right\rfloor,$$
entonces el total buscado es
$$T(N)=\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{2N}\!\bigl(n(n+t)\bigr)+\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{6N}\!\bigl(t(3n+t)\bigr).$$
Solo contribuyen los pares con \(q_B\le 2N/\sqrt3\) o \(q_A\le 6N/\sqrt3\), porque cuando \(q\) supera ese umbral ni siquiera el caso primitivo \(k=1\) cabe dentro del limite.
Tomemos \(m=2\) y \(n=1\), asi que \(t=1\). El triple primitivo de \(120^\circ\) es
$$x=2^2-1^2=3,\qquad y=2\cdot2\cdot1+1^2=5,\qquad z=2^2+2\cdot1+1^2=7.$$
Esto produce los dos triangulos primitivos de \(60^\circ\)
$$ (3,8,7)\qquad\text{y}\qquad (5,8,7). $$
Para la Familia A,
$$q_A=t(3n+t)=1\cdot(3+1)=4,\qquad r_A=\frac{\sqrt3}{6}\cdot4=\frac{2\sqrt3}{3}.$$
Para la Familia B,
$$q_B=n(n+t)=1\cdot2=2,\qquad r_B=\frac{\sqrt3}{2}\cdot2=\sqrt3.$$
Si solo como ilustracion se toma \(N=10\), los numeros de escalados admisibles son
$$\left\lfloor \frac{60}{4\sqrt3}\right\rfloor=8\qquad\text{y}\qquad \left\lfloor \frac{20}{2\sqrt3}\right\rfloor=5.$$
El problema real usa un \(N\) mucho mayor, pero el mecanismo de conteo es exactamente el mismo.
Las implementaciones organizan todo alrededor de la funcion \(M_C(q)=\lfloor C/(q\sqrt3)\rfloor\). Se construye una tabla para \(C=2N\) y otra para \(C=6N\), porque las dos familias solo difieren en esa constante y en la formula de \(q\).
Cada entrada de tabla almacena el mayor \(k\) que satisface \(qk\sqrt3\le C\). En lugar de fiarse de la aritmetica de punto flotante en la frontera, el codigo usa la desigualdad entera exacta
$$3q^2k^2\le C^2.$$
Una estimacion inicial con raices cuadradas sirve solo como punto de partida; despues se corrige hacia arriba o hacia abajo hasta que la desigualdad es exacta. Eso evita errores de una unidad cuando \(C/(q\sqrt3)\) esta muy cerca de un entero.
Despues de construir las tablas, el codigo recorre los parametros primitivos \((n,t)\). En la Familia B itera sobre \(n\) y, para cada \(n\), sobre todos los \(t\) tales que \(q_B=n(n+t)\) siga dentro del limite. En la Familia A itera sobre \(t\) y, para cada \(t\), sobre todos los \(n\) tales que \(q_A=t(3n+t)\) siga dentro del limite. En ambos casos impone \(\gcd(n,t)=1\) y descarta los \(t\) divisibles por 3.
Cada par valido aporta exactamente una consulta en la tabla precalculada, de modo que el total final es la suma de esas entradas en las dos familias. La implementacion en C++ puede repartir el bucle exterior entre varios hilos; las implementaciones en Python y Java realizan la misma aritmetica en serie. Ademas, la version en C++ comprueba antes los valores conocidos \(T(100)=1234\), \(T(1000)=22767\) y \(T(10000)=359912\).
Definamos
$$Q_B=\left\lfloor\frac{2N}{\sqrt3}\right\rfloor,\qquad Q_A=\left\lfloor\frac{6N}{\sqrt3}\right\rfloor.$$
Construir las dos tablas cuesta \(O(Q_A+Q_B)=O(N)\) tiempo y memoria. La enumeracion de candidatos de la Familia B visita, antes del filtro por gcd,
$$\sum_{n\le \sqrt{Q_B}} O\!\left(\frac{Q_B}{n}\right)=O(Q_B\log Q_B),$$
y la Familia A se comporta de forma analoga:
$$\sum_{t\le \sqrt{Q_A}} O\!\left(\frac{Q_A}{t}\right)=O(Q_A\log Q_A).$$
Por tanto, el coste total es \(O(N\log N)\) con \(O(N)\) memoria. Esto esta muy por debajo de cualquier exploracion directa sobre ternas de lados, porque la geometria ya se redujo de antemano a dos familias diofanticas estructuradas.
设 \(T(N)\) 表示所有满足以下条件的整数边三角形个数：它有一个 \(60^\circ\) 角，并且内切圆半径不超过 \(N\)。本题要求的就是 \(T(1{,}053{,}779)\)。
如果直接枚举三条边，再去检查角度条件和内切圆半径条件，规模会非常大。代码采用的思路不是“枚举三角形”，而是先把问题压缩成两个有结构的数论族，再统计每个原始三角形可以放大多少次仍然满足半径上界。
整个解法建立在一个重要变换上：把一个含 \(60^\circ\) 角的整数三角形，改写成一个满足 \(z^2=x^2+xy+y^2\) 的整数三元组。这个三元组对应的是一个 \(120^\circ\) 三角形，而这类原始三元组有标准参数化。参数化一旦写出，内切圆半径就会化成简单的线性表达式，最后只需要统计合法的整数倍数。
设三角形中 \(60^\circ\) 角夹在整数边 \(a\) 和 \(b\) 之间，对边为 \(c\)。不妨设 \(a\le b\)。由余弦定理可得
$$c^2=a^2+b^2-ab.$$
令 \(x=a\)，\(y=b-a\)，于是 \(b=x+y\)。代回上式后得到
$$c^2=x^2+(x+y)^2-x(x+y)=x^2+xy+y^2.$$
因此，每一个目标三角形都会对应到一个满足
$$z^2=x^2+xy+y^2$$
的正整数三元组 \((x,y,z)\)。这正是一个含 \(120^\circ\) 角的三角形的边长关系。反过来，只要有这样一个正整数三元组，就能构造出两个 \(60^\circ\) 三角形：
$$ (x,\ x+y,\ z)\qquad\text{和}\qquad (y,\ x+y,\ z). $$
代码中的两大计数族，正是从这里分裂出来的。
对于原始解 \(z^2=x^2+xy+y^2\)，实现使用标准参数化
$$x=m^2-n^2,\qquad y=2mn+n^2,\qquad z=m^2+mn+n^2,$$
其中
$$m>n\ge 1,\qquad \gcd(m,n)=1,\qquad m\not\equiv n \pmod{3}.$$
\(\gcd(m,n)=1\) 保证原始性，模 3 条件则排除会退化到非原始情形的重复参数。代码里进一步把参数改写成
$$t=m-n,$$
于是 \(m=n+t\)，并且 \(\gcd(m,n)=\gcd(n,t)\)，而模 3 条件也简化成 \(t\not\equiv 0\pmod 3\)。这样写之后，后面的上界会变得很整齐。
A 类三角形取 \((x,\ x+y,\ z)\)。因为 \(x+y=m^2+2mn=m(m+2n)\)，所以它的面积为
$$\Delta_A=\frac{\sqrt{3}}{4}\,x(x+y),$$
半周长为
$$s_A=\frac{x+(x+y)+z}{2}=\frac{2x+y+z}{2}=\frac{3m(m+n)}{2}.$$
因此内切圆半径简化为
$$r_A=\frac{\Delta_A}{s_A}=\frac{\sqrt{3}}{6}(m-n)(m+2n)=\frac{\sqrt{3}}{6}\,t(3n+t).$$
B 类三角形取 \((y,\ x+y,\ z)\)。这时
$$\Delta_B=\frac{\sqrt{3}}{4}\,y(x+y),\qquad s_B=\frac{y+(x+y)+z}{2}=\frac{x+2y+z}{2}=\frac{(m+2n)(2m+n)}{2},$$
所以
$$r_B=\frac{\Delta_B}{s_B}=\frac{\sqrt{3}}{2}mn=\frac{\sqrt{3}}{2}\,n(n+t).$$
如果把一个原始三角形整体放大 \(k\) 倍，那么边长和内切圆半径都会同时乘以 \(k\)。因此非原始情形只需要统计
$$r_A(k)=\frac{k\sqrt{3}}{6}\,q_A,\qquad q_A=t(3n+t),$$
$$r_B(k)=\frac{k\sqrt{3}}{2}\,q_B,\qquad q_B=n(n+t).$$
对于一个固定的原始三角形，剩下的问题只是：有多少个正整数 \(k\) 使得内切圆半径仍然不超过 \(N\)。对 B 类来说，需要满足
$$\frac{k\sqrt{3}}{2}\,q_B\le N,$$
因此合法倍数个数为
$$\left\lfloor \frac{2N}{q_B\sqrt{3}} \right\rfloor.$$
A 类同理得到
$$\left\lfloor \frac{6N}{q_A\sqrt{3}} \right\rfloor.$$
这正是实现中真正累计的量。若定义
$$M_C(q)=\left\lfloor \frac{C}{q\sqrt{3}} \right\rfloor,$$
那么总数可以写成
$$T(N)=\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{2N}\!\bigl(n(n+t)\bigr)+\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{6N}\!\bigl(t(3n+t)\bigr).$$
只有那些满足 \(q_B\le 2N/\sqrt3\) 或 \(q_A\le 6N/\sqrt3\) 的参数对才有贡献；因为一旦 \(q\) 太大，连最小的放大倍数 \(k=1\) 都已经超出半径限制了。
取 \(m=2\)、\(n=1\)，于是 \(t=1\)。对应的原始 \(120^\circ\) 三元组为
$$x=2^2-1^2=3,\qquad y=2\cdot2\cdot1+1^2=5,\qquad z=2^2+2\cdot1+1^2=7.$$
它给出两个原始 \(60^\circ\) 三角形：
$$ (3,8,7)\qquad\text{和}\qquad (5,8,7). $$
对 A 类，
$$q_A=t(3n+t)=1\cdot(3+1)=4,\qquad r_A=\frac{\sqrt3}{6}\cdot4=\frac{2\sqrt3}{3}.$$
对 B 类，
$$q_B=n(n+t)=1\cdot2=2,\qquad r_B=\frac{\sqrt3}{2}\cdot2=\sqrt3.$$
如果只是为了说明机制而取 \(N=10\)，那么允许的放大倍数分别是
$$\left\lfloor \frac{60}{4\sqrt3}\right\rfloor=8\qquad\text{和}\qquad \left\lfloor \frac{20}{2\sqrt3}\right\rfloor=5.$$
真实题目的 \(N\) 远大于 10，但代码做的事情完全一样：每个原始参数对只贡献它所对应的合法整数倍数个数。
三份实现都围绕 \(M_C(q)=\lfloor C/(q\sqrt3)\rfloor\) 这个函数组织。它们分别为 \(C=2N\) 和 \(C=6N\) 建立查表，因为两类三角形只是在常数项和 \(q\) 的定义上不同。
每个表项存的是满足 \(qk\sqrt3\le C\) 的最大 \(k\)。实现不会直接相信浮点运算的边界结果，而是把条件改写成精确的整数不等式
$$3q^2k^2\le C^2.$$
平方根只用来给出一个初始估计，随后再向上或向下修正，直到这个整数不等式恰好成立。这样就能避免当 \(C/(q\sqrt3)\) 非常接近整数时出现的 off-by-one 错误。
查表准备好之后，程序开始枚举原始参数 \((n,t)\)。对 B 类，外层按 \(n\) 递增，内层枚举所有仍满足 \(q_B=n(n+t)\) 上界的 \(t\)。对 A 类，外层按 \(t\) 递增，内层枚举所有仍满足 \(q_A=t(3n+t)\) 上界的 \(n\)。两边都强制要求 \(\gcd(n,t)=1\)，并跳过所有被 3 整除的 \(t\)。
每个合法参数对只做一次预计算表查询，因此总答案就是两类查询值的总和。C++ 实现还可以把外层参数循环分配到多个线程；Python 和 Java 实现使用相同的数学公式串行完成。C++ 版本在正式计算之前还会先验证三个已知检查点：\(T(100)=1234\)、\(T(1000)=22767\)、\(T(10000)=359912\)。
记
$$Q_B=\left\lfloor\frac{2N}{\sqrt3}\right\rfloor,\qquad Q_A=\left\lfloor\frac{6N}{\sqrt3}\right\rfloor.$$
两张查表的构造代价是 \(O(Q_A+Q_B)=O(N)\) 时间和空间。B 类在 gcd 过滤之前枚举的候选数规模为
$$\sum_{n\le \sqrt{Q_B}} O\!\left(\frac{Q_B}{n}\right)=O(Q_B\log Q_B),$$
A 类同样满足
$$\sum_{t\le \sqrt{Q_A}} O\!\left(\frac{Q_A}{t}\right)=O(Q_A\log Q_A).$$
因此总体时间复杂度为 \(O(N\log N)\)，空间复杂度为 \(O(N)\)。与直接枚举边长三元组相比，这已经小得多，因为几何条件已经先被压缩成两个规则的数论参数族。
Пусть \(T(N)\) обозначает число треугольников с целыми сторонами, у которых один из углов равен \(60^\circ\), а радиус вписанной окружности не превосходит \(N\). В задаче требуется найти \(T(1{,}053{,}779)\).
Полный перебор троек сторон здесь непрактичен. Условие на угол \(60^\circ\) уже задает диофантово ограничение, а сверху накладывается еще и условие на вписанную окружность. Поэтому реализации переходят не к прямому перечислению треугольников, а к параметризации примитивных объектов с последующим подсчетом допустимых целых масштабов.
Основная идея состоит в том, чтобы заменить треугольник с углом \(60^\circ\) на связанный с ним целочисленный тройственный объект для угла \(120^\circ\). Для таких троек существует классическая взаимно-простая параметризация. После этого радиус вписанной окружности выражается линейно, и задача сводится к суммированию числа допустимых коэффициентов масштабирования.
Пусть у треугольника угол \(60^\circ\) расположен между целыми сторонами \(a\) и \(b\), а противолежащая сторона равна \(c\). Без ограничения общности считаем, что \(a\le b\). По теореме косинусов
$$c^2=a^2+b^2-ab.$$
Положим \(x=a\) и \(y=b-a\), тогда \(b=x+y\). После подстановки получаем
$$c^2=x^2+(x+y)^2-x(x+y)=x^2+xy+y^2.$$
Значит, каждый искомый треугольник задает целочисленную тройку \((x,y,z)\), удовлетворяющую
$$z^2=x^2+xy+y^2.$$
Это ровно соотношение сторон для треугольника с углом \(120^\circ\). Обратное тоже верно: любая положительная целочисленная тройка такого вида порождает два треугольника с углом \(60^\circ\):
$$ (x,\ x+y,\ z)\qquad\text{и}\qquad (y,\ x+y,\ z). $$
Именно поэтому алгоритм разбивает счет на два семейства.
Для примитивных решений уравнения \(z^2=x^2+xy+y^2\) реализации используют стандартную форму
$$x=m^2-n^2,\qquad y=2mn+n^2,\qquad z=m^2+mn+n^2,$$
где
$$m>n\ge 1,\qquad \gcd(m,n)=1,\qquad m\not\equiv n \pmod{3}.$$
Условие взаимной простоты гарантирует примитивность, а ограничение по модулю 3 убирает лишние непервичные повторения. Для счета удобнее перейти к разности
$$t=m-n,$$
тогда \(m=n+t\), \(\gcd(m,n)=\gcd(n,t)\), а условие по модулю 3 превращается в \(t\not\equiv 0\pmod 3\).
Семейство A использует треугольник \((x,\ x+y,\ z)\). Поскольку \(x+y=m^2+2mn=m(m+2n)\), его площадь равна
$$\Delta_A=\frac{\sqrt{3}}{4}\,x(x+y),$$
а полупериметр равен
$$s_A=\frac{x+(x+y)+z}{2}=\frac{2x+y+z}{2}=\frac{3m(m+n)}{2}.$$
Следовательно,
$$r_A=\frac{\Delta_A}{s_A}=\frac{\sqrt{3}}{6}(m-n)(m+2n)=\frac{\sqrt{3}}{6}\,t(3n+t).$$
Семейство B использует \((y,\ x+y,\ z)\). Здесь
$$\Delta_B=\frac{\sqrt{3}}{4}\,y(x+y),\qquad s_B=\frac{y+(x+y)+z}{2}=\frac{x+2y+z}{2}=\frac{(m+2n)(2m+n)}{2},$$
поэтому
$$r_B=\frac{\Delta_B}{s_B}=\frac{\sqrt{3}}{2}mn=\frac{\sqrt{3}}{2}\,n(n+t).$$
Если примитивный треугольник умножить на целый коэффициент \(k\), то и стороны, и радиус вписанной окружности умножатся на \(k\). Поэтому непримитивные случаи учитываются через
$$r_A(k)=\frac{k\sqrt{3}}{6}\,q_A,\qquad q_A=t(3n+t),$$
$$r_B(k)=\frac{k\sqrt{3}}{2}\,q_B,\qquad q_B=n(n+t).$$
Для фиксированного примитивного треугольника остается только узнать, сколько положительных целых \(k\) оставляют радиус не больше \(N\). Для семейства B требуется
$$\frac{k\sqrt{3}}{2}\,q_B\le N,$$
откуда число допустимых масштабов равно
$$\left\lfloor \frac{2N}{q_B\sqrt{3}} \right\rfloor.$$
Для семейства A аналогично получается
$$\left\lfloor \frac{6N}{q_A\sqrt{3}} \right\rfloor.$$
Именно эта величина суммируется в коде. Если ввести обозначение
$$M_C(q)=\left\lfloor \frac{C}{q\sqrt{3}} \right\rfloor,$$
то общий счет можно записать так:
$$T(N)=\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{2N}\!\bigl(n(n+t)\bigr)+\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{6N}\!\bigl(t(3n+t)\bigr).$$
Вклад дают только те пары параметров, для которых \(q_B\le 2N/\sqrt3\) или \(q_A\le 6N/\sqrt3\), потому что при больших \(q\) даже примитивный случай \(k=1\) уже не проходит ограничение.
Возьмем \(m=2\) и \(n=1\), так что \(t=1\). Тогда примитивная тройка для \(120^\circ\) равна
$$x=2^2-1^2=3,\qquad y=2\cdot2\cdot1+1^2=5,\qquad z=2^2+2\cdot1+1^2=7.$$
Она порождает два примитивных треугольника с углом \(60^\circ\):
$$ (3,8,7)\qquad\text{и}\qquad (5,8,7). $$
Для семейства A имеем
$$q_A=t(3n+t)=1\cdot(3+1)=4,\qquad r_A=\frac{\sqrt3}{6}\cdot4=\frac{2\sqrt3}{3}.$$
Для семейства B имеем
$$q_B=n(n+t)=1\cdot2=2,\qquad r_B=\frac{\sqrt3}{2}\cdot2=\sqrt3.$$
Если просто для иллюстрации взять \(N=10\), то допустимые числа масштабов будут
$$\left\lfloor \frac{60}{4\sqrt3}\right\rfloor=8\qquad\text{и}\qquad \left\lfloor \frac{20}{2\sqrt3}\right\rfloor=5.$$
В самой задаче \(N\) гораздо больше, но принцип счета не меняется: каждая примитивная пара параметров дает ровно число допустимых целых масштабов.
Все три реализации организованы вокруг функции \(M_C(q)=\lfloor C/(q\sqrt3)\rfloor\). Одна таблица строится для \(C=2N\), вторая для \(C=6N\), поскольку два семейства различаются только этой константой и формулой для \(q\).
Каждая запись таблицы хранит наибольшее \(k\), удовлетворяющее \(qk\sqrt3\le C\). Вместо слепого доверия вычислениям с плавающей точкой на границе код использует точное целочисленное неравенство
$$3q^2k^2\le C^2.$$
Оценка через квадратный корень нужна только как стартовая догадка, после чего значение сдвигается вверх или вниз до точного выполнения неравенства. Это устраняет погрешности на единицу в тех случаях, когда \(C/(q\sqrt3)\) почти целое.
После подготовки таблиц код перечисляет примитивные пары \((n,t)\). Для семейства B внешний цикл идет по \(n\), а затем перебираются все \(t\), пока \(q_B=n(n+t)\) не выйдет за допустимую границу. Для семейства A внешний цикл идет по \(t\), а затем перебираются все \(n\), пока \(q_A=t(3n+t)\) не выйдет за предел. В обоих случаях накладывается условие \(\gcd(n,t)=1\), а все \(t\), кратные 3, отбрасываются.
Каждая допустимая пара делает ровно одно обращение к заранее построенной таблице, так что итоговый ответ представляет собой сумму этих значений по обоим семействам. Реализация на C++ при желании распараллеливает внешний цикл; реализации на Python и Java выполняют ту же арифметику последовательно. Кроме того, версия на C++ перед основным запуском проверяет известные контрольные значения \(T(100)=1234\), \(T(1000)=22767\) и \(T(10000)=359912\).
Обозначим
$$Q_B=\left\lfloor\frac{2N}{\sqrt3}\right\rfloor,\qquad Q_A=\left\lfloor\frac{6N}{\sqrt3}\right\rfloor.$$
Построение двух таблиц стоит \(O(Q_A+Q_B)=O(N)\) времени и памяти. До фильтра по gcd перебор кандидатов для семейства B имеет размер
$$\sum_{n\le \sqrt{Q_B}} O\!\left(\frac{Q_B}{n}\right)=O(Q_B\log Q_B),$$
а для семейства A аналогично
$$\sum_{t\le \sqrt{Q_A}} O\!\left(\frac{Q_A}{t}\right)=O(Q_A\log Q_A).$$
Следовательно, полная трудоемкость равна \(O(N\log N)\), а память равна \(O(N)\). Это на порядки лучше прямого перебора троек сторон, потому что геометрия заранее сведена к двум структурированным диофантовым семействам.
لتكن \(T(N)\) هي عدد المثلثات ذات الأضلاع الصحيحة التي تحتوي على زاوية مقدارها \(60^\circ\) ويكون نصف قطر الدائرة الداخلية فيها لا يتجاوز \(N\). المطلوب في المسألة هو حساب \(T(1{,}053{,}779)\).
الفحص المباشر لكل ثلاثيات الأضلاع غير عملي. فشرط وجود زاوية \(60^\circ\) يفرض معادلة ديوفانتية، ثم يأتي فوقه شرط إضافي على نصف القطر الداخلي. لذلك لا تعد التطبيقات المثلثات مباشرة، بل تبدأ بتمثيل أولي منظم، ثم تحسب عدد معاملات التوسيع الصحيحة المسموح بها لكل مثلث أولي.
الفكرة الأساسية هي تحويل مثلث بزاوية \(60^\circ\) إلى ثلاثية أعداد صحيحة مرتبطة بمثلث ذي زاوية \(120^\circ\). هذه الثلاثيات لها تمثيل كلاسيكي بمعلمتين أوليتين متباينتي القاسم. وبعد هذا التحويل يصبح نصف القطر الداخلي تعبيرا خطيا بسيطا، فتتحول المسألة إلى جمع أعداد معاملات القياس الصالحة.
خذ مثلثا تكون الزاوية \(60^\circ\) فيه بين الضلعين الصحيحين \(a\) و\(b\)، وليكن الضلع المقابل هو \(c\). ومن دون فقدان للعمومية نفترض \(a\le b\). من قانون جيب التمام نحصل على
$$c^2=a^2+b^2-ab.$$
إذا كتبنا \(x=a\) و\(y=b-a\) فسنحصل على \(b=x+y\). بالتعويض نحصل على
$$c^2=x^2+(x+y)^2-x(x+y)=x^2+xy+y^2.$$
إذن كل مثلث مطلوب يقابل ثلاثية صحيحة \((x,y,z)\) تحقق
$$z^2=x^2+xy+y^2.$$
وهذه بالضبط علاقة الأضلاع في مثلث له زاوية \(120^\circ\). والعكس صحيح أيضا: أي حل صحيح موجب لهذه المعادلة يولد مثلثين بزاوية \(60^\circ\):
$$ (x,\ x+y,\ z)\qquad\text{and}\qquad (y,\ x+y,\ z). $$
ومن هنا جاء انقسام العد إلى عائلتين مستقلتين.
للحلول الأولية للمعادلة \(z^2=x^2+xy+y^2\) تستخدم التطبيقات التمثيل القياسي
$$x=m^2-n^2,\qquad y=2mn+n^2,\qquad z=m^2+mn+n^2,$$
مع الشروط
$$m>n\ge 1,\qquad \gcd(m,n)=1,\qquad m\not\equiv n \pmod{3}.$$
شرط القاسم المشترك الأكبر يضمن الأولية، أما شرط الباقي modulo 3 فيستبعد الصور غير الأولية المكررة. ومن الأنسب حسابيا استعمال الفرق
$$t=m-n,$$
فتصبح \(m=n+t\)، كما أن \(\gcd(m,n)=\gcd(n,t)\)، ويتحول شرط modulo 3 إلى \(t\not\equiv 0\pmod 3\).
العائلة A تستخدم المثلث \((x,\ x+y,\ z)\). وبما أن \(x+y=m^2+2mn=m(m+2n)\)، فإن مساحته تساوي
$$\Delta_A=\frac{\sqrt{3}}{4}\,x(x+y),$$
ونصف محيطه هو
$$s_A=\frac{x+(x+y)+z}{2}=\frac{2x+y+z}{2}=\frac{3m(m+n)}{2}.$$
إذن
$$r_A=\frac{\Delta_A}{s_A}=\frac{\sqrt{3}}{6}(m-n)(m+2n)=\frac{\sqrt{3}}{6}\,t(3n+t).$$
أما العائلة B فتستخدم \((y,\ x+y,\ z)\). وفيها
$$\Delta_B=\frac{\sqrt{3}}{4}\,y(x+y),\qquad s_B=\frac{y+(x+y)+z}{2}=\frac{x+2y+z}{2}=\frac{(m+2n)(2m+n)}{2},$$
ومن ثم
$$r_B=\frac{\Delta_B}{s_B}=\frac{\sqrt{3}}{2}mn=\frac{\sqrt{3}}{2}\,n(n+t).$$
إذا كبرنا مثلثا أوليا بمعامل صحيح \(k\)، فإن جميع الأضلاع وكذلك نصف القطر الداخلي تتضاعف بالمعامل نفسه. لذلك تحسب الحالات غير الأولية عبر
$$r_A(k)=\frac{k\sqrt{3}}{6}\,q_A,\qquad q_A=t(3n+t),$$
$$r_B(k)=\frac{k\sqrt{3}}{2}\,q_B,\qquad q_B=n(n+t).$$
إذا ثبتنا مثلثا أوليا، فالسؤال الباقي هو: كم عدد القيم الصحيحة الموجبة لـ \(k\) التي تبقي نصف القطر الداخلي تحت الحد \(N\)؟ بالنسبة إلى العائلة B يجب أن يتحقق
$$\frac{k\sqrt{3}}{2}\,q_B\le N,$$
ولذلك يكون عدد معاملات القياس المسموح بها
$$\left\lfloor \frac{2N}{q_B\sqrt{3}} \right\rfloor.$$
وبالطريقة نفسها تعطي العائلة A
$$\left\lfloor \frac{6N}{q_A\sqrt{3}} \right\rfloor.$$
وهذه هي الكمية الجوهرية التي يجمعها الكود. إذا عرفنا
$$M_C(q)=\left\lfloor \frac{C}{q\sqrt{3}} \right\rfloor,$$
فإن العدد الكلي يكتب على الصورة
$$T(N)=\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{2N}\!\bigl(n(n+t)\bigr)+\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{6N}\!\bigl(t(3n+t)\bigr).$$
ولا تسهم إلا الأزواج التي تحقق \(q_B\le 2N/\sqrt3\) أو \(q_A\le 6N/\sqrt3\)، لأن القيم الأكبر من ذلك تجعل حتى الحالة الأولية \(k=1\) تتجاوز الحد.
خذ \(m=2\) و\(n=1\)، وعندها \(t=1\). الثلاثية الأولية الموافقة لزاوية \(120^\circ\) هي
$$x=2^2-1^2=3,\qquad y=2\cdot2\cdot1+1^2=5,\qquad z=2^2+2\cdot1+1^2=7.$$
وهذه تعطي مثلثين أوليين بزاوية \(60^\circ\):
$$ (3,8,7)\qquad\text{and}\qquad (5,8,7). $$
في العائلة A نحصل على
$$q_A=t(3n+t)=1\cdot(3+1)=4,\qquad r_A=\frac{\sqrt3}{6}\cdot4=\frac{2\sqrt3}{3}.$$
وفي العائلة B نحصل على
$$q_B=n(n+t)=1\cdot2=2,\qquad r_B=\frac{\sqrt3}{2}\cdot2=\sqrt3.$$
ولو أخذنا \(N=10\) فقط من أجل التوضيح، فسيكون عدد معاملات القياس المسموح بها
$$\left\lfloor \frac{60}{4\sqrt3}\right\rfloor=8\qquad\text{and}\qquad \left\lfloor \frac{20}{2\sqrt3}\right\rfloor=5.$$
المسألة الفعلية تستخدم قيمة أكبر بكثير لـ \(N\)، لكن آلية العد نفسها لا تتغير: كل زوج أولي من المعلمات يضيف بالضبط عدد المضاعفات الصحيحة المسموح بها.
تنظم التطبيقات الحساب كله حول الدالة \(M_C(q)=\lfloor C/(q\sqrt3)\rfloor\). تبنى مائدة واحدة عندما يكون \(C=2N\)، ومائدة ثانية عندما يكون \(C=6N\)، لأن الاختلاف بين العائلتين محصور في هذا الثابت وفي تعريف \(q\).
كل خانة في الجدول تخزن أكبر \(k\) يحقق \(qk\sqrt3\le C\). وبدلا من الاعتماد الكامل على الحسابات العشرية قرب الحد الفاصل، يعاد كتابة الشرط على صورة متباينة صحيحة دقيقة:
$$3q^2k^2\le C^2.$$
يستخدم تقدير أولي بالجذر التربيعي فقط كنقطة بداية، ثم يصحح صعودا أو هبوطا حتى تصبح المتباينة صحيحة تماما. وبهذا يتجنب التنفيذ أخطاء الزيادة أو النقصان بمقدار واحد عندما تكون القيمة قريبة جدا من عدد صحيح.
بعد تجهيز الجداول يبدأ الكود بتعداد الأزواج الأولية \((n,t)\). في العائلة B تدور الحلقة الخارجية على \(n\)، ثم لكل \(n\) تفحص جميع قيم \(t\) التي يبقى معها \(q_B=n(n+t)\) ضمن الحد. وفي العائلة A تدور الحلقة الخارجية على \(t\)، ثم لكل \(t\) تفحص جميع قيم \(n\) التي يبقى معها \(q_A=t(3n+t)\) ضمن الحد. وفي الحالتين يفرض الشرط \(\gcd(n,t)=1\)، كما تستبعد جميع قيم \(t\) القابلة للقسمة على 3.
كل زوج صالح يضيف قيمة واحدة فقط من جدول محسوب مسبقا، ولذلك فالجواب النهائي ليس إلا مجموع هذه القيم عبر العائلتين. تنفيذ C++ يستطيع توزيع الحلقة الخارجية على عدة خيوط، بينما تنفذ نسختا Python وJava الحساب نفسه بصورة تسلسلية. كما تتحقق نسخة C++ قبل التشغيل الكامل من القيم المعروفة \(T(100)=1234\) و\(T(1000)=22767\) و\(T(10000)=359912\).
لنضع
$$Q_B=\left\lfloor\frac{2N}{\sqrt3}\right\rfloor,\qquad Q_A=\left\lfloor\frac{6N}{\sqrt3}\right\rfloor.$$
بناء الجدولين يكلف \(O(Q_A+Q_B)=O(N)\) زمنا وذاكرة. أما تعداد المرشحين في العائلة B قبل تطبيق شرط القاسم المشترك الأكبر فيساوي
$$\sum_{n\le \sqrt{Q_B}} O\!\left(\frac{Q_B}{n}\right)=O(Q_B\log Q_B),$$
والعائلة A تتبع السلوك نفسه:
$$\sum_{t\le \sqrt{Q_A}} O\!\left(\frac{Q_A}{t}\right)=O(Q_A\log Q_A).$$
إذن الزمن الكلي هو \(O(N\log N)\)، والذاكرة هي \(O(N)\). وهذا أصغر بكثير من أي محاولة مباشرة لاستعراض ثلاثيات الأضلاع، لأن البنية الهندسية اختزلت منذ البداية إلى عائلتين ديوفانتيتين منظمتين.