The problem starts with
$$A(a,0),\qquad B(b,0),\qquad C(0,a),\qquad D(0,d),$$
where \(0<a<b\) and \(0<a<d\). We seek integer triplets \((a,b,d)\) for which there exists an integer point \(P\) on \(AC\) such that the three triangles \(ABP\), \(CDP\), and \(BDP\) are all similar. The quantity to count is the number of such triplets with
$$b+d<N.$$
Project Euler already states that similarity is possible only when \(a=c\), so the segment \(AC\) lies on the line
$$x+y=a.$$
Because \(OA\) and \(OC\) are symmetric, the angles at \(A\) and \(C\) are both \(135^\circ\). Matching the three similar triangles leaves two possible angle correspondences:
Incenter case. The lines \(PB\) and \(PD\) are angle bisectors of the right triangle \(OBD\), so \(P\) is the incenter of \(\triangle OBD\).
Parallel case. The line \(AC\) is parallel to \(BD\).
These two families are disjoint, and the code counts them separately.
If \(P\) is the incenter of the right triangle with legs \(b\) and \(d\), then its coordinates must be
$$P=(i,i),$$
where \(i\) is the inradius. Since \(P\in AC\), we have
$$a=2i.$$
For a right triangle, the inradius is
$$i=\frac{b+d-\sqrt{b^2+d^2}}{2}.$$
Therefore \(a\) is integral exactly when \(\sqrt{b^2+d^2}\) is integral. So the incenter family is equivalent to counting right triangles with integer legs \(b,d\) and hypotenuse
$$z=\sqrt{b^2+d^2},$$
under the limit \(b+d<N\).
The sample \((a,b,d)=(2,3,4)\) comes from the primitive Pythagorean triple
$$3^2+4^2=5^2,$$
because
$$a=b+d-z=3+4-5=2,$$
and then \(P=(1,1)\) lies on \(x+y=2\).
Write
$$u=b-a,\qquad v=d-a.$$
Then
$$b=a+u,\qquad d=a+v,\qquad z=b+d-a=a+u+v.$$
Substituting \(z^2=b^2+d^2\) gives
$$a^2=2uv.$$
So the primitive solutions come in two orientations:
$$u=g m^2,\qquad v=2g n^2,\qquad a=2gmn,$$
or
$$u=2g m^2,\qquad v=g n^2,\qquad a=2gmn,$$
with \(\gcd(m,n)=1\). After reconstructing \(b\) and \(d\), the perimeter bound becomes
$$b+d=g(m^2+4mn+2n^2)$$
in the first orientation, and
$$b+d=g(2m^2+4mn+n^2)$$
in the second. These are exactly the denominators
$$s_1=m^2+4mn+2n^2,\qquad s_2=2m^2+4mn+n^2$$
used by the code. For fixed primitive \((m,n)\), all scaled copies are obtained by multiplying by \(g\), so the number of valid scales is
$$\left\lfloor\frac{N-1}{s_1}\right\rfloor \quad \text{or} \quad \left\lfloor\frac{N-1}{s_2}\right\rfloor.$$
The parity filters in the implementation are the primitive-normalization rules that prevent duplicate descriptions.
In the second similarity pattern we have
$$AC\parallel BD,$$
so the slope condition forces
$$d=b.$$
Let
$$f=b-a>0.$$
Then \(D=(0,b)\), \(B=(b,0)\), and the circumcenter of \(\triangle BDP\) is \(X=(b,b)\). Hence \(P\) must lie on the circle
$$ (x-b)^2+(y-b)^2=b^2,$$
and also on the line \(AC\), namely
$$y=a-x.$$
Substituting gives
$$x=\frac{a\pm \sqrt{a^2-2f^2}}{2}.$$
Therefore an integer point \(P\) exists exactly when
$$Q^2=a^2-2f^2,$$
that is,
$$Q^2+2f^2=a^2.$$
A small example is
$$a=3,\qquad f=2,\qquad b=d=5,$$
because \(1^2+2\cdot 2^2=3^2\), giving the triplet \((3,5,5)\).
Primitive solutions of
$$Q^2+2f^2=a^2$$
are parameterized by coprime integers \(p,q\) with odd \(p\):
$$Q=p^2-2q^2,\qquad f=2pq,\qquad a=p^2+2q^2.$$
After scaling by \(g\), we get
$$b=d=a+f=g(p^2+2pq+2q^2).$$
Hence the bound \(b+d<N\) becomes
$$2g(p^2+2pq+2q^2)<N,$$
so for each primitive pair the number of scales is
$$\left\lfloor\frac{N-1}{2(p^2+2pq+2q^2)}\right\rfloor.$$
This is exactly the denominator
$$s_3=2(p^2+2pq+2q^2)$$
used in the implementation.
The two families are disjoint, so the total is
$$T(N)=\sum \left\lfloor\frac{N-1}{s_1}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_2}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_3}\right\rfloor.$$
The code validates itself with the published checkpoints
$$T(100)=92,\qquad T(100000)=320471.$$
count_family_x_eq_y(...) enumerates the incenter family via the two forms \(s_1,s_2\). count_family_u_eq_v(...) enumerates the parallel family via \(s_3\). For each primitive parameter pair, the contribution is the number of scale factors \(g\) allowed by \(b+d<N\). The final answer is the sum of both family totals.
The loops over \((m,n)\) and \((p,q)\) break as soon as the corresponding denominator reaches \(N\). So the practical runtime is far below a naive scan over all triples \((a,b,d)\). Memory usage is \(O(1)\) beyond a few counters, and the C++ / Python versions optionally split independent parameter ranges across threads or processes.
Gegeben sind
$$A(a,0),\qquad B(b,0),\qquad C(0,a),\qquad D(0,d),$$
mit \(0<a<b\) und \(0<a<d\). Gesucht sind ganzzahlige Tripel \((a,b,d)\), für die es einen ganzzahligen Punkt \(P\) auf \(AC\) gibt, so dass die drei Dreiecke \(ABP\), \(CDP\) und \(BDP\) ähnlich sind. Gezählt wird unter der Schranke
$$b+d<N.$$
Das Problem selbst sagt bereits, dass Ähnlichkeit nur möglich ist, wenn \(a=c\). Also liegt \(AC\) auf der Geraden
$$x+y=a.$$
Die Winkelsituation erzwingt dann genau zwei Möglichkeiten:
Inkreis-Fall. \(PB\) und \(PD\) sind Winkelhalbierende im rechtwinkligen Dreieck \(OBD\), also ist \(P\) der Inkreismittelpunkt.
Parallel-Fall. \(AC\parallel BD\).
Diese beiden Familien sind disjunkt; der Code zählt sie getrennt.
Ist \(P\) der Inkreismittelpunkt des rechtwinkligen Dreiecks mit Katheten \(b\) und \(d\), dann hat \(P\) die Form
$$P=(i,i),$$
wobei \(i\) der Inkreisradius ist. Weil \(P\in AC\), gilt
$$a=2i.$$
Für ein rechtwinkliges Dreieck ist
$$i=\frac{b+d-\sqrt{b^2+d^2}}{2}.$$
Damit ist \(a\) genau dann ganzzahlig, wenn \(\sqrt{b^2+d^2}\) ganzzahlig ist. Also reduziert sich dieser Fall auf ganzzahlige rechtwinklige Dreiecke mit
$$z=\sqrt{b^2+d^2}.$$
Das Beispiel \((a,b,d)=(2,3,4)\) entsteht aus
$$3^2+4^2=5^2,$$
denn
$$a=b+d-z=3+4-5=2,$$
und damit liegt \(P=(1,1)\) auf \(x+y=2\).
Setze
$$u=b-a,\qquad v=d-a.$$
Dann gilt
$$b=a+u,\qquad d=a+v,\qquad z=a+u+v.$$
Aus \(z^2=b^2+d^2\) folgt unmittelbar
$$a^2=2uv.$$
Die primitiven Lösungen zerfallen in zwei Orientierungen:
$$u=g m^2,\qquad v=2g n^2,\qquad a=2gmn,$$
oder
$$u=2g m^2,\qquad v=g n^2,\qquad a=2gmn,$$
mit \(\gcd(m,n)=1\). Daraus wird
$$b+d=g(m^2+4mn+2n^2)$$
bzw.
$$b+d=g(2m^2+4mn+n^2).$$
Das sind genau die im Code auftauchenden Nenner
$$s_1=m^2+4mn+2n^2,\qquad s_2=2m^2+4mn+n^2.$$
Für ein primitives Paar \((m,n)\) ist die Zahl der zulässigen Skalierungen \(g\) also
$$\left\lfloor\frac{N-1}{s_1}\right\rfloor \quad\text{oder}\quad \left\lfloor\frac{N-1}{s_2}\right\rfloor.$$
Die Paritätsfilter sorgen dafür, dass nur primitive und nicht doppelt beschriebene Familien erzeugt werden.
Im zweiten Ähnlichkeitsmuster gilt
$$AC\parallel BD,$$
also wegen der Steigung bereits
$$d=b.$$
Schreibe
$$f=b-a>0.$$
Dann ist der Umkreismittelpunkt von \(\triangle BDP\) der Punkt \(X=(b,b)\), also muss \(P\) auf dem Kreis
$$ (x-b)^2+(y-b)^2=b^2$$
und zugleich auf \(AC\) liegen, also auf
$$y=a-x.$$
Einsetzen liefert
$$x=\frac{a\pm \sqrt{a^2-2f^2}}{2}.$$
Ein ganzzahliger Punkt \(P\) existiert also genau dann, wenn
$$Q^2=a^2-2f^2,$$
also
$$Q^2+2f^2=a^2.$$
Ein kleines Beispiel ist
$$a=3,\qquad f=2,\qquad b=d=5,$$
denn \(1^2+2\cdot 2^2=3^2\).
Primitive Lösungen von
$$Q^2+2f^2=a^2$$
werden durch teilerfremde \(p,q\) mit ungeradem \(p\) parametrisiert:
$$Q=p^2-2q^2,\qquad f=2pq,\qquad a=p^2+2q^2.$$
Nach Skalierung mit \(g\) folgt
$$b=d=a+f=g(p^2+2pq+2q^2).$$
Die Schranke \(b+d<N\) wird somit zu
$$2g(p^2+2pq+2q^2)<N,$$
also ist die Zahl der zulässigen Skalierungen
$$\left\lfloor\frac{N-1}{2(p^2+2pq+2q^2)}\right\rfloor.$$
Genau dieser Nenner ist
$$s_3=2(p^2+2pq+2q^2).$$
Da die beiden Familien disjunkt sind, ist die Gesamtzahl
$$T(N)=\sum \left\lfloor\frac{N-1}{s_1}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_2}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_3}\right\rfloor.$$
Der Code prüft sich mit
$$T(100)=92,\qquad T(100000)=320471.$$
count_family_x_eq_y(...) zählt den Inkreis-Fall über die beiden Formen \(s_1,s_2\). count_family_u_eq_v(...) zählt den Parallel-Fall über \(s_3\). Für jedes primitive Parametertupel wird nur noch bestimmt, wie viele Skalierungsfaktoren \(g\) die Schranke \(b+d<N\) erlauben.
Die Schleifen über \((m,n)\) und \((p,q)\) brechen ab, sobald der jeweilige Nenner \(N\) erreicht. Dadurch ist die praktische Laufzeit weit kleiner als eine naive Suche über alle \((a,b,d)\). Der Speicherbedarf bleibt \(O(1)\); unabhängige Parameterbereiche können parallel abgearbeitet werden.
Başlangıç noktaları
$$A(a,0),\qquad B(b,0),\qquad C(0,a),\qquad D(0,d)$$
olsun; burada \(0<a<b\) ve \(0<a<d\). Amaç, \(AC\) doğrusu üzerinde tam sayı koordinatlı bir \(P\) noktası bulunabilen ve \(ABP\), \(CDP\), \(BDP\) üçgenlerini birbirine benzer yapan tüm tam sayı \((a,b,d)\) üçlülerini saymaktır. Sayım koşulu
$$b+d<N$$
şeklindedir.
Problem metni benzerliğin ancak \(a=c\) iken mümkün olduğunu söyler. Böylece \(AC\) doğrusu
$$x+y=a$$
haline gelir. Açı eşleşmeleri geriye tam olarak iki olasılık bırakır:
İçteğet merkezi durumu. \(PB\) ve \(PD\), dik üçgen \(OBD\)'nin açıortayları olur; dolayısıyla \(P\), \(\triangle OBD\)'nin içteğet merkezidir.
Paralel durum. \(AC\parallel BD\).
Bu iki aile çakışmaz; kod bunları ayrı ayrı sayar.
\(P\), kenarları \(b\) ve \(d\) olan dik üçgenin içteğet merkezi ise
$$P=(i,i)$$
biçimindedir; burada \(i\) inradius'tur. \(P\in AC\) olduğundan
$$a=2i.$$
Dik üçgende inradius formülü
$$i=\frac{b+d-\sqrt{b^2+d^2}}{2}$$
olduğundan, \(a\)'nın tam sayı olması ancak
$$z=\sqrt{b^2+d^2}$$
tam sayı ise mümkündür. Yani bu aile, \(b+d<N\) sınırı altında Pisagor üçlüleri sayımına iner.
Verilen örnek \((a,b,d)=(2,3,4)\) tam olarak
$$3^2+4^2=5^2$$
üçlüsünden gelir; çünkü
$$a=b+d-z=3+4-5=2$$
ve bu durumda \(P=(1,1)\) olur.
$$u=b-a,\qquad v=d-a$$
tanımlarını yapalım. O zaman
$$b=a+u,\qquad d=a+v,\qquad z=a+u+v$$
olur. \(z^2=b^2+d^2\) denklemi doğrudan
$$a^2=2uv$$
sonucunu verir. Primitive çözümler iki yönelime ayrılır:
$$u=g m^2,\qquad v=2g n^2,\qquad a=2gmn,$$
veya
$$u=2g m^2,\qquad v=g n^2,\qquad a=2gmn,$$
burada \(\gcd(m,n)=1\)'dir. Buradan
$$b+d=g(m^2+4mn+2n^2)$$
ya da
$$b+d=g(2m^2+4mn+n^2)$$
elde edilir. Kodun kullandığı
$$s_1=m^2+4mn+2n^2,\qquad s_2=2m^2+4mn+n^2$$
denklemleri tam olarak bunlardır. Dolayısıyla her primitive \((m,n)\) çifti için geçerli ölçek sayısı
$$\left\lfloor\frac{N-1}{s_1}\right\rfloor \quad \text{veya} \quad \left\lfloor\frac{N-1}{s_2}\right\rfloor$$
olur. Kod içindeki tek/çift filtreleri primitive normalizasyonundan gelir ve tekrarları engeller.
İkinci benzerlik eşleşmesinde
$$AC\parallel BD$$
olur. Eğime bakınca hemen
$$d=b$$
çıkar. Şimdi
$$f=b-a>0$$
yazalım. \(\triangle BDP\)'nin çevrel merkezinin \(X=(b,b)\) olduğu görülür. Bu yüzden \(P\), hem şu çember üzerinde olmalıdır:
$$ (x-b)^2+(y-b)^2=b^2,$$
hem de \(AC\) üzerinde:
$$y=a-x.$$
Yerine koyunca
$$x=\frac{a\pm \sqrt{a^2-2f^2}}{2}$$
elde edilir. Tam sayı \(P\) varlığı tam olarak
$$Q^2=a^2-2f^2$$
ya da eşdeğer biçimde
$$Q^2+2f^2=a^2$$
koşuluna iner. Küçük bir örnek
$$a=3,\qquad f=2,\qquad b=d=5$$
olup, çünkü \(1^2+2\cdot 2^2=3^2\).
$$Q^2+2f^2=a^2$$
denkleminin primitive çözümleri, aralarında asal ve \(p\) tek olacak şekilde
$$Q=p^2-2q^2,\qquad f=2pq,\qquad a=p^2+2q^2$$
ile parametrize edilir. Ölçek \(g\) ile
$$b=d=a+f=g(p^2+2pq+2q^2)$$
olur. Dolayısıyla sınır
$$b+d<N$$
eşitsizliği
$$2g(p^2+2pq+2q^2)<N$$
haline gelir. Her primitive çiftin katkısı da
$$\left\lfloor\frac{N-1}{2(p^2+2pq+2q^2)}\right\rfloor$$
olur. Kodun kullandığı
$$s_3=2(p^2+2pq+2q^2)$$
paydası tam olarak budur.
İki aile ayrık olduğundan toplam sayı
$$T(N)=\sum \left\lfloor\frac{N-1}{s_1}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_2}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_3}\right\rfloor$$
şeklindedir. Kod şu yayınlanmış checkpoint'lerle kendini doğrular:
$$T(100)=92,\qquad T(100000)=320471.$$
count_family_x_eq_y(...) içteğet merkezi ailesini \(s_1,s_2\) üzerinden, count_family_u_eq_v(...) ise paralel aileyi \(s_3\) üzerinden tarar. Her primitive parametre seti için yapılması gereken tek şey, \(b+d<N\) sınırını sağlayan ölçek katsayısı \(g\) sayısını bulmaktır.
\((m,n)\) ve \((p,q)\) döngüleri, ilgili payda \(N\)'e ulaştığında erkenden kırılır. Bu yüzden pratik süre, tüm \((a,b,d)\) üçlülerini denemekten çok daha düşüktür. Bellek kullanımı sayaçlar dışında \(O(1)\)'dir; bağımsız parametre aralıkları paralel çalıştırılabilir.
Se parte de
$$A(a,0),\qquad B(b,0),\qquad C(0,a),\qquad D(0,d),$$
con \(0<a<b\) y \(0<a<d\). Buscamos tríos enteros \((a,b,d)\) para los que existe un punto entero \(P\) sobre \(AC\) tal que los triángulos \(ABP\), \(CDP\) y \(BDP\) sean similares. La condición de conteo es
$$b+d<N.$$
El propio enunciado afirma que la similitud sólo es posible si \(a=c\). Entonces \(AC\) está en la recta
$$x+y=a.$$
La correspondencia angular deja exactamente dos posibilidades:
Caso del incentro. \(PB\) y \(PD\) son bisectrices angulares del triángulo rectángulo \(OBD\), por lo que \(P\) es su incentro.
Caso paralelo. \(AC\parallel BD\).
Las dos familias son disjuntas y el código las cuenta por separado.
Si \(P\) es el incentro del triángulo rectángulo de catetos \(b\) y \(d\), entonces
$$P=(i,i),$$
donde \(i\) es el inradio. Como \(P\in AC\), se tiene
$$a=2i.$$
En un triángulo rectángulo,
$$i=\frac{b+d-\sqrt{b^2+d^2}}{2}.$$
Por tanto, \(a\) es entero exactamente cuando \(\sqrt{b^2+d^2}\) es entero. El problema se reduce así a contar triángulos rectángulos enteros con
$$z=\sqrt{b^2+d^2},$$
bajo la cota \(b+d<N\).
El ejemplo \((2,3,4)\) sale de
$$3^2+4^2=5^2,$$
porque
$$a=b+d-z=3+4-5=2,$$
y entonces \(P=(1,1)\).
Definimos
$$u=b-a,\qquad v=d-a.$$
Entonces
$$b=a+u,\qquad d=a+v,\qquad z=a+u+v,$$
y la identidad \(z^2=b^2+d^2\) se convierte en
$$a^2=2uv.$$
Las soluciones primitivas se separan en dos orientaciones:
$$u=g m^2,\qquad v=2g n^2,\qquad a=2gmn,$$
o bien
$$u=2g m^2,\qquad v=g n^2,\qquad a=2gmn,$$
con \(\gcd(m,n)=1\). De aquí resulta
$$b+d=g(m^2+4mn+2n^2)$$
o
$$b+d=g(2m^2+4mn+n^2).$$
Ésos son exactamente los denominadores
$$s_1=m^2+4mn+2n^2,\qquad s_2=2m^2+4mn+n^2$$
del programa. Para cada par primitivo, el número de escalas válidas es
$$\left\lfloor\frac{N-1}{s_1}\right\rfloor \quad \text{o} \quad \left\lfloor\frac{N-1}{s_2}\right\rfloor.$$
En el segundo patrón de similitud se cumple
$$AC\parallel BD,$$
lo cual fuerza
$$d=b.$$
Sea
$$f=b-a>0.$$
El circuncentro de \(\triangle BDP\) es \(X=(b,b)\), así que \(P\) debe estar sobre el círculo
$$ (x-b)^2+(y-b)^2=b^2$$
y también sobre la recta \(AC\):
$$y=a-x.$$
Al sustituir se obtiene
$$x=\frac{a\pm \sqrt{a^2-2f^2}}{2}.$$
Luego existe un punto entero \(P\) si y sólo si
$$Q^2=a^2-2f^2,$$
es decir,
$$Q^2+2f^2=a^2.$$
Un ejemplo pequeño es
$$a=3,\qquad f=2,\qquad b=d=5,$$
porque \(1^2+2\cdot 2^2=3^2\).
Las soluciones primitivas de
$$Q^2+2f^2=a^2$$
se parametrizan mediante enteros coprimos \(p,q\) con \(p\) impar:
$$Q=p^2-2q^2,\qquad f=2pq,\qquad a=p^2+2q^2.$$
Al escalar por \(g\), queda
$$b=d=a+f=g(p^2+2pq+2q^2).$$
Así, la cota \(b+d<N\) se vuelve
$$2g(p^2+2pq+2q^2)<N,$$
de donde la contribución es
$$\left\lfloor\frac{N-1}{2(p^2+2pq+2q^2)}\right\rfloor.$$
Éste es exactamente
$$s_3=2(p^2+2pq+2q^2).$$
Como las familias son disjuntas, el total es
$$T(N)=\sum \left\lfloor\frac{N-1}{s_1}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_2}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_3}\right\rfloor.$$
El código se valida con
$$T(100)=92,\qquad T(100000)=320471.$$
count_family_x_eq_y(...) enumera la familia del incentro usando \(s_1,s_2\). count_family_u_eq_v(...) enumera la familia paralela usando \(s_3\). Para cada conjunto primitivo de parámetros, sólo hay que contar cuántos factores de escala \(g\) siguen cumpliendo \(b+d<N\).
Los bucles sobre \((m,n)\) y \((p,q)\) se cortan tan pronto como el denominador correspondiente alcanza \(N\). Por eso el tiempo real es muy inferior al de explorar todos los tríos \((a,b,d)\). La memoria adicional es \(O(1)\), y los rangos de parámetros independientes pueden paralelizarse.
给定
$$A(a,0),\qquad B(b,0),\qquad C(0,a),\qquad D(0,d),$$
其中 \(0<a<b\) 且 \(0<a<d\)。我们要统计所有整数三元组 \((a,b,d)\)，使得在线段 \(AC\) 上存在整数点 \(P\)，并且三角形 \(ABP\)、\(CDP\)、\(BDP\) 两两相似。计数条件是
$$b+d<N.$$
题目本身已经说明：只有 \(a=c\) 时相似才可能发生。于是 \(AC\) 位于直线
$$x+y=a$$
上。角对应关系最终只剩两种可能：
内心情形。 \(PB\) 与 \(PD\) 是直角三角形 \(OBD\) 的角平分线，因此 \(P\) 是 \(\triangle OBD\) 的内心。
平行情形。 \(AC\parallel BD\)。
这两类互不重叠，代码分别计数。
若 \(P\) 是边长为 \(b,d\) 的直角三角形的内心，则
$$P=(i,i),$$
其中 \(i\) 是内切圆半径。因为 \(P\in AC\)，所以
$$a=2i.$$
直角三角形的内切圆半径满足
$$i=\frac{b+d-\sqrt{b^2+d^2}}{2}.$$
因此 \(a\) 为整数，当且仅当 \(\sqrt{b^2+d^2}\) 为整数。于是这一类完全等价于统计
$$z=\sqrt{b^2+d^2}$$
也是整数的勾股三元组，并满足 \(b+d<N\)。
题目给出的例子 \((2,3,4)\) 就来自
$$3^2+4^2=5^2,$$
因为
$$a=b+d-z=3+4-5=2,$$
于是 \(P=(1,1)\)。
定义
$$u=b-a,\qquad v=d-a.$$
则有
$$b=a+u,\qquad d=a+v,\qquad z=a+u+v.$$
把 \(z^2=b^2+d^2\) 代入可得
$$a^2=2uv.$$
原始解分成两个方向：
$$u=g m^2,\qquad v=2g n^2,\qquad a=2gmn,$$
或者
$$u=2g m^2,\qquad v=g n^2,\qquad a=2gmn,$$
其中 \(\gcd(m,n)=1\)。于是
$$b+d=g(m^2+4mn+2n^2)$$
或
$$b+d=g(2m^2+4mn+n^2).$$
这正是程序中的
$$s_1=m^2+4mn+2n^2,\qquad s_2=2m^2+4mn+n^2.$$
因此每个原始参数对的贡献就是
$$\left\lfloor\frac{N-1}{s_1}\right\rfloor \quad \text{或} \quad \left\lfloor\frac{N-1}{s_2}\right\rfloor.$$
在第二种相似配对里有
$$AC\parallel BD,$$
于是斜率立刻给出
$$d=b.$$
再设
$$f=b-a>0.$$
\(\triangle BDP\) 的外心是 \(X=(b,b)\)，因此 \(P\) 必须落在圆
$$ (x-b)^2+(y-b)^2=b^2$$
上，同时又在直线
$$y=a-x$$
上。代入可得
$$x=\frac{a\pm \sqrt{a^2-2f^2}}{2}.$$
于是存在整数点 \(P\) 当且仅当
$$Q^2=a^2-2f^2,$$
也就是
$$Q^2+2f^2=a^2.$$
一个小例子是
$$a=3,\qquad f=2,\qquad b=d=5,$$
因为 \(1^2+2\cdot 2^2=3^2\)。
方程
$$Q^2+2f^2=a^2$$
的原始解可参数化为互素整数 \(p,q\)，其中 \(p\) 为奇数：
$$Q=p^2-2q^2,\qquad f=2pq,\qquad a=p^2+2q^2.$$
再乘上缩放因子 \(g\) 以后，得到
$$b=d=a+f=g(p^2+2pq+2q^2).$$
因此约束 \(b+d<N\) 变成
$$2g(p^2+2pq+2q^2)<N,$$
所以贡献数就是
$$\left\lfloor\frac{N-1}{2(p^2+2pq+2q^2)}\right\rfloor.$$
这正是程序中的
$$s_3=2(p^2+2pq+2q^2).$$
两类互不相交，所以总数为
$$T(N)=\sum \left\lfloor\frac{N-1}{s_1}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_2}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_3}\right\rfloor.$$
代码用公开检查点
$$T(100)=92,\qquad T(100000)=320471$$
来验证正确性。
count_family_x_eq_y(...) 负责内心家族，对应 \(s_1,s_2\)。count_family_u_eq_v(...) 负责平行家族，对应 \(s_3\)。对每个原始参数对，只需计算有多少个缩放因子 \(g\) 仍满足 \(b+d<N\)。
当相应分母达到 \(N\) 时，\((m,n)\) 与 \((p,q)\) 的循环都会提前停止。因此实际运行远优于对全部 \((a,b,d)\) 三元组做暴力扫描。除少量计数器外，额外空间为 \(O(1)\)，并且独立参数区间可以并行处理。
Даны точки
$$A(a,0),\qquad B(b,0),\qquad C(0,a),\qquad D(0,d),$$
где \(0<a<b\) и \(0<a<d\). Нужно подсчитать все целочисленные тройки \((a,b,d)\), для которых на прямой \(AC\) существует целочисленная точка \(P\), делающая треугольники \(ABP\), \(CDP\) и \(BDP\) подобными. Ограничение таково:
$$b+d<N.$$
В условии уже сказано, что подобие возможно только при \(a=c\). Значит, отрезок \(AC\) лежит на прямой
$$x+y=a.$$
Разбор углов оставляет ровно две возможности:
Случай инцентра. Прямые \(PB\) и \(PD\) оказываются биссектрисами в прямоугольном треугольнике \(OBD\), значит, \(P\) — инцентр \(\triangle OBD\).
Параллельный случай. \(AC\parallel BD\).
Эти семейства не пересекаются, поэтому код считает их отдельно.
Если \(P\) — инцентр прямоугольного треугольника с катетами \(b\) и \(d\), то
$$P=(i,i),$$
где \(i\) — радиус вписанной окружности. Так как \(P\in AC\), имеем
$$a=2i.$$
Для прямоугольного треугольника
$$i=\frac{b+d-\sqrt{b^2+d^2}}{2}.$$
Следовательно, \(a\) целое тогда и только тогда, когда \(\sqrt{b^2+d^2}\) целое. Итак, задача в этом случае сводится к поиску пифагоровых троек с
$$z=\sqrt{b^2+d^2}$$
и ограничением \(b+d<N\).
Пример \((2,3,4)\) получается из
$$3^2+4^2=5^2,$$
потому что
$$a=b+d-z=3+4-5=2,$$
а значит \(P=(1,1)\).
Обозначим
$$u=b-a,\qquad v=d-a.$$
Тогда
$$b=a+u,\qquad d=a+v,\qquad z=a+u+v,$$
и из \(z^2=b^2+d^2\) немедленно следует
$$a^2=2uv.$$
Примитивные решения распадаются на две ориентации:
$$u=g m^2,\qquad v=2g n^2,\qquad a=2gmn,$$
или
$$u=2g m^2,\qquad v=g n^2,\qquad a=2gmn,$$
при \(\gcd(m,n)=1\). Отсюда получаем
$$b+d=g(m^2+4mn+2n^2)$$
или
$$b+d=g(2m^2+4mn+n^2).$$
Это и есть знаменатели программы
$$s_1=m^2+4mn+2n^2,\qquad s_2=2m^2+4mn+n^2.$$
Для каждого примитивного \((m,n)\) число допустимых масштабов равно
$$\left\lfloor\frac{N-1}{s_1}\right\rfloor \quad \text{или} \quad \left\lfloor\frac{N-1}{s_2}\right\rfloor.$$
Во втором типе подобия выполняется
$$AC\parallel BD,$$
что сразу даёт
$$d=b.$$
Положим
$$f=b-a>0.$$
Тогда центр описанной окружности треугольника \(BDP\) равен \(X=(b,b)\), значит, \(P\) должен лежать на окружности
$$ (x-b)^2+(y-b)^2=b^2$$
и одновременно на прямой
$$y=a-x.$$
Подстановка даёт
$$x=\frac{a\pm \sqrt{a^2-2f^2}}{2}.$$
Значит, целочисленная точка \(P\) существует тогда и только тогда, когда
$$Q^2=a^2-2f^2,$$
то есть
$$Q^2+2f^2=a^2.$$
Малый пример:
$$a=3,\qquad f=2,\qquad b=d=5,$$
поскольку \(1^2+2\cdot 2^2=3^2\).
Примитивные решения уравнения
$$Q^2+2f^2=a^2$$
параметризуются взаимно простыми \(p,q\), причём \(p\) нечётно:
$$Q=p^2-2q^2,\qquad f=2pq,\qquad a=p^2+2q^2.$$
После масштабирования на \(g\) получаем
$$b=d=a+f=g(p^2+2pq+2q^2).$$
Тогда ограничение \(b+d<N\) превращается в
$$2g(p^2+2pq+2q^2)<N,$$
а число масштабов равно
$$\left\lfloor\frac{N-1}{2(p^2+2pq+2q^2)}\right\rfloor.$$
Именно здесь появляется
$$s_3=2(p^2+2pq+2q^2).$$
Так как семейства не пересекаются,
$$T(N)=\sum \left\lfloor\frac{N-1}{s_1}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_2}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_3}\right\rfloor.$$
Код проверяется на значениях
$$T(100)=92,\qquad T(100000)=320471.$$
count_family_x_eq_y(...) перечисляет семейство инцентра через формы \(s_1,s_2\). count_family_u_eq_v(...) перечисляет параллельное семейство через \(s_3\). Для каждого примитивного набора параметров остаётся лишь посчитать, сколько коэффициентов масштаба \(g\) удовлетворяют неравенству \(b+d<N\).
Циклы по \((m,n)\) и \((p,q)\) обрываются сразу, как только соответствующий знаменатель достигает \(N\). Поэтому реальное время работы намного меньше, чем у полного перебора всех троек \((a,b,d)\). Память остаётся \(O(1)\), а независимые диапазоны параметров можно распараллелить.
لدينا النقاط
$$A(a,0),\qquad B(b,0),\qquad C(0,a),\qquad D(0,d),$$
مع \(0<a<b\) و\(0<a<d\). نريد عدّ كل الثلاثيات الصحيحة \((a,b,d)\) التي يوجد معها نقطة صحيحة \(P\) على \(AC\) تجعل المثلثات \(ABP\) و\(CDP\) و\(BDP\) كلها متشابهة. شرط العد هو
$$b+d<N.$$
المسألة نفسها تذكر أن التشابه لا يمكن أن يحدث إلا إذا كان \(a=c\). عندئذ يكون الخط \(AC\) هو
$$x+y=a.$$
ومن مطابقة الزوايا لا يبقى إلا احتمالان:
حالة المركز الداخلي. يكون \(PB\) و\(PD\) منصفَي زاويتين في المثلث القائم \(OBD\)، ولذلك تكون \(P\) هي المركز الداخلي للمثلث \(\triangle OBD\).
حالة التوازي. يكون \(AC\parallel BD\).
هاتان العائلتان منفصلتان، ولذلك يحسبهما الكود على حدة.
إذا كانت \(P\) هي المركز الداخلي لمثلث قائم ضلعا قائمته \(b\) و\(d\)، فإن
$$P=(i,i),$$
حيث \(i\) نصف قطر الدائرة الداخلية. وبما أن \(P\in AC\)، فإن
$$a=2i.$$
وفي المثلث القائم لدينا
$$i=\frac{b+d-\sqrt{b^2+d^2}}{2}.$$
إذًا يكون \(a\) عددًا صحيحًا بالضبط عندما تكون
$$z=\sqrt{b^2+d^2}$$
عددًا صحيحًا. وهكذا تتحول هذه العائلة إلى عدّ ثلاثيات فيثاغورس مع القيد \(b+d<N\).
والمثال \((2,3,4)\) يأتي من
$$3^2+4^2=5^2,$$
لأن
$$a=b+d-z=3+4-5=2,$$
وعندئذ \(P=(1,1)\).
لنكتب
$$u=b-a,\qquad v=d-a.$$
عندها
$$b=a+u,\qquad d=a+v,\qquad z=a+u+v.$$
ومن المعادلة \(z^2=b^2+d^2\) نحصل مباشرة على
$$a^2=2uv.$$
الحلول الأولية تنقسم إلى اتجاهين:
$$u=g m^2,\qquad v=2g n^2,\qquad a=2gmn,$$
أو
$$u=2g m^2,\qquad v=g n^2,\qquad a=2gmn,$$
مع \(\gcd(m,n)=1\). ومن هنا يصبح
$$b+d=g(m^2+4mn+2n^2)$$
أو
$$b+d=g(2m^2+4mn+n^2).$$
وهذه بالضبط هي المقادير
$$s_1=m^2+4mn+2n^2,\qquad s_2=2m^2+4mn+n^2$$
المستخدمة في الكود. ومن ثم فإن عدد عوامل التحجيم الممكنة لكل زوج أولي هو
$$\left\lfloor\frac{N-1}{s_1}\right\rfloor \quad \text{أو} \quad \left\lfloor\frac{N-1}{s_2}\right\rfloor.$$
في النمط الثاني من التشابه لدينا
$$AC\parallel BD,$$
ومن الميل ينتج فورًا
$$d=b.$$
ضع
$$f=b-a>0.$$
عندئذ يكون مركز الدائرة المحيطة بالمثلث \(BDP\) هو \(X=(b,b)\)، ولذلك يجب أن تقع \(P\) على الدائرة
$$ (x-b)^2+(y-b)^2=b^2$$
وفي الوقت نفسه على الخط
$$y=a-x.$$
بالتعويض نحصل على
$$x=\frac{a\pm \sqrt{a^2-2f^2}}{2}.$$
إذن وجود نقطة صحيحة \(P\) يكافئ تمامًا أن يكون
$$Q^2=a^2-2f^2,$$
أي
$$Q^2+2f^2=a^2.$$
ومثال صغير هو
$$a=3,\qquad f=2,\qquad b=d=5,$$
لأن \(1^2+2\cdot 2^2=3^2\).
الحلول الأولية للمعادلة
$$Q^2+2f^2=a^2$$
يمكن برمجتها باستخدام عددين متباينين أوليًا \(p,q\) مع \(p\) فردي:
$$Q=p^2-2q^2,\qquad f=2pq,\qquad a=p^2+2q^2.$$
وبعد التحجيم بعامل \(g\) نحصل على
$$b=d=a+f=g(p^2+2pq+2q^2).$$
لذلك يصبح القيد \(b+d<N\) هو
$$2g(p^2+2pq+2q^2)<N,$$
ومن ثم تكون مساهمة هذا الزوج الأولي
$$\left\lfloor\frac{N-1}{2(p^2+2pq+2q^2)}\right\rfloor.$$
وهذا هو بالضبط
$$s_3=2(p^2+2pq+2q^2).$$
بما أن العائلتين منفصلتان، فإن العدد الكلي هو
$$T(N)=\sum \left\lfloor\frac{N-1}{s_1}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_2}\right\rfloor+\sum \left\lfloor\frac{N-1}{s_3}\right\rfloor.$$
ويتحقق الكود من نفسه باستخدام
$$T(100)=92,\qquad T(100000)=320471.$$
الدالة count_family_x_eq_y(...) تعدّ عائلة المركز الداخلي باستخدام \(s_1,s_2\)، بينما count_family_u_eq_v(...) تعدّ عائلة التوازي باستخدام \(s_3\). ولكل زوج أولي من المعاملات، لا يبقى إلا حساب عدد عوامل التحجيم \(g\) التي ما زالت تحقق الشرط \(b+d<N\).
تتوقف حلقات \((m,n)\) و\((p,q)\) مبكرًا بمجرد أن يصل المقام الموافق إلى \(N\). لذلك فالزمن العملي أقل بكثير من فحص جميع الثلاثيات \((a,b,d)\) مباشرة. أما الذاكرة الإضافية فهي \(O(1)\)، ويمكن توزيع مجالات المعاملات المستقلة على خيوط أو عمليات متعددة.