For each positive integer \(m\), let \(P(m)\) denote the sum of the perimeters of all integer-sided quadrilaterals whose maximal possible area is exactly \(m\). The target quantity is
$$SP(n)=\sum_{m=1}^{n} P(m).$$
The implementations verify the approach with the checkpoints \(SP(10)=186\) and \(SP(100)=23238\), then evaluate the full case \(n=10^6\).
The geometry becomes manageable after rewriting the maximal-area condition as a factorization problem for \(m^2\).
For side lengths \(a,b,c,d\), write the semiperimeter as
$$s=\frac{a+b+c+d}{2}.$$
Among all quadrilaterals with these side lengths, the area is maximized when the quadrilateral is cyclic. Brahmagupta's formula then gives
$$A_{\max}^2=(s-a)(s-b)(s-c)(s-d).$$
Problem 681 asks us to study the cases where \(A_{\max}=m\), so the defining equation is
$$m^2=(s-a)(s-b)(s-c)(s-d).$$
Set
$$x=s-a,\qquad y=s-b,\qquad z=s-c,\qquad w=s-d.$$
Then the area condition becomes
$$xyzw=m^2.$$
The side lengths are recovered by solving the linear system:
$$a=\frac{-x+y+z+w}{2},\qquad b=\frac{x-y+z+w}{2},$$
$$c=\frac{x+y-z+w}{2},\qquad d=\frac{x+y+z-w}{2}.$$
The perimeter is especially simple:
$$a+b+c+d=x+y+z+w.$$
So once a valid quadruple \((x,y,z,w)\) is known, its contribution to \(P(m)\) is exactly the sum \(x+y+z+w\).
Permuting the side lengths only permutes \(x,y,z,w\), so we sort them and count only
$$x\ge y\ge z\ge w\ge 1.$$
Under this ordering, \(a\) is the smallest recovered side because it subtracts the largest term \(x\). Therefore positivity of all four sides is equivalent to the single inequality
$$a>0\iff x<y+z+w.$$
Integrality is controlled by parity. Since each recovered side is half of an integer expression, it is enough to require
$$x+y+z+w\equiv 0 \pmod{2}.$$
Hence valid quadrilaterals with maximal area \(m\) are in bijection with ordered positive integer quadruples satisfying
$$xyzw=m^2,\qquad x\ge y\ge z\ge w,\qquad x<y+z+w,\qquad x+y+z+w\equiv 0\pmod{2}.$$
If
$$m=\prod_i p_i^{e_i},$$
then
$$m^2=\prod_i p_i^{2e_i}.$$
Every candidate value \(w,z,y,x\) must therefore be a divisor of \(m^2\). The implementation generates the full divisor list of \(m^2\), sorts it, chooses \(w\le z\le y\), and determines the last factor by
$$x=\frac{m^2}{wzy}.$$
This automatically enforces the product constraint, and the sorted divisor list makes monotone early stopping possible: once a partial product is too large, all later divisors are too large as well.
Here \(m^2=16\). The ordered factor quadruples \((x,y,z,w)\) with product \(16\) are
$$\begin{aligned} &(16,1,1,1),\\ &(8,2,1,1),\\ &(4,4,1,1),\\ &(4,2,2,1),\\ &(2,2,2,2). \end{aligned}$$
The first two fail \(x<y+z+w\). The fourth has odd perimeter \(4+2+2+1=9\), so it does not produce integer side lengths. The remaining two are valid:
$$\begin{aligned} (4,4,1,1)&\longrightarrow (a,b,c,d)=(1,1,4,4),\quad x+y+z+w=10,\\ (2,2,2,2)&\longrightarrow (a,b,c,d)=(2,2,2,2),\quad x+y+z+w=8. \end{aligned}$$
Therefore
$$P(4)=10+8=18.$$
For each fixed \(m\), the program adds the perimeters of all valid quadruples to obtain \(P(m)\). The final answer is then
$$SP(n)=\sum_{m=1}^{n}P(m).$$
Because different values of \(m\) are independent, the outer summation is a natural place for parallel execution.
The C++, Python, and Java implementations begin by preparing prime-factor information for all integers up to \(n\). For a given \(m\), the implementation factors \(m\), doubles the exponents to describe \(m^2\), and recursively generates every divisor of \(m^2\).
After sorting those divisors, the implementation scans candidates in the order \(w\le z\le y\). Whenever a partial product already forces the missing factor to fall below the required order, the loop stops early. If the remaining quotient is divisible by the chosen factors, that quotient becomes \(x\), and the code applies exactly the two mathematical filters derived above: the positivity inequality \(x<y+z+w\) and the parity condition \(x+y+z+w\equiv 0\pmod{2}\).
Each surviving quadruple contributes its perimeter \(x+y+z+w\) to \(P(m)\). The C++ and Java implementations distribute distinct values of \(m\) across worker threads, while the Python implementation reuses the compiled C++ computation path and returns the parsed final result.
Let \(D(m)=\tau(m^2)\) be the number of divisors of \(m^2\). Building the prime-factor table up to \(n\) uses \(O(n)\) memory and \(O(n\log\log n)\) time in the usual sieve analysis, with the C++ version using a linear smallest-prime-factor construction. For one fixed \(m\), generating all divisors costs \(O(D(m))\). The subsequent ordered scan over divisor triples has worst-case \(O(D(m)^3)\) behavior, but the monotone break conditions and divisibility tests cut away most combinations in practice. Extra working memory beyond the sieve is dominated by the divisor list for one value of \(m\).
Für jede positive ganze Zahl \(m\) sei \(P(m)\) die Summe der Umfänge aller ganzzahligen Vierecke, deren maximal mögliche Fläche genau \(m\) ist. Gesucht ist
$$SP(n)=\sum_{m=1}^{n} P(m).$$
Die Implementierungen prüfen den Ansatz zunächst mit \(SP(10)=186\) und \(SP(100)=23238\) und berechnen danach den vollen Fall \(n=10^6\).
Der entscheidende Schritt besteht darin, die Geometrie in ein Faktorisierungsproblem für \(m^2\) umzuschreiben.
Für Seitenlängen \(a,b,c,d\) sei der Semiumfang
$$s=\frac{a+b+c+d}{2}.$$
Unter allen Vierecken mit diesen Seiten ist die Fläche im zyklischen Fall maximal. Dann liefert die Brahmagupta-Formel
$$A_{\max}^2=(s-a)(s-b)(s-c)(s-d).$$
In Problem 681 betrachten wir den Fall \(A_{\max}=m\), also
$$m^2=(s-a)(s-b)(s-c)(s-d).$$
Setze
$$x=s-a,\qquad y=s-b,\qquad z=s-c,\qquad w=s-d.$$
Dann wird die Flächenbedingung zu
$$xyzw=m^2.$$
Die Seiten lassen sich aus \(x,y,z,w\) zurückgewinnen durch
$$a=\frac{-x+y+z+w}{2},\qquad b=\frac{x-y+z+w}{2},$$
$$c=\frac{x+y-z+w}{2},\qquad d=\frac{x+y+z-w}{2}.$$
Für den Umfang gilt besonders einfach
$$a+b+c+d=x+y+z+w.$$
Jedes gültige Tupel \((x,y,z,w)\) liefert also genau den Beitrag \(x+y+z+w\) zu \(P(m)\).
Eine Permutation der Seiten permutiert nur \(x,y,z,w\). Um Mehrfachzählungen zu vermeiden, betrachten wir daher nur
$$x\ge y\ge z\ge w\ge 1.$$
Unter dieser Ordnung ist \(a\) die kleinste rekonstruierte Seite, weil dort der größte Term \(x\) subtrahiert wird. Daher ist die Positivität aller vier Seiten äquivalent zu
$$a>0\iff x<y+z+w.$$
Für Ganzzahligkeit genügt die Paritätsbedingung
$$x+y+z+w\equiv 0 \pmod{2}.$$
Damit stehen die gesuchten Vierecke in Bijektion zu geordneten positiven Vierern mit
$$xyzw=m^2,\qquad x\ge y\ge z\ge w,\qquad x<y+z+w,\qquad x+y+z+w\equiv 0\pmod{2}.$$
Schreibe
$$m=\prod_i p_i^{e_i}.$$
Dann folgt
$$m^2=\prod_i p_i^{2e_i}.$$
Jeder Kandidat \(w,z,y,x\) ist also ein Teiler von \(m^2\). Die Implementierung erzeugt alle Teiler von \(m^2\), sortiert sie, wählt \(w\le z\le y\) und bestimmt den letzten Faktor durch
$$x=\frac{m^2}{wzy}.$$
So ist die Produktbedingung automatisch erfüllt. Außerdem erlaubt die sortierte Teilerliste monotone Abbrüche: Sobald ein Teilprodukt zu groß ist, sind alle späteren Kandidaten ebenfalls zu groß.
Hier ist \(m^2=16\). Die geordneten Faktorvierer \((x,y,z,w)\) mit Produkt \(16\) lauten
$$\begin{aligned} &(16,1,1,1),\\ &(8,2,1,1),\\ &(4,4,1,1),\\ &(4,2,2,1),\\ &(2,2,2,2). \end{aligned}$$
Die ersten beiden verletzen \(x<y+z+w\). Beim vierten Vierer ist der Umfang \(4+2+2+1=9\) ungerade, also entstehen keine ganzzahligen Seiten. Gültig bleiben
$$\begin{aligned} (4,4,1,1)&\longrightarrow (a,b,c,d)=(1,1,4,4),\quad x+y+z+w=10,\\ (2,2,2,2)&\longrightarrow (a,b,c,d)=(2,2,2,2),\quad x+y+z+w=8. \end{aligned}$$
Damit gilt
$$P(4)=10+8=18.$$
Für jedes feste \(m\) summiert das Programm die Umfänge aller gültigen Vierer und erhält so \(P(m)\). Die gesuchte Gesamtgröße ist dann
$$SP(n)=\sum_{m=1}^{n}P(m).$$
Da verschiedene Werte von \(m\) unabhängig voneinander sind, eignet sich gerade die äußere Summe sehr gut für Parallelisierung.
Die C++-, Python- und Java-Implementierungen bereiten zuerst Primfaktorinformationen für alle Zahlen bis \(n\) vor. Für ein gegebenes \(m\) faktorisiert die Implementierung \(m\), verdoppelt die Exponenten für \(m^2\) und erzeugt rekursiv alle Teiler von \(m^2\).
Nach dem Sortieren dieser Teiler werden Kandidaten in der Reihenfolge \(w\le z\le y\) durchlaufen. Erzwingt ein Teilprodukt bereits, dass der fehlende Faktor die Ordnung verletzen würde, endet die jeweilige Schleife sofort. Ist der verbleibende Quotient durch die gewählten Faktoren teilbar, so ist dieser Quotient das zugehörige \(x\), und der Code prüft genau die beiden hergeleiteten Bedingungen: die Positivitätsungleichung \(x<y+z+w\) und die Parität \(x+y+z+w\equiv 0\pmod{2}\).
Jeder verbleibende Vierer trägt seinen Umfang \(x+y+z+w\) zu \(P(m)\) bei. Die C++- und Java-Implementierungen verteilen unterschiedliche Werte von \(m\) auf mehrere Threads, während die Python-Implementierung denselben kompilierten C++-Rechenweg verwendet und nur das Endergebnis zurückgibt.
Sei \(D(m)=\tau(m^2)\) die Anzahl der Teiler von \(m^2\). Die Primfaktortabelle bis \(n\) benötigt \(O(n)\) Speicher und im üblichen Sieb-Modell \(O(n\log\log n)\) Zeit, wobei die C++-Variante eine lineare Konstruktion des kleinsten Primfaktors benutzt. Für ein festes \(m\) kostet das Erzeugen aller Teiler \(O(D(m))\). Der anschließende geordnete Durchlauf über Teilertripel hat im Worst Case \(O(D(m)^3)\), wird in der Praxis aber durch monotone Abbrüche und Teilbarkeitstests stark beschnitten. Zusätzlicher Speicher neben dem Sieb wird im Wesentlichen nur für die Teilerliste eines einzelnen \(m\) gebraucht.
Her pozitif tamsayı \(m\) için \(P(m)\), maksimum mümkün alanı tam olarak \(m\) olan bütün tam kenarlı dörtgenlerin çevreleri toplamı olsun. İstenen büyüklük
$$SP(n)=\sum_{m=1}^{n} P(m).$$
Uygulamalar önce \(SP(10)=186\) ve \(SP(100)=23238\) kontrol noktalarını doğruluyor, ardından tam durum olan \(n=10^6\) için sonucu hesaplıyor.
Ana fikir, geometrik koşulu \(m^2\) için bir çarpanlaştırma problemine dönüştürmektir.
Kenar uzunlukları \(a,b,c,d\) için yarı çevreyi
$$s=\frac{a+b+c+d}{2}$$
olarak yazalım. Bu kenarlara sahip dörtgenler arasında alan, dörtgen çevrel olduğunda maksimum olur. Brahmagupta formülü bu durumda
$$A_{\max}^2=(s-a)(s-b)(s-c)(s-d)$$
sonucunu verir. Problem 681'de \(A_{\max}=m\) olduğundan temel denklem
$$m^2=(s-a)(s-b)(s-c)(s-d)$$
şeklindedir.
Şöyle tanımlayalım:
$$x=s-a,\qquad y=s-b,\qquad z=s-c,\qquad w=s-d.$$
Böylece alan koşulu
$$xyzw=m^2$$
olur. Kenar uzunlukları ters yönde şu şekilde geri elde edilir:
$$a=\frac{-x+y+z+w}{2},\qquad b=\frac{x-y+z+w}{2},$$
$$c=\frac{x+y-z+w}{2},\qquad d=\frac{x+y+z-w}{2}.$$
Çevre için çok sade bir ifade elde ederiz:
$$a+b+c+d=x+y+z+w.$$
Yani geçerli her \((x,y,z,w)\) dörtlüsü, \(P(m)\)'ye tam olarak \(x+y+z+w\) kadar katkı yapar.
Kenarların yer değiştirmesi sadece \(x,y,z,w\)'yi de yer değiştirir. Aynı dörtgeni tekrar saymamak için yalnızca
$$x\ge y\ge z\ge w\ge 1$$
sıralamasını dikkate alırız. Bu düzende en küçük geri kazanılan kenar \(a\)'dır; çünkü en büyük terim olan \(x\) ondan çıkarılır. Dolayısıyla bütün kenarların pozitif olması tek başına
$$a>0\iff x<y+z+w$$
koşuluna denktir. Tamsayılık için ise
$$x+y+z+w\equiv 0 \pmod{2}$$
yeterlidir. Sonuç olarak maksimum alanı \(m\) olan dörtgenler, şu şartları sağlayan sıralı pozitif dörtlülerle bire bir eşleşir:
$$xyzw=m^2,\qquad x\ge y\ge z\ge w,\qquad x<y+z+w,\qquad x+y+z+w\equiv 0\pmod{2}.$$
Eğer
$$m=\prod_i p_i^{e_i}$$
ise
$$m^2=\prod_i p_i^{2e_i}$$
olur. O halde tüm aday değerler \(w,z,y,x\), \(m^2\)'nin bölenleri arasındadır. Uygulama önce \(m^2\)'nin bütün bölenlerini üretir, sıralar, \(w\le z\le y\) seçer ve son çarpanı
$$x=\frac{m^2}{wzy}$$
formülüyle tamamlar. Böylece çarpım koşulu otomatik sağlanır. Ayrıca bölenler sıralı olduğu için, kısmi çarpım fazla büyüdüğü anda daha sonraki bütün adaylar da elenir.
Bu durumda \(m^2=16\). Çarpımı \(16\) olan sıralı \((x,y,z,w)\) dörtlüleri şunlardır:
$$\begin{aligned} &(16,1,1,1),\\ &(8,2,1,1),\\ &(4,4,1,1),\\ &(4,2,2,1),\\ &(2,2,2,2). \end{aligned}$$
İlk iki dörtlü \(x<y+z+w\) şartını bozduğu için geçersizdir. Dördüncü dörtlünün çevresi \(4+2+2+1=9\) tek olduğu için geri kazanılan kenarlar tamsayı olmaz. Geriye iki geçerli durum kalır:
$$\begin{aligned} (4,4,1,1)&\longrightarrow (a,b,c,d)=(1,1,4,4),\quad x+y+z+w=10,\\ (2,2,2,2)&\longrightarrow (a,b,c,d)=(2,2,2,2),\quad x+y+z+w=8. \end{aligned}$$
Dolayısıyla
$$P(4)=10+8=18.$$
Her sabit \(m\) için program, tüm geçerli dörtlülerin çevrelerini toplayarak \(P(m)\)'yi elde eder. Son hedef ise
$$SP(n)=\sum_{m=1}^{n}P(m)$$
ifadesidir. Farklı \(m\) değerleri birbirinden bağımsız olduğu için dış toplam paralelleştirmeye çok uygundur.
C++, Python ve Java uygulamaları önce \(n\)'ye kadar olan tüm sayılar için asal çarpan bilgisi hazırlar. Belirli bir \(m\) için uygulama önce \(m\)'yi çarpanlarına ayırır, üsleri iki katına çıkararak \(m^2\)'yi temsil eder ve sonra \(m^2\)'nin tüm bölenlerini özyinelemeli biçimde üretir.
Bölenler sıralandıktan sonra adaylar \(w\le z\le y\) düzeninde taranır. Bir kısmi çarpım, eksik kalan çarpanın sıralama şartını bozacağını daha baştan gösteriyorsa ilgili döngü hemen kırılır. Kalan bölüm seçilen çarpanlara bölünebiliyorsa bu bölüm \(x\) olur ve kod yalnızca yukarıda türetilen iki matematiksel testi uygular: \(x<y+z+w\) pozitiflik koşulu ve \(x+y+z+w\equiv 0\pmod{2}\) parity testi.
Bu iki testten geçen her dörtlü, çevresi olan \(x+y+z+w\) kadar katkı yapar. C++ ve Java uygulamaları farklı \(m\) değerlerini iş parçacıklarına dağıtır; Python uygulaması ise derlenmiş C++ hesaplama yolunu kullanır ve son sayısal çıktıyı döndürür.
\(D(m)=\tau(m^2)\), yani \(m^2\)'nin bölen sayısı olsun. \(n\)'ye kadar asal çarpan tablosu kurmak \(O(n)\) bellek ve klasik elek analizinde \(O(n\log\log n)\) zaman gerektirir; C++ sürümü bunu lineer en küçük asal çarpan yapısıyla kurar. Sabit bir \(m\) için tüm bölenleri üretmek \(O(D(m))\) maliyetlidir. Ardından gelen sıralı bölen üçlüsü taraması en kötü durumda \(O(D(m)^3)\) olabilir; fakat monoton erken duruşlar ve bölünebilme testleri pratikte kombinasyonların çoğunu eler. Elek dışında ek bellek ihtiyacı esas olarak tek bir \(m\) için tutulan bölen listesidir.
Para cada entero positivo \(m\), sea \(P(m)\) la suma de los perímetros de todos los cuadriláteros de lados enteros cuya área máxima posible es exactamente \(m\). La cantidad buscada es
$$SP(n)=\sum_{m=1}^{n} P(m).$$
Las implementaciones validan el método con los puntos de control \(SP(10)=186\) y \(SP(100)=23238\), y después calculan el caso completo \(n=10^6\).
La clave es transformar la condición geométrica en un problema de factorización de \(m^2\).
Para lados \(a,b,c,d\), escribimos el semiperímetro como
$$s=\frac{a+b+c+d}{2}.$$
Entre todos los cuadriláteros con esos lados, el área es máxima cuando el cuadrilátero es cíclico. Entonces la fórmula de Brahmagupta da
$$A_{\max}^2=(s-a)(s-b)(s-c)(s-d).$$
En el problema 681 interesa el caso \(A_{\max}=m\), de modo que
$$m^2=(s-a)(s-b)(s-c)(s-d).$$
Definimos
$$x=s-a,\qquad y=s-b,\qquad z=s-c,\qquad w=s-d.$$
Con ello, la condición del área se convierte en
$$xyzw=m^2.$$
Las longitudes se recuperan resolviendo
$$a=\frac{-x+y+z+w}{2},\qquad b=\frac{x-y+z+w}{2},$$
$$c=\frac{x+y-z+w}{2},\qquad d=\frac{x+y+z-w}{2}.$$
Además, el perímetro queda
$$a+b+c+d=x+y+z+w.$$
Por lo tanto, cada cuádrupla válida \((x,y,z,w)\) aporta exactamente \(x+y+z+w\) a \(P(m)\).
Permutar los lados solo permuta \(x,y,z,w\), así que para evitar repeticiones imponemos
$$x\ge y\ge z\ge w\ge 1.$$
Bajo ese orden, \(a\) es el lado recuperado más pequeño, porque es el que resta el mayor término \(x\). Por eso la positividad de todos los lados equivale a
$$a>0\iff x<y+z+w.$$
La integridad se reduce a la condición de paridad
$$x+y+z+w\equiv 0 \pmod{2}.$$
Así, los cuadriláteros buscados están en biyección con las cuádruplas ordenadas de enteros positivos que cumplen
$$xyzw=m^2,\qquad x\ge y\ge z\ge w,\qquad x<y+z+w,\qquad x+y+z+w\equiv 0\pmod{2}.$$
Si
$$m=\prod_i p_i^{e_i},$$
entonces
$$m^2=\prod_i p_i^{2e_i}.$$
Cada candidato \(w,z,y,x\) debe ser un divisor de \(m^2\). La implementación genera todos los divisores de \(m^2\), los ordena, elige \(w\le z\le y\) y fija el último factor por
$$x=\frac{m^2}{wzy}.$$
De esa forma la restricción del producto queda incorporada automáticamente, y el orden creciente de los divisores permite cortar pronto cuando un producto parcial ya es demasiado grande.
Aquí \(m^2=16\). Las cuádruplas ordenadas \((x,y,z,w)\) con producto \(16\) son
$$\begin{aligned} &(16,1,1,1),\\ &(8,2,1,1),\\ &(4,4,1,1),\\ &(4,2,2,1),\\ &(2,2,2,2). \end{aligned}$$
Las dos primeras no satisfacen \(x<y+z+w\). La cuarta tiene perímetro impar \(4+2+2+1=9\), así que no produce lados enteros. Permanecen dos casos válidos:
$$\begin{aligned} (4,4,1,1)&\longrightarrow (a,b,c,d)=(1,1,4,4),\quad x+y+z+w=10,\\ (2,2,2,2)&\longrightarrow (a,b,c,d)=(2,2,2,2),\quad x+y+z+w=8. \end{aligned}$$
Por consiguiente,
$$P(4)=10+8=18.$$
Para cada \(m\), el programa suma los perímetros de todas las cuádruplas válidas y obtiene \(P(m)\). La respuesta final es
$$SP(n)=\sum_{m=1}^{n}P(m).$$
Como distintos valores de \(m\) son independientes, el bucle exterior se presta muy bien a la paralelización.
Las implementaciones en C++, Python y Java empiezan preparando información de factorización prima para todos los enteros hasta \(n\). Para un valor dado de \(m\), la implementación factoriza \(m\), duplica los exponentes para describir \(m^2\) y genera recursivamente todos los divisores de \(m^2\).
Después de ordenar esos divisores, la implementación recorre candidatos en el orden \(w\le z\le y\). Si un producto parcial ya obliga a que el factor restante viole el orden requerido, el bucle se corta en ese punto. Cuando el cociente restante es divisible por los factores elegidos, ese cociente es \(x\), y el código aplica exactamente los dos filtros matemáticos obtenidos antes: la desigualdad de positividad \(x<y+z+w\) y la condición de paridad \(x+y+z+w\equiv 0\pmod{2}\).
Cada cuádrupla que supera ambos filtros aporta su perímetro \(x+y+z+w\) a \(P(m)\). Las implementaciones de C++ y Java reparten distintos valores de \(m\) entre varios hilos, mientras que la implementación de Python reutiliza la ruta de cálculo compilada en C++ y devuelve el valor final ya interpretado.
Sea \(D(m)=\tau(m^2)\) el número de divisores de \(m^2\). Construir la tabla de factores primos hasta \(n\) requiere \(O(n)\) memoria y \(O(n\log\log n)\) tiempo en el análisis usual del cribado, aunque la versión en C++ usa una construcción lineal del menor factor primo. Para un \(m\) fijo, generar todos los divisores cuesta \(O(D(m))\). El recorrido ordenado sobre ternas de divisores tiene peor caso \(O(D(m)^3)\), pero en la práctica los cortes monótonos y las comprobaciones de divisibilidad eliminan la mayoría de las combinaciones. La memoria adicional, aparte del cribado, queda dominada por la lista de divisores de un solo valor de \(m\).
对每个正整数 \(m\)，记 \(P(m)\) 为所有边长均为整数、且最大可能面积恰好等于 \(m\) 的四边形的周长之和。题目要求计算
$$SP(n)=\sum_{m=1}^{n} P(m).$$
实现中先用 \(SP(10)=186\) 和 \(SP(100)=23238\) 作为检查点，再求完整目标 \(n=10^6\)。
核心思路是把“最大面积”为 \(m\) 的几何条件改写成关于 \(m^2\) 的因子分解问题。
设四边形边长为 \(a,b,c,d\)，半周长为
$$s=\frac{a+b+c+d}{2}.$$
在边长固定时，面积在四边形为圆内接四边形时达到最大。此时 Brahmagupta 公式给出
$$A_{\max}^2=(s-a)(s-b)(s-c)(s-d).$$
在本题中我们关心的是 \(A_{\max}=m\)，因此基本方程就是
$$m^2=(s-a)(s-b)(s-c)(s-d).$$
令
$$x=s-a,\qquad y=s-b,\qquad z=s-c,\qquad w=s-d.$$
那么面积条件立刻化为
$$xyzw=m^2.$$
反过来，边长可以由 \(x,y,z,w\) 线性恢复：
$$a=\frac{-x+y+z+w}{2},\qquad b=\frac{x-y+z+w}{2},$$
$$c=\frac{x+y-z+w}{2},\qquad d=\frac{x+y+z-w}{2}.$$
周长也有一个非常整齐的表达式：
$$a+b+c+d=x+y+z+w.$$
因此只要某个 \((x,y,z,w)\) 对应合法四边形，它对 \(P(m)\) 的贡献就正好是 \(x+y+z+w\)。
交换边的顺序只会交换 \(x,y,z,w\) 的顺序，所以为了避免重复计数，可以只保留
$$x\ge y\ge z\ge w\ge 1.$$
在这个排序下，恢复出的四条边中最小的是 \(a\)，因为它减去了最大的项 \(x\)。因此“四条边都为正”这一组条件可以压缩成单个不等式
$$a>0\iff x<y+z+w.$$
另一方面，四条边要是整数，只需要求
$$x+y+z+w\equiv 0 \pmod{2}.$$
于是，最大面积为 \(m\) 的目标四边形，与满足下列条件的有序正整数四元组一一对应：
$$xyzw=m^2,\qquad x\ge y\ge z\ge w,\qquad x<y+z+w,\qquad x+y+z+w\equiv 0\pmod{2}.$$
若
$$m=\prod_i p_i^{e_i},$$
则
$$m^2=\prod_i p_i^{2e_i}.$$
所以候选值 \(w,z,y,x\) 必然全都是 \(m^2\) 的因子。实现先生成 \(m^2\) 的全部因子并排序，再选取 \(w\le z\le y\)，最后由
$$x=\frac{m^2}{wzy}$$
补出最后一个因子。这样一来，乘积条件自动满足；同时由于因子列表已经排好序，只要某个部分乘积已经过大，后面更大的因子也不可能成功，可以立刻停止当前分支。
此时 \(m^2=16\)。满足乘积为 \(16\) 的有序四元组 \((x,y,z,w)\) 为
$$\begin{aligned} &(16,1,1,1),\\ &(8,2,1,1),\\ &(4,4,1,1),\\ &(4,2,2,1),\\ &(2,2,2,2). \end{aligned}$$
前两个四元组不满足 \(x<y+z+w\)。第四个四元组的周长为 \(4+2+2+1=9\)，是奇数，因此恢复出的边长不是整数。只剩下两个合法情形：
$$\begin{aligned} (4,4,1,1)&\longrightarrow (a,b,c,d)=(1,1,4,4),\quad x+y+z+w=10,\\ (2,2,2,2)&\longrightarrow (a,b,c,d)=(2,2,2,2),\quad x+y+z+w=8. \end{aligned}$$
因此
$$P(4)=10+8=18.$$
对每个固定的 \(m\)，程序把所有合法四元组的周长加起来得到 \(P(m)\)。最终目标就是
$$SP(n)=\sum_{m=1}^{n}P(m).$$
由于不同的 \(m\) 彼此独立，最外层求和天然适合并行处理。
C++、Python 和 Java 实现都会先为 \(1\) 到 \(n\) 的整数准备质因数信息。对某个给定的 \(m\)，实现先分解 \(m\) 的质因数，再把各指数翻倍来描述 \(m^2\)，然后递归生成 \(m^2\) 的全部因子。
因子排序后，程序按 \(w\le z\le y\) 的顺序扫描候选值。如果某个部分乘积已经迫使剩余因子无法满足排序要求，那么该层循环就可以直接停止。若剩余商能够被当前选中的因子整除，这个商就是 \(x\)，随后程序只做两个数学判定：检查正边长条件 \(x<y+z+w\)，以及检查奇偶条件 \(x+y+z+w\equiv 0\pmod{2}\)。
每个通过筛选的四元组都会把自己的周长 \(x+y+z+w\) 加入 \(P(m)\)。C++ 和 Java 实现把不同的 \(m\) 分配给多个工作线程，而 Python 实现复用已经编译好的 C++ 计算路径，再把最终输出解析成答案。
记 \(D(m)=\tau(m^2)\) 为 \(m^2\) 的因子个数。建立到 \(n\) 为止的质因数表需要 \(O(n)\) 内存，在通常筛法分析下需要 \(O(n\log\log n)\) 时间，其中 C++ 版本采用线性的最小质因子构造。对单个 \(m\) 而言，生成全部因子需要 \(O(D(m))\)。之后对因子三元组的有序扫描最坏可达 \(O(D(m)^3)\)，但单调剪枝和整除检查会在实际运行中删去绝大多数无效组合。除筛表以外，额外空间主要就是单个 \(m\) 的因子列表。
Для каждого положительного целого \(m\) обозначим через \(P(m)\) сумму периметров всех четырёхугольников с целыми сторонами, у которых максимально возможная площадь равна ровно \(m\). Требуется вычислить
$$SP(n)=\sum_{m=1}^{n} P(m).$$
Реализации сначала проверяют метод на контрольных значениях \(SP(10)=186\) и \(SP(100)=23238\), а затем переходят к полному случаю \(n=10^6\).
Главная идея состоит в том, чтобы превратить геометрическое условие в задачу о разложении числа \(m^2\) на множители.
Пусть стороны равны \(a,b,c,d\), а полупериметр равен
$$s=\frac{a+b+c+d}{2}.$$
Среди всех четырёхугольников с такими сторонами максимальная площадь достигается у вписанного четырёхугольника. Тогда формула Брахмагупты даёт
$$A_{\max}^2=(s-a)(s-b)(s-c)(s-d).$$
В задаче 681 рассматривается случай \(A_{\max}=m\), то есть
$$m^2=(s-a)(s-b)(s-c)(s-d).$$
Введём
$$x=s-a,\qquad y=s-b,\qquad z=s-c,\qquad w=s-d.$$
Тогда условие на площадь становится
$$xyzw=m^2.$$
Обратные формулы для сторон имеют вид
$$a=\frac{-x+y+z+w}{2},\qquad b=\frac{x-y+z+w}{2},$$
$$c=\frac{x+y-z+w}{2},\qquad d=\frac{x+y+z-w}{2}.$$
Периметр при этом выражается особенно просто:
$$a+b+c+d=x+y+z+w.$$
Значит, каждая допустимая четвёрка \((x,y,z,w)\) вносит в \(P(m)\) вклад, равный \(x+y+z+w\).
Перестановка сторон просто переставляет \(x,y,z,w\), поэтому для исключения повторов достаточно рассматривать
$$x\ge y\ge z\ge w\ge 1.$$
При таком порядке величина \(a\) является наименьшей восстановленной стороной, потому что из неё вычитается самый большой член \(x\). Поэтому положительность всех четырёх сторон эквивалентна одному условию
$$a>0\iff x<y+z+w.$$
Чтобы стороны были целыми, достаточно паритета
$$x+y+z+w\equiv 0 \pmod{2}.$$
Итак, искомые четырёхугольники находятся во взаимно однозначном соответствии с упорядоченными положительными четвёрками, для которых выполняется
$$xyzw=m^2,\qquad x\ge y\ge z\ge w,\qquad x<y+z+w,\qquad x+y+z+w\equiv 0\pmod{2}.$$
Если
$$m=\prod_i p_i^{e_i},$$
то
$$m^2=\prod_i p_i^{2e_i}.$$
Следовательно, все кандидаты \(w,z,y,x\) являются делителями \(m^2\). Реализация строит полный список делителей \(m^2\), сортирует его, выбирает \(w\le z\le y\) и затем восстанавливает последний множитель по формуле
$$x=\frac{m^2}{wzy}.$$
Так условие произведения выполняется автоматически. Кроме того, сортировка делителей позволяет делать монотонные отсечения: как только частичное произведение становится слишком большим, дальнейшие делители уже не подходят.
Здесь \(m^2=16\). Упорядоченные четвёрки \((x,y,z,w)\) с произведением \(16\) таковы:
$$\begin{aligned} &(16,1,1,1),\\ &(8,2,1,1),\\ &(4,4,1,1),\\ &(4,2,2,1),\\ &(2,2,2,2). \end{aligned}$$
Первые две не проходят условие \(x<y+z+w\). У четвёртой периметр \(4+2+2+1=9\) нечётный, поэтому восстановленные стороны не будут целыми. Остаются два допустимых случая:
$$\begin{aligned} (4,4,1,1)&\longrightarrow (a,b,c,d)=(1,1,4,4),\quad x+y+z+w=10,\\ (2,2,2,2)&\longrightarrow (a,b,c,d)=(2,2,2,2),\quad x+y+z+w=8. \end{aligned}$$
Следовательно,
$$P(4)=10+8=18.$$
Для каждого фиксированного \(m\) программа суммирует периметры всех допустимых четвёрок и получает \(P(m)\). После этого искомая величина вычисляется по формуле
$$SP(n)=\sum_{m=1}^{n}P(m).$$
Так как разные значения \(m\) независимы друг от друга, внешний цикл удобно распараллеливать.
Реализации на C++, Python и Java сначала подготавливают информацию о простых делителях для всех чисел до \(n\). Для выбранного \(m\) реализация раскладывает \(m\) на простые множители, удваивает показатели степеней для \(m^2\), а затем рекурсивно генерирует все делители числа \(m^2\).
После сортировки делителей программа перебирает кандидаты в порядке \(w\le z\le y\). Если частичное произведение уже заставляет оставшийся множитель нарушить нужный порядок, соответствующий цикл сразу завершается. Когда оставшееся частное делится на выбранные множители, это частное принимается за \(x\), и код проверяет ровно два математических условия: неравенство положительности \(x<y+z+w\) и условие чётности \(x+y+z+w\equiv 0\pmod{2}\).
Каждая прошедшая проверку четвёрка добавляет свой периметр \(x+y+z+w\) к \(P(m)\). Реализации на C++ и Java распределяют разные значения \(m\) между рабочими потоками, а Python-реализация использует тот же скомпилированный путь вычислений на C++ и возвращает уже разобранный финальный ответ.
Пусть \(D(m)=\tau(m^2)\) обозначает число делителей \(m^2\). Построение таблицы простых делителей до \(n\) требует \(O(n)\) памяти и \(O(n\log\log n)\) времени в стандартном анализе решета, при этом версия на C++ использует линейное построение наименьшего простого делителя. Для одного фиксированного \(m\) генерация всех делителей стоит \(O(D(m))\). Дальнейший упорядоченный перебор троек делителей имеет худшую оценку \(O(D(m)^3)\), но монотонные отсечения и проверки делимости на практике убирают большую часть комбинаций. Дополнительная память помимо решета в основном расходуется на список делителей для одного значения \(m\).
لكل عدد صحيح موجب \(m\)، نرمز بـ \(P(m)\) إلى مجموع محيطات جميع الرباعيات ذات الأضلاع الصحيحة التي تساوي مساحتها العظمى الممكنة العدد \(m\) بالضبط. والكمية المطلوبة هي
$$SP(n)=\sum_{m=1}^{n} P(m).$$
تتحقق التطبيقات أولًا من صحة الفكرة باستخدام النقطتين \(SP(10)=186\) و\(SP(100)=23238\)، ثم تنتقل إلى الحالة الكاملة \(n=10^6\).
الفكرة الأساسية هي تحويل الشرط الهندسي إلى مسألة تفكيك عوامل للعدد \(m^2\).
إذا كانت أطوال الأضلاع هي \(a,b,c,d\)، فإن نصف المحيط يساوي
$$s=\frac{a+b+c+d}{2}.$$
وبين جميع الرباعيات ذات هذه الأضلاع، تبلغ المساحة أقصاها عندما يكون الرباعي دائريًا. عندئذ تعطي صيغة Brahmagupta
$$A_{\max}^2=(s-a)(s-b)(s-c)(s-d).$$
وفي هذه المسألة نهتم بالحالة \(A_{\max}=m\)، ولذلك تصبح المعادلة الأساسية
$$m^2=(s-a)(s-b)(s-c)(s-d).$$
لنضع
$$x=s-a,\qquad y=s-b,\qquad z=s-c,\qquad w=s-d.$$
فتتحول معادلة المساحة مباشرة إلى
$$xyzw=m^2.$$
أما استرجاع الأضلاع من \(x,y,z,w\) فيكون عبر
$$a=\frac{-x+y+z+w}{2},\qquad b=\frac{x-y+z+w}{2},$$
$$c=\frac{x+y-z+w}{2},\qquad d=\frac{x+y+z-w}{2}.$$
ولدينا أيضًا صيغة شديدة البساطة للمحيط:
$$a+b+c+d=x+y+z+w.$$
إذن كل رباعية صحيحة من القيم \((x,y,z,w)\) تضيف بالضبط المقدار \(x+y+z+w\) إلى \(P(m)\).
تبديل ترتيب الأضلاع لا يفعل أكثر من تبديل ترتيب \(x,y,z,w\)، ولذلك نكتفي بعدّ الحالات التي تحقق
$$x\ge y\ge z\ge w\ge 1.$$
مع هذا الترتيب تكون \(a\) أصغر ضلع مستعاد، لأنها تطرح أكبر قيمة وهي \(x\). ومن ثم فإن إيجابية الأضلاع الأربعة كلها تكافئ الشرط الوحيد
$$a>0\iff x<y+z+w.$$
ولكي تكون الأضلاع أعدادًا صحيحة يكفي أن يكون
$$x+y+z+w\equiv 0 \pmod{2}.$$
وبالتالي فإن الرباعيات المطلوبة تقع في تقابل واحد لواحد مع الرباعيات المرتبة من الأعداد الصحيحة الموجبة التي تحقق
$$xyzw=m^2,\qquad x\ge y\ge z\ge w,\qquad x<y+z+w,\qquad x+y+z+w\equiv 0\pmod{2}.$$
إذا كتبنا
$$m=\prod_i p_i^{e_i},$$
فإن
$$m^2=\prod_i p_i^{2e_i}.$$
لذلك يجب أن تكون كل قيمة مرشحة من \(w,z,y,x\) قاسمًا للعدد \(m^2\). تقوم الشيفرة بتوليد جميع قواسم \(m^2\)، ثم ترتبها، ثم تختار \(w\le z\le y\)، وبعد ذلك تحدد العامل الأخير بواسطة
$$x=\frac{m^2}{wzy}.$$
وبهذه الطريقة يتحقق شرط الضرب تلقائيًا، كما أن ترتيب القواسم يسمح بقطع مبكر رتيب: فإذا صار حاصل الضرب الجزئي كبيرًا أكثر من اللازم، فإن كل القواسم اللاحقة ستكون أسوأ.
لدينا هنا \(m^2=16\). والرباعيات المرتبة \((x,y,z,w)\) التي حاصل ضربها \(16\) هي
$$\begin{aligned} &(16,1,1,1),\\ &(8,2,1,1),\\ &(4,4,1,1),\\ &(4,2,2,1),\\ &(2,2,2,2). \end{aligned}$$
الحالتان الأوليان تفشلان في الشرط \(x<y+z+w\). أما الحالة الرابعة فمحيطها \(4+2+2+1=9\) وهو عدد فردي، ولذلك لا تعطي أضلاعًا صحيحة. وتبقى حالتان صحيحتان فقط:
$$\begin{aligned} (4,4,1,1)&\longrightarrow (a,b,c,d)=(1,1,4,4),\quad x+y+z+w=10,\\ (2,2,2,2)&\longrightarrow (a,b,c,d)=(2,2,2,2),\quad x+y+z+w=8. \end{aligned}$$
ومن ثم
$$P(4)=10+8=18.$$
لكل \(m\) ثابت، تجمع الشيفرة محيطات جميع الرباعيات الصالحة لتحصل على \(P(m)\). وبعد ذلك يكون الجواب النهائي
$$SP(n)=\sum_{m=1}^{n}P(m).$$
وبما أن كل قيمة من \(m\) مستقلة عن غيرها، فإن الحلقة الخارجية مناسبة جدًا للتنفيذ المتوازي.
تبدأ تطبيقات C++ وPython وJava بإعداد معلومات التحليل إلى العوامل الأولية لكل الأعداد حتى \(n\). وبالنسبة إلى قيمة معينة من \(m\)، تقوم الشيفرة بتحليل \(m\)، ثم تضاعف الأسس لوصف \(m^2\)، ثم تولد جميع قواسم \(m^2\) بطريقة عودية.
بعد ترتيب هذه القواسم، تمسح الشيفرة المرشحات بالترتيب \(w\le z\le y\). وإذا كان حاصل ضرب جزئي معين يجبر العامل الباقي على كسر ترتيب الفرز المطلوب، تتوقف الحلقة في تلك النقطة مباشرة. وإذا كان خارج القسمة المتبقي قابلًا للقسمة على العوامل المختارة، فإن هذا الخارج يكون هو \(x\)، ثم تطبق الشيفرة الاختبارين الرياضيين المشتقين سابقًا: شرط الإيجابية \(x<y+z+w\)، وشرط الزوجية \(x+y+z+w\equiv 0\pmod{2}\).
كل رباعية تنجح في هذين الاختبارين تضيف محيطها \(x+y+z+w\) إلى \(P(m)\). وتوزع تطبيقتا C++ وJava قيم \(m\) المختلفة على عدة خيوط عمل، بينما يعيد تطبيق Python استخدام مسار الحساب المترجم في C++ ثم يعيد القيمة النهائية بعد استخراجها.
لنرمز بـ \(D(m)=\tau(m^2)\) إلى عدد قواسم \(m^2\). إن بناء جدول العوامل الأولية حتى \(n\) يستهلك \(O(n)\) من الذاكرة ويحتاج إلى \(O(n\log\log n)\) من الزمن في التحليل المعتاد للغربال، مع استخدام نسخة C++ لبناء خطي لأصغر عامل أولي. وبالنسبة إلى \(m\) ثابت، فإن توليد جميع القواسم يكلف \(O(D(m))\). أما المسح المرتب على ثلاثيات القواسم فله حد أسوأ من نوع \(O(D(m)^3)\)، لكن شروط الإيقاف الرتيبة وفحوص القسمة تستبعد معظم التركيبات عمليًا. والذاكرة الإضافية، بعد جدول الغربال، تهيمن عليها قائمة القواسم الخاصة بقيمة واحدة من \(m\).