We want the number of primitive integer triangles with perimeter at most \(N\), where “primitive” means
$$\gcd(a,b,c)=1.$$
The code does not generate triangles one by one. Instead, it first counts all integer triangles by perimeter using a closed formula, then removes scaled copies with Möbius inversion.
Let \(T(p)\) be the number of integer triangles with perimeter exactly \(p\), written in sorted form \(a\le b\le c\) and
$$a+b+c=p,\qquad a+b>c.$$
A convenient way to count them is to start from all partitions of \(p\) into three positive parts, then subtract the non-triangles.
All partitions into three positive parts. The number of triples \(a\le b\le c\) with \(a+b+c=p\) is the classical partition formula
$$Q(p)=\left\lfloor\frac{p^2+3}{12}\right\rfloor.$$
Invalid triples. A partition fails to be a triangle exactly when \(c\ge a+b\). If we set \(d=a+b\), then \(d\le\lfloor p/2\rfloor\), and the number of ordered-by-size pairs \(a\le b\) with \(a+b=d\) is \(\lfloor d/2\rfloor\). Hence the number of invalid triples is
$$I(p)=\sum_{d=2}^{\lfloor p/2\rfloor}\left\lfloor\frac d2\right\rfloor =\left\lfloor\frac{\lfloor p/2\rfloor^2}{4}\right\rfloor.$$
Therefore
$$T(p)=Q(p)-I(p).$$
After simplifying by parity, this becomes the compact formula used in code:
For even \(p\):
$$T(p)=\left\lfloor\frac{p^2+24}{48}\right\rfloor,$$
For odd \(p\):
$$T(p)=\left\lfloor\frac{(p+3)^2+24}{48}\right\rfloor.$$
The partitions of \(12\) into three positive nondecreasing parts are
$$\begin{aligned} &(1,1,10),(1,2,9),(1,3,8),(1,4,7),(1,5,6),\\ &(2,2,8),(2,3,7),(2,4,6),(2,5,5),\\ &(3,3,6),(3,4,5),(4,4,4). \end{aligned}$$
The first nine fail the triangle inequality. The last three are valid:
$$T(12)=3,$$
corresponding to
$$ (2,5,5),\qquad (3,4,5),\qquad (4,4,4). $$
The formula agrees:
$$T(12)=\left\lfloor\frac{12^2+24}{48}\right\rfloor=\left\lfloor\frac{168}{48}\right\rfloor=3.$$
Let
$$A(n)=\sum_{p\le n} T(p).$$
Then \(A(n)\) counts all integer triangles with perimeter at most \(n\), primitive or not. The code builds this array as a prefix sum of the closed formula above.
Every integer triangle has a unique gcd \(d\). Dividing all three sides by \(d\) gives a unique primitive triangle. Conversely, multiplying a primitive triangle by \(d\) produces a non-primitive one.
For exact perimeter this means “all triangles with perimeter \(p\)” are obtained by scaling primitive triangles whose primitive perimeter divides \(p\). Summing over all perimeters up to \(n\) gives the cumulative identity
$$A(n)=\sum_{d\ge1} P\!\left(\left\lfloor\frac nd\right\rfloor\right),$$
where \(P(n)\) is the number of primitive triangles with perimeter at most \(n\).
This is exactly a divisor-sum transform, so Möbius inversion yields
$$P(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac nd\right\rfloor\right).$$
That is the final formula implemented by the solver.
The triangle \((6,8,10)\) is not primitive because its gcd is \(2\); dividing by \(2\) gives the primitive triangle \((3,4,5)\). Likewise, \((2,4,4)\) comes from the primitive triangle \((1,2,2)\). The Möbius sum corrects exactly for the overcount caused by all such scaled copies.
Closed formula. all_triangles_with_perimeter(p) evaluates the parity-based formula for
\(T(p)\).
Möbius sieve. mobius_up_to() computes \(\mu(1),\dots,\mu(N)\) with a linear sieve.
Prefix of all triangles. prefix_all[n] stores \(A(n)\).
Primitive answer. solve() evaluates
$$P(N)=\sum_{d=1}^{N}\mu(d)\,A\!\left(\left\lfloor\frac Nd\right\rfloor\right).$$
Validation. The source compares the fast method to a brute-force triangle generator for perimeter limits \(30,50,100,150,250\). For example, the primitive cumulative count at \(N=30\) is
$$P(30)=179.$$
The linear sieve for \(\mu\) costs \(O(N)\) time and \(O(N)\) memory. Building the prefix array \(A(n)\) is another \(O(N)\), and the Möbius inversion sum is a final \(O(N)\) pass. So the total complexity is near-linear:
$$O(N)\text{ time},\qquad O(N)\text{ memory}.$$
Gesucht ist die Anzahl primitiver ganzzahliger Dreiecke mit Umfang höchstens \(N\), wobei „primitiv“ bedeutet
$$\gcd(a,b,c)=1.$$
Der Code erzeugt keine Dreiecke einzeln. Stattdessen zählt er zuerst alle ganzzahligen Dreiecke nach Umfang über eine geschlossene Formel und entfernt anschließend skalierte Vielfache per Möbius-Inversion.
Sei \(T(p)\) die Anzahl der ganzzahligen Dreiecke mit Umfang genau \(p\), in sortierter Form \(a\le b\le c\) und
$$a+b+c=p,\qquad a+b>c.$$
Bequemerweise zählt man zunächst alle Zerlegungen von \(p\) in drei positive Teile und zieht dann die Nicht-Dreiecke ab.
Alle Partitionen in drei positive Teile. Die Anzahl der Tripel \(a\le b\le c\) mit \(a+b+c=p\) ist die klassische Partitionsformel
$$Q(p)=\left\lfloor\frac{p^2+3}{12}\right\rfloor.$$
Ungültige Tripel. Eine Partition ist genau dann kein Dreieck, wenn \(c\ge a+b\). Setzt man \(d=a+b\), dann gilt \(d\le\lfloor p/2\rfloor\), und die Zahl der Paare \(a\le b\) mit \(a+b=d\) ist \(\lfloor d/2\rfloor\). Also ist die Anzahl ungültiger Tripel
$$I(p)=\sum_{d=2}^{\lfloor p/2\rfloor}\left\lfloor\frac d2\right\rfloor =\left\lfloor\frac{\lfloor p/2\rfloor^2}{4}\right\rfloor.$$
Damit folgt
$$T(p)=Q(p)-I(p).$$
Nach Vereinfachung nach der Parität von \(p\) erhält man genau die im Code verwendete Formel:
Für gerades \(p\):
$$T(p)=\left\lfloor\frac{p^2+24}{48}\right\rfloor,$$
Für ungerades \(p\):
$$T(p)=\left\lfloor\frac{(p+3)^2+24}{48}\right\rfloor.$$
Die Partitionen von \(12\) in drei positive, nicht absteigende Teile sind
$$\begin{aligned} &(1,1,10),(1,2,9),(1,3,8),(1,4,7),(1,5,6),\\ &(2,2,8),(2,3,7),(2,4,6),(2,5,5),\\ &(3,3,6),(3,4,5),(4,4,4). \end{aligned}$$
Die ersten neun verletzen die Dreiecksungleichung. Gültig bleiben nur
$$T(12)=3,$$
nämlich
$$ (2,5,5),\qquad (3,4,5),\qquad (4,4,4). $$
Die Formel bestätigt das:
$$T(12)=\left\lfloor\frac{12^2+24}{48}\right\rfloor=\left\lfloor\frac{168}{48}\right\rfloor=3.$$
Definiere
$$A(n)=\sum_{p\le n} T(p).$$
Dann zählt \(A(n)\) alle ganzzahligen Dreiecke mit Umfang höchstens \(n\), primitive wie nicht-primitive. Der Code baut dieses Feld als Präfixsumme der geschlossenen Formel auf.
Jedes ganzzahlige Dreieck besitzt einen eindeutigen ggT \(d\). Teilt man alle drei Seiten durch \(d\), erhält man ein eindeutiges primitives Dreieck. Umgekehrt erzeugt Multiplikation eines primitiven Dreiecks mit \(d\) ein nicht-primitives.
Für exakte Umfänge bedeutet das: Alle Dreiecke mit Umfang \(p\) entstehen durch Skalierung primitiver Dreiecke, deren primitiver Umfang \(p\) teilt. Über alle Umfänge bis \(n\) aufsummiert ergibt das
$$A(n)=\sum_{d\ge1} P\!\left(\left\lfloor\frac nd\right\rfloor\right),$$
wobei \(P(n)\) die Anzahl primitiver Dreiecke mit Umfang höchstens \(n\) ist.
Das ist genau eine Divisorsumme, also liefert Möbius-Inversion
$$P(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac nd\right\rfloor\right).$$
Diese Formel implementiert der Solver direkt.
Das Dreieck \((6,8,10)\) ist nicht primitiv, denn sein ggT ist \(2\); nach Division durch \(2\) erhält man das primitive Dreieck \((3,4,5)\). Ebenso stammt \((2,4,4)\) vom primitiven Dreieck \((1,2,2)\). Die Möbius-Summe korrigiert genau das Überzählen, das durch solche skalierten Kopien entsteht.
Geschlossene Formel. all_triangles_with_perimeter(p) berechnet die Paritätsformel für
\(T(p)\).
Möbius-Sieb. mobius_up_to() berechnet \(\mu(1),\dots,\mu(N)\) per linearem Sieb.
Präfix aller Dreiecke. prefix_all[n] speichert \(A(n)\).
Primitive Antwort. solve() wertet
$$P(N)=\sum_{d=1}^{N}\mu(d)\,A\!\left(\left\lfloor\frac Nd\right\rfloor\right)$$
aus.
Validierung. Die Quelle vergleicht die schnelle Methode mit einem Brute-Force-Generator für die Umfangsgrenzen \(30,50,100,150,250\). Zum Beispiel gilt
$$P(30)=179.$$
Das lineare Sieb für \(\mu\) kostet \(O(N)\) Zeit und \(O(N)\) Speicher. Der Aufbau des Präfixarrays \(A(n)\) ist nochmals \(O(N)\), und die Möbius-Summe ist ein letzter \(O(N)\)-Durchlauf. Insgesamt also nahezu linear:
$$O(N)\text{ Zeit},\qquad O(N)\text{ Speicher}.$$
Çevresi en fazla \(N\) olan ilkel tam sayı üçgenlerin sayısı istenir. “İlkel” demek
$$\gcd(a,b,c)=1$$
demektir. Kod üçgenleri tek tek üretmez; önce her çevre için tüm tam sayı üçgenleri kapalı formülle sayar, sonra ölçeklenmiş kopyaları Möbius terslemesiyle ayıklar.
\(T(p)\), çevresi tam olarak \(p\) olan tam sayı üçgenlerin sayısı olsun. Kenarları sıralı düşünürüz:
$$a\le b\le c,\qquad a+b+c=p,\qquad a+b>c.$$
Sayımı doğrudan yapmak yerine önce \(p\)'nin üç pozitif parçaya tüm ayrışımlarını sayıp, üçgen olmayanları çıkarırız.
Üç pozitif parçaya tüm ayrışımlar. \(a\le b\le c\) ve \(a+b+c=p\) koşulunu sağlayan üçlü sayısı klasik partition formülüyle
$$Q(p)=\left\lfloor\frac{p^2+3}{12}\right\rfloor$$
olur.
Geçersiz üçlüler. Bir ayrışım tam olarak \(c\ge a+b\) ise üçgen değildir. \(d=a+b\) dersek \(d\le\lfloor p/2\rfloor\) olur ve \(a\le b\), \(a+b=d\) koşulunu sağlayan çift sayısı \(\lfloor d/2\rfloor\)'dür. Dolayısıyla geçersiz üçlü sayısı
$$I(p)=\sum_{d=2}^{\lfloor p/2\rfloor}\left\lfloor\frac d2\right\rfloor =\left\lfloor\frac{\lfloor p/2\rfloor^2}{4}\right\rfloor$$
olur. Böylece
$$T(p)=Q(p)-I(p).$$
Bu ifade pariteye göre sadeleşince kodun kullandığı kapalı form gelir:
Çift \(p\) için
$$T(p)=\left\lfloor\frac{p^2+24}{48}\right\rfloor,$$
Tek \(p\) için
$$T(p)=\left\lfloor\frac{(p+3)^2+24}{48}\right\rfloor.$$
\(12\)'nin üç pozitif, artmayan olmayan parçaya ayrışımları şunlardır:
$$\begin{aligned} &(1,1,10),(1,2,9),(1,3,8),(1,4,7),(1,5,6),\\ &(2,2,8),(2,3,7),(2,4,6),(2,5,5),\\ &(3,3,6),(3,4,5),(4,4,4). \end{aligned}$$
İlk dokuzu üçgen eşitsizliğini bozduğu için geçersizdir. Geriye üç geçerli üçgen kalır:
$$T(12)=3,$$
yani
$$ (2,5,5),\qquad (3,4,5),\qquad (4,4,4). $$
Kapalı form da aynı sonucu verir:
$$T(12)=\left\lfloor\frac{12^2+24}{48}\right\rfloor=\left\lfloor\frac{168}{48}\right\rfloor=3.$$
Şimdi
$$A(n)=\sum_{p\le n} T(p)$$
olsun. O zaman \(A(n)\), çevresi en fazla \(n\) olan tüm tam sayı üçgenleri sayar; ilkel olup olmamaları önemli değildir. Kod bu diziyi yukarıdaki kapalı formülün prefix toplamı olarak kurar.
Her tam sayı üçgenin tek bir \(\gcd\) değeri \(d\) vardır. Kenarları \(d\)'ye bölersek tek bir ilkel üçgen elde ederiz. Tersine, ilkel bir üçgeni \(d\) ile çarpmak ilkel olmayan bir kopya üretir.
Tam çevre düzeyinde bu, çevresi \(p\) olan tüm üçgenlerin, ilkel çevresi \(p\)'yi bölen üçgenlerin ölçekli halleri olduğunu söyler. Tüm çevreler \(n\)'ye kadar toplanınca kümülatif özdeşlik gelir:
$$A(n)=\sum_{d\ge1} P\!\left(\left\lfloor\frac nd\right\rfloor\right),$$
burada \(P(n)\), çevresi en fazla \(n\) olan ilkel üçgen sayısıdır.
Bu tam bir bölen toplamı dönüşümüdür; dolayısıyla Möbius terslemesi
$$P(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac nd\right\rfloor\right)$$
formülünü verir. Çözücünün hesapladığı nihai ifade budur.
\((6,8,10)\) üçgeni ilkel değildir, çünkü \(\gcd=2\)'dir; 2'ye böldüğümüzde ilkel \((3,4,5)\) üçgeni gelir. Benzer şekilde \((2,4,4)\), ilkel \((1,2,2)\) üçgeninden türemiştir. Möbius toplamı tam olarak bu tür ölçeklenmiş kopyaların yol açtığı fazla sayımı düzeltir.
Kapalı form. all_triangles_with_perimeter(p), \(T(p)\) için pariteye bağlı formülü
hesaplar.
Möbius eleği. mobius_up_to(), \(\mu(1),\dots,\mu(N)\) değerlerini lineer elek ile üretir.
Tüm üçgenlerin prefix'i. prefix_all[n], \(A(n)\) değerini saklar.
İlkel cevap. solve()
$$P(N)=\sum_{d=1}^{N}\mu(d)\,A\!\left(\left\lfloor\frac Nd\right\rfloor\right)$$
ifadesini toplar.
Doğrulama. Kaynak kod hızlı yöntemi \(30,50,100,150,250\) çevre sınırlarında brute-force üçgen üreticisiyle karşılaştırır. Örneğin
$$P(30)=179.$$
\(\mu\) için lineer elek \(O(N)\) zaman ve \(O(N)\) bellek kullanır. \(A(n)\) prefix dizisini kurmak bir başka \(O(N)\) geçiştir, Möbius toplamı da son bir \(O(N)\) turdur. Toplam karmaşıklık yaklaşık lineerdir:
$$O(N)\text{ zaman},\qquad O(N)\text{ bellek}.$$
Queremos contar triángulos enteros primitivos con perímetro a lo sumo \(N\), donde “primitivo” significa
$$\gcd(a,b,c)=1.$$
El código no genera triángulos uno por uno. Primero cuenta todos los triángulos enteros por perímetro mediante una fórmula cerrada y después elimina las copias escaladas con inversión de Möbius.
Sea \(T(p)\) el número de triángulos enteros con perímetro exacto \(p\), escritos ordenadamente como \(a\le b\le c\) y cumpliendo
$$a+b+c=p,\qquad a+b>c.$$
La forma cómoda de contarlos es empezar por todas las particiones de \(p\) en tres partes positivas y restar las que no forman triángulo.
Todas las particiones en tres partes positivas. El número de ternas \(a\le b\le c\) con \(a+b+c=p\) es
$$Q(p)=\left\lfloor\frac{p^2+3}{12}\right\rfloor.$$
Ternas inválidas. Una partición falla exactamente cuando \(c\ge a+b\). Si escribimos \(d=a+b\), entonces \(d\le\lfloor p/2\rfloor\), y el número de pares \(a\le b\) con \(a+b=d\) es \(\lfloor d/2\rfloor\). Por tanto, el número de ternas inválidas es
$$I(p)=\sum_{d=2}^{\lfloor p/2\rfloor}\left\lfloor\frac d2\right\rfloor =\left\lfloor\frac{\lfloor p/2\rfloor^2}{4}\right\rfloor.$$
Así,
$$T(p)=Q(p)-I(p).$$
Al simplificar según la paridad de \(p\), se obtiene la fórmula compacta usada por el código:
Para \(p\) par:
$$T(p)=\left\lfloor\frac{p^2+24}{48}\right\rfloor,$$
Para \(p\) impar:
$$T(p)=\left\lfloor\frac{(p+3)^2+24}{48}\right\rfloor.$$
Las particiones de \(12\) en tres partes positivas no decrecientes son
$$\begin{aligned} &(1,1,10),(1,2,9),(1,3,8),(1,4,7),(1,5,6),\\ &(2,2,8),(2,3,7),(2,4,6),(2,5,5),\\ &(3,3,6),(3,4,5),(4,4,4). \end{aligned}$$
Las nueve primeras violan la desigualdad triangular. Solo sobreviven
$$T(12)=3,$$
es decir,
$$ (2,5,5),\qquad (3,4,5),\qquad (4,4,4). $$
La fórmula coincide:
$$T(12)=\left\lfloor\frac{12^2+24}{48}\right\rfloor=\left\lfloor\frac{168}{48}\right\rfloor=3.$$
Definimos
$$A(n)=\sum_{p\le n} T(p).$$
Entonces \(A(n)\) cuenta todos los triángulos enteros con perímetro a lo sumo \(n\), primitivos o no. El programa construye este arreglo como prefijo de la fórmula cerrada anterior.
Cada triángulo entero tiene un mcd único \(d\). Si dividimos sus lados por \(d\), obtenemos un triángulo primitivo único. Recíprocamente, multiplicar un triángulo primitivo por \(d\) produce uno no primitivo.
En términos de perímetro exacto, eso significa que todos los triángulos de perímetro \(p\) proceden de escalar triángulos primitivos cuyo perímetro primitivo divide a \(p\). Sumando hasta \(n\) obtenemos
$$A(n)=\sum_{d\ge1} P\!\left(\left\lfloor\frac nd\right\rfloor\right),$$
donde \(P(n)\) es el número de triángulos primitivos con perímetro a lo sumo \(n\).
Esto es exactamente una transformada de divisores, así que la inversión de Möbius da
$$P(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac nd\right\rfloor\right).$$
Esa es la fórmula final implementada por el solucionador.
El triángulo \((6,8,10)\) no es primitivo porque su mcd es \(2\); al dividir por \(2\) aparece el triángulo primitivo \((3,4,5)\). Del mismo modo, \((2,4,4)\) procede del triángulo primitivo \((1,2,2)\). La suma de Möbius corrige exactamente el sobreconteo causado por estas copias escaladas.
Fórmula cerrada. all_triangles_with_perimeter(p) evalúa la fórmula por paridad de
\(T(p)\).
Criba de Möbius. mobius_up_to() calcula \(\mu(1),\dots,\mu(N)\) con una criba lineal.
Prefijo de todos los triángulos. prefix_all[n] almacena \(A(n)\).
Respuesta primitiva. solve() evalúa
$$P(N)=\sum_{d=1}^{N}\mu(d)\,A\!\left(\left\lfloor\frac Nd\right\rfloor\right).$$
Validación. El código compara el método rápido con un generador por fuerza bruta para límites \(30,50,100,150,250\). Por ejemplo,
$$P(30)=179.$$
La criba lineal para \(\mu\) cuesta \(O(N)\) tiempo y \(O(N)\) memoria. Construir el prefijo \(A(n)\) es otro recorrido \(O(N)\), y la suma de Möbius es un último paso \(O(N)\). En total, la complejidad es casi lineal:
$$O(N)\text{ tiempo},\qquad O(N)\text{ memoria}.$$
我们要统计周长不超过 \(N\) 的原始整边三角形个数，其中“原始”指
$$\gcd(a,b,c)=1.$$
代码并不逐个生成三角形，而是先用闭式公式统计每个周长下的全部整边三角形，再用 Möbius 反演去掉所有放大倍数。
设 \(T(p)\) 表示周长恰好为 \(p\) 的整边三角形个数，并约定边长已排序为 \(a\le b\le c\)，满足
$$a+b+c=p,\qquad a+b>c.$$
一种方便的计数办法是：先统计 \(p\) 分拆成三个正整数的所有方式，再减去不能构成三角形的那些。
分成三个正整数的所有分拆。 满足 \(a\le b\le c\) 且 \(a+b+c=p\) 的三元组个数是经典公式
$$Q(p)=\left\lfloor\frac{p^2+3}{12}\right\rfloor.$$
无效三元组。 一个分拆恰好在 \(c\ge a+b\) 时不能构成三角形。若记 \(d=a+b\)，则 \(d\le\lfloor p/2\rfloor\)，而满足 \(a\le b\) 且 \(a+b=d\) 的对数为 \(\lfloor d/2\rfloor\)。因此无效分拆数为
$$I(p)=\sum_{d=2}^{\lfloor p/2\rfloor}\left\lfloor\frac d2\right\rfloor =\left\lfloor\frac{\lfloor p/2\rfloor^2}{4}\right\rfloor.$$
于是
$$T(p)=Q(p)-I(p).$$
按奇偶性化简后，就得到代码中使用的紧凑公式：
当 \(p\) 为偶数时
$$T(p)=\left\lfloor\frac{p^2+24}{48}\right\rfloor,$$
当 \(p\) 为奇数时
$$T(p)=\left\lfloor\frac{(p+3)^2+24}{48}\right\rfloor.$$
\(12\) 分拆成三个正整数且不降序的所有结果为
$$\begin{aligned} &(1,1,10),(1,2,9),(1,3,8),(1,4,7),(1,5,6),\\ &(2,2,8),(2,3,7),(2,4,6),(2,5,5),\\ &(3,3,6),(3,4,5),(4,4,4). \end{aligned}$$
前九个都违反三角不等式，只有后三个有效，因此
$$T(12)=3,$$
也就是
$$ (2,5,5),\qquad (3,4,5),\qquad (4,4,4). $$
闭式公式给出的结果完全一致：
$$T(12)=\left\lfloor\frac{12^2+24}{48}\right\rfloor=\left\lfloor\frac{168}{48}\right\rfloor=3.$$
定义
$$A(n)=\sum_{p\le n} T(p).$$
那么 \(A(n)\) 就是周长不超过 \(n\) 的全部整边三角形个数，不区分是否原始。代码把它作为闭式公式的前缀和数组来构造。
每个整边三角形都有唯一的公因数 \(d\)。把三条边都除以 \(d\)，得到唯一的原始三角形；反过来，把一个原始三角形乘以 \(d\)，就得到一个非原始三角形。
在“精确周长”层面，这意味着周长为 \(p\) 的所有三角形，都是某些原始周长整除 \(p\) 的原始三角形放大而来。把所有周长 累加到 \(n\)，得到
$$A(n)=\sum_{d\ge1} P\!\left(\left\lfloor\frac nd\right\rfloor\right),$$
其中 \(P(n)\) 表示周长不超过 \(n\) 的原始三角形个数。
这正是一个除数和变换，所以 Möbius 反演给出
$$P(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac nd\right\rfloor\right).$$
这就是求解器最终实现的公式。
\((6,8,10)\) 不是原始三角形，因为其公因数是 \(2\)；除以 \(2\) 后得到原始三角形 \((3,4,5)\)。类似地， \((2,4,4)\) 来自原始三角形 \((1,2,2)\)。Möbius 求和正是用来校正这些放大副本造成的重复计数。
闭式公式。 all_triangles_with_perimeter(p) 计算 \(T(p)\) 的奇偶分段公式。
Möbius 筛。 mobius_up_to() 用线性筛求出 \(\mu(1),\dots,\mu(N)\)。
全部三角形前缀和。 prefix_all[n] 存储 \(A(n)\)。
原始答案。 solve() 计算
$$P(N)=\sum_{d=1}^{N}\mu(d)\,A\!\left(\left\lfloor\frac Nd\right\rfloor\right).$$
校验。 源码把快速算法与暴力枚举在 \(30,50,100,150,250\) 这些周长上进行比较。例如
$$P(30)=179.$$
Möbius 线性筛需要 \(O(N)\) 时间和 \(O(N)\) 内存。构造 \(A(n)\) 前缀数组又是一次 \(O(N)\) 遍历，最后的 Möbius 求和仍是 \(O(N)\)。因此总复杂度接近线性：
$$O(N)\text{ 时间},\qquad O(N)\text{ 内存}.$$
Нужно посчитать число примитивных целочисленных треугольников с периметром не больше \(N\), где «примитивный» означает
$$\gcd(a,b,c)=1.$$
Код не перебирает треугольники по одному. Он сначала считает все целочисленные треугольники по периметру по замкнутой формуле, а затем убирает масштабированные копии с помощью инверсии Мёбиуса.
Пусть \(T(p)\) — число целочисленных треугольников с точным периметром \(p\), записанных в упорядоченном виде \(a\le b\le c\) и удовлетворяющих
$$a+b+c=p,\qquad a+b>c.$$
Удобно сначала посчитать все разбиения числа \(p\) на три положительные части, а затем вычесть те, которые не дают треугольник.
Все разбиения на три положительные части. Число троек \(a\le b\le c\) при \(a+b+c=p\) задаётся классической формулой
$$Q(p)=\left\lfloor\frac{p^2+3}{12}\right\rfloor.$$
Неверные тройки. Разбиение не является треугольником тогда и только тогда, когда \(c\ge a+b\). Обозначив \(d=a+b\), получаем \(d\le\lfloor p/2\rfloor\), а число пар \(a\le b\) с \(a+b=d\) равно \(\lfloor d/2\rfloor\). Поэтому число неверных троек равно
$$I(p)=\sum_{d=2}^{\lfloor p/2\rfloor}\left\lfloor\frac d2\right\rfloor =\left\lfloor\frac{\lfloor p/2\rfloor^2}{4}\right\rfloor.$$
Следовательно,
$$T(p)=Q(p)-I(p).$$
После упрощения по чётности \(p\) получаем компактную формулу из кода:
Для чётного \(p\):
$$T(p)=\left\lfloor\frac{p^2+24}{48}\right\rfloor,$$
Для нечётного \(p\):
$$T(p)=\left\lfloor\frac{(p+3)^2+24}{48}\right\rfloor.$$
Разбиения числа \(12\) на три положительные неубывающие части таковы:
$$\begin{aligned} &(1,1,10),(1,2,9),(1,3,8),(1,4,7),(1,5,6),\\ &(2,2,8),(2,3,7),(2,4,6),(2,5,5),\\ &(3,3,6),(3,4,5),(4,4,4). \end{aligned}$$
Первые девять нарушают неравенство треугольника. Остаются только
$$T(12)=3,$$
то есть
$$ (2,5,5),\qquad (3,4,5),\qquad (4,4,4). $$
Замкнутая формула даёт тот же ответ:
$$T(12)=\left\lfloor\frac{12^2+24}{48}\right\rfloor=\left\lfloor\frac{168}{48}\right\rfloor=3.$$
Определим
$$A(n)=\sum_{p\le n} T(p).$$
Тогда \(A(n)\) считает все целочисленные треугольники с периметром не больше \(n\), примитивные и непримитивные. Код строит этот массив как префиксную сумму замкнутой формулы выше.
У каждого целочисленного треугольника есть единственный общий делитель \(d\). Деление всех сторон на \(d\) даёт единственный примитивный треугольник. Обратно, умножение примитивного треугольника на \(d\) создаёт непримитивную копию.
Для точного периметра это означает, что все треугольники периметра \(p\) получаются масштабированием примитивных треугольников, чей примитивный периметр делит \(p\). После суммирования по всем периметрам до \(n\) получаем
$$A(n)=\sum_{d\ge1} P\!\left(\left\lfloor\frac nd\right\rfloor\right),$$
где \(P(n)\) — число примитивных треугольников с периметром не больше \(n\).
Это точная сумма по делителям, поэтому инверсия Мёбиуса даёт
$$P(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac nd\right\rfloor\right).$$
Именно эту формулу реализует программа.
Треугольник \((6,8,10)\) непримитивен, потому что его общий делитель равен \(2\); после деления на \(2\) получаем примитивный \((3,4,5)\). Аналогично \((2,4,4)\) возникает из примитивного \((1,2,2)\). Сумма Мёбиуса точно корректирует переучёт, вызванный такими масштабированными копиями.
Замкнутая формула. all_triangles_with_perimeter(p) вычисляет формулу для \(T(p)\) по
чётности.
Решето Мёбиуса. mobius_up_to() находит \(\mu(1),\dots,\mu(N)\) линейным решетом.
Префикс всех треугольников. prefix_all[n] хранит \(A(n)\).
Примитивный ответ. solve() вычисляет
$$P(N)=\sum_{d=1}^{N}\mu(d)\,A\!\left(\left\lfloor\frac Nd\right\rfloor\right).$$
Проверка. Исходник сравнивает быстрый метод с brute-force-перебором для ограничений \(30,50,100,150,250\). Например,
$$P(30)=179.$$
Линейное решето для \(\mu\) требует \(O(N)\) времени и \(O(N)\) памяти. Построение префиксного массива \(A(n)\) — ещё один проход \(O(N)\), а сумма Мёбиуса — последний проход \(O(N)\). Итого почти линейная сложность:
$$O(N)\text{ времени},\qquad O(N)\text{ памяти}.$$
نريد حساب عدد المثلثات الصحيحة البدائية التي لا يتجاوز محيطها \(N\)، حيث تعني كلمة “بدائي” أن
$$\gcd(a,b,c)=1.$$
لا تقوم الشيفرة بتوليد المثلثات واحداً واحداً، بل تحسب أولاً جميع المثلثات الصحيحة لكل محيط بصيغة مغلقة، ثم تزيل النسخ المكبرة باستخدام عكس Möbius.
لتكن \(T(p)\) عدد المثلثات الصحيحة ذات المحيط الدقيق \(p\)، بعد ترتيب الأضلاع بحيث \(a\le b\le c\) ومع الشرطين
$$a+b+c=p,\qquad a+b>c.$$
الطريقة الأنسب هي أن نعدّ أولاً جميع تقسيمات \(p\) إلى ثلاثة أجزاء موجبة، ثم نطرح منها الحالات التي لا تكوّن مثلثاً.
جميع التقسيمات إلى ثلاثة أجزاء موجبة. عدد الثلاثيات \(a\le b\le c\) التي تحقق \(a+b+c=p\) هو الصيغة الكلاسيكية
$$Q(p)=\left\lfloor\frac{p^2+3}{12}\right\rfloor.$$
الثلاثيات غير الصالحة. يفشل التقسيم في إعطاء مثلث بالضبط عندما \(c\ge a+b\). إذا وضعنا \(d=a+b\)، فسنحصل على \(d\le\lfloor p/2\rfloor\)، وعدد الأزواج \(a\le b\) مع \(a+b=d\) هو \(\lfloor d/2\rfloor\). لذلك يكون عدد الثلاثيات غير الصالحة
$$I(p)=\sum_{d=2}^{\lfloor p/2\rfloor}\left\lfloor\frac d2\right\rfloor =\left\lfloor\frac{\lfloor p/2\rfloor^2}{4}\right\rfloor.$$
ومن ثم
$$T(p)=Q(p)-I(p).$$
وبعد التبسيط بحسب فردية \(p\) نحصل على الصيغة المضغوطة التي يستخدمها الكود:
إذا كان \(p\) زوجياً:
$$T(p)=\left\lfloor\frac{p^2+24}{48}\right\rfloor,$$
وإذا كان \(p\) فردياً:
$$T(p)=\left\lfloor\frac{(p+3)^2+24}{48}\right\rfloor.$$
تقسيمات \(12\) إلى ثلاثة أجزاء موجبة غير متناقصة هي
$$\begin{aligned} &(1,1,10),(1,2,9),(1,3,8),(1,4,7),(1,5,6),\\ &(2,2,8),(2,3,7),(2,4,6),(2,5,5),\\ &(3,3,6),(3,4,5),(4,4,4). \end{aligned}$$
أول تسعة منها تخالف متباينة المثلث، لذلك لا يبقى إلا
$$T(12)=3,$$
أي المثلثات
$$ (2,5,5),\qquad (3,4,5),\qquad (4,4,4). $$
والصيغة المغلقة تعطي النتيجة نفسها:
$$T(12)=\left\lfloor\frac{12^2+24}{48}\right\rfloor=\left\lfloor\frac{168}{48}\right\rfloor=3.$$
لنعرّف
$$A(n)=\sum_{p\le n} T(p).$$
إذن \(A(n)\) يعدّ جميع المثلثات الصحيحة التي لا يتجاوز محيطها \(n\)، سواء كانت بدائية أم لا. ويبني الكود هذه الدالة كتجميع تراكمي للصيغة المغلقة السابقة.
كل مثلث صحيح يملك قاسماً مشتركاً أعظم وحيداً \(d\). وإذا قسمنا الأضلاع الثلاثة على \(d\) نحصل على مثلث بدائي وحيد. وبالعكس، فإن ضرب مثلث بدائي في \(d\) ينتج نسخة غير بدائية.
على مستوى المحيط الدقيق، يعني هذا أن جميع المثلثات ذات المحيط \(p\) تأتي من تكبير مثلثات بدائية يكون محيطها البدائي قاسماً لـ \(p\). وبعد الجمع حتى \(n\) نحصل على العلاقة التراكمية
$$A(n)=\sum_{d\ge1} P\!\left(\left\lfloor\frac nd\right\rfloor\right),$$
حيث \(P(n)\) هو عدد المثلثات البدائية ذات المحيط حتى \(n\).
وهذه بالضبط صيغة مجموع قواسم، ومن ثم يعطي عكس Möbius
$$P(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac nd\right\rfloor\right).$$
وهذه هي الصيغة النهائية التي يطبقها البرنامج.
المثلث \((6,8,10)\) ليس بدائياً لأن القاسم المشترك الأعظم له هو \(2\)؛ وبعد القسمة على \(2\) نحصل على المثلث البدائي \((3,4,5)\). وكذلك \((2,4,4)\) يأتي من المثلث البدائي \((1,2,2)\). ومجموع Möbius هو ما يصحح بدقة الزيادة الناتجة عن هذه النسخ المكبرة.
الصيغة المغلقة. تحسب all_triangles_with_perimeter(p) قيمة \(T(p)\) حسب فردية \(p\).
غربال Möbius. تحسب mobius_up_to() القيم \(\mu(1),\dots,\mu(N)\) باستخدام غربال خطي.
التراكم لكل المثلثات. تخزن prefix_all[n] القيمة \(A(n)\).
الجواب البدائي. تقوم solve() بحساب
$$P(N)=\sum_{d=1}^{N}\mu(d)\,A\!\left(\left\lfloor\frac Nd\right\rfloor\right).$$
التحقق. يقارن المصدر الطريقة السريعة مع مولد brute-force عند الحدود \(30,50,100,150,250\). ومن القيم المفيدة مثلاً
$$P(30)=179.$$
الغربال الخطي لـ \(\mu\) يكلف \(O(N)\) زمناً و\(O(N)\) ذاكرة. وبناء التراكم \(A(n)\) هو مرور إضافي \(O(N)\)، ثم يأتي مجموع Möbius في مرور أخير \(O(N)\). لذلك فالتعقيد الكلي شبه خطي:
$$O(N)\text{ زمن},\qquad O(N)\text{ ذاكرة}.$$