Let a triangle with integer sides \(a,b,c\) have area \(A\) and perimeter \(P=a+b+c\). We want all triangles for which
$$\frac{A}{P}=k$$
is an integer. For each \(k\), let \(p(k)\) be the sum of the corresponding perimeters. The program computes
$$\sum_{k=1}^{1000} p(k),$$
but the final numeric answer is intentionally omitted here.
1) Replace side lengths by semiperimeter gaps. Let
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
Then \(x,y,z\) are positive integers, and conversely
$$a=y+z,\qquad b=z+x,\qquad c=x+y,\qquad s=x+y+z.$$
So every integer triangle corresponds to one positive integer triple \((x,y,z)\). If we sort the sides as \(a \ge b \ge c\), then \(x \le y \le z\), which is exactly the ordering used in the code to avoid duplicates.
2) Heron's formula gives a Diophantine equation. Heron's formula is
$$A^2=s(s-a)(s-b)(s-c)=sxyz.$$
The condition \(A/P=k\) means
$$A=k(a+b+c)=2ks.$$
Squaring and cancelling one factor of \(s\) gives
$$xyz=4k^2s=4k^2(x+y+z).$$
If we define
$$n=(2k)^2=4k^2,$$
the triangle problem becomes the pure integer equation
$$xyz=n(x+y+z),\qquad x \le y \le z.$$
The perimeter of the recovered triangle is
$$P=2s=2(x+y+z),$$
which is why the program adds \(2(x+y+z)\) for each valid triple.
3) Why this is a bijection. Starting from a triangle, we get one positive triple \((x,y,z)\). Starting from a positive solution of \(xyz=n(x+y+z)\), the inverse map
$$a=y+z,\qquad b=z+x,\qquad c=x+y$$
automatically satisfies the triangle inequalities because \(x,y,z>0\). So no valid triangle is lost and no extra object is counted.
4) Solve one variable in terms of the other two. Rearranging the main equation gives
$$z=\frac{n(x+y)}{xy-n}.$$
Therefore \(xy>n\) is necessary, and once \(x\) and \(y\) are fixed there is at most one possible \(z\). The brute-force checkpoint routine in the code uses exactly this formula.
5) The key factorization for the fast algorithm. For the production algorithm, fixing \(k\) and \(x\) is enough. Starting from
$$xyz=n(x+y+z),$$
one checks that
$$(xy-n)(xz-n)=x^2yz-nx(y+z)+n^2=n(x^2+n).$$
Define
$$m=x^2+n,\qquad M=nm,\qquad u=xy-n,\qquad v=xz-n.$$
Then
$$uv=M,$$
and the original variables are recovered by
$$y=\frac{u+n}{x},\qquad z=\frac{v+n}{x}.$$
So for fixed \((k,x)\), every divisor pair \((u,v)\) of \(M\) gives a candidate, and the only remaining tests are:
$$x \mid (u+n),\qquad x \mid (v+n),\qquad y \ge x,\qquad z \ge y.$$
Because \(y \le z\) is equivalent to \(u \le v\), the code only needs divisor pairs with \(u^2 \le M\).
6) Why the bound \(x \le \sqrt{3n}\) is correct. For fixed \(x\), the function
$$f(y,z)=\frac{xyz}{x+y+z}$$
is increasing in both \(y\) and \(z\) on positive inputs. Since \(y,z \ge x\), the smallest possible value is at \(y=z=x\), so
$$n=f(y,z)\ge \frac{x^3}{3x}=\frac{x^2}{3}.$$
Hence
$$x \le \sqrt{3n}.$$
This is exactly the outer bound used by both the fast solver and the brute-force verifier.
7) The brute-force upper bound for \(y\). In the verifier, the extra condition \(z \ge y\) and the formula for \(z\) imply
$$\frac{n(x+y)}{xy-n}\ge y,$$
which rearranges to
$$xy^2-2ny-nx \le 0.$$
Solving this quadratic inequality yields
$$y \le \frac{n+\sqrt{n(n+x^2)}}{x},$$
which is the exact bound used in the checkpoint routine.
Example 1: \(k=1\). Then \(n=4\). Take \(x=2\). We get
$$M=n(x^2+n)=4(4+4)=32.$$
Choose the divisor pair \((u,v)=(4,8)\). Then
$$y=\frac{4+4}{2}=4,\qquad z=\frac{8+4}{2}=6.$$
So \((x,y,z)=(2,4,6)\), which gives the triangle
$$a=y+z=10,\qquad b=z+x=8,\qquad c=x+y=6.$$
Its semiperimeter is \(s=12\), its area is \(\sqrt{12\cdot 2\cdot 4\cdot 6}=24\), and its perimeter is \(24\). Therefore \(A/P=1\), exactly as required.
Example 2: \(k=2\). Then \(n=16\). The triple \((x,y,z)=(6,7,8)\) satisfies
$$6\cdot 7\cdot 8 = 16(6+7+8)=336.$$
The corresponding sides are
$$a=15,\qquad b=14,\qquad c=13,$$
so we recover the classical \(13\)-\(14\)-\(15\) triangle. Its perimeter is \(42\), its area is \(84\), and \(84/42=2\).
The code first chooses \(k\), hence \(n=(2k)^2\). It then loops over all admissible \(x\), factors
$$M=n(x^2+n),$$
generates all divisors of \(M\), keeps only \(u\) with \(u^2 \le M\), reconstructs \(y\) and \(z\), and accepts exactly the candidates that satisfy the divisibility and ordering constraints. By the derivation above, every accepted candidate is a valid triangle, and every valid triangle appears exactly once.
The file contains two explicit checkpoints. The fast method and the brute-force method both give
$$\sum_{k \le 5} p(k)=140098,\qquad \sum_{k \le 10} p(k)=3781786.$$
For complexity, the expensive part is factoring \(m=x^2+n\) and enumerating divisors of \(M=n(x^2+n)\). The SPF sieve is built up to
$$4(2K)^2,$$
because \(x^2 \le 3n\) implies \(m=x^2+n \le 4n\). In practice this makes each factorization cheap, and divisor enumeration is far smaller than brute forcing all \((y,z)\).
Gegeben sei ein Dreieck mit ganzzahligen Seiten \(a,b,c\), Fläche \(A\) und Umfang \(P=a+b+c\). Gesucht sind alle Dreiecke, für die
$$\frac{A}{P}=k$$
eine ganze Zahl ist. Für jedes \(k\) bezeichne \(p(k)\) die Summe der zugehörigen Umfänge. Das Programm berechnet
$$\sum_{k=1}^{1000} p(k),$$
der endgültige Zahlenwert wird hier aber bewusst nicht ausgeschrieben.
1) Seiten durch Halbumfangsdifferenzen ersetzen. Setze
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
Dann sind \(x,y,z\) positive ganze Zahlen und umgekehrt gilt
$$a=y+z,\qquad b=z+x,\qquad c=x+y,\qquad s=x+y+z.$$
Damit entspricht jedes ganzzahlige Dreieck genau einem positiven Tripel \((x,y,z)\). Sortiert man die Seiten als \(a \ge b \ge c\), so folgt \(x \le y \le z\), also genau die Reihenfolge des Codes.
2) Heron liefert eine diophantische Gleichung. Nach Heron gilt
$$A^2=s(s-a)(s-b)(s-c)=sxyz.$$
Die Bedingung \(A/P=k\) bedeutet
$$A=k(a+b+c)=2ks.$$
Nach dem Quadrieren und Kürzen eines Faktors \(s\) bleibt
$$xyz=4k^2s=4k^2(x+y+z).$$
Mit
$$n=(2k)^2=4k^2$$
wird daraus die reine Ganzzahligkeitsaufgabe
$$xyz=n(x+y+z),\qquad x \le y \le z.$$
Der Umfang des rekonstruierten Dreiecks ist
$$P=2s=2(x+y+z),$$
deshalb summiert das Programm für jedes gültige Tripel genau \(2(x+y+z)\).
3) Warum dies eine Bijektion ist. Aus jedem Dreieck entsteht genau ein positives Tripel \((x,y,z)\). Umgekehrt liefert jede positive Lösung von \(xyz=n(x+y+z)\) über
$$a=y+z,\qquad b=z+x,\qquad c=x+y$$
wieder ein gültiges Dreieck, denn \(x,y,z>0\) erzwingen automatisch die Dreiecksungleichungen. Es geht also nichts verloren und es wird nichts Falsches mitgezählt.
4) Eine Variable explizit lösen. Aus der Hauptgleichung folgt
$$z=\frac{n(x+y)}{xy-n}.$$
Also ist \(xy>n\) notwendig, und für feste \(x,y\) gibt es höchstens ein mögliches \(z\). Genau diese Formel benutzt der Brute-Force-Checkpoint.
5) Der entscheidende Faktorisierungstrick. Für den schnellen Algorithmus werden \(k\) und \(x\) fixiert. Dann gilt
$$(xy-n)(xz-n)=x^2yz-nx(y+z)+n^2=n(x^2+n).$$
Definiert man
$$m=x^2+n,\qquad M=nm,\qquad u=xy-n,\qquad v=xz-n,$$
so erhält man
$$uv=M,$$
und die Rückrechnung
$$y=\frac{u+n}{x},\qquad z=\frac{v+n}{x}.$$
Für festes \((k,x)\) muss man also nur Teilerpaare \((u,v)\) von \(M\) durchlaufen und anschließend die Bedingungen
$$x \mid (u+n),\qquad x \mid (v+n),\qquad y \ge x,\qquad z \ge y$$
prüfen. Aus \(y \le z\) folgt äquivalent \(u \le v\), daher reichen Teiler mit \(u^2 \le M\).
6) Warum \(x \le \sqrt{3n}\) gilt. Für festes \(x\) ist
$$f(y,z)=\frac{xyz}{x+y+z}$$
in beiden Variablen \(y\) und \(z\) streng wachsend. Wegen \(y,z \ge x\) ist der kleinste mögliche Wert also bei \(y=z=x\), also
$$n=f(y,z)\ge \frac{x^3}{3x}=\frac{x^2}{3}.$$
Daraus folgt
$$x \le \sqrt{3n}.$$
7) Obere Schranke für \(y\) im Brute-Force-Test. Aus \(z \ge y\) und der Formel für \(z\) folgt
$$\frac{n(x+y)}{xy-n}\ge y,$$
also
$$xy^2-2ny-nx \le 0.$$
Die quadratische Ungleichung liefert
$$y \le \frac{n+\sqrt{n(n+x^2)}}{x},$$
und genau diese Grenze steht auch im Verifikationscode.
Beispiel 1: \(k=1\). Dann ist \(n=4\). Für \(x=2\) erhält man
$$M=n(x^2+n)=4(4+4)=32.$$
Wählt man das Teilerpaar \((u,v)=(4,8)\), dann
$$y=\frac{4+4}{2}=4,\qquad z=\frac{8+4}{2}=6.$$
Also \((x,y,z)=(2,4,6)\), und das zugehörige Dreieck hat Seiten
$$a=10,\qquad b=8,\qquad c=6.$$
Der Halbumfang ist \(12\), die Fläche \(\sqrt{12\cdot 2\cdot 4\cdot 6}=24\), der Umfang ebenfalls \(24\). Also ist \(A/P=1\).
Beispiel 2: \(k=2\). Dann ist \(n=16\). Das Tripel \((x,y,z)=(6,7,8)\) erfüllt
$$6\cdot 7\cdot 8 = 16(6+7+8)=336.$$
Daraus folgen die Seiten
$$a=15,\qquad b=14,\qquad c=13,$$
also das klassische \(13\)-\(14\)-\(15\)-Dreieck mit Umfang \(42\) und Fläche \(84\). Damit ist \(84/42=2\).
Der Code wählt zuerst \(k\), also \(n=(2k)^2\), läuft dann über alle zulässigen \(x\), faktorisiert
$$M=n(x^2+n),$$
erzeugt alle Teiler, behält nur \(u\) mit \(u^2 \le M\), rekonstruiert daraus \(y\) und \(z\) und akzeptiert genau die Kandidaten, die die Teilbarkeits- und Ordnungsbedingungen erfüllen. Wegen der Herleitung oben entspricht jeder akzeptierte Kandidat genau einem Dreieck, und jedes gültige Dreieck taucht genau einmal auf.
Im Quelltext stehen zwei explizite Prüfpunkte. Schneller Algorithmus und Brute Force liefern beide
$$\sum_{k \le 5} p(k)=140098,\qquad \sum_{k \le 10} p(k)=3781786.$$
Der Hauptaufwand entsteht durch die Faktorisierung von \(m=x^2+n\) und die Teilererzeugung für \(M=n(x^2+n)\). Das SPF-Sieb wird bis
$$4(2K)^2$$
aufgebaut, weil aus \(x^2 \le 3n\) sofort \(m=x^2+n \le 4n\) folgt. Damit bleiben die Faktorisierungen billig und die Teilersuche ist viel kleiner als eine direkte Suche über alle \((y,z)\).
Tam kenarlı bir üçgenin kenarları \(a,b,c\), alanı \(A\), çevresi \(P=a+b+c\) olsun. Aradığımız üçgenler
$$\frac{A}{P}=k$$
oranının tam sayı olduğu üçgenlerdir. Her \(k\) için ilgili çevrelerin toplamı \(p(k)\) ile gösterilir. Programın hedefi
$$\sum_{k=1}^{1000} p(k)$$
değerini hesaplamaktır; nihai sayı burada bilinçli olarak yazılmıyor.
1) Kenarları semiperimetre farklarına çevir. Tanımlayalım:
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
Burada \(x,y,z\) pozitif tam sayılardır. Tersi yönde ise
$$a=y+z,\qquad b=z+x,\qquad c=x+y,\qquad s=x+y+z$$
olur. Yani her tam kenarlı üçgen ile bir pozitif \((x,y,z)\) üçlüsü arasında birebir eşleme vardır. Kenarları \(a \ge b \ge c\) diye sıralarsak \(x \le y \le z\) elde ederiz; kod da tekrar saymamak için tam bu sıralamayı kullanır.
2) Heron formülü problemi Diofant denkleme indirger. Heron formülü
$$A^2=s(s-a)(s-b)(s-c)=sxyz$$
şeklindedir. Şartımız \(A/P=k\) olduğuna göre
$$A=k(a+b+c)=2ks.$$
Karesini alıp bir \(s\) çarpanını sadeleştirince
$$xyz=4k^2s=4k^2(x+y+z)$$
çıkar. Şimdi
$$n=(2k)^2=4k^2$$
dersek problem şu tam sayı denklemine dönüşür:
$$xyz=n(x+y+z),\qquad x \le y \le z.$$
Bulunan üçgenin çevresi ise
$$P=2s=2(x+y+z)$$
olduğu için kod her geçerli üçlüye \(2(x+y+z)\) ekler.
3) Neden bu dönüşüm tam ve doğru? Her üçgenden tek bir pozitif \((x,y,z)\) gelir. Ters yönde de, pozitif bir çözümden
$$a=y+z,\qquad b=z+x,\qquad c=x+y$$
formülüyle yeniden bir üçgen elde edilir; çünkü \(x,y,z>0\) olması üçgen eşitsizliklerini otomatik sağlar. Dolayısıyla ne çözüm kaybedilir ne de sahte bir nesne sayılır.
4) Bir değişkeni açıkça çöz. Ana denklemden
$$z=\frac{n(x+y)}{xy-n}$$
elde edilir. Demek ki \(xy>n\) gerekli, ayrıca sabit \(x\) ve \(y\) için en fazla bir tane \(z\) vardır. Koddaki brute-force checkpoint tam olarak bu formülü kullanır.
5) Hızlı algoritmanın temel çarpanlara ayırma numarası. Hızlı kısımda \(k\) ve \(x\) sabitlenir. O zaman
$$(xy-n)(xz-n)=x^2yz-nx(y+z)+n^2=n(x^2+n)$$
olur. Şimdi
$$m=x^2+n,\qquad M=nm,\qquad u=xy-n,\qquad v=xz-n$$
tanımlarını yapalım. O zaman
$$uv=M$$
ve geri kurulum
$$y=\frac{u+n}{x},\qquad z=\frac{v+n}{x}$$
şeklindedir. Yani sabit \((k,x)\) için yapılacak iş, \(M\)'nin bölen çiftlerini dolaşıp sadece şu koşulları geçenleri kabul etmektir:
$$x \mid (u+n),\qquad x \mid (v+n),\qquad y \ge x,\qquad z \ge y.$$
\(y \le z\) şartı \(u \le v\) ile eşdeğer olduğu için kod yalnızca \(u^2 \le M\) yarısını dolaşır.
6) Neden \(x \le \sqrt{3n}\)? Sabit \(x\) için
$$f(y,z)=\frac{xyz}{x+y+z}$$
fonksiyonu hem \(y\) hem \(z\) yönünde artandır. \(y,z \ge x\) olduğundan en küçük değer \(y=z=x\) noktasında alınır:
$$n=f(y,z)\ge \frac{x^3}{3x}=\frac{x^2}{3}.$$
Buradan
$$x \le \sqrt{3n}$$
gelir. Kodun dış sınırı tam budur.
7) Checkpoint kodundaki \(y\) üst sınırı. \(z \ge y\) ve \(z\) formülü birlikte
$$\frac{n(x+y)}{xy-n}\ge y$$
eşitsizliğini verir. Düzenlersek
$$xy^2-2ny-nx \le 0$$
elde ederiz. Bu kuadratik eşitsizliğin çözümü
$$y \le \frac{n+\sqrt{n(n+x^2)}}{x}$$
olur; doğrulama rutinindeki sınır tam olarak budur.
Örnek 1: \(k=1\). Bu durumda \(n=4\). \(x=2\) seçelim:
$$M=n(x^2+n)=4(4+4)=32.$$
\((u,v)=(4,8)\) bölen çifti alınırsa
$$y=\frac{4+4}{2}=4,\qquad z=\frac{8+4}{2}=6$$
çıkar. Yani \((x,y,z)=(2,4,6)\). Buna karşılık gelen üçgen
$$a=10,\qquad b=8,\qquad c=6$$
kenarlarına sahiptir. Semiperimetre \(12\), alan \(\sqrt{12\cdot 2\cdot 4\cdot 6}=24\), çevre de \(24\) olduğundan gerçekten \(A/P=1\).
Örnek 2: \(k=2\). Bu kez \(n=16\). \((x,y,z)=(6,7,8)\) üçlüsü
$$6\cdot 7\cdot 8 = 16(6+7+8)=336$$
eşitliğini sağlar. Karşılık gelen kenarlar
$$a=15,\qquad b=14,\qquad c=13$$
olur. Böylece klasik \(13\)-\(14\)-\(15\) üçgenine ulaşırız; çevresi \(42\), alanı \(84\) ve oran \(84/42=2\).
Kod önce \(k\)'yı seçip \(n=(2k)^2\) kurar. Sonra tüm izinli \(x\) değerlerini gezer,
$$M=n(x^2+n)$$
sayısını çarpanlara ayırır, bölenleri üretir, yalnızca \(u^2 \le M\) olan yarıyı dolaşır, \(y\) ve \(z\)'yi geri kurar ve sadece bölünebilme ve sıralama koşullarını geçen adayları kabul eder. Yukarıdaki türetim yüzünden kabul edilen her aday gerçek bir üçgendir ve her geçerli üçgen tam bir kez üretilir.
Dosyada iki açık checkpoint vardır. Hızlı yöntem ve brute-force yöntem aynı şekilde
$$\sum_{k \le 5} p(k)=140098,\qquad \sum_{k \le 10} p(k)=3781786$$
sonucunu verir. Karmaşıklık açısından pahalı kısım, \(m=x^2+n\)'nin asal çarpanlara ayrılması ve \(M=n(x^2+n)\)'nin bölenlerinin üretilmesidir. SPF dizisi
$$4(2K)^2$$
sınırına kadar hazırlanır; çünkü \(x^2 \le 3n\) olduğundan \(m=x^2+n \le 4n\) olur. Bu yüzden pratikte faktorizasyon ucuz, bölen gezisi de doğrudan \((y,z)\) taramasından çok daha küçüktür.
Sea un triángulo de lados enteros \(a,b,c\), área \(A\) y perímetro \(P=a+b+c\). Buscamos los triángulos para los que
$$\frac{A}{P}=k$$
es un entero. Para cada \(k\), \(p(k)\) denota la suma de los perímetros correspondientes. El programa calcula
$$\sum_{k=1}^{1000} p(k),$$
pero aquí se omite a propósito el valor final.
1) Cambiar los lados por diferencias respecto al semiperímetro. Definimos
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
Entonces \(x,y,z\) son enteros positivos y, en sentido inverso,
$$a=y+z,\qquad b=z+x,\qquad c=x+y,\qquad s=x+y+z.$$
Así, cada triángulo entero corresponde a un único triple positivo \((x,y,z)\). Si ordenamos \(a \ge b \ge c\), obtenemos \(x \le y \le z\), que es justo la convención del código.
2) La fórmula de Herón produce una ecuación diofántica. Herón dice que
$$A^2=s(s-a)(s-b)(s-c)=sxyz.$$
La condición \(A/P=k\) equivale a
$$A=k(a+b+c)=2ks.$$
Al cuadrar y cancelar un factor \(s\), queda
$$xyz=4k^2s=4k^2(x+y+z).$$
Si ponemos
$$n=(2k)^2=4k^2,$$
el problema se convierte en
$$xyz=n(x+y+z),\qquad x \le y \le z.$$
El perímetro del triángulo reconstruido es
$$P=2s=2(x+y+z),$$
por eso el programa añade \(2(x+y+z)\) por cada solución válida.
3) Por qué esto es una biyección. De cada triángulo obtenemos un triple positivo \((x,y,z)\). Y de cada solución positiva de \(xyz=n(x+y+z)\), la fórmula inversa
$$a=y+z,\qquad b=z+x,\qquad c=x+y$$
produce automáticamente un triángulo válido, porque \(x,y,z>0\) fuerzan las desigualdades triangulares. No se pierde ninguna solución ni se cuentan objetos falsos.
4) Resolver una variable. De la ecuación principal se obtiene
$$z=\frac{n(x+y)}{xy-n}.$$
Así, \(xy>n\) es necesario, y una vez fijados \(x\) e \(y\), existe a lo sumo un \(z\). La rutina de comprobación por fuerza bruta usa exactamente esta fórmula.
5) La factorización clave del algoritmo rápido. Fijamos \(k\) y \(x\). Entonces
$$(xy-n)(xz-n)=x^2yz-nx(y+z)+n^2=n(x^2+n).$$
Definimos
$$m=x^2+n,\qquad M=nm,\qquad u=xy-n,\qquad v=xz-n,$$
y obtenemos
$$uv=M,$$
con reconstrucción
$$y=\frac{u+n}{x},\qquad z=\frac{v+n}{x}.$$
Así, para cada \((k,x)\) basta recorrer los pares de divisores \((u,v)\) de \(M\) y verificar
$$x \mid (u+n),\qquad x \mid (v+n),\qquad y \ge x,\qquad z \ge y.$$
La condición \(y \le z\) equivale a \(u \le v\), así que solo hace falta la mitad con \(u^2 \le M\).
6) Por qué \(x \le \sqrt{3n}\). Para \(x\) fijo, la función
$$f(y,z)=\frac{xyz}{x+y+z}$$
crece en \(y\) y en \(z\). Como \(y,z \ge x\), el valor mínimo ocurre en \(y=z=x\), y por tanto
$$n=f(y,z)\ge \frac{x^3}{3x}=\frac{x^2}{3}.$$
Luego
$$x \le \sqrt{3n}.$$
7) Cota superior de \(y\) en la verificación. De \(z \ge y\) y la expresión para \(z\) se deduce
$$\frac{n(x+y)}{xy-n}\ge y,$$
que se reordena como
$$xy^2-2ny-nx \le 0.$$
Resolver esta desigualdad cuadrática da
$$y \le \frac{n+\sqrt{n(n+x^2)}}{x},$$
que es exactamente la cota usada por el código de comprobación.
Ejemplo 1: \(k=1\). Entonces \(n=4\). Si tomamos \(x=2\),
$$M=n(x^2+n)=4(4+4)=32.$$
Con el par de divisores \((u,v)=(4,8)\) obtenemos
$$y=\frac{4+4}{2}=4,\qquad z=\frac{8+4}{2}=6.$$
Así, \((x,y,z)=(2,4,6)\), y el triángulo asociado tiene lados
$$a=10,\qquad b=8,\qquad c=6.$$
Su semiperímetro es \(12\), su área es \(\sqrt{12\cdot 2\cdot 4\cdot 6}=24\), y su perímetro también es \(24\). Por tanto \(A/P=1\).
Ejemplo 2: \(k=2\). Ahora \(n=16\). El triple \((x,y,z)=(6,7,8)\) cumple
$$6\cdot 7\cdot 8 = 16(6+7+8)=336.$$
Los lados recuperados son
$$a=15,\qquad b=14,\qquad c=13,$$
es decir, el conocido triángulo \(13\)-\(14\)-\(15\). Su perímetro es \(42\), su área \(84\), y \(84/42=2\).
El código elige primero \(k\), de modo que \(n=(2k)^2\). Luego recorre todos los \(x\) admisibles, factoriza
$$M=n(x^2+n),$$
genera todos sus divisores, conserva solo los \(u\) con \(u^2 \le M\), reconstruye \(y\) y \(z\), y acepta exactamente los candidatos que pasan las condiciones de divisibilidad y orden. Por la derivación anterior, cada candidato aceptado corresponde a un triángulo válido y cada triángulo válido aparece una sola vez.
El archivo contiene dos checkpoints explícitos. Tanto el método rápido como el brute force producen
$$\sum_{k \le 5} p(k)=140098,\qquad \sum_{k \le 10} p(k)=3781786.$$
El coste principal está en factorizar \(m=x^2+n\) y enumerar los divisores de \(M=n(x^2+n)\). La criba SPF se construye hasta
$$4(2K)^2,$$
porque \(x^2 \le 3n\) implica \(m=x^2+n \le 4n\). En la práctica esto hace que la factorización sea barata y que la enumeración de divisores sea mucho más pequeña que recorrer directamente todos los pares \((y,z)\).
设一个整数边三角形的边长为 \(a,b,c\)，面积为 \(A\)，周长为 \(P=a+b+c\)。我们关心的是满足
$$\frac{A}{P}=k$$
为整数的三角形。对每个 \(k\)，记所有这类三角形周长之和为 \(p(k)\)。程序要求计算
$$\sum_{k=1}^{1000} p(k),$$
但这里故意不写出最终数值答案。
1) 用半周长差变量代替边长。 设
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
则 \(x,y,z\) 都是正整数，反过来又有
$$a=y+z,\qquad b=z+x,\qquad c=x+y,\qquad s=x+y+z.$$
因此每个整数三角形都唯一对应一个正整数三元组 \((x,y,z)\)。如果把边按 \(a \ge b \ge c\) 排序，那么就得到 \(x \le y \le z\)，这正是代码用来去重的顺序。
2) 用海伦公式得到丢番图方程。 海伦公式为
$$A^2=s(s-a)(s-b)(s-c)=sxyz.$$
条件 \(A/P=k\) 等价于
$$A=k(a+b+c)=2ks.$$
平方后约去一个 \(s\)，得到
$$xyz=4k^2s=4k^2(x+y+z).$$
令
$$n=(2k)^2=4k^2,$$
则问题变成纯整数方程
$$xyz=n(x+y+z),\qquad x \le y \le z.$$
恢复出来的三角形周长为
$$P=2s=2(x+y+z),$$
这就是程序为何对每个有效三元组累加 \(2(x+y+z)\)。
3) 为什么这是一个双射。 从任意三角形都能得到唯一的正三元组 \((x,y,z)\)。反过来，任意正解 \(xyz=n(x+y+z)\) 都能通过
$$a=y+z,\qquad b=z+x,\qquad c=x+y$$
恢复成三角形，因为 \(x,y,z>0\) 自动保证三角不等式成立。因此不会漏解，也不会引入额外对象。
4) 先把一个变量显式解出来。 由主方程可以得到
$$z=\frac{n(x+y)}{xy-n}.$$
因此 \(xy>n\) 是必要条件，而且一旦固定 \(x,y\)，\(z\) 至多只有一个可能值。代码中的 brute-force 校验正是用这条公式。
5) 快速算法的核心分解。 固定 \(k\) 和 \(x\) 后，有恒等式
$$(xy-n)(xz-n)=x^2yz-nx(y+z)+n^2=n(x^2+n).$$
定义
$$m=x^2+n,\qquad M=nm,\qquad u=xy-n,\qquad v=xz-n,$$
则
$$uv=M,$$
并且
$$y=\frac{u+n}{x},\qquad z=\frac{v+n}{x}.$$
所以对固定的 \((k,x)\)，只要枚举 \(M\) 的因子对 \((u,v)\)，再检查
$$x \mid (u+n),\qquad x \mid (v+n),\qquad y \ge x,\qquad z \ge y$$
即可。因为 \(y \le z\) 等价于 \(u \le v\)，代码只需处理满足 \(u^2 \le M\) 的一半因子。
6) 为什么 \(x \le \sqrt{3n}\)。 对固定 \(x\)，函数
$$f(y,z)=\frac{xyz}{x+y+z}$$
在正区间内对 \(y,z\) 都是递增的。由于 \(y,z \ge x\)，最小值出现在 \(y=z=x\)，所以
$$n=f(y,z)\ge \frac{x^3}{3x}=\frac{x^2}{3}.$$
因此
$$x \le \sqrt{3n}.$$
7) 校验代码中 \(y\) 的上界。 由 \(z \ge y\) 和 \(z\) 的公式得到
$$\frac{n(x+y)}{xy-n}\ge y,$$
整理为
$$xy^2-2ny-nx \le 0.$$
解这个二次不等式可得
$$y \le \frac{n+\sqrt{n(n+x^2)}}{x},$$
这正是校验例程里用到的边界。
示例 1: \(k=1\). 此时 \(n=4\)。取 \(x=2\)，则
$$M=n(x^2+n)=4(4+4)=32.$$
若选择因子对 \((u,v)=(4,8)\)，则
$$y=\frac{4+4}{2}=4,\qquad z=\frac{8+4}{2}=6.$$
于是 \((x,y,z)=(2,4,6)\)，对应三角形边长
$$a=10,\qquad b=8,\qquad c=6.$$
其半周长为 \(12\)，面积为 \(\sqrt{12\cdot 2\cdot 4\cdot 6}=24\)，周长也是 \(24\)，因此 \(A/P=1\)。
示例 2: \(k=2\). 此时 \(n=16\)。三元组 \((x,y,z)=(6,7,8)\) 满足
$$6\cdot 7\cdot 8 = 16(6+7+8)=336.$$
恢复出的边长是
$$a=15,\qquad b=14,\qquad c=13,$$
也就是经典的 \(13\)-\(14\)-\(15\) 三角形。它的周长为 \(42\)，面积为 \(84\)，比例 \(84/42=2\)。
代码先固定 \(k\)，于是 \(n=(2k)^2\)。然后遍历所有允许的 \(x\)，分解
$$M=n(x^2+n),$$
生成全部约数，只保留 \(u^2 \le M\) 的那一半，重建 \(y,z\)，并且只接受满足整除和顺序条件的候选。根据上面的推导，每个被接受的候选恰好对应一个合法三角形，而每个合法三角形也恰好出现一次。
源文件里有两个明确的 checkpoint。快速算法和 brute force 都得到
$$\sum_{k \le 5} p(k)=140098,\qquad \sum_{k \le 10} p(k)=3781786.$$
复杂度的主成本是分解 \(m=x^2+n\) 以及枚举 \(M=n(x^2+n)\) 的约数。SPF 筛只需要做到
$$4(2K)^2,$$
因为由 \(x^2 \le 3n\) 可知 \(m=x^2+n \le 4n\)。这使得每次分解都很便宜，而约数枚举也远小于直接遍历所有 \((y,z)\)。
Пусть у треугольника с целыми сторонами \(a,b,c\) площадь равна \(A\), а периметр \(P=a+b+c\). Нас интересуют треугольники, для которых
$$\frac{A}{P}=k$$
является целым числом. Для каждого \(k\) обозначим через \(p(k)\) сумму всех таких периметров. Программа вычисляет
$$\sum_{k=1}^{1000} p(k),$$
но окончательное числовое значение здесь намеренно не приводится.
1) Замена сторон на отступы от полупериметра. Введем
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
Тогда \(x,y,z\) - положительные целые числа, а обратные формулы имеют вид
$$a=y+z,\qquad b=z+x,\qquad c=x+y,\qquad s=x+y+z.$$
Значит, каждый целочисленный треугольник однозначно задается положительной тройкой \((x,y,z)\). Если отсортировать стороны как \(a \ge b \ge c\), то получим \(x \le y \le z\), ровно как в коде.
2) Формула Герона дает диофантово уравнение. По формуле Герона
$$A^2=s(s-a)(s-b)(s-c)=sxyz.$$
Условие \(A/P=k\) означает
$$A=k(a+b+c)=2ks.$$
После возведения в квадрат и сокращения одного множителя \(s\) получаем
$$xyz=4k^2s=4k^2(x+y+z).$$
Если положить
$$n=(2k)^2=4k^2,$$
то задача сводится к уравнению
$$xyz=n(x+y+z),\qquad x \le y \le z.$$
Периметр восстановленного треугольника равен
$$P=2s=2(x+y+z),$$
поэтому программа суммирует именно \(2(x+y+z)\).
3) Почему это биекция. Из любого треугольника получается одна положительная тройка \((x,y,z)\). И наоборот, из любой положительной решения уравнения \(xyz=n(x+y+z)\) по формулам
$$a=y+z,\qquad b=z+x,\qquad c=x+y$$
получается допустимый треугольник, потому что \(x,y,z>0\) автоматически обеспечивают неравенства треугольника. Значит, ничего не теряется и ничего лишнего не добавляется.
4) Явная формула для одной переменной. Из основного уравнения следует
$$z=\frac{n(x+y)}{xy-n}.$$
Следовательно, необходимо \(xy>n\), и при фиксированных \(x,y\) возможен не более чем один \(z\). Именно эту формулу использует проверка brute force.
5) Ключевая факторизация быстрого алгоритма. Зафиксируем \(k\) и \(x\). Тогда
$$(xy-n)(xz-n)=x^2yz-nx(y+z)+n^2=n(x^2+n).$$
Введем обозначения
$$m=x^2+n,\qquad M=nm,\qquad u=xy-n,\qquad v=xz-n.$$
Тогда
$$uv=M,$$
а исходные переменные восстанавливаются как
$$y=\frac{u+n}{x},\qquad z=\frac{v+n}{x}.$$
Значит, для фиксированного \((k,x)\) надо перебрать пары делителей \((u,v)\) числа \(M\) и проверить
$$x \mid (u+n),\qquad x \mid (v+n),\qquad y \ge x,\qquad z \ge y.$$
Условие \(y \le z\) эквивалентно \(u \le v\), поэтому достаточно половины пар с \(u^2 \le M\).
6) Почему \(x \le \sqrt{3n}\). При фиксированном \(x\) функция
$$f(y,z)=\frac{xyz}{x+y+z}$$
возрастает по обеим переменным \(y\) и \(z\). Так как \(y,z \ge x\), минимальное значение достигается при \(y=z=x\), и потому
$$n=f(y,z)\ge \frac{x^3}{3x}=\frac{x^2}{3}.$$
Отсюда следует
$$x \le \sqrt{3n}.$$
7) Верхняя граница для \(y\) в проверке. Из условия \(z \ge y\) и формулы для \(z\) получаем
$$\frac{n(x+y)}{xy-n}\ge y,$$
то есть
$$xy^2-2ny-nx \le 0.$$
Решение этого квадратного неравенства дает
$$y \le \frac{n+\sqrt{n(n+x^2)}}{x},$$
ровно ту границу, которая стоит в коде проверки.
Пример 1: \(k=1\). Тогда \(n=4\). Возьмем \(x=2\):
$$M=n(x^2+n)=4(4+4)=32.$$
Если выбрать пару делителей \((u,v)=(4,8)\), то
$$y=\frac{4+4}{2}=4,\qquad z=\frac{8+4}{2}=6.$$
Значит, \((x,y,z)=(2,4,6)\), а стороны треугольника равны
$$a=10,\qquad b=8,\qquad c=6.$$
Полупериметр равен \(12\), площадь \(\sqrt{12\cdot 2\cdot 4\cdot 6}=24\), периметр тоже \(24\). Следовательно, \(A/P=1\).
Пример 2: \(k=2\). Теперь \(n=16\). Тройка \((x,y,z)=(6,7,8)\) удовлетворяет
$$6\cdot 7\cdot 8 = 16(6+7+8)=336.$$
Восстановленные стороны:
$$a=15,\qquad b=14,\qquad c=13,$$
то есть знаменитый треугольник \(13\)-\(14\)-\(15\). Его периметр \(42\), площадь \(84\), и \(84/42=2\).
Код сначала выбирает \(k\), то есть \(n=(2k)^2\). Затем он перебирает все допустимые \(x\), факторизует
$$M=n(x^2+n),$$
генерирует все делители, оставляет только \(u\) с \(u^2 \le M\), восстанавливает \(y\) и \(z\) и принимает ровно те кандидаты, которые проходят проверки делимости и порядка. Из выведенной выше теории следует, что каждый принятый кандидат соответствует одному допустимому треугольнику, и каждый допустимый треугольник возникает ровно один раз.
В файле есть два явных checkpoint'а. Быстрый метод и brute force оба дают
$$\sum_{k \le 5} p(k)=140098,\qquad \sum_{k \le 10} p(k)=3781786.$$
Основная стоимость связана с факторизацией \(m=x^2+n\) и перечислением делителей \(M=n(x^2+n)\). SPF-решето строится до
$$4(2K)^2,$$
потому что из \(x^2 \le 3n\) следует \(m=x^2+n \le 4n\). Поэтому разложения выполняются быстро, а перечисление делителей намного дешевле прямого перебора всех \((y,z)\).
لدينا مثلث ذو أضلاع صحيحة \(a,b,c\)، ومساحته \(A\)، ومحيطه \(P=a+b+c\). نبحث عن جميع المثلثات التي يكون فيها
$$\frac{A}{P}=k$$
عددًا صحيحًا. ولكل \(k\)، نرمز بمجموع المحيطات الموافقة إلى \(p(k)\). البرنامج يحسب
$$\sum_{k=1}^{1000} p(k),$$
لكن القيمة العددية النهائية لا نعرضها هنا عمدًا.
1) استبدال الأضلاع بفروق نصف المحيط. نعرّف
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
عندئذ تكون \(x,y,z\) أعدادًا صحيحة موجبة، والعكس صحيح أيضًا لأن
$$a=y+z,\qquad b=z+x,\qquad c=x+y,\qquad s=x+y+z.$$
إذًا كل مثلث صحيح الأضلاع يقابل ثلاثية موجبة واحدة \((x,y,z)\). وإذا رتبنا الأضلاع بحيث \(a \ge b \ge c\)، نحصل على \(x \le y \le z\)، وهذا بالضبط ترتيب الكود لتجنب العد المكرر.
2) صيغة هيرون تحول المسألة إلى معادلة ديوفانتية. صيغة هيرون هي
$$A^2=s(s-a)(s-b)(s-c)=sxyz.$$
أما الشرط \(A/P=k\) فيعني أن
$$A=k(a+b+c)=2ks.$$
بعد التربيع واختزال عامل واحد من \(s\) نحصل على
$$xyz=4k^2s=4k^2(x+y+z).$$
إذا وضعنا
$$n=(2k)^2=4k^2,$$
تصبح المسألة هي حل المعادلة الصحيحة
$$xyz=n(x+y+z),\qquad x \le y \le z.$$
ومحيط المثلث المستعاد يساوي
$$P=2s=2(x+y+z),$$
ولهذا يضيف البرنامج \(2(x+y+z)\) لكل ثلاثية صحيحة مقبولة.
3) لماذا هذا تقابل تام. من كل مثلث نحصل على ثلاثية موجبة وحيدة \((x,y,z)\). وبالعكس، من كل حل موجب للمعادلة \(xyz=n(x+y+z)\)، تعطي الصيغ
$$a=y+z,\qquad b=z+x,\qquad c=x+y$$
مثلثًا صالحًا تلقائيًا لأن \(x,y,z>0\) تضمن متباينات المثلث. لذلك لا نفقد حلولًا ولا نعد أشياء غير صحيحة.
4) حل متغير واحد صراحة. من المعادلة الأساسية نحصل على
$$z=\frac{n(x+y)}{xy-n}.$$
إذن الشرط \(xy>n\) ضروري، وبمجرد تثبيت \(x\) و\(y\) يكون هناك على الأكثر \(z\) واحد ممكن. روتين التحقق المباشر في الكود يستخدم هذه الصيغة نفسها.
5) التحليل العاملـي الحاسم في الخوارزمية السريعة. بعد تثبيت \(k\) و\(x\) نجد أن
$$(xy-n)(xz-n)=x^2yz-nx(y+z)+n^2=n(x^2+n).$$
نعرّف
$$m=x^2+n,\qquad M=nm,\qquad u=xy-n,\qquad v=xz-n.$$
وعندئذ
$$uv=M,$$
ونسترجع المتغيرات الأصلية عبر
$$y=\frac{u+n}{x},\qquad z=\frac{v+n}{x}.$$
إذن، عند ثبوت \((k,x)\)، يكفي أن نولد أزواج القواسم \((u,v)\) للعدد \(M\)، ثم نتحقق من الشروط
$$x \mid (u+n),\qquad x \mid (v+n),\qquad y \ge x,\qquad z \ge y.$$
وبما أن \(y \le z\) مكافئ لـ \(u \le v\)، فإن الكود يكتفي بنصف الأزواج الذي يحقق \(u^2 \le M\).
6) لماذا \(x \le \sqrt{3n}\). عندما يكون \(x\) ثابتًا، فإن الدالة
$$f(y,z)=\frac{xyz}{x+y+z}$$
تزداد مع كل من \(y\) و\(z\). وبما أن \(y,z \ge x\)، فإن أصغر قيمة تتحقق عند \(y=z=x\)، وبالتالي
$$n=f(y,z)\ge \frac{x^3}{3x}=\frac{x^2}{3}.$$
ومن هنا نحصل على
$$x \le \sqrt{3n}.$$
7) الحد الأعلى لـ \(y\) في روتين التحقق. من الشرط \(z \ge y\) وصيغة \(z\) نحصل على
$$\frac{n(x+y)}{xy-n}\ge y,$$
أي
$$xy^2-2ny-nx \le 0.$$
وحل هذه المتباينة التربيعية يعطي
$$y \le \frac{n+\sqrt{n(n+x^2)}}{x},$$
وهو بالضبط الحد الذي يستعمله كود التحقق.
مثال 1: \(k=1\). عندئذ \(n=4\). إذا أخذنا \(x=2\)، فلدينا
$$M=n(x^2+n)=4(4+4)=32.$$
وباختيار زوج القواسم \((u,v)=(4,8)\) نحصل على
$$y=\frac{4+4}{2}=4,\qquad z=\frac{8+4}{2}=6.$$
إذن \((x,y,z)=(2,4,6)\)، والمثلث الموافق أضلاعه
$$a=10,\qquad b=8,\qquad c=6.$$
نصف محيطه \(12\)، ومساحته \(\sqrt{12\cdot 2\cdot 4\cdot 6}=24\)، ومحيطه أيضًا \(24\)، لذا فعلًا \(A/P=1\).
مثال 2: \(k=2\). الآن \(n=16\). الثلاثية \((x,y,z)=(6,7,8)\) تحقق
$$6\cdot 7\cdot 8 = 16(6+7+8)=336.$$
والأضلاع المستعادة هي
$$a=15,\qquad b=14,\qquad c=13,$$
أي المثلث الشهير \(13\)-\(14\)-\(15\). محيطه \(42\)، ومساحته \(84\)، وبالتالي \(84/42=2\).
يبدأ الكود بتثبيت \(k\)، ومنه \(n=(2k)^2\). بعد ذلك يمر على جميع قيم \(x\) المسموح بها، ويحلل
$$M=n(x^2+n)$$
إلى عوامله، ويولد جميع القواسم، ويحتفظ فقط بالقيم \(u\) التي تحقق \(u^2 \le M\)، ثم يعيد بناء \(y\) و\(z\)، ولا يقبل إلا المرشحين الذين يحققون شروط القسمة والترتيب. وبحسب الاشتقاق السابق، فإن كل مرشح مقبول يمثل مثلثًا صالحًا واحدًا، وكل مثلث صالح يظهر مرة واحدة فقط.
يحتوي الملف على نقطتي تحقق صريحتين. كل من الطريقة السريعة والطريقة المباشرة يعطيان
$$\sum_{k \le 5} p(k)=140098,\qquad \sum_{k \le 10} p(k)=3781786.$$
أما الكلفة الرئيسية فتأتي من تحليل \(m=x^2+n\) إلى عوامل أولية وتوليد قواسم \(M=n(x^2+n)\). مصفوفة SPF تُبنى حتى
$$4(2K)^2,$$
لأن \(x^2 \le 3n\) تعطي مباشرة \(m=x^2+n \le 4n\). عمليًا هذا يجعل التحليل العاملـي رخيصًا، كما أن تعداد القواسم أصغر بكثير من المسح المباشر لكل الأزواج \((y,z)\).