The contributing triangles split into two infinite Pythagorean families. One family has hypotenuse exactly one larger than a leg, and the other has two consecutive legs. The task is to sum every distinct perimeter not exceeding \(N=10^{10^{10}}\) and return the result modulo \(1234567891\). Because \(N\) is unimaginably large, the solution replaces any geometric search with closed formulas, a Pell-type recurrence, and one overlap correction.
Let \(S(N)\) be the required perimeter sum, and let \(M=1234567891\) be the modulus used at the end.
For a primitive right triangle we may write
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,\qquad m>n\ge 1.$$
Impose the condition that the hypotenuse is one larger than one leg:
$$c=b+1.$$
Then
$$m^2+n^2=2mn+1 \Longrightarrow (m-n)^2=1,$$
so necessarily \(m=n+1\). Substituting gives
$$a=2n+1,\qquad b=2n(n+1),\qquad c=2n(n+1)+1.$$
If we set \(t=2n+1\), then \(t\) is odd and the perimeter becomes
$$p=t+\frac{t^2-1}{2}+\frac{t^2+1}{2}=t(t+1).$$
So Family I contributes exactly the perimeters \(t(t+1)\) with odd \(t\ge 3\).
The inequality \(t(t+1)\le N\) implies \(t<\sqrt{N}\). Here \(N=10^E\) with \(E=10^{10}\), and \(E\) is even, so
$$\sqrt{N}=10^{E/2}.$$
Write
$$s=10^{E/2},\qquad q=\frac{s}{2}.$$
The odd values below \(s\) are \(1,3,\dots,s-1\). Using \(t=2j-1\),
$$\sum_{j=1}^{q}(2j-1)(2j)=\sum_{j=1}^{q}(4j^2-2j)=\frac{q(q+1)(4q-1)}{3}.$$
The term \(t=1\) corresponds to the degenerate triple \((1,0,1)\) with perimeter \(2\), so the valid Family I contribution is
$$S_I(N)=\frac{q(q+1)(4q-1)}{3}-2.$$
Now look at right triangles whose legs are consecutive, say \(x\) and \(x+1\), with hypotenuse \(c\). Then
$$x^2+(x+1)^2=c^2.$$
Introduce
$$u=2x+1.$$
Since \(u^2=4x^2+4x+1\), the Pythagorean condition becomes the negative Pell equation
$$u^2-2c^2=-1.$$
Its positive solutions are generated by multiplication with \(3+2\sqrt{2}\). Starting from \(7+5\sqrt{2}\), which corresponds to the triangle \((3,4,5)\), we get
$$u_{k+1}=3u_k+4c_k,\qquad c_{k+1}=2u_k+3c_k.$$
The perimeter of such a triangle is
$$p_k=u_k+c_k,$$
so the first values are
$$12,\ 70,\ 408,\ 2378,\dots$$
The Pell multiplier has conjugate roots
$$\lambda=3+2\sqrt{2},\qquad \mu=3-2\sqrt{2}.$$
They satisfy \(\lambda+\mu=6\) and \(\lambda\mu=1\), so any sequence built from these Pell solutions satisfies
$$r^2-6r+1=0.$$
In particular, the perimeter sequence obeys
$$p_{k+1}=6p_k-p_{k-1},\qquad p_1=12,\qquad p_2=70.$$
If \(K\) is the largest index with \(p_K\le N\), then Family II contributes
$$S_{II}(N)=\sum_{k=1}^{K}p_k.$$
The recurrence has closed form
$$p_k=\alpha \lambda^k+\beta \mu^k,$$
with \(|\mu|<1\). Therefore \(p_k\) grows like \(\alpha \lambda^k\), and an accurate first estimate is
$$K\approx \frac{\log_{10}N-\log_{10}\alpha}{\log_{10}\lambda}.$$
After that estimate is computed, a few monotone comparisons are enough to adjust \(K\) until \(p_K\le N<p_{K+1}\). This avoids building huge integers such as \(10^{10^{10}}\) explicitly.
The only perimeter counted twice is \(12\), coming from the triangle \((3,4,5)\). In Family I the sides are
$$t,\qquad \frac{t^2-1}{2},\qquad \frac{t^2+1}{2}.$$
To also have consecutive legs we need
$$\frac{t^2-1}{2}=t+1 \Longrightarrow t^2-2t-3=0 \Longrightarrow t=3.$$
Hence the final formula is
$$S(N)=S_I(N)+S_{II}(N)-12 \pmod{1234567891}.$$
Family I contributes the perimeters \(12,30,56,90\), whose sum is \(188\).
Family II contributes \(12,70\), whose sum is \(82\).
Subtract the shared perimeter \(12\) once:
$$S(100)=188+82-12=258.$$
This matches the checkpoint used by the implementations.
The C++, Python, and Java implementations evaluate Family I entirely modulo \(1234567891\). They compute \(10^{E/2}\bmod M\), replace division by \(2\) and \(3\) with modular inverses, and apply the closed formula for \(S_I(N)\) directly.
For Family II, the implementation first estimates the largest admissible index from the dominant root \(3+2\sqrt{2}\), then corrects the index with a few monotone checks. The sum of the recurrence is obtained with fast exponentiation of a \(3\times 3\) transition matrix whose state stores the current perimeter, the previous perimeter, and the running total.
Finally the two partial sums are added modulo \(1234567891\), and the overlap \(12\) is removed exactly once.
Family I is handled in \(O(1)\) modular arithmetic. Family II uses \(O(\log K)\) multiplications of fixed \(3\times 3\) matrices, plus constant-time index correction. Memory usage is \(O(1)\). The running time depends only on the recurrence index, not on the astronomical size of \(N\).
Die beitragenden Dreiecke zerfallen in zwei unendliche pythagoreische Familien. In der ersten ist die Hypotenuse genau um \(1\) größer als eine Kathete, in der zweiten sind die beiden Katheten aufeinanderfolgende Zahlen. Gesucht ist die Summe aller verschiedenen Umfänge bis \(N=10^{10^{10}}\), modulo \(1234567891\). Weil \(N\) extrem groß ist, ersetzt die Lösung jede direkte Suche durch geschlossene Formeln, eine Pell-artige Rekurrenz und genau eine Überlappungskorrektur.
Sei \(S(N)\) die gesuchte Umfangssumme und \(M=1234567891\) der am Ende verwendete Modulus.
Ein primitives rechtwinkliges Dreieck kann man schreiben als
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,\qquad m>n\ge 1.$$
Wir erzwingen nun, dass die Hypotenuse um \(1\) größer als eine Kathete ist:
$$c=b+1.$$
Dann gilt
$$m^2+n^2=2mn+1 \Longrightarrow (m-n)^2=1,$$
also notwendigerweise \(m=n+1\). Einsetzen liefert
$$a=2n+1,\qquad b=2n(n+1),\qquad c=2n(n+1)+1.$$
Mit \(t=2n+1\) ist \(t\) ungerade, und der Umfang wird zu
$$p=t+\frac{t^2-1}{2}+\frac{t^2+1}{2}=t(t+1).$$
Familie I liefert also genau die Umfänge \(t(t+1)\) mit ungeradem \(t\ge 3\).
Aus \(t(t+1)\le N\) folgt \(t<\sqrt{N}\). Hier ist \(N=10^E\) mit \(E=10^{10}\), und \(E\) ist gerade, also
$$\sqrt{N}=10^{E/2}.$$
Setze
$$s=10^{E/2},\qquad q=\frac{s}{2}.$$
Die ungeraden Werte unterhalb von \(s\) sind \(1,3,\dots,s-1\). Mit \(t=2j-1\) erhält man
$$\sum_{j=1}^{q}(2j-1)(2j)=\sum_{j=1}^{q}(4j^2-2j)=\frac{q(q+1)(4q-1)}{3}.$$
Der Term \(t=1\) gehört zum degenerierten Dreieck \((1,0,1)\) mit Umfang \(2\) und wird deshalb abgezogen. Somit ist
$$S_I(N)=\frac{q(q+1)(4q-1)}{3}-2.$$
Nun betrachten wir rechtwinklige Dreiecke mit Katheten \(x\) und \(x+1\) sowie Hypotenuse \(c\). Dann gilt
$$x^2+(x+1)^2=c^2.$$
Wir definieren
$$u=2x+1.$$
Weil \(u^2=4x^2+4x+1\), ist die Bedingung äquivalent zur negativen Pell-Gleichung
$$u^2-2c^2=-1.$$
Alle positiven Lösungen entstehen durch Multiplikation mit \(3+2\sqrt{2}\). Beginnend bei \(7+5\sqrt{2}\), also dem Dreieck \((3,4,5)\), folgt
$$u_{k+1}=3u_k+4c_k,\qquad c_{k+1}=2u_k+3c_k.$$
Der Umfang lautet
$$p_k=u_k+c_k,$$
und die ersten Werte sind
$$12,\ 70,\ 408,\ 2378,\dots$$
Der Pell-Multiplikator besitzt die konjugierten Wurzeln
$$\lambda=3+2\sqrt{2},\qquad \mu=3-2\sqrt{2}.$$
Mit \(\lambda+\mu=6\) und \(\lambda\mu=1\) erfüllt jede daraus aufgebaute Folge die charakteristische Gleichung
$$r^2-6r+1=0.$$
Insbesondere gilt für die Umfangsfolge
$$p_{k+1}=6p_k-p_{k-1},\qquad p_1=12,\qquad p_2=70.$$
Ist \(K\) der größte Index mit \(p_K\le N\), dann ist der Beitrag von Familie II
$$S_{II}(N)=\sum_{k=1}^{K}p_k.$$
Die Rekurrenz hat die geschlossene Form
$$p_k=\alpha \lambda^k+\beta \mu^k,$$
wobei \(|\mu|<1\). Daher wächst \(p_k\) wie \(\alpha \lambda^k\), und eine sehr gute erste Schätzung ist
$$K\approx \frac{\log_{10}N-\log_{10}\alpha}{\log_{10}\lambda}.$$
Danach reichen einige monotone Vergleiche aus, um \(K\) so zu korrigieren, dass \(p_K\le N<p_{K+1}\) gilt. Das riesige \(10^{10^{10}}\) muss also nie explizit aufgebaut werden.
Doppelt gezählt wird nur der Umfang \(12\), also das Dreieck \((3,4,5)\). In Familie I lauten die Seiten
$$t,\qquad \frac{t^2-1}{2},\qquad \frac{t^2+1}{2}.$$
Damit zusätzlich die Katheten aufeinanderfolgend sind, muss gelten
$$\frac{t^2-1}{2}=t+1 \Longrightarrow t^2-2t-3=0 \Longrightarrow t=3.$$
Somit ist die Endformel
$$S(N)=S_I(N)+S_{II}(N)-12 \pmod{1234567891}.$$
Familie I liefert die Umfänge \(12,30,56,90\) mit Summe \(188\).
Familie II liefert \(12,70\) mit Summe \(82\).
Der gemeinsame Umfang \(12\) wird einmal abgezogen:
$$S(100)=188+82-12=258.$$
Das stimmt mit dem Kontrollwert der Implementierungen überein.
Die C++-, Python- und Java-Implementierungen berechnen Familie I vollständig modulo \(1234567891\). Dazu wird \(10^{E/2}\bmod M\) bestimmt, die Division durch \(2\) und \(3\) durch modulare Inverse ersetzt und die geschlossene Formel für \(S_I(N)\) direkt ausgewertet.
Für Familie II schätzt die Implementierung zuerst den größten zulässigen Index aus der dominanten Wurzel \(3+2\sqrt{2}\) und korrigiert ihn mit wenigen monotonen Tests. Die Summation der Rekurrenz erfolgt per schneller Potenzierung einer \(3\times 3\)-Übergangsmatrix, deren Zustand aktuellen Umfang, vorherigen Umfang und laufende Summe speichert.
Zum Schluss werden beide Teilsummen modulo \(1234567891\) addiert und die Überlappung \(12\) genau einmal abgezogen.
Familie I benötigt \(O(1)\) modulare Arithmetik. Familie II braucht \(O(\log K)\) Multiplikationen fester \(3\times 3\)-Matrizen sowie eine konstante Nachkorrektur des Index. Der Speicherverbrauch ist \(O(1)\). Die Laufzeit hängt also nur vom Rekurrenzindex ab und nicht von der astronomischen Größe von \(N\).
Katkı veren üçgenler iki sonsuz Pisagor ailesine ayrılıyor. İlk ailede hipotenüs, kenarlardan birinden tam \(1\) büyük; ikinci ailede ise iki dik kenar ardışık tam sayılar. İstenen şey, çevresi \(N=10^{10^{10}}\) değerini aşmayan tüm farklı çevrelerin toplamını \(1234567891\) modunda bulmak. \(N\) akıl almaz büyüklükte olduğu için çözüm, doğrudan tarama yerine kapalı formüller, Pell tipi bir yineleme ve tek bir çakışma düzeltmesi kullanıyor.
\(S(N)\) aranan çevre toplamı, \(M=1234567891\) ise sonda kullanılan mod olsun.
Primitif bir dik üçgen şu şekilde yazılabilir:
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,\qquad m>n\ge 1.$$
Şimdi hipotenüsün bir dik kenardan tam \(1\) büyük olmasını isteyelim:
$$c=b+1.$$
Bu durumda
$$m^2+n^2=2mn+1 \Longrightarrow (m-n)^2=1,$$
dolayısıyla zorunlu olarak \(m=n+1\) olur. Yerine koyunca
$$a=2n+1,\qquad b=2n(n+1),\qquad c=2n(n+1)+1.$$
\(t=2n+1\) dersek \(t\) tektir ve çevre
$$p=t+\frac{t^2-1}{2}+\frac{t^2+1}{2}=t(t+1)$$
biçimine gelir. Demek ki Aile I tam olarak tek \(t\ge 3\) için \(t(t+1)\) çevrelerini üretir.
\(t(t+1)\le N\) eşitsizliği \(t<\sqrt{N}\) verir. Burada \(N=10^E\) ve \(E=10^{10}\) çift sayı olduğu için
$$\sqrt{N}=10^{E/2}.$$
Şimdi
$$s=10^{E/2},\qquad q=\frac{s}{2}$$
tanımlarını yapalım. \(s\)'den küçük tek değerler \(1,3,\dots,s-1\) olduğundan, \(t=2j-1\) yazarsak
$$\sum_{j=1}^{q}(2j-1)(2j)=\sum_{j=1}^{q}(4j^2-2j)=\frac{q(q+1)(4q-1)}{3}.$$
\(t=1\) terimi \((1,0,1)\) dejenere üçgenine ve çevre \(2\)'ye karşılık gelir; bu nedenle çıkarılır. Böylece
$$S_I(N)=\frac{q(q+1)(4q-1)}{3}-2.$$
Şimdi dik kenarları \(x\) ve \(x+1\) olan, hipotenüsü \(c\) olan üçgenleri ele alalım. O zaman
$$x^2+(x+1)^2=c^2.$$
\(u=2x+1\) tanımı yapılırsa, \(u^2=4x^2+4x+1\) olduğundan denklem negatif Pell denklemine dönüşür:
$$u^2-2c^2=-1.$$
Pozitif çözümler \(3+2\sqrt{2}\) ile çarparak üretilir. Başlangıçtaki \(7+5\sqrt{2}\) çözümü \((3,4,5)\) üçgenine karşılık gelir ve bundan sonra
$$u_{k+1}=3u_k+4c_k,\qquad c_{k+1}=2u_k+3c_k$$
elde edilir. Çevre
$$p_k=u_k+c_k$$
olduğu için ilk değerler
$$12,\ 70,\ 408,\ 2378,\dots$$
şeklindedir.
Pell çarpanının eşlenik kökleri
$$\lambda=3+2\sqrt{2},\qquad \mu=3-2\sqrt{2}$$
olup \(\lambda+\mu=6\) ve \(\lambda\mu=1\) sağlar. Bu yüzden bu çözümlerden türeyen her dizi
$$r^2-6r+1=0$$
karakteristik denklemine uyar. Özellikle çevreler için
$$p_{k+1}=6p_k-p_{k-1},\qquad p_1=12,\qquad p_2=70$$
vardır. \(p_K\le N\) koşulunu sağlayan en büyük indeks \(K\) ise, Aile II katkısı
$$S_{II}(N)=\sum_{k=1}^{K}p_k$$
olur.
Yinelemenin kapalı biçimi
$$p_k=\alpha \lambda^k+\beta \mu^k$$
şeklindedir ve \(|\mu|<1\). Bu nedenle büyümeyi belirleyen ana terim \(\alpha\lambda^k\) olur. İlk tahmin
$$K\approx \frac{\log_{10}N-\log_{10}\alpha}{\log_{10}\lambda}$$
ile yapılır. Sonra birkaç monoton karşılaştırma ile \(p_K\le N<p_{K+1}\) şartı tam olarak sağlanır. Böylece \(10^{10^{10}}\) gibi devasa sayılar açık biçimde üretilmez.
İki kez sayılan tek çevre \(12\)'dir; bu da \((3,4,5)\) üçgeninden gelir. Aile I tarafında kenarlar
$$t,\qquad \frac{t^2-1}{2},\qquad \frac{t^2+1}{2}$$
olduğundan, aynı zamanda dik kenarların ardışık olması için
$$\frac{t^2-1}{2}=t+1 \Longrightarrow t^2-2t-3=0 \Longrightarrow t=3$$
gerekir. Sonuç formülü bu yüzden
$$S(N)=S_I(N)+S_{II}(N)-12 \pmod{1234567891}$$
olur.
Aile I, \(12,30,56,90\) çevrelerini verir ve toplam \(188\)'dir.
Aile II, \(12,70\) çevrelerini verir ve toplam \(82\)'dir.
Ortak olan \(12\) bir kez çıkarılır:
$$S(100)=188+82-12=258.$$
Bu değer, uygulamaların kullandığı küçük kontrol sonucuyla aynıdır.
C++, Python ve Java implementasyonları Aile I'i tamamen \(1234567891\) modunda hesaplar. Bunun için \(10^{E/2}\bmod M\) bulunur, \(2\) ve \(3\) ile bölmeler modüler terslerle yapılır ve \(S_I(N)\) için kapalı form doğrudan uygulanır.
Aile II tarafında uygulama önce baskın kök \(3+2\sqrt{2}\) yardımıyla en büyük uygun indeksi tahmin eder, ardından birkaç monoton sınır kontrolüyle bunu düzeltir. Yineleme toplamı ise mevcut çevreyi, bir önceki çevreyi ve kümülatif toplamı tutan \(3\times 3\) bir geçiş matrisinin hızlı üs alınmasıyla elde edilir.
Son adımda iki modüler toplam birleştirilir ve çakışan \(12\) çevresi tam bir kez çıkarılır.
Aile I için maliyet \(O(1)\) modüler aritmetiktir. Aile II, sabit boyutlu \(3\times 3\) matrislerle \(O(\log K)\) çarpım gerektirir; indeks düzeltmesi ise sabit zamandır. Bellek kullanımı \(O(1)\)'dir. Yani çalışma süresi \(N\)'in dev boyutuna değil, yalnızca yineleme indeksine bağlıdır.
Los triangulos que aportan al total se separan en dos familias pitagoricas infinitas. En la primera, la hipotenusa es exactamente \(1\) mayor que un cateto; en la segunda, los dos catetos son consecutivos. Hay que sumar todos los perimetros distintos no mayores que \(N=10^{10^{10}}\) y devolver el resultado modulo \(1234567891\). Como \(N\) es gigantesco, la solucion evita toda enumeracion directa y usa formulas cerradas, una recurrencia de tipo Pell y una sola correccion por interseccion.
Sea \(S(N)\) la suma pedida y \(M=1234567891\) el modulo final.
Un triangulo rectangulo primitivo puede escribirse como
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,\qquad m>n\ge 1.$$
Imponemos ahora que la hipotenusa sea \(1\) mayor que un cateto:
$$c=b+1.$$
Entonces
$$m^2+n^2=2mn+1 \Longrightarrow (m-n)^2=1,$$
y por tanto necesariamente \(m=n+1\). Sustituyendo obtenemos
$$a=2n+1,\qquad b=2n(n+1),\qquad c=2n(n+1)+1.$$
Si definimos \(t=2n+1\), entonces \(t\) es impar y el perimetro vale
$$p=t+\frac{t^2-1}{2}+\frac{t^2+1}{2}=t(t+1).$$
Asi, la Familia I aporta exactamente los perimetros \(t(t+1)\) con \(t\) impar y \(t\ge 3\).
La condicion \(t(t+1)\le N\) implica \(t<\sqrt{N}\). Aqui \(N=10^E\) con \(E=10^{10}\), y como \(E\) es par, tenemos
$$\sqrt{N}=10^{E/2}.$$
Escribimos
$$s=10^{E/2},\qquad q=\frac{s}{2}.$$
Los valores impares por debajo de \(s\) son \(1,3,\dots,s-1\). Con \(t=2j-1\), resulta
$$\sum_{j=1}^{q}(2j-1)(2j)=\sum_{j=1}^{q}(4j^2-2j)=\frac{q(q+1)(4q-1)}{3}.$$
El termino \(t=1\) corresponde al triangulo degenerado \((1,0,1)\), cuyo perimetro es \(2\), y debe restarse. Por tanto,
$$S_I(N)=\frac{q(q+1)(4q-1)}{3}-2.$$
Consideremos ahora triangulos rectangulos con catetos \(x\) y \(x+1\), e hipotenusa \(c\). Entonces
$$x^2+(x+1)^2=c^2.$$
Definimos
$$u=2x+1.$$
Como \(u^2=4x^2+4x+1\), la ecuacion se transforma en la ecuacion negativa de Pell
$$u^2-2c^2=-1.$$
Sus soluciones positivas se generan multiplicando por \(3+2\sqrt{2}\). Partiendo de \(7+5\sqrt{2}\), que corresponde al triangulo \((3,4,5)\), se obtiene
$$u_{k+1}=3u_k+4c_k,\qquad c_{k+1}=2u_k+3c_k.$$
El perimetro es
$$p_k=u_k+c_k,$$
y los primeros valores son
$$12,\ 70,\ 408,\ 2378,\dots$$
El multiplicador de Pell tiene raices conjugadas
$$\lambda=3+2\sqrt{2},\qquad \mu=3-2\sqrt{2}.$$
Como \(\lambda+\mu=6\) y \(\lambda\mu=1\), toda sucesion construida a partir de estas soluciones satisface
$$r^2-6r+1=0.$$
En particular, la sucesion de perimetros cumple
$$p_{k+1}=6p_k-p_{k-1},\qquad p_1=12,\qquad p_2=70.$$
Si \(K\) es el mayor indice con \(p_K\le N\), entonces la contribucion de la Familia II es
$$S_{II}(N)=\sum_{k=1}^{K}p_k.$$
La recurrencia tiene forma cerrada
$$p_k=\alpha \lambda^k+\beta \mu^k,$$
y \(|\mu|<1\). Por eso el crecimiento dominante es \(\alpha\lambda^k\), y una primera estimacion muy precisa es
$$K\approx \frac{\log_{10}N-\log_{10}\alpha}{\log_{10}\lambda}.$$
Despues bastan unas pocas comprobaciones monótonas para ajustar \(K\) hasta que \(p_K\le N<p_{K+1}\). Nunca hace falta construir de manera explicita un numero como \(10^{10^{10}}\).
El unico perimetro contado dos veces es \(12\), proveniente del triangulo \((3,4,5)\). En la Familia I los lados son
$$t,\qquad \frac{t^2-1}{2},\qquad \frac{t^2+1}{2}.$$
Para que los catetos tambien sean consecutivos, debe cumplirse
$$\frac{t^2-1}{2}=t+1 \Longrightarrow t^2-2t-3=0 \Longrightarrow t=3.$$
Por tanto, la formula final es
$$S(N)=S_I(N)+S_{II}(N)-12 \pmod{1234567891}.$$
La Familia I produce los perimetros \(12,30,56,90\), cuya suma es \(188\).
La Familia II produce \(12,70\), cuya suma es \(82\).
Restando una sola vez el perimetro compartido \(12\), obtenemos
$$S(100)=188+82-12=258.$$
Este valor coincide con la comprobacion pequena utilizada por las implementaciones.
Las implementaciones en C++, Python y Java evalúan la Familia I completamente modulo \(1234567891\). Calculan \(10^{E/2}\bmod M\), convierten las divisiones por \(2\) y \(3\) en multiplicaciones por inversos modulares y aplican directamente la formula cerrada de \(S_I(N)\).
Para la Familia II, la implementacion estima primero el mayor indice permitido a partir de la raiz dominante \(3+2\sqrt{2}\) y luego lo corrige con unas pocas comparaciones monótonas. La suma de la recurrencia se obtiene mediante exponenciacion rapida de una matriz de transicion \(3\times 3\) cuyo estado guarda el perimetro actual, el anterior y la suma acumulada.
Al final se suman ambas contribuciones modulo \(1234567891\) y se resta una vez la superposicion \(12\).
La Familia I se resuelve en \(O(1)\) operaciones modulares. La Familia II requiere \(O(\log K)\) multiplicaciones de matrices fijas de \(3\times 3\), mas una correccion final de tiempo constante para el indice. El uso de memoria es \(O(1)\). En la practica, el costo depende del indice de la recurrencia y no del tamano astronomico de \(N\).
满足条件的三角形可以分成两条无穷的勾股三角形族。第一族满足“斜边比某一条直角边恰好大 \(1\)”，第二族满足“两条直角边是连续整数”。题目要求把所有周长不超过 \(N=10^{10^{10}}\) 的不同周长全部求和，并对 \(1234567891\) 取模。由于这个上界巨大到根本无法枚举，解法必须把几何条件改写成可直接求和的公式、Pell 型递推，以及最后的一次去重。
记所求周长和为 \(S(N)\)，最终模数记为 \(M=1234567891\)。
原始勾股三角形可以写成
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,\qquad m>n\ge 1.$$
现在要求斜边比一条直角边大 \(1\)，即
$$c=b+1.$$
代入以后得到
$$m^2+n^2=2mn+1 \Longrightarrow (m-n)^2=1,$$
因此只能有 \(m=n+1\)。把它代回去，可得三边为
$$a=2n+1,\qquad b=2n(n+1),\qquad c=2n(n+1)+1.$$
令 \(t=2n+1\)，那么 \(t\) 一定是奇数，而且周长变成
$$p=t+\frac{t^2-1}{2}+\frac{t^2+1}{2}=t(t+1).$$
所以第一族恰好对应所有奇数 \(t\ge 3\) 的周长 \(t(t+1)\)。
由 \(t(t+1)\le N\) 可知 \(t<\sqrt{N}\)。这里 \(N=10^E\)，其中 \(E=10^{10}\) 是偶数，所以
$$\sqrt{N}=10^{E/2}.$$
记
$$s=10^{E/2},\qquad q=\frac{s}{2}.$$
小于 \(s\) 的奇数正好是 \(1,3,\dots,s-1\)。写成 \(t=2j-1\) 后，有
$$\sum_{j=1}^{q}(2j-1)(2j)=\sum_{j=1}^{q}(4j^2-2j)=\frac{q(q+1)(4q-1)}{3}.$$
其中 \(t=1\) 对应退化三角形 \((1,0,1)\)，周长为 \(2\)，必须删去。因此第一族的总贡献为
$$S_I(N)=\frac{q(q+1)(4q-1)}{3}-2.$$
再看另一类勾股三角形：两条直角边分别为 \(x\) 与 \(x+1\)，斜边为 \(c\)。它们满足
$$x^2+(x+1)^2=c^2.$$
令
$$u=2x+1.$$
由于 \(u^2=4x^2+4x+1\)，上式等价于负 Pell 方程
$$u^2-2c^2=-1.$$
这个方程的正整数解可以通过不断乘以 \(3+2\sqrt{2}\) 生成。起点 \(7+5\sqrt{2}\) 对应的正是三角形 \((3,4,5)\)。于是后续解满足
$$u_{k+1}=3u_k+4c_k,\qquad c_{k+1}=2u_k+3c_k.$$
而周长就是
$$p_k=u_k+c_k.$$
前几项依次为
$$12,\ 70,\ 408,\ 2378,\dots$$
Pell 乘子的共轭根为
$$\lambda=3+2\sqrt{2},\qquad \mu=3-2\sqrt{2}.$$
它们满足 \(\lambda+\mu=6\)、\(\lambda\mu=1\)，所以由这些 Pell 解构造出的任意序列都会满足特征方程
$$r^2-6r+1=0.$$
特别地，周长序列满足
$$p_{k+1}=6p_k-p_{k-1},\qquad p_1=12,\qquad p_2=70.$$
若 \(K\) 是满足 \(p_K\le N\) 的最大下标，那么第二族的总贡献就是
$$S_{II}(N)=\sum_{k=1}^{K}p_k.$$
这个递推有闭式
$$p_k=\alpha \lambda^k+\beta \mu^k,$$
其中 \(|\mu|<1\)。因此主导增长项是 \(\alpha\lambda^k\)，于是可以先用
$$K\approx \frac{\log_{10}N-\log_{10}\alpha}{\log_{10}\lambda}$$
得到一个非常接近的估计值。然后再做少量单调比较，把 \(K\) 修正到精确满足 \(p_K\le N<p_{K+1}\) 的位置。整个过程中完全不需要真的构造 \(10^{10^{10}}\) 这样的天文数字。
被重复计算的只有周长 \(12\)，也就是三角形 \((3,4,5)\)。在第一族中，三边写成
$$t,\qquad \frac{t^2-1}{2},\qquad \frac{t^2+1}{2}.$$
如果还要求两条直角边连续，就必须满足
$$\frac{t^2-1}{2}=t+1 \Longrightarrow t^2-2t-3=0 \Longrightarrow t=3.$$
因此最终公式为
$$S(N)=S_I(N)+S_{II}(N)-12 \pmod{1234567891}.$$
第一族给出周长 \(12,30,56,90\)，总和为 \(188\)。
第二族给出周长 \(12,70\)，总和为 \(82\)。
把重复出现的 \(12\) 减去一次，就得到
$$S(100)=188+82-12=258.$$
这与实现中使用的小规模校验结果一致。
C++、Python 和 Java 三个实现对第一族都直接在模 \(1234567891\) 下计算。它们先求 \(10^{E/2}\bmod M\)，再用模逆处理除以 \(2\) 与 \(3\)，最后把闭式公式直接代入得到 \(S_I(N)\)。
对于第二族，实现先利用主导根 \(3+2\sqrt{2}\) 估计最大合法下标，再用少量单调检查把下标修正到精确值。递推和则通过一个 \(3\times 3\) 转移矩阵的快速幂来完成，状态里保存当前周长、上一项周长以及累计和。
最后把两部分结果相加，并把重叠的周长 \(12\) 恰好减去一次。
第一族只需要 \(O(1)\) 次模运算。第二族需要 \(O(\log K)\) 次固定大小 \(3\times 3\) 矩阵乘法，再加上常数次的下标修正。空间复杂度是 \(O(1)\)。也就是说，算法的成本取决于递推项数的对数，而不是 \(N\) 这个天文级上界本身。
Все учитываемые треугольники распадаются на два бесконечных семейства пифагоровых троек. В первом семействе гипотенуза ровно на \(1\) больше одного катета, во втором два катета являются соседними целыми числами. Нужно просуммировать все различные периметры, не превосходящие \(N=10^{10^{10}}\), и взять результат по модулю \(1234567891\). Поскольку граница колоссальна, решение полностью аналитическое: замкнутая формула для первого семейства, Pell-подобная рекурсия для второго и одна поправка на пересечение.
Обозначим через \(S(N)\) искомую сумму периметров, а через \(M=1234567891\) итоговый модуль.
Примитивную прямоугольную тройку можно записать так:
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,\qquad m>n\ge 1.$$
Потребуем, чтобы гипотенуза была на \(1\) больше одного катета:
$$c=b+1.$$
Тогда
$$m^2+n^2=2mn+1 \Longrightarrow (m-n)^2=1,$$
значит, обязательно \(m=n+1\). Подстановка дает
$$a=2n+1,\qquad b=2n(n+1),\qquad c=2n(n+1)+1.$$
Если ввести \(t=2n+1\), то \(t\) нечетно, а периметр равен
$$p=t+\frac{t^2-1}{2}+\frac{t^2+1}{2}=t(t+1).$$
Итак, Семейство I дает ровно периметры вида \(t(t+1)\) для нечетных \(t\ge 3\).
Из неравенства \(t(t+1)\le N\) следует \(t<\sqrt{N}\). Здесь \(N=10^E\), где \(E=10^{10}\) четно, поэтому
$$\sqrt{N}=10^{E/2}.$$
Обозначим
$$s=10^{E/2},\qquad q=\frac{s}{2}.$$
Нечетные значения ниже \(s\) равны \(1,3,\dots,s-1\). При \(t=2j-1\) имеем
$$\sum_{j=1}^{q}(2j-1)(2j)=\sum_{j=1}^{q}(4j^2-2j)=\frac{q(q+1)(4q-1)}{3}.$$
Слагаемое \(t=1\) соответствует вырожденному треугольнику \((1,0,1)\) с периметром \(2\), поэтому его надо вычесть. Получаем
$$S_I(N)=\frac{q(q+1)(4q-1)}{3}-2.$$
Теперь рассмотрим прямоугольные треугольники с катетами \(x\) и \(x+1\) и гипотенузой \(c\). Тогда
$$x^2+(x+1)^2=c^2.$$
Введем
$$u=2x+1.$$
Так как \(u^2=4x^2+4x+1\), это равносильно отрицательному уравнению Пелля
$$u^2-2c^2=-1.$$
Все положительные решения порождаются умножением на \(3+2\sqrt{2}\). Начальное решение \(7+5\sqrt{2}\) соответствует треугольнику \((3,4,5)\), а дальше выполняется
$$u_{k+1}=3u_k+4c_k,\qquad c_{k+1}=2u_k+3c_k.$$
Периметр равен
$$p_k=u_k+c_k,$$
поэтому первые значения таковы:
$$12,\ 70,\ 408,\ 2378,\dots$$
У Pell-множителя есть сопряженные корни
$$\lambda=3+2\sqrt{2},\qquad \mu=3-2\sqrt{2}.$$
Они удовлетворяют \(\lambda+\mu=6\) и \(\lambda\mu=1\), поэтому любая последовательность, построенная из этих решений, подчиняется характеристическому уравнению
$$r^2-6r+1=0.$$
В частности, для периметров имеем
$$p_{k+1}=6p_k-p_{k-1},\qquad p_1=12,\qquad p_2=70.$$
Если \(K\) - наибольший индекс, для которого \(p_K\le N\), то вклад Семейства II равен
$$S_{II}(N)=\sum_{k=1}^{K}p_k.$$
Рекурсия имеет замкнутый вид
$$p_k=\alpha \lambda^k+\beta \mu^k,$$
где \(|\mu|<1\). Значит, главный рост задает \(\alpha\lambda^k\), и хорошая первая оценка выглядит так:
$$K\approx \frac{\log_{10}N-\log_{10}\alpha}{\log_{10}\lambda}.$$
После этого достаточно нескольких монотонных проверок, чтобы поправить \(K\) до точного условия \(p_K\le N<p_{K+1}\). Никакого явного построения числа \(10^{10^{10}}\) не требуется.
Дважды учитывается только периметр \(12\), то есть треугольник \((3,4,5)\). В первом семействе стороны имеют вид
$$t,\qquad \frac{t^2-1}{2},\qquad \frac{t^2+1}{2}.$$
Чтобы катеты одновременно были соседними, нужно
$$\frac{t^2-1}{2}=t+1 \Longrightarrow t^2-2t-3=0 \Longrightarrow t=3.$$
Следовательно, окончательная формула такова:
$$S(N)=S_I(N)+S_{II}(N)-12 \pmod{1234567891}.$$
Семейство I дает периметры \(12,30,56,90\), их сумма равна \(188\).
Семейство II дает \(12,70\), их сумма равна \(82\).
Вычитаем общий периметр \(12\) один раз:
$$S(100)=188+82-12=258.$$
Это совпадает с контрольным значением, используемым в реализациях.
Реализации на C++, Python и Java вычисляют вклад первого семейства целиком по модулю \(1234567891\). Для этого находится \(10^{E/2}\bmod M\), деление на \(2\) и \(3\) заменяется умножением на модульные обратные, а затем напрямую подставляется замкнутая формула для \(S_I(N)\).
Для второго семейства реализация сначала оценивает максимальный допустимый индекс по доминирующему корню \(3+2\sqrt{2}\), а затем уточняет его несколькими монотонными проверками. Сумма рекурсии считается быстрым возведением в степень переходной матрицы \(3\times 3\), в состоянии которой хранятся текущий периметр, предыдущий периметр и накопленная сумма.
В конце обе части складываются по модулю \(1234567891\), после чего один раз вычитается пересечение \(12\).
Для Семейства I требуется \(O(1)\) модульных операций. Для Семейства II нужно \(O(\log K)\) умножений фиксированных матриц \(3\times 3\) и константная по времени коррекция индекса. Память равна \(O(1)\). Итак, стоимость алгоритма определяется только логарифмом номера члена рекурсии, а не астрономическим размером \(N\).
المثلثات التي تدخل في المجموع تنقسم إلى عائلتين لا نهائيتين من ثلاثيات فيثاغورس. في العائلة الأولى يكون الوتر أكبر من أحد الضلعين القائمين بمقدار \(1\) بالضبط، وفي العائلة الثانية يكون الضلعان القائمان عددين متتاليين. المطلوب هو جمع جميع المحيطات المختلفة التي لا تتجاوز \(N=10^{10^{10}}\) ثم أخذ النتيجة بترديد \(1234567891\). وبما أن هذا الحد هائل للغاية، فالحل لا يعتمد على أي تعداد مباشر، بل على صيغ مغلقة، وعلاقة من نوع Pell، وتصحيح واحد فقط للتداخل.
لنرمز إلى مجموع المحيطات المطلوب بـ \(S(N)\)، وإلى الترديد النهائي بـ \(M=1234567891\).
يمكن كتابة مثلث قائم أولي على الصورة
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,\qquad m>n\ge 1.$$
نفرض الآن أن الوتر أكبر من أحد الضلعين القائمين بمقدار \(1\):
$$c=b+1.$$
عندئذ نحصل على
$$m^2+n^2=2mn+1 \Longrightarrow (m-n)^2=1,$$
ومن ثم لا بد أن يكون \(m=n+1\). بالتعويض نحصل على
$$a=2n+1,\qquad b=2n(n+1),\qquad c=2n(n+1)+1.$$
إذا وضعنا \(t=2n+1\)، فإن \(t\) يكون عددا فرديا، ويصبح المحيط
$$p=t+\frac{t^2-1}{2}+\frac{t^2+1}{2}=t(t+1).$$
إذن العائلة الأولى تعطي بالضبط المحيطات \(t(t+1)\) لكل \(t\) فردي مع \(t\ge 3\).
من الشرط \(t(t+1)\le N\) ينتج أن \(t<\sqrt{N}\). وهنا \(N=10^E\) حيث \(E=10^{10}\) عدد زوجي، ولذلك
$$\sqrt{N}=10^{E/2}.$$
لنكتب
$$s=10^{E/2},\qquad q=\frac{s}{2}.$$
القيم الفردية الأصغر من \(s\) هي \(1,3,\dots,s-1\). وبوضع \(t=2j-1\) نحصل على
$$\sum_{j=1}^{q}(2j-1)(2j)=\sum_{j=1}^{q}(4j^2-2j)=\frac{q(q+1)(4q-1)}{3}.$$
لكن الحد \(t=1\) يمثل المثلث المنعدم \((1,0,1)\) ومحيطه \(2\)، ولذلك يجب طرحه. ومن ثم يكون
$$S_I(N)=\frac{q(q+1)(4q-1)}{3}-2.$$
لنأخذ الآن مثلثا قائما ضلعاه القائمان \(x\) و\(x+1\)، ووتره \(c\). عندئذ
$$x^2+(x+1)^2=c^2.$$
عرّف
$$u=2x+1.$$
وبما أن \(u^2=4x^2+4x+1\)، فإن المعادلة السابقة تكافئ معادلة Pell السالبة
$$u^2-2c^2=-1.$$
جميع الحلول الموجبة تتولد بالضرب في \(3+2\sqrt{2}\). والبداية \(7+5\sqrt{2}\) تقابل المثلث \((3,4,5)\). بعد ذلك نحصل على
$$u_{k+1}=3u_k+4c_k,\qquad c_{k+1}=2u_k+3c_k.$$
ومحيط هذا المثلث يساوي
$$p_k=u_k+c_k,$$
ولذلك تكون القيم الأولى
$$12,\ 70,\ 408,\ 2378,\dots$$
للمضاعف Pell جذران مرافقان هما
$$\lambda=3+2\sqrt{2},\qquad \mu=3-2\sqrt{2}.$$
وبما أن \(\lambda+\mu=6\) و\(\lambda\mu=1\)، فإن أي متتالية ناشئة من هذه الحلول تحقق المعادلة المميزة
$$r^2-6r+1=0.$$
وبالأخص تحقق متتالية المحيطات
$$p_{k+1}=6p_k-p_{k-1},\qquad p_1=12,\qquad p_2=70.$$
إذا كان \(K\) هو أكبر فهرس يحقق \(p_K\le N\)، فإن مساهمة العائلة الثانية هي
$$S_{II}(N)=\sum_{k=1}^{K}p_k.$$
للرابطة الخطية صيغة مغلقة من الشكل
$$p_k=\alpha \lambda^k+\beta \mu^k,$$
حيث \(|\mu|<1\). لذلك فإن النمو المسيطر هو \(\alpha\lambda^k\)، ويمكن أخذ تقدير أولي دقيق جدا على الصورة
$$K\approx \frac{\log_{10}N-\log_{10}\alpha}{\log_{10}\lambda}.$$
بعد ذلك تكفي بضع مقارنات رتيبة لتصحيح \(K\) حتى يتحقق الشرط الدقيق \(p_K\le N<p_{K+1}\). وبهذا لا نحتاج أبدا إلى بناء عدد مثل \(10^{10^{10}}\) بشكل صريح.
المحيط الوحيد الذي يُحسب مرتين هو \(12\)، وهو محيط المثلث \((3,4,5)\). في العائلة الأولى تكون الأضلاع
$$t,\qquad \frac{t^2-1}{2},\qquad \frac{t^2+1}{2}.$$
ولكي يكون الضلعان القائمان متتاليين أيضا، لا بد من تحقق
$$\frac{t^2-1}{2}=t+1 \Longrightarrow t^2-2t-3=0 \Longrightarrow t=3.$$
إذن الصيغة النهائية هي
$$S(N)=S_I(N)+S_{II}(N)-12 \pmod{1234567891}.$$
العائلة الأولى تعطي المحيطات \(12,30,56,90\)، ومجموعها \(188\).
العائلة الثانية تعطي \(12,70\)، ومجموعها \(82\).
بعد طرح المحيط المشترك \(12\) مرة واحدة نحصل على
$$S(100)=188+82-12=258.$$
وهذه هي نفس قيمة التحقق الصغيرة المستخدمة في التنفيذات.
تنفذ تطبيقات C++ وPython وJava حساب العائلة الأولى بالكامل تحت الترديد \(1234567891\). فهي تحسب \(10^{E/2}\bmod M\)، وتستبدل القسمة على \(2\) و\(3\) بمعكوسين تعديليين، ثم تطبق الصيغة المغلقة لـ \(S_I(N)\) مباشرة.
أما في العائلة الثانية، فيجري أولا تقدير أكبر فهرس مسموح به انطلاقا من الجذر المسيطر \(3+2\sqrt{2}\)، ثم يُصحح هذا التقدير ببضع مقارنات رتيبة. وبعد ذلك يُحسب مجموع المتتالية بواسطة الرفع السريع لمصفوفة انتقال \(3\times 3\) تخزن في حالتها المحيط الحالي والمحيط السابق والمجموع التراكمي.
وفي النهاية تُجمع النتيجتان تحت الترديد \(1234567891\)، ثم يُطرح التداخل \(12\) مرة واحدة فقط.
العائلة الأولى تحتاج إلى \(O(1)\) من العمليات التعديلية. أما العائلة الثانية فتحتاج إلى \(O(\log K)\) من ضرب مصفوفات ثابتة الحجم \(3\times 3\)، مع تصحيح زمني ثابت للفهرس. استهلاك الذاكرة هو \(O(1)\). لذلك فإن زمن التنفيذ يعتمد على لوغاريتم فهرس المتتالية، لا على الحجم الفلكي لـ \(N\).