Let \(a\le b\le c\) be the side lengths of a nondegenerate integer triangle \(ABC\), so its perimeter is
$$p=a+b+c.$$
As in the problem statement, the angle bisectors cut the sides at points \(E,F,G\), and we are interested in the area ratio
$$\frac{[ABC]}{[AEG]}.$$
We must count all integer-sided triangles with
$$a+b+c\le P$$
for which that ratio is an integer. The final count for the full Euler limit is intentionally omitted here.
The code does not work directly with angles or areas. It first turns the geometry into a pure arithmetic condition.
Let \(E\) be the point where the bisector at \(A\) meets \(BC\), and let \(G\) be the point where the bisector at \(B\) meets \(AC\). By the angle bisector theorem,
$$\frac{BE}{EC}=\frac{AB}{AC}=\frac{c}{b},\qquad \frac{AG}{GC}=\frac{AB}{BC}=\frac{c}{a}.$$
Because \(BC=a\) and \(AC=b\), this gives
$$EC=\frac{ab}{b+c},\qquad AG=\frac{bc}{a+c}.$$
Now compare areas in two stages. Triangles \(ABC\) and \(AEC\) share the altitude from \(A\) to line \(BC\), so
$$\frac{[ABC]}{[AEC]}=\frac{BC}{EC}=\frac{a}{ab/(b+c)}=\frac{b+c}{b}.$$
Likewise, triangles \(AEC\) and \(AEG\) share the altitude from \(E\) to line \(AC\), so
$$\frac{[AEC]}{[AEG]}=\frac{AC}{AG}=\frac{b}{bc/(a+c)}=\frac{a+c}{c}.$$
Multiplying the two ratios yields the key identity used everywhere in the solver:
$$\frac{[ABC]}{[AEG]}=\frac{(a+b)(a+c)}{bc}.$$
So the whole problem is equivalent to counting triangles for which
$$k=\frac{(a+b)(a+c)}{bc}$$
is an integer.
Rewrite \(k\) as
$$k=\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right).$$
Because \(a\le b\le c\), we have
$$0<\frac{a}{c}\le \frac{a}{b}\le 1.$$
Therefore
$$1<k\le 4.$$
Since \(k\) must be an integer, the only possibilities are
$$k\in\{2,3,4\}.$$
This is the decisive simplification behind the code: instead of searching over all possible ratios, we only need to classify three arithmetic cases.
To make
$$\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right)=4,$$
both factors must equal \(2\), because each factor is at most \(2\). That forces
$$a=b=c.$$
Hence the \(k=4\) contribution is simply the number of equilateral triangles with perimeter at most \(P\):
$$\left\lfloor\frac{P}{3}\right\rfloor.$$
Starting from
$$\frac{(a+b)(a+c)}{bc}=2,$$
we get
$$a^2+a(b+c)=bc.$$
Rearranging gives
$$bc-a(b+c)+a^2=2a^2,$$
hence
$$(b-a)(c-a)=2a^2.$$
Now define
$$d_1=b-a,\qquad d_2=c-a.$$
Then \(d_1,d_2>0\) and
$$d_1d_2=2a^2.$$
Let
$$g=\gcd(d_1,d_2),\qquad d_1=gu,\qquad d_2=gv,\qquad \gcd(u,v)=1.$$
Because \(g\mid a\), write \(a=gh\). Then
$$uv=2h^2.$$
Since \(u\) and \(v\) are coprime and their product is twice a square, one of them must be a square and the other must be twice a square. So, after possibly swapping the two factors, there are exactly two canonical possibilities:
$$u=x^2,\quad v=2y^2,$$
or
$$u=2x^2,\quad v=y^2,$$
with
$$\gcd(x,y)=1.$$
Family A. Take
$$d_1=gx^2,\qquad d_2=2gy^2.$$
Then \(a^2=d_1d_2/2=g^2x^2y^2\), so
$$a=gxy.$$
Therefore
$$b=a+d_1=gx(x+y),$$
$$c=a+d_2=gy(x+2y).$$
The perimeter becomes
$$p=g(x+y)(x+2y).$$
The ordering and triangle inequalities give the parameter range
$$y<x\le \sqrt{2}\,y.$$
Also \(x\) must be odd, because \(u=x^2\) must stay coprime to \(v=2y^2\).
For every primitive pair \((x,y)\), all positive scales
$$1\le g\le \left\lfloor\frac{P}{(x+y)(x+2y)}\right\rfloor$$
produce valid triangles.
Family B. Take
$$d_1=2gx^2,\qquad d_2=gy^2.$$
Then again
$$a=gxy,$$
and now
$$b=a+d_1=gx(2x+y),$$
$$c=a+d_2=gy(x+y).$$
The perimeter is
$$p=g(x+y)(2x+y).$$
The constraints become
$$\sqrt{2}\,x\le y<2x.$$
Here \(y\) must be odd so that \(y^2\) remains coprime to \(2x^2\). The number of valid scales is
$$\left\lfloor\frac{P}{(x+y)(2x+y)}\right\rfloor.$$
The smallest \(k=2\) triangle already appears in Family B. Take
$$x=2,\qquad y=3,\qquad g=1.$$
Then
$$a=gxy=6,$$
$$b=gx(2x+y)=2(4+3)=14,$$
$$c=gy(x+y)=3(5)=15.$$
So we get the triangle
$$ (a,b,c)=(6,14,15),\qquad p=35. $$
Checking the ratio:
$$\frac{(a+b)(a+c)}{bc}=\frac{20\cdot 21}{14\cdot 15}=2.$$
Starting from
$$\frac{(a+b)(a+c)}{bc}=3,$$
we obtain
$$a^2+a(b+c)=2bc.$$
From this, one convenient factorization is
$$(2b-a)(2c-a)=3a^2.$$
Now define
$$u=2b-a,\qquad v=2c-a.$$
Then
$$uv=3a^2.$$
Let
$$u=gs,\qquad v=gt,\qquad \gcd(s,t)=1,\qquad a=gh.$$
Then
$$st=3h^2.$$
Exactly the same squarefree reasoning shows that one factor must be a square and the other three times a square. So there are again two canonical forms:
$$s=x^2,\quad t=3y^2,$$
or
$$s=3x^2,\quad t=y^2,$$
with \(\gcd(x,y)=1\).
Family A. Take
$$u=gx^2,\qquad v=3gy^2.$$
Then
$$a=gxy,$$
$$b=\frac{u+a}{2}=\frac{gx(x+y)}{2},$$
$$c=\frac{v+a}{2}=\frac{gy(x+3y)}{2}.$$
The perimeter is
$$p=\frac{g(x+y)(x+3y)}{2}.$$
The ordering and triangle inequalities become
$$y<x\le \sqrt{3}\,y.$$
Also \(x\not\equiv 0\pmod 3\), otherwise \(x^2\) would not stay coprime to \(3y^2\).
Because the formulas for \(b\) and \(c\) contain division by \(2\), parity matters. If \(x\) and \(y\) are both odd, then every positive \(g\) works. If one of them is even, then only even \(g\) produce integer side lengths.
Define
$$B_A=(x+y)(x+3y),\qquad g_{\max}=\left\lfloor\frac{2P}{B_A}\right\rfloor.$$
The contribution is
$$g_{\max}$$
when \(x,y\) are both odd, and
$$\left\lfloor\frac{g_{\max}}{2}\right\rfloor$$
otherwise.
Family B. Take
$$u=3gx^2,\qquad v=gy^2.$$
Then
$$a=gxy,$$
$$b=\frac{u+a}{2}=\frac{gx(3x+y)}{2},$$
$$c=\frac{v+a}{2}=\frac{gy(x+y)}{2}.$$
The perimeter is
$$p=\frac{g(x+y)(3x+y)}{2}.$$
Now the admissible range is
$$\sqrt{3}\,x\le y<3x,$$
and \(y\not\equiv 0\pmod 3\).
The parity rule is the same as in Family A: all \(g\) work when \(x,y\) are both odd, otherwise only even \(g\) work. If
$$B_B=(x+y)(3x+y),\qquad g_{\max}=\left\lfloor\frac{2P}{B_B}\right\rfloor,$$
then the contribution is \(g_{\max}\) or \(\lfloor g_{\max}/2\rfloor\) according to that parity test.
The smallest \(k=3\) triangle is the familiar
$$ (4,5,6). $$
It comes from Family B with
$$x=1,\qquad y=2,\qquad g=2.$$
Indeed,
$$a=gxy=4,$$
$$b=\frac{gx(3x+y)}{2}=\frac{2\cdot 1\cdot 5}{2}=5,$$
$$c=\frac{gy(x+y)}{2}=\frac{2\cdot 2\cdot 3}{2}=6.$$
And the ratio is
$$\frac{(a+b)(a+c)}{bc}=\frac{9\cdot 10}{5\cdot 6}=3.$$
This example also illustrates the parity rule: with \(x=1\) and \(y=2\), odd \(g\) would make \(b\) and \(c\) half-integers, so the first legal choice is \(g=2\).
Every valid triangle belongs to exactly one integer ratio \(k\in\{2,3,4\}\).
The case \(k=4\) is equilateral and is completely separate.
For \(k=2\), once \(d_1=b-a\) and \(d_2=c-a\) are normalized by their gcd, the coprime product \(uv=2h^2\) has a unique squarefree split: the factor \(2\) lies either in the first normalized part or in the second. That is exactly the A/B split above. The same uniqueness argument holds for \(k=3\), with the factor \(3\) lying in one coprime part or the other.
Finally, for fixed primitive parameters \((x,y)\), changing \(g\) only scales the triangle. So every valid triangle is generated exactly once.
Let \(N(P)\) denote the number of valid triangles with perimeter at most \(P\). The code contains a brute-force verifier and checks the fast formulas against it for
$$P\in\{40,60,100,150,200,300\}.$$
Those brute-force totals are
$$N(40)=16,\quad N(60)=26,\quad N(100)=46,$$
$$N(150)=72,\quad N(200)=100,\quad N(300)=160.$$
For example, \(N(40)=16\) breaks into 13 equilateral triangles, two \(k=3\) triangles \((4,5,6)\) and \((8,10,12)\), and one \(k=2\) triangle \((6,14,15)\).
The function count_valid_triangles(P) starts with the equilateral contribution \(\lfloor P/3\rfloor\), sets
$$\text{max\_var}=\lfloor\sqrt{P}\rfloor+2,$$
and then counts the four nontrivial families. Each family loops over primitive parameter pairs \((x,y)\), applies the coprimality, parity, and mod-3 filters derived above, computes the base perimeter expression, and adds the number of admissible scale factors \(g\).
The four family counters are independent, so the implementation can distribute them across up to four pthread workers. If thread creation fails, it falls back to the serial path. The helper brute_count is used only for checkpoint verification on small perimeter limits.
The parameters \(x\) and \(y\) only range up to \(O(\sqrt{P})\), so the search is roughly quadratic in \(\sqrt{P}\), that is, about \(O(P)\) candidate pairs. Each candidate only needs a gcd computation and a constant amount of integer arithmetic. Thus the solution is fast enough for \(P=10^8\) while using only constant extra memory apart from tiny thread-local contexts.
Seien \(a\le b\le c\) die Seitenlängen eines nichtentarteten ganzzahligen Dreiecks \(ABC\). Der Umfang ist
$$p=a+b+c.$$
Wie in der Aufgabenstellung schneiden die Winkelhalbierenden die Seiten in den Punkten \(E,F,G\), und relevant ist das Flächenverhältnis
$$\frac{[ABC]}{[AEG]}.$$
Gesucht ist die Anzahl aller ganzzahligen Dreiecke mit
$$a+b+c\le P$$
für die dieses Verhältnis ganzzahlig ist. Der endgültige Euler-Wert wird hier absichtlich nicht angegeben.
Der Code arbeitet nicht direkt mit Flächen, sondern reduziert alles auf eine Seitenformel.
Sei \(E\) der Schnittpunkt der Winkelhalbierenden bei \(A\) mit \(BC\), und \(G\) der Schnittpunkt der Winkelhalbierenden bei \(B\) mit \(AC\). Nach dem Winkelhalbierendensatz gilt
$$\frac{BE}{EC}=\frac{AB}{AC}=\frac{c}{b},\qquad \frac{AG}{GC}=\frac{AB}{BC}=\frac{c}{a}.$$
Mit \(BC=a\) und \(AC=b\) folgt
$$EC=\frac{ab}{b+c},\qquad AG=\frac{bc}{a+c}.$$
Die Dreiecke \(ABC\) und \(AEC\) haben dieselbe Höhe auf \(BC\), also
$$\frac{[ABC]}{[AEC]}=\frac{BC}{EC}=\frac{b+c}{b}.$$
Ebenso haben \(AEC\) und \(AEG\) dieselbe Höhe auf \(AC\), daher
$$\frac{[AEC]}{[AEG]}=\frac{AC}{AG}=\frac{a+c}{c}.$$
Multiplikation liefert die zentrale Identität:
$$\frac{[ABC]}{[AEG]}=\frac{(a+b)(a+c)}{bc}.$$
Damit ist das Problem äquivalent dazu, die ganzzahligen Dreiecke mit
$$k=\frac{(a+b)(a+c)}{bc}\in \mathbb Z$$
zu zählen.
Man schreibt
$$k=\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right).$$
Wegen \(a\le b\le c\) gilt
$$0<\frac{a}{c}\le \frac{a}{b}\le 1,$$
also
$$1<k\le 4.$$
Da \(k\) ganzzahlig sein muss, bleiben nur
$$k\in\{2,3,4\}.$$
Damit
$$\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right)=4$$
gilt, müssen beide Faktoren gleich \(2\) sein. Also folgt sofort
$$a=b=c.$$
Die Anzahl dieser Dreiecke ist daher einfach
$$\left\lfloor\frac{P}{3}\right\rfloor.$$
Aus
$$\frac{(a+b)(a+c)}{bc}=2$$
folgt
$$a^2+a(b+c)=bc,$$
also
$$(b-a)(c-a)=2a^2.$$
Setze
$$d_1=b-a,\qquad d_2=c-a.$$
Dann gilt
$$d_1d_2=2a^2.$$
Mit
$$g=\gcd(d_1,d_2),\qquad d_1=gu,\qquad d_2=gv,\qquad \gcd(u,v)=1$$
und \(a=gh\) erhält man
$$uv=2h^2.$$
Da \(u\) und \(v\) teilerfremd sind, muss einer der beiden Faktoren ein Quadrat und der andere das Doppelte eines Quadrats sein. Also gibt es genau zwei kanonische Formen:
$$u=x^2,\quad v=2y^2,$$
oder
$$u=2x^2,\quad v=y^2,$$
mit \(\gcd(x,y)=1\).
Familie A. Sei
$$d_1=gx^2,\qquad d_2=2gy^2.$$
Dann ist
$$a=gxy,\qquad b=gx(x+y),\qquad c=gy(x+2y),$$
und der Umfang lautet
$$p=g(x+y)(x+2y).$$
Die Nebenbedingungen werden zu
$$y<x\le \sqrt{2}\,y.$$
Außerdem muss \(x\) ungerade sein, damit \(x^2\) zu \(2y^2\) teilerfremd bleibt. Für ein primitives Paar \((x,y)\) ist die Zahl zulässiger Skalierungen
$$\left\lfloor\frac{P}{(x+y)(x+2y)}\right\rfloor.$$
Familie B. Sei
$$d_1=2gx^2,\qquad d_2=gy^2.$$
Dann folgt
$$a=gxy,\qquad b=gx(2x+y),\qquad c=gy(x+y),$$
und
$$p=g(x+y)(2x+y).$$
Hier gilt
$$\sqrt{2}\,x\le y<2x,$$
und \(y\) muss ungerade sein. Die Anzahl der Skalierungen ist
$$\left\lfloor\frac{P}{(x+y)(2x+y)}\right\rfloor.$$
Das kleinste \(k=2\)-Dreieck stammt bereits aus Familie B. Wähle
$$x=2,\qquad y=3,\qquad g=1.$$
Dann ergibt sich
$$a=6,\qquad b=14,\qquad c=15,$$
also
$$ (a,b,c)=(6,14,15),\qquad p=35. $$
Kontrolle:
$$\frac{(a+b)(a+c)}{bc}=\frac{20\cdot 21}{14\cdot 15}=2.$$
Aus
$$\frac{(a+b)(a+c)}{bc}=3$$
folgt
$$a^2+a(b+c)=2bc,$$
und damit
$$(2b-a)(2c-a)=3a^2.$$
Setze
$$u=2b-a,\qquad v=2c-a.$$
Dann gilt
$$uv=3a^2.$$
Mit
$$u=gs,\qquad v=gt,\qquad \gcd(s,t)=1,\qquad a=gh$$
erhält man
$$st=3h^2.$$
Wieder ist einer der beiden teilerfremden Faktoren ein Quadrat und der andere das Dreifache eines Quadrats. Also:
$$s=x^2,\quad t=3y^2,$$
oder
$$s=3x^2,\quad t=y^2.$$
Familie A. Sei
$$u=gx^2,\qquad v=3gy^2.$$
Dann
$$a=gxy,\qquad b=\frac{gx(x+y)}{2},\qquad c=\frac{gy(x+3y)}{2},$$
und
$$p=\frac{g(x+y)(x+3y)}{2}.$$
Die Bereichsbedingungen sind
$$y<x\le \sqrt{3}\,y,$$
außerdem \(x\not\equiv 0\pmod 3\).
Wegen der Division durch \(2\) in \(b\) und \(c\) spielt die Parität von \(g\) eine Rolle. Sind \(x\) und \(y\) beide ungerade, so ist jedes \(g\) erlaubt. Andernfalls funktioniert nur gerades \(g\).
Mit
$$B_A=(x+y)(x+3y),\qquad g_{\max}=\left\lfloor\frac{2P}{B_A}\right\rfloor$$
ist der Beitrag also \(g_{\max}\) oder \(\lfloor g_{\max}/2\rfloor\).
Familie B. Sei
$$u=3gx^2,\qquad v=gy^2.$$
Dann
$$a=gxy,\qquad b=\frac{gx(3x+y)}{2},\qquad c=\frac{gy(x+y)}{2},$$
mit Umfang
$$p=\frac{g(x+y)(3x+y)}{2}.$$
Hier gilt
$$\sqrt{3}\,x\le y<3x,$$
und \(y\not\equiv 0\pmod 3\). Die Paritätsregel für \(g\) ist dieselbe wie in Familie A.
Das kleinste \(k=3\)-Dreieck ist
$$ (4,5,6). $$
Es entsteht aus Familie B mit
$$x=1,\qquad y=2,\qquad g=2.$$
Denn
$$a=4,\qquad b=5,\qquad c=6,$$
und
$$\frac{(a+b)(a+c)}{bc}=\frac{9\cdot 10}{5\cdot 6}=3.$$
Hier sieht man auch die Paritätsbedingung: Für ungerades \(g\) wären \(b\) und \(c\) keine ganzen Zahlen.
Jedes gültige Dreieck besitzt genau einen ganzzahligen Wert \(k\in\{2,3,4\}\).
Der Fall \(k=4\) ist vollständig gleichseitig und separat. In den Fällen \(k=2\) und \(k=3\) ist nach Herausziehen des ggT und Zerlegung in teilerfremde Faktoren eindeutig festgelegt, in welchem Teil der quadratfreie Faktor \(2\) bzw. \(3\) liegt. Genau daraus entsteht die A/B-Aufteilung. Der Skalierungsfaktor \(g\) ist anschließend ebenfalls eindeutig. Somit wird jedes Dreieck genau einmal erzeugt.
Sei \(N(P)\) die Anzahl gültiger Dreiecke mit Umfang höchstens \(P\). Der Code vergleicht die schnelle Formel mit einer Brute-Force-Zählung für
$$P\in\{40,60,100,150,200,300\}.$$
Die entsprechenden Werte sind
$$N(40)=16,\quad N(60)=26,\quad N(100)=46,$$
$$N(150)=72,\quad N(200)=100,\quad N(300)=160.$$
count_valid_triangles(P) startet mit dem gleichseitigen Beitrag \(\lfloor P/3\rfloor\), setzt
$$\text{max\_var}=\lfloor\sqrt{P}\rfloor+2,$$
und summiert dann die vier parametrisierten Familien. Jede Zählfunktion iteriert über primitive Paare \((x,y)\), prüft ggT, Parität und Modulo-3-Bedingungen, berechnet den Basisumfang und addiert die zulässige Zahl von Skalierungsfaktoren \(g\).
Da die vier Familien unabhängig sind, kann der Code sie parallel auf bis zu vier pthread-Worker verteilen. Für kleine Kontrollwerte dient brute_count als exakter Vergleich.
Die Parameter \(x\) und \(y\) laufen nur bis \(O(\sqrt{P})\), also ist die Suche quadratisch in \(\sqrt{P}\), praktisch also etwa \(O(P)\) Kandidatenpaare. Pro Kandidat fallen nur ein ggT und konstante Ganzzahlarithmetik an. Der Speicherverbrauch bleibt bis auf kleine Thread-Kontexte konstant.
\(a\le b\le c\) olan ve dejenere olmayan bir \(ABC\) üçgeninin tam sayı kenar uzunlukları verilsin. Çevre
$$p=a+b+c$$
olsun. Problemdeki gibi açıortaylar kenarları \(E,F,G\) noktalarında kesiyor ve ilgilendiğimiz oran
$$\frac{[ABC]}{[AEG]}$$
oluyor. Amaç,
$$a+b+c\le P$$
koşulunu sağlayan tam sayı kenarlı üçgenler arasında bu oranı tam sayı yapanların sayısını bulmak. Tam Euler limiti için nihai değer burada özellikle verilmez.
Kod doğrudan alanlarla çalışmıyor; önce problemi tamamen kenar uzunlukları cinsinden yazıyor.
\(E\), \(A\) açısının açıortayının \(BC\) ile kesişimi; \(G\) ise \(B\) açısının açıortayının \(AC\) ile kesişimi olsun. Açıortay teoreminden
$$\frac{BE}{EC}=\frac{AB}{AC}=\frac{c}{b},\qquad \frac{AG}{GC}=\frac{AB}{BC}=\frac{c}{a}$$
elde edilir. Buradan
$$EC=\frac{ab}{b+c},\qquad AG=\frac{bc}{a+c}$$
çıkar.
\(ABC\) ve \(AEC\) üçgenleri \(BC\) doğrusu üzerine aynı yüksekliği paylaştığı için
$$\frac{[ABC]}{[AEC]}=\frac{BC}{EC}=\frac{b+c}{b}.$$
Aynı şekilde \(AEC\) ile \(AEG\), \(AC\) doğrusu üzerine aynı yüksekliği paylaştığından
$$\frac{[AEC]}{[AEG]}=\frac{AC}{AG}=\frac{a+c}{c}.$$
Çarpınca çözümün temel bağıntısı gelir:
$$\frac{[ABC]}{[AEG]}=\frac{(a+b)(a+c)}{bc}.$$
Dolayısıyla artık saymamız gereken nesneler,
$$k=\frac{(a+b)(a+c)}{bc}$$
değeri tam sayı olan üçgenlerdir.
Şunu yazalım:
$$k=\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right).$$
\(a\le b\le c\) olduğundan
$$0<\frac{a}{c}\le \frac{a}{b}\le 1$$
ve dolayısıyla
$$1<k\le 4$$
olur. \(k\) tam sayı olmak zorunda olduğuna göre geriye yalnızca
$$k\in\{2,3,4\}$$
kalır. Kodun bütün gücü buradan gelir: sonsuz oran olasılığı yerine yalnızca üç aritmetik sınıf sayılır.
\(k=4\) olabilmesi için
$$\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right)=4$$
eşitliğinde her iki çarpanın da 2 olması gerekir; çünkü her biri en fazla 2 olabilir. Bu da doğrudan
$$a=b=c$$
demektir. O halde bu ailenin katkısı
$$\left\lfloor\frac{P}{3}\right\rfloor$$
olur.
\(k=2\) için
$$\frac{(a+b)(a+c)}{bc}=2$$
yazar ve düzenlersek
$$(b-a)(c-a)=2a^2$$
elde ederiz.
Şimdi
$$d_1=b-a,\qquad d_2=c-a$$
tanımını yapalım. Böylece
$$d_1d_2=2a^2.$$
Ayrıca
$$g=\gcd(d_1,d_2),\qquad d_1=gu,\qquad d_2=gv,\qquad \gcd(u,v)=1$$
olsun. \(g\mid a\) olduğundan \(a=gh\) yazabiliriz ve
$$uv=2h^2$$
kalır. \(u\) ile \(v\) aralarında asal olduğu için, bunlardan biri kare, diğeri ise iki ile çarpılmış kare olmak zorundadır. Bu da tam olarak iki kanonik aile verir:
$$u=x^2,\quad v=2y^2$$
veya
$$u=2x^2,\quad v=y^2,$$
burada \(\gcd(x,y)=1\).
Ailesi A. Şunu alalım:
$$d_1=gx^2,\qquad d_2=2gy^2.$$
O zaman
$$a=gxy,\qquad b=gx(x+y),\qquad c=gy(x+2y)$$
ve çevre
$$p=g(x+y)(x+2y)$$
olur. Sıralama ve üçgen eşitsizliği şu aralığı verir:
$$y<x\le \sqrt{2}\,y.$$
Ayrıca \(x\) tek olmalıdır; çünkü \(x^2\)'nin \(2y^2\) ile aralarında asal kalması gerekir. Her ilkel \((x,y)\) çifti için geçerli ölçek sayısı
$$\left\lfloor\frac{P}{(x+y)(x+2y)}\right\rfloor$$
olur.
Ailesi B. Bu kez
$$d_1=2gx^2,\qquad d_2=gy^2$$
alınır. O zaman
$$a=gxy,\qquad b=gx(2x+y),\qquad c=gy(x+y)$$
ve
$$p=g(x+y)(2x+y)$$
elde edilir. Şartlar
$$\sqrt{2}\,x\le y<2x$$
şeklindedir ve bu kez \(y\) tek olmalıdır. Ölçek sayısı
$$\left\lfloor\frac{P}{(x+y)(2x+y)}\right\rfloor$$
olur.
En küçük \(k=2\) üçgeni Aile B'den gelir. Şöyle seçelim:
$$x=2,\qquad y=3,\qquad g=1.$$
Böylece
$$a=6,\qquad b=14,\qquad c=15$$
ve
$$ (a,b,c)=(6,14,15),\qquad p=35 $$
olur. Doğrulama:
$$\frac{(a+b)(a+c)}{bc}=\frac{20\cdot 21}{14\cdot 15}=2.$$
\(k=3\) için
$$\frac{(a+b)(a+c)}{bc}=3$$
başlangıcından
$$(2b-a)(2c-a)=3a^2$$
eşitliği çıkar.
Şimdi
$$u=2b-a,\qquad v=2c-a$$
tanımını yapalım. Böylece
$$uv=3a^2.$$
Yine
$$u=gs,\qquad v=gt,\qquad \gcd(s,t)=1,\qquad a=gh$$
yazarsak
$$st=3h^2$$
olur. Aralarında asal iki çarpandan biri kare, diğeri 3 ile çarpılmış kare olmalıdır. Dolayısıyla iki kanonik ayrışım vardır:
$$s=x^2,\quad t=3y^2$$
veya
$$s=3x^2,\quad t=y^2.$$
Ailesi A. Şunu alalım:
$$u=gx^2,\qquad v=3gy^2.$$
Bu durumda
$$a=gxy,\qquad b=\frac{gx(x+y)}{2},\qquad c=\frac{gy(x+3y)}{2}$$
ve
$$p=\frac{g(x+y)(x+3y)}{2}$$
olur. Parametre aralığı
$$y<x\le \sqrt{3}\,y$$
şeklindedir ve ayrıca \(x\not\equiv 0\pmod 3\) gerekir.
\(b\) ve \(c\) formüllerinde 2'ye bölme olduğu için \(g\)'nin paritesi önem kazanır. \(x\) ve \(y\) ikisi birden tek ise her \(g\) çalışır; aksi halde yalnızca çift \(g\) çalışır.
$$B_A=(x+y)(x+3y),\qquad g_{\max}=\left\lfloor\frac{2P}{B_A}\right\rfloor$$
dersek katkı, duruma göre \(g_{\max}\) veya \(\lfloor g_{\max}/2\rfloor\) olur.
Ailesi B. Bu kez
$$u=3gx^2,\qquad v=gy^2$$
alınır. O zaman
$$a=gxy,\qquad b=\frac{gx(3x+y)}{2},\qquad c=\frac{gy(x+y)}{2}$$
ve
$$p=\frac{g(x+y)(3x+y)}{2}$$
elde edilir. Şartlar
$$\sqrt{3}\,x\le y<3x$$
ve \(y\not\equiv 0\pmod 3\) biçimindedir. \(g\)'nin parite filtresi burada da aynıdır.
En küçük \(k=3\) üçgeni bilinen
$$ (4,5,6) $$
üçgenidir. Bu, Aile B'de
$$x=1,\qquad y=2,\qquad g=2$$
seçiminden gelir. Gerçekten
$$a=4,\qquad b=5,\qquad c=6$$
ve
$$\frac{(a+b)(a+c)}{bc}=\frac{9\cdot 10}{5\cdot 6}=3$$
olur. Burada \(g\)'nin neden çift olması gerektiği de açıkça görülür.
Her geçerli üçgenin tek bir \(k\in\{2,3,4\}\) değeri vardır. \(k=4\) ailesi eşkenarlardan ibarettir ve ayrıdır. \(k=2\) ve \(k=3\) durumlarında ise, gcd ile normalleştirdikten sonra kare-dışı çarpan olan 2 veya 3'ün hangi tarafta durduğu tek biçimde belirlenir; bu da A/B ayrımıdır. Son olarak \(g\) da benzersiz ölçek faktörüdür. Böylece her üçgen tam bir kez üretilir.
\(N(P)\), çevresi en çok \(P\) olan geçerli üçgen sayısı olsun. Kod, hızlı yöntemi küçük \(P\) değerlerinde brute-force ile karşılaştırır:
$$P\in\{40,60,100,150,200,300\}.$$
Bu değerler için sonuçlar
$$N(40)=16,\quad N(60)=26,\quad N(100)=46,$$
$$N(150)=72,\quad N(200)=100,\quad N(300)=160$$
şeklindedir. Örneğin \(P=40\) için 13 eşkenar, iki adet \(k=3\) ve bir adet \(k=2\) üçgen vardır.
count_valid_triangles(P) önce eşkenar katkıyı \(\lfloor P/3\rfloor\) olarak ekler, sonra
$$\text{max\_var}=\lfloor\sqrt{P}\rfloor+2$$
değerini hesaplar ve dört parametrik aileyi ayrı ayrı sayar. Her aile sayacı, ilkel \((x,y)\) çiftlerini dolaşır, gcd/parite/mod-3 filtrelerini uygular, taban çevre ifadesini çıkarır ve geçerli \(g\) sayısını toplar.
Dört aile birbirinden bağımsız olduğu için kod bunları en fazla dört pthread işçisine dağıtabilir. Küçük çevrelerde brute_count fonksiyonu doğrulama amacıyla kullanılır.
\(x\) ve \(y\) parametreleri ancak \(O(\sqrt{P})\) mertebesine kadar çıkar. Dolayısıyla arama, \(\sqrt{P}\) üzerinde yaklaşık ikinci derecedir; pratikte yaklaşık \(O(P)\) aday çift demektir. Her aday için bir gcd ve sabit sayıda tamsayı işlemi yapılır. Bellek kullanımı ise küçük iş parçacığı bağlamları dışında sabittir.
Sean \(a\le b\le c\) los lados enteros de un triangulo no degenerado \(ABC\). Su perimetro es
$$p=a+b+c.$$
Como en el enunciado, las bisectrices cortan los lados en \(E,F,G\), y el cociente relevante es
$$\frac{[ABC]}{[AEG]}.$$
Hay que contar todos los triangulos de lados enteros con
$$a+b+c\le P$$
para los que ese cociente sea entero. El valor final del limite grande se omite aqui deliberadamente.
La solucion no trabaja directamente con areas; primero las reescribe en funcion de \(a,b,c\).
Sea \(E\) el punto donde la bisectriz en \(A\) corta a \(BC\), y sea \(G\) el punto donde la bisectriz en \(B\) corta a \(AC\). Por el teorema de la bisectriz,
$$\frac{BE}{EC}=\frac{AB}{AC}=\frac{c}{b},\qquad \frac{AG}{GC}=\frac{AB}{BC}=\frac{c}{a}.$$
Como \(BC=a\) y \(AC=b\), se obtiene
$$EC=\frac{ab}{b+c},\qquad AG=\frac{bc}{a+c}.$$
Los triangulos \(ABC\) y \(AEC\) comparten altura sobre \(BC\), asi que
$$\frac{[ABC]}{[AEC]}=\frac{BC}{EC}=\frac{b+c}{b}.$$
Igualmente, \(AEC\) y \(AEG\) comparten altura sobre \(AC\), luego
$$\frac{[AEC]}{[AEG]}=\frac{AC}{AG}=\frac{a+c}{c}.$$
Al multiplicar aparece la identidad central:
$$\frac{[ABC]}{[AEG]}=\frac{(a+b)(a+c)}{bc}.$$
Por tanto el problema equivale a contar los triangulos para los que
$$k=\frac{(a+b)(a+c)}{bc}$$
es entero.
Reescribimos
$$k=\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right).$$
Dado que \(a\le b\le c\), se cumple
$$0<\frac{a}{c}\le \frac{a}{b}\le 1,$$
y por ello
$$1<k\le 4.$$
Como \(k\) debe ser entero, los unicos valores posibles son
$$k\in\{2,3,4\}.$$
Para que
$$\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right)=4$$
se cumpla, ambos factores tienen que valer 2, pues ninguno puede superar 2. Eso obliga a
$$a=b=c.$$
La contribucion de este caso es entonces
$$\left\lfloor\frac{P}{3}\right\rfloor.$$
Partiendo de
$$\frac{(a+b)(a+c)}{bc}=2$$
se llega a
$$(b-a)(c-a)=2a^2.$$
Definimos
$$d_1=b-a,\qquad d_2=c-a,$$
y asi
$$d_1d_2=2a^2.$$
Tomemos
$$g=\gcd(d_1,d_2),\qquad d_1=gu,\qquad d_2=gv,\qquad \gcd(u,v)=1.$$
Como \(g\mid a\), escribimos \(a=gh\), y queda
$$uv=2h^2.$$
Al ser \(u\) y \(v\) coprimos, uno debe ser un cuadrado y el otro el doble de un cuadrado. Por tanto hay dos formas canonicas:
$$u=x^2,\quad v=2y^2,$$
o bien
$$u=2x^2,\quad v=y^2,$$
con \(\gcd(x,y)=1\).
Familia A. Sea
$$d_1=gx^2,\qquad d_2=2gy^2.$$
Entonces
$$a=gxy,\qquad b=gx(x+y),\qquad c=gy(x+2y),$$
y el perimetro vale
$$p=g(x+y)(x+2y).$$
Las restricciones se convierten en
$$y<x\le \sqrt{2}\,y.$$
Ademas \(x\) debe ser impar. El numero de escalas validas es
$$\left\lfloor\frac{P}{(x+y)(x+2y)}\right\rfloor.$$
Familia B. Sea
$$d_1=2gx^2,\qquad d_2=gy^2.$$
Entonces
$$a=gxy,\qquad b=gx(2x+y),\qquad c=gy(x+y),$$
con
$$p=g(x+y)(2x+y).$$
Ahora las condiciones son
$$\sqrt{2}\,x\le y<2x,$$
y \(y\) debe ser impar. Su contribucion es
$$\left\lfloor\frac{P}{(x+y)(2x+y)}\right\rfloor.$$
El menor triangulo con \(k=2\) sale ya de la Familia B. Tomemos
$$x=2,\qquad y=3,\qquad g=1.$$
Entonces
$$a=6,\qquad b=14,\qquad c=15,$$
de modo que
$$ (a,b,c)=(6,14,15),\qquad p=35. $$
La comprobacion directa da
$$\frac{(a+b)(a+c)}{bc}=\frac{20\cdot 21}{14\cdot 15}=2.$$
Partiendo de
$$\frac{(a+b)(a+c)}{bc}=3$$
se obtiene
$$(2b-a)(2c-a)=3a^2.$$
Definimos
$$u=2b-a,\qquad v=2c-a,$$
de modo que
$$uv=3a^2.$$
Escribimos
$$u=gs,\qquad v=gt,\qquad \gcd(s,t)=1,\qquad a=gh,$$
y por tanto
$$st=3h^2.$$
Asi, uno de los factores es un cuadrado y el otro es tres veces un cuadrado:
$$s=x^2,\quad t=3y^2,$$
o
$$s=3x^2,\quad t=y^2.$$
Familia A. Sea
$$u=gx^2,\qquad v=3gy^2.$$
Entonces
$$a=gxy,\qquad b=\frac{gx(x+y)}{2},\qquad c=\frac{gy(x+3y)}{2},$$
y
$$p=\frac{g(x+y)(x+3y)}{2}.$$
Las restricciones son
$$y<x\le \sqrt{3}\,y,$$
junto con \(x\not\equiv 0\pmod 3\).
Como \(b\) y \(c\) llevan un factor \(1/2\), la paridad de \(g\) importa. Si \(x\) e \(y\) son ambos impares, cualquier \(g\) sirve. Si no, solo sirven \(g\) pares.
Con
$$B_A=(x+y)(x+3y),\qquad g_{\max}=\left\lfloor\frac{2P}{B_A}\right\rfloor,$$
la contribucion es \(g_{\max}\) o \(\lfloor g_{\max}/2\rfloor\).
Familia B. Sea
$$u=3gx^2,\qquad v=gy^2.$$
Entonces
$$a=gxy,\qquad b=\frac{gx(3x+y)}{2},\qquad c=\frac{gy(x+y)}{2},$$
con perimetro
$$p=\frac{g(x+y)(3x+y)}{2}.$$
Aqui se exige
$$\sqrt{3}\,x\le y<3x,$$
y \(y\not\equiv 0\pmod 3\). La regla de paridad para \(g\) es la misma.
El menor triangulo con \(k=3\) es
$$ (4,5,6). $$
Proviene de la Familia B con
$$x=1,\qquad y=2,\qquad g=2.$$
Se obtiene
$$a=4,\qquad b=5,\qquad c=6,$$
y
$$\frac{(a+b)(a+c)}{bc}=\frac{9\cdot 10}{5\cdot 6}=3.$$
Cada triangulo valido tiene un unico \(k\in\{2,3,4\}\). El caso \(k=4\) es solo equilatero. En \(k=2\) y \(k=3\), una vez normalizados los factores por su gcd, queda determinado de manera unica en que lado cae el factor libre de cuadrados, 2 o 3. Eso produce exactamente la separacion A/B. Luego \(g\) es el factor de escala unico. Asi, cada triangulo se genera una sola vez.
Si \(N(P)\) es el numero de triangulos validos con perimetro a lo sumo \(P\), el codigo compara la formula rapida con una busqueda brute force para
$$P\in\{40,60,100,150,200,300\}.$$
Los valores son
$$N(40)=16,\quad N(60)=26,\quad N(100)=46,$$
$$N(150)=72,\quad N(200)=100,\quad N(300)=160.$$
count_valid_triangles(P) comienza con la contribucion equilatera \(\lfloor P/3\rfloor\), fija
$$\text{max\_var}=\lfloor\sqrt{P}\rfloor+2,$$
y luego suma las cuatro familias no triviales. Cada contador recorre pares primitivos \((x,y)\), aplica filtros de coprimalidad, paridad y modulo 3, calcula el perimetro base y suma el numero de escalas \(g\) permitidas.
Como las cuatro familias son independientes, la implementacion puede repartirlas entre hasta cuatro hilos pthread. Para los limites pequenos, brute_count sirve de verificacion exacta.
Los parametros \(x\) e \(y\) solo llegan hasta \(O(\sqrt{P})\), asi que el recorrido es cuadratico en \(\sqrt{P}\), es decir, alrededor de \(O(P)\) pares candidatos. Cada par requiere solo un gcd y aritmetica entera constante. La memoria adicional es constante, salvo pequenos contextos de hilo.
设 \(a\le b\le c\) 是非退化整数三角形 \(ABC\) 的三边，则周长为
$$p=a+b+c.$$
按照题目中的记号，角平分线把边切分于点 \(E,F,G\)，我们关心的面积比是
$$\frac{[ABC]}{[AEG]}.$$
要求统计所有满足
$$a+b+c\le P$$
且该比值为整数的整边三角形。完整 Euler 极限下的最终答案这里不直接写出。
代码并不直接计算面积，而是先把问题改写成纯算术条件。
设 \(E\) 是 \(A\) 点角平分线与 \(BC\) 的交点，\(G\) 是 \(B\) 点角平分线与 \(AC\) 的交点。由角平分线定理，
$$\frac{BE}{EC}=\frac{AB}{AC}=\frac{c}{b},\qquad \frac{AG}{GC}=\frac{AB}{BC}=\frac{c}{a}.$$
因为 \(BC=a\), \(AC=b\)，可得
$$EC=\frac{ab}{b+c},\qquad AG=\frac{bc}{a+c}.$$
\(ABC\) 与 \(AEC\) 在 \(BC\) 上有相同高，因此
$$\frac{[ABC]}{[AEC]}=\frac{BC}{EC}=\frac{b+c}{b}.$$
同理，\(AEC\) 与 \(AEG\) 在 \(AC\) 上有相同高，所以
$$\frac{[AEC]}{[AEG]}=\frac{AC}{AG}=\frac{a+c}{c}.$$
相乘就得到核心恒等式：
$$\frac{[ABC]}{[AEG]}=\frac{(a+b)(a+c)}{bc}.$$
于是问题等价于统计使得
$$k=\frac{(a+b)(a+c)}{bc}$$
为整数的三角形。
把 \(k\) 改写为
$$k=\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right).$$
由于 \(a\le b\le c\)，有
$$0<\frac{a}{c}\le \frac{a}{b}\le 1,$$
因此
$$1<k\le 4.$$
而 \(k\) 又必须是整数，所以只可能是
$$k\in\{2,3,4\}.$$
若
$$\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right)=4,$$
由于两个因子都不超过 2，所以只能同时等于 2，从而必有
$$a=b=c.$$
因此这一部分的贡献就是
$$\left\lfloor\frac{P}{3}\right\rfloor.$$
从
$$\frac{(a+b)(a+c)}{bc}=2$$
出发，可化为
$$(b-a)(c-a)=2a^2.$$
令
$$d_1=b-a,\qquad d_2=c-a,$$
则
$$d_1d_2=2a^2.$$
再设
$$g=\gcd(d_1,d_2),\qquad d_1=gu,\qquad d_2=gv,\qquad \gcd(u,v)=1.$$
由于 \(g\mid a\)，写成 \(a=gh\)，于是
$$uv=2h^2.$$
因为 \(u,v\) 互素且乘积是“2乘平方”，所以其中一个必须是平方，另一个必须是 \(2\) 倍平方。故只有两种规范形式：
$$u=x^2,\quad v=2y^2,$$
或者
$$u=2x^2,\quad v=y^2,$$
并且 \(\gcd(x,y)=1\)。
家族 A。 取
$$d_1=gx^2,\qquad d_2=2gy^2.$$
则
$$a=gxy,\qquad b=gx(x+y),\qquad c=gy(x+2y),$$
周长为
$$p=g(x+y)(x+2y).$$
顺序关系和三角不等式化为
$$y<x\le \sqrt{2}\,y.$$
此外 \(x\) 必须是奇数。对每个原始参数对 \((x,y)\)，允许的缩放数目为
$$\left\lfloor\frac{P}{(x+y)(x+2y)}\right\rfloor.$$
家族 B。 取
$$d_1=2gx^2,\qquad d_2=gy^2.$$
则
$$a=gxy,\qquad b=gx(2x+y),\qquad c=gy(x+y),$$
且
$$p=g(x+y)(2x+y).$$
参数范围变成
$$\sqrt{2}\,x\le y<2x,$$
并且 \(y\) 必须是奇数。此时贡献为
$$\left\lfloor\frac{P}{(x+y)(2x+y)}\right\rfloor.$$
最小的 \(k=2\) 例子来自家族 B。取
$$x=2,\qquad y=3,\qquad g=1,$$
便得到
$$a=6,\qquad b=14,\qquad c=15,$$
即
$$ (a,b,c)=(6,14,15),\qquad p=35. $$
直接检验：
$$\frac{(a+b)(a+c)}{bc}=\frac{20\cdot 21}{14\cdot 15}=2.$$
从
$$\frac{(a+b)(a+c)}{bc}=3$$
可推出
$$(2b-a)(2c-a)=3a^2.$$
令
$$u=2b-a,\qquad v=2c-a,$$
则
$$uv=3a^2.$$
写成
$$u=gs,\qquad v=gt,\qquad \gcd(s,t)=1,\qquad a=gh,$$
就有
$$st=3h^2.$$
因此互素的两个因子中，一个必须是平方，另一个必须是 3 倍平方：
$$s=x^2,\quad t=3y^2,$$
或者
$$s=3x^2,\quad t=y^2.$$
家族 A。 取
$$u=gx^2,\qquad v=3gy^2.$$
则
$$a=gxy,\qquad b=\frac{gx(x+y)}{2},\qquad c=\frac{gy(x+3y)}{2},$$
并且
$$p=\frac{g(x+y)(x+3y)}{2}.$$
参数范围是
$$y<x\le \sqrt{3}\,y,$$
同时要求 \(x\not\equiv 0\pmod 3\)。
由于 \(b,c\) 带有除以 2，\(g\) 的奇偶性会影响边长是否仍为整数。若 \(x,y\) 都是奇数，则任意正整数 \(g\) 都可以；否则只能取偶数 \(g\)。设
$$B_A=(x+y)(x+3y),\qquad g_{\max}=\left\lfloor\frac{2P}{B_A}\right\rfloor,$$
则贡献是 \(g_{\max}\) 或 \(\lfloor g_{\max}/2\rfloor\)。
家族 B。 取
$$u=3gx^2,\qquad v=gy^2.$$
则
$$a=gxy,\qquad b=\frac{gx(3x+y)}{2},\qquad c=\frac{gy(x+y)}{2},$$
周长为
$$p=\frac{g(x+y)(3x+y)}{2}.$$
其范围条件是
$$\sqrt{3}\,x\le y<3x,$$
且 \(y\not\equiv 0\pmod 3\)。这里 \(g\) 的奇偶规则与家族 A 相同。
最小的 \(k=3\) 三角形是
$$ (4,5,6). $$
它来自家族 B，参数为
$$x=1,\qquad y=2,\qquad g=2.$$
于是
$$a=4,\qquad b=5,\qquad c=6,$$
而且
$$\frac{(a+b)(a+c)}{bc}=\frac{9\cdot 10}{5\cdot 6}=3.$$
每个合法三角形都有唯一的整数比值 \(k\in\{2,3,4\}\)。\(k=4\) 只对应等边。对于 \(k=2\) 和 \(k=3\)，在提出 gcd 并化到互素部分之后，平方自由因子 2 或 3 放在哪一侧是唯一确定的，这正对应 A/B 两个家族。随后缩放因子 \(g\) 也唯一。因此每个三角形只被生成一次。
记 \(N(P)\) 为周长不超过 \(P\) 的合法三角形个数。代码把快速公式与暴力枚举在
$$P\in\{40,60,100,150,200,300\}$$
上逐一比较。这些结果为
$$N(40)=16,\quad N(60)=26,\quad N(100)=46,$$
$$N(150)=72,\quad N(200)=100,\quad N(300)=160.$$
count_valid_triangles(P) 先加入等边部分 \(\lfloor P/3\rfloor\)，再设置
$$\text{max\_var}=\lfloor\sqrt{P}\rfloor+2,$$
然后分别统计四个非平凡家族。每个计数器都遍历原始参数对 \((x,y)\)，应用互素、奇偶与模 3 过滤，计算基础周长表达式，并累加允许的缩放因子 \(g\) 数量。
四个家族彼此独立，因此实现可以把它们分配给最多四个 pthread 线程。小范围验证则使用 brute_count。
\(x\) 和 \(y\) 的范围都只到 \(O(\sqrt{P})\)，所以整体搜索相当于在 \(\sqrt{P}\) 上做二次遍历，也就是大约 \(O(P)\) 个候选参数对。每个候选只需要一个 gcd 和常数次整数运算。除少量线程上下文外，额外内存为常数级。
Пусть \(a\le b\le c\) - целые стороны невырожденного треугольника \(ABC\). Его периметр равен
$$p=a+b+c.$$
Как и в условии, биссектрисы пересекают стороны в точках \(E,F,G\), и нас интересует отношение площадей
$$\frac{[ABC]}{[AEG]}.$$
Нужно посчитать все треугольники с целыми сторонами, удовлетворяющие
$$a+b+c\le P,$$
для которых это отношение является целым числом. Окончательный численный ответ для полного лимита Euler здесь сознательно не приводится.
Решение не считает площади напрямую. Сначала оно выражает все через \(a,b,c\).
Пусть \(E\) - точка пересечения биссектрисы из \(A\) со стороной \(BC\), а \(G\) - точка пересечения биссектрисы из \(B\) со стороной \(AC\). По теореме о биссектрисе
$$\frac{BE}{EC}=\frac{AB}{AC}=\frac{c}{b},\qquad \frac{AG}{GC}=\frac{AB}{BC}=\frac{c}{a}.$$
Так как \(BC=a\) и \(AC=b\), получаем
$$EC=\frac{ab}{b+c},\qquad AG=\frac{bc}{a+c}.$$
Треугольники \(ABC\) и \(AEC\) имеют общую высоту к \(BC\), поэтому
$$\frac{[ABC]}{[AEC]}=\frac{BC}{EC}=\frac{b+c}{b}.$$
А треугольники \(AEC\) и \(AEG\) имеют общую высоту к \(AC\), значит
$$\frac{[AEC]}{[AEG]}=\frac{AC}{AG}=\frac{a+c}{c}.$$
Перемножая, получаем основную формулу:
$$\frac{[ABC]}{[AEG]}=\frac{(a+b)(a+c)}{bc}.$$
Итак, задача сводится к подсчету треугольников, для которых
$$k=\frac{(a+b)(a+c)}{bc}$$
является целым числом.
Перепишем
$$k=\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right).$$
Из \(a\le b\le c\) следует
$$0<\frac{a}{c}\le \frac{a}{b}\le 1,$$
поэтому
$$1<k\le 4.$$
Так как \(k\) должно быть целым, остаются только
$$k\in\{2,3,4\}.$$
Чтобы
$$\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right)=4,$$
оба множителя должны быть равны 2. Это возможно только при
$$a=b=c.$$
Следовательно, вклад этого случая равен
$$\left\lfloor\frac{P}{3}\right\rfloor.$$
Из равенства
$$\frac{(a+b)(a+c)}{bc}=2$$
получаем
$$(b-a)(c-a)=2a^2.$$
Положим
$$d_1=b-a,\qquad d_2=c-a.$$
Тогда
$$d_1d_2=2a^2.$$
Пусть
$$g=\gcd(d_1,d_2),\qquad d_1=gu,\qquad d_2=gv,\qquad \gcd(u,v)=1.$$
Так как \(g\mid a\), пишем \(a=gh\), и тогда
$$uv=2h^2.$$
Поскольку \(u\) и \(v\) взаимно просты, один из множителей обязан быть квадратом, а другой - удвоенным квадратом. Отсюда две канонические формы:
$$u=x^2,\quad v=2y^2,$$
или
$$u=2x^2,\quad v=y^2,$$
где \(\gcd(x,y)=1\).
Семейство A. Пусть
$$d_1=gx^2,\qquad d_2=2gy^2.$$
Тогда
$$a=gxy,\qquad b=gx(x+y),\qquad c=gy(x+2y),$$
а периметр равен
$$p=g(x+y)(x+2y).$$
Условия порядка и неравенства треугольника дают
$$y<x\le \sqrt{2}\,y.$$
Кроме того, \(x\) должен быть нечетным. Число допустимых масштабов равно
$$\left\lfloor\frac{P}{(x+y)(x+2y)}\right\rfloor.$$
Семейство B. Пусть
$$d_1=2gx^2,\qquad d_2=gy^2.$$
Тогда
$$a=gxy,\qquad b=gx(2x+y),\qquad c=gy(x+y),$$
с периметром
$$p=g(x+y)(2x+y).$$
Здесь условия имеют вид
$$\sqrt{2}\,x\le y<2x,$$
и \(y\) должен быть нечетным. Вклад равен
$$\left\lfloor\frac{P}{(x+y)(2x+y)}\right\rfloor.$$
Наименьший треугольник с \(k=2\) возникает уже в семействе B. Возьмем
$$x=2,\qquad y=3,\qquad g=1.$$
Тогда
$$a=6,\qquad b=14,\qquad c=15,$$
то есть
$$ (a,b,c)=(6,14,15),\qquad p=35. $$
Проверка:
$$\frac{(a+b)(a+c)}{bc}=\frac{20\cdot 21}{14\cdot 15}=2.$$
Из
$$\frac{(a+b)(a+c)}{bc}=3$$
получаем
$$(2b-a)(2c-a)=3a^2.$$
Положим
$$u=2b-a,\qquad v=2c-a.$$
Тогда
$$uv=3a^2.$$
Снова пишем
$$u=gs,\qquad v=gt,\qquad \gcd(s,t)=1,\qquad a=gh,$$
и получаем
$$st=3h^2.$$
Значит, один множитель является квадратом, а другой - тремя квадратами:
$$s=x^2,\quad t=3y^2,$$
или
$$s=3x^2,\quad t=y^2.$$
Семейство A. Пусть
$$u=gx^2,\qquad v=3gy^2.$$
Тогда
$$a=gxy,\qquad b=\frac{gx(x+y)}{2},\qquad c=\frac{gy(x+3y)}{2},$$
а периметр
$$p=\frac{g(x+y)(x+3y)}{2}.$$
Ограничения таковы:
$$y<x\le \sqrt{3}\,y,$$
и \(x\not\equiv 0\pmod 3\).
Из-за деления на 2 в формулах для \(b\) и \(c\) важна четность \(g\). Если \(x\) и \(y\) оба нечетные, то подходит любое \(g\). Иначе подходят только четные \(g\).
Если
$$B_A=(x+y)(x+3y),\qquad g_{\max}=\left\lfloor\frac{2P}{B_A}\right\rfloor,$$
то вклад равен \(g_{\max}\) или \(\lfloor g_{\max}/2\rfloor\).
Семейство B. Пусть
$$u=3gx^2,\qquad v=gy^2.$$
Тогда
$$a=gxy,\qquad b=\frac{gx(3x+y)}{2},\qquad c=\frac{gy(x+y)}{2},$$
а периметр равен
$$p=\frac{g(x+y)(3x+y)}{2}.$$
Условия теперь
$$\sqrt{3}\,x\le y<3x,$$
и \(y\not\equiv 0\pmod 3\). Правило четности для \(g\) то же самое.
Наименьший треугольник с \(k=3\) - это
$$ (4,5,6). $$
Он получается из семейства B при
$$x=1,\qquad y=2,\qquad g=2.$$
Тогда
$$a=4,\qquad b=5,\qquad c=6,$$
и
$$\frac{(a+b)(a+c)}{bc}=\frac{9\cdot 10}{5\cdot 6}=3.$$
У каждого допустимого треугольника есть единственное целое \(k\in\{2,3,4\}\). Случай \(k=4\) отделен полностью. В случаях \(k=2\) и \(k=3\) после вынесения gcd и перехода к взаимно простым частям квадратсвободный множитель 2 или 3 может лежать только в одной из двух сторон, и это ровно разбиение на A и B. После этого масштаб \(g\) тоже определяется однозначно. Поэтому каждый треугольник учитывается ровно один раз.
Пусть \(N(P)\) обозначает число допустимых треугольников с периметром не более \(P\). Код сравнивает быструю формулу с полным перебором для
$$P\in\{40,60,100,150,200,300\}.$$
Получаются значения
$$N(40)=16,\quad N(60)=26,\quad N(100)=46,$$
$$N(150)=72,\quad N(200)=100,\quad N(300)=160.$$
count_valid_triangles(P) начинает с равностороннего вклада \(\lfloor P/3\rfloor\), затем берет
$$\text{max\_var}=\lfloor\sqrt{P}\rfloor+2,$$
после чего суммирует четыре нетривиальных семейства. Каждая функция перебирает примитивные пары \((x,y)\), применяет условия взаимной простоты, четности и остатка по модулю 3, вычисляет базовый периметр и добавляет число допустимых масштабов \(g\).
Поскольку четыре семейства независимы, реализация может распределить их между четырьмя pthread-потоками. Для маленьких значений \(P\) правильность проверяет brute_count.
Параметры \(x\) и \(y\) ограничены величиной \(O(\sqrt{P})\), поэтому поиск квадратичен по \(\sqrt{P}\), то есть порядка \(O(P)\) кандидатных пар. Для каждой пары выполняется один gcd и константное число целочисленных операций. Дополнительная память постоянна, если не считать маленьких потоковых структур.
لتكن \(a\le b\le c\) أطوال أضلاع مثلث صحيح غير منعدم \(ABC\)، وليكن محيطه
$$p=a+b+c.$$
كما في نص المسألة، تقطع منصفات الزوايا الأضلاع في النقاط \(E,F,G\)، والنسبة التي نهتم بها هي
$$\frac{[ABC]}{[AEG]}.$$
المطلوب هو عد جميع المثلثات الصحيحة التي تحقق
$$a+b+c\le P$$
بحيث تكون هذه النسبة عددًا صحيحًا. أمّا الجواب النهائي للحد الكبير في Euler فمتروك هنا دون تصريح.
الحل لا يعمل على المساحات مباشرة، بل يحولها أولًا إلى علاقة صريحة بين \(a,b,c\).
لتكن \(E\) نقطة تقاطع منصف الزاوية عند \(A\) مع \(BC\)، ولتكن \(G\) نقطة تقاطع منصف الزاوية عند \(B\) مع \(AC\). من نظرية منصف الزاوية نحصل على
$$\frac{BE}{EC}=\frac{AB}{AC}=\frac{c}{b},\qquad \frac{AG}{GC}=\frac{AB}{BC}=\frac{c}{a}.$$
وبما أن \(BC=a\) و \(AC=b\)، فإن
$$EC=\frac{ab}{b+c},\qquad AG=\frac{bc}{a+c}.$$
المثلثان \(ABC\) و \(AEC\) يشتركان في الارتفاع نفسه على \(BC\)، ولذلك
$$\frac{[ABC]}{[AEC]}=\frac{BC}{EC}=\frac{b+c}{b}.$$
وبالمثل فإن \(AEC\) و \(AEG\) يشتركان في الارتفاع نفسه على \(AC\)، ومن ثم
$$\frac{[AEC]}{[AEG]}=\frac{AC}{AG}=\frac{a+c}{c}.$$
وبضرب النسبتين نحصل على العلاقة المحورية:
$$\frac{[ABC]}{[AEG]}=\frac{(a+b)(a+c)}{bc}.$$
إذن تصبح المسألة هي عد المثلثات التي يكون فيها
$$k=\frac{(a+b)(a+c)}{bc}$$
عددًا صحيحًا.
نكتب
$$k=\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right).$$
وبسبب \(a\le b\le c\) فإن
$$0<\frac{a}{c}\le \frac{a}{b}\le 1,$$
ومن ثم
$$1<k\le 4.$$
ولأن \(k\) يجب أن يكون عددًا صحيحًا، فلا يبقى إلا
$$k\in\{2,3,4\}.$$
لكي يتحقق
$$\left(1+\frac{a}{b}\right)\left(1+\frac{a}{c}\right)=4,$$
فلا بد أن يساوي كل عامل 2، لأن كل عامل لا يمكن أن يتجاوز 2. وهذا يجبرنا على
$$a=b=c.$$
لذلك يكون إسهام هذه العائلة ببساطة
$$\left\lfloor\frac{P}{3}\right\rfloor.$$
من
$$\frac{(a+b)(a+c)}{bc}=2$$
نصل إلى
$$(b-a)(c-a)=2a^2.$$
لنعرّف
$$d_1=b-a,\qquad d_2=c-a.$$
عندها
$$d_1d_2=2a^2.$$
ولتكن
$$g=\gcd(d_1,d_2),\qquad d_1=gu,\qquad d_2=gv,\qquad \gcd(u,v)=1.$$
وبما أن \(g\mid a\)، نكتب \(a=gh\)، فنحصل على
$$uv=2h^2.$$
وبما أن \(u\) و \(v\) متباينان أوليًا، فلا بد أن يكون أحدهما مربعًا كاملًا والآخر ضعف مربع كامل. إذن توجد صورتان قانونيتان فقط:
$$u=x^2,\quad v=2y^2,$$
أو
$$u=2x^2,\quad v=y^2,$$
مع \(\gcd(x,y)=1\).
العائلة A. نأخذ
$$d_1=gx^2,\qquad d_2=2gy^2.$$
فتكون
$$a=gxy,\qquad b=gx(x+y),\qquad c=gy(x+2y),$$
ويصبح المحيط
$$p=g(x+y)(x+2y).$$
وتتحول الشروط إلى
$$y<x\le \sqrt{2}\,y.$$
كما يجب أن يكون \(x\) فرديًا. وعدد معاملات القياس المسموح بها هو
$$\left\lfloor\frac{P}{(x+y)(x+2y)}\right\rfloor.$$
العائلة B. نأخذ
$$d_1=2gx^2,\qquad d_2=gy^2.$$
فتصبح
$$a=gxy,\qquad b=gx(2x+y),\qquad c=gy(x+y),$$
ومنه
$$p=g(x+y)(2x+y).$$
والشروط هنا هي
$$\sqrt{2}\,x\le y<2x,$$
مع ضرورة أن يكون \(y\) فرديًا. ويكون عدد معاملات القياس
$$\left\lfloor\frac{P}{(x+y)(2x+y)}\right\rfloor.$$
أصغر مثلث من نوع \(k=2\) يظهر بالفعل في العائلة B. خذ
$$x=2,\qquad y=3,\qquad g=1.$$
فنحصل على
$$a=6,\qquad b=14,\qquad c=15,$$
أي
$$ (a,b,c)=(6,14,15),\qquad p=35. $$
والتحقق المباشر يعطي
$$\frac{(a+b)(a+c)}{bc}=\frac{20\cdot 21}{14\cdot 15}=2.$$
من
$$\frac{(a+b)(a+c)}{bc}=3$$
نستنتج
$$(2b-a)(2c-a)=3a^2.$$
لنعرّف
$$u=2b-a,\qquad v=2c-a.$$
وعندها
$$uv=3a^2.$$
ثم نكتب
$$u=gs,\qquad v=gt,\qquad \gcd(s,t)=1,\qquad a=gh,$$
فنصل إلى
$$st=3h^2.$$
وهذا يعني أن أحد العاملين مربع كامل، والآخر ثلاثة أضعاف مربع كامل:
$$s=x^2,\quad t=3y^2,$$
أو
$$s=3x^2,\quad t=y^2.$$
العائلة A. إذا أخذنا
$$u=gx^2,\qquad v=3gy^2,$$
فإن
$$a=gxy,\qquad b=\frac{gx(x+y)}{2},\qquad c=\frac{gy(x+3y)}{2},$$
ويكون المحيط
$$p=\frac{g(x+y)(x+3y)}{2}.$$
وتصبح الشروط
$$y<x\le \sqrt{3}\,y,$$
مع \(x\not\equiv 0\pmod 3\).
وبسبب القسمة على 2 في صيغتي \(b\) و \(c\)، فإن فردية أو زوجية \(g\) مهمة. إذا كان \(x\) و \(y\) فرديين معًا، فكل \(g\) يصلح. وإلا فلا تصلح إلا قيم \(g\) الزوجية.
إذا عرّفنا
$$B_A=(x+y)(x+3y),\qquad g_{\max}=\left\lfloor\frac{2P}{B_A}\right\rfloor,$$
فإن الإسهام يكون \(g_{\max}\) أو \(\lfloor g_{\max}/2\rfloor\).
العائلة B. وإذا أخذنا
$$u=3gx^2,\qquad v=gy^2,$$
فنحصل على
$$a=gxy,\qquad b=\frac{gx(3x+y)}{2},\qquad c=\frac{gy(x+y)}{2},$$
وبالتالي
$$p=\frac{g(x+y)(3x+y)}{2}.$$
والشروط الآن هي
$$\sqrt{3}\,x\le y<3x,$$
مع \(y\not\equiv 0\pmod 3\). وقاعدة الفردي/الزوجي الخاصة بـ \(g\) تبقى نفسها.
أصغر مثلث من نوع \(k=3\) هو
$$ (4,5,6). $$
وهو يأتي من العائلة B عند
$$x=1,\qquad y=2,\qquad g=2.$$
فنجد
$$a=4,\qquad b=5,\qquad c=6,$$
وبالتالي
$$\frac{(a+b)(a+c)}{bc}=\frac{9\cdot 10}{5\cdot 6}=3.$$
لكل مثلث صالح قيمة صحيحة وحيدة \(k\in\{2,3,4\}\). حالة \(k=4\) منفصلة تمامًا لأنها تعطي المثلثات المتساوية الأضلاع فقط. وفي حالتي \(k=2\) و \(k=3\)، بعد استخراج القاسم المشترك الأكبر وتقسيم الجزء المربع الحر، يتحدد بشكل فريد في أي عامل يظهر العدد 2 أو 3، وهذا هو بالضبط انقسام A/B. ثم يأتي \(g\) بوصفه معامل القياس الوحيد. لذلك يُولد كل مثلث مرة واحدة فقط.
إذا رمزنا بعدد المثلثات الصالحة ذات المحيط حتى \(P\) بالرمز \(N(P)\)، فإن الكود يقارن الصيغة السريعة مع العد الشامل للقيم
$$P\in\{40,60,100,150,200,300\}.$$
وتكون النتائج
$$N(40)=16,\quad N(60)=26,\quad N(100)=46,$$
$$N(150)=72,\quad N(200)=100,\quad N(300)=160.$$
تبدأ الدالة count_valid_triangles(P) بإضافة مساهمة المثلثات المتساوية الأضلاع \(\lfloor P/3\rfloor\)، ثم تضبط
$$\text{max\_var}=\lfloor\sqrt{P}\rfloor+2,$$
وبعد ذلك تجمع العائلات الأربع غير البديهية. كل دالة عد تمر على أزواج أولية \((x,y)\)، وتطبق شروط التباين الأولي والفردي/الزوجي وشرط modulo 3، ثم تحسب تعبير المحيط الأساسي وتضيف عدد معاملات القياس \(g\) المقبولة.
وبما أن العائلات الأربع مستقلة، فإن التنفيذ يستطيع توزيعها على ما يصل إلى أربعة خيوط pthread. أما للتحقق عند القيم الصغيرة فيستخدم brute_count.
المعاملان \(x\) و \(y\) لا يتجاوزان \(O(\sqrt{P})\)، ولذلك يكون البحث تربيعيًا بالنسبة إلى \(\sqrt{P}\)، أي ما يقارب \(O(P)\) من الأزواج المرشحة. وكل زوج يحتاج فقط إلى gcd واحد وبعض العمليات الصحيحة الثابتة. واستهلاك الذاكرة يبقى ثابتًا تقريبًا باستثناء سياقات الخيوط الصغيرة.