Problem 791 studies nondecreasing positive integer quadruples \((a,b,c,d)\) whose average equals their variance. Writing
$$\mu=\frac{a+b+c+d}{4},\qquad V=\frac{(a-\mu)^2+(b-\mu)^2+(c-\mu)^2+(d-\mu)^2}{4},$$
we seek all quadruples with \(\mu=V\) and \(\mu\le n\), and \(S(n)\) is the sum of the corresponding totals \(a+b+c+d=4\mu\). The direct four-variable search is far too large for \(n=10^8\), so the implementations reduce the problem to a three-dimensional lattice search with closed-form summation over the innermost coordinate.
The important fact encoded by the implementations is that the original average-equals-variance constraint can be rewritten in terms of three odd integers. Once that reduction is done, the remaining work is purely arithmetic.
After ordering the quadruple, eliminating the redundant degree of freedom, and applying the linear change of variables used by the implementations, every admissible configuration is represented by odd integers \((u,v,w)\) satisfying
$$u\equiv v\equiv w\equiv 1\pmod 2.$$
Its contribution to \(S(n)\) becomes
$$T(u,v,w)=\frac{u^2+v^2+w^2+2u+2v+2w+3}{2}.$$
This is the quantity accumulated by the implementations. The original quadruple is no longer enumerated explicitly; the whole computation is carried out in the reduced \((u,v,w)\)-space.
Set
$$R=8n.$$
The outer coordinate is restricted to odd values in
$$1\le u\le \left\lfloor\sqrt{R+3}\right\rfloor-2,\qquad u\equiv 1\pmod 2.$$
For each fixed \(u\), the second coordinate is restricted to
$$-1\le v\le \min\!\left(u,\left\lfloor\sqrt{R-u^2-4u-1}\right\rfloor-2\right),\qquad v\equiv 1\pmod 2.$$
These bounds already remove most of the search space. Instead of a four-dimensional brute-force enumeration, the solver now scans only the feasible odd lattice points in a curved two-dimensional outer region.
For each admissible pair \((u,v)\), define
$$w_{\max}=\left\lfloor\sqrt{R-u^2-v^2-4u-4v-5}\right\rfloor.$$
Then \(w\) must lie in the odd interval
$$\max(-w_{\max},-v-2)\le w\le \min(w_{\max},v),\qquad w\equiv 1\pmod 2.$$
There is one more condition. If
$$11-u^2-v^2>0,$$
then the middle of the interval is forbidden and we must keep only
$$|w|\ge \left\lceil\sqrt{11-u^2-v^2}\right\rceil.$$
So for a fixed \((u,v)\), the innermost search is never an arbitrary set: it is either one odd interval or two odd intervals separated by a central gap. That structural fact is exactly what makes the constant-time interval summation possible.
Suppose one admissible \(w\)-interval is
$$w=L,L+2,\dots,H,$$
with \(L\) and \(H\) odd. Let
$$m=\frac{H-L}{2}+1,\qquad w_j=L+2j\quad (0\le j\le m-1).$$
Then
$$\sum_{j=0}^{m-1} j=\frac{m(m-1)}{2},\qquad \sum_{j=0}^{m-1} j^2=\frac{(m-1)m(2m-1)}{6},$$
and therefore
$$\sum_{j=0}^{m-1} w_j=mL+2\sum_{j=0}^{m-1}j,$$
$$\sum_{j=0}^{m-1} w_j^2=mL^2+4L\sum_{j=0}^{m-1}j+4\sum_{j=0}^{m-1}j^2.$$
If we abbreviate the part independent of \(w\) by
$$K(u,v)=u^2+v^2+2u+2v+3,$$
then the whole interval contributes
$$\sum_{j=0}^{m-1} T(u,v,w_j)=\frac{mK(u,v)+\sum w_j^2+2\sum w_j}{2}.$$
This replaces a potentially long inner loop by a handful of arithmetic operations.
If the central exclusion is absent, one closed-form evaluation is enough. If the exclusion is present, the allowed odd values split into a negative tail and a positive tail:
$$[L,H]\cap\{w:w\equiv 1\pmod 2\}=[L,-c]\cup[c,H]$$
for the smallest admissible odd threshold \(c\). Each tail is summed by the same interval formula, and the two results are added modulo \(433494437\).
So the algorithm never iterates over admissible \(w\)-values one by one. That is the decisive optimization shared by the C++, Python, and Java implementations.
When \(n=5\), we have \(R=40\). The reduced search produces exactly the following admissible odd triples:
$$\begin{aligned} (1,1,-3)&\mapsto T=6,\\ (3,-1,-1)&\mapsto T=8,\\ (3,1,-3)&\mapsto T=12,\\ (3,1,-1)&\mapsto T=10,\\ (3,1,1)&\mapsto T=12. \end{aligned}$$
Therefore
$$S(5)=6+8+12+10+12=48,$$
which matches the checkpoint built into the overall solution strategy.
The C++, Python, and Java implementations all follow the same mathematical pipeline. First they compute \(R=8n\), determine the largest admissible odd outer coordinate, and loop over the feasible odd pairs \((u,v)\) using integer square roots to obtain sharp bounds instead of trial-and-error scanning.
For each outer pair, the implementation constructs the admissible odd range for the innermost coordinate. If the central hole is inactive, it evaluates one interval. If the hole is active, it evaluates a negative interval and a positive interval. In both cases it uses the closed forms for \(\sum w\) and \(\sum w^2\), so the innermost work is constant time.
The arithmetic is always reduced modulo \(433494437\). The C++ implementation parallelizes the outer loop because different odd \(u\)-slices are independent; the Python and Java implementations use the same bounds and formulas in sequential form. The C++ version also checks the intermediate values \(S(5)=48\) and \(S(10^3)=37048340\) before computing the final target.
The outer coordinate ranges over \(O(\sqrt{n})\) odd values, and for each such value the second coordinate also spans at most \(O(\sqrt{n})\) odd values. Hence the number of feasible outer pairs is \(O(n)\). Since each pair is handled by at most two constant-time interval evaluations, the total running time is \(O(n)\). The sequential versions use \(O(1)\) auxiliary space, while the parallel C++ version uses \(O(P)\) partial storage for \(P\) worker threads.
Problem 791 betrachtet nicht abnehmende positive ganzzahlige Vierer-Tupel \((a,b,c,d)\), deren Mittelwert gleich ihrer Varianz ist. Mit
$$\mu=\frac{a+b+c+d}{4},\qquad V=\frac{(a-\mu)^2+(b-\mu)^2+(c-\mu)^2+(d-\mu)^2}{4}$$
suchen wir alle Tupel mit \(\mu=V\) und \(\mu\le n\). Die Funktion \(S(n)\) summiert dann die zugehörigen Gesamtsummen \(a+b+c+d=4\mu\). Für \(n=10^8\) ist eine direkte Suche in vier Variablen unbrauchbar, deshalb arbeiten die Implementierungen nach einer Reduktion in drei ungeraden Koordinaten und summieren die innerste Variable in geschlossener Form.
Die in den Implementierungen kodierte Schlüsseltatsache ist, dass sich die ursprüngliche Bedingung „Mittelwert gleich Varianz“ in ein Gitterproblem mit drei ungeraden Variablen übersetzen lässt. Danach bleibt nur noch effiziente ganzzahlige Arithmetik.
Nach dem Sortieren des Tupels, dem Eliminieren einer redundanten Freiheitsgrad-Komponente und der linearen Variablentransformation aus den Implementierungen wird jede zulässige Konfiguration durch ungerade ganze Zahlen \((u,v,w)\) beschrieben mit
$$u\equiv v\equiv w\equiv 1\pmod 2.$$
Ihr Beitrag zu \(S(n)\) lautet dann
$$T(u,v,w)=\frac{u^2+v^2+w^2+2u+2v+2w+3}{2}.$$
Die ursprünglichen Vierer-Tupel werden also nicht mehr direkt durchlaufen; die ganze Rechnung findet in diesem reduzierten \((u,v,w)\)-Raum statt.
Setze
$$R=8n.$$
Dann darf die äußere Koordinate nur ungerade Werte in
$$1\le u\le \left\lfloor\sqrt{R+3}\right\rfloor-2,\qquad u\equiv 1\pmod 2$$
annehmen. Für festes \(u\) ist die zweite Koordinate beschränkt durch
$$-1\le v\le \min\!\left(u,\left\lfloor\sqrt{R-u^2-4u-1}\right\rfloor-2\right),\qquad v\equiv 1\pmod 2.$$
Diese Schranken schneiden bereits den Großteil des Suchraums weg. Anstelle einer vierdimensionalen Brute-Force-Suche bleibt nur noch ein gekrümmter zweidimensionaler Bereich ungerader Gitterpunkte übrig.
Für jedes zulässige Paar \((u,v)\) definieren wir
$$w_{\max}=\left\lfloor\sqrt{R-u^2-v^2-4u-4v-5}\right\rfloor.$$
Dann muss \(w\) im ungeraden Intervall
$$\max(-w_{\max},-v-2)\le w\le \min(w_{\max},v),\qquad w\equiv 1\pmod 2$$
liegen. Dazu kommt noch eine zusätzliche Bedingung: Falls
$$11-u^2-v^2>0,$$
darf die Mitte des Intervalls nicht benutzt werden, und es muss gelten
$$|w|\ge \left\lceil\sqrt{11-u^2-v^2}\right\rceil.$$
Damit ist die innerste Menge nie beliebig zerstreut: Für festes \((u,v)\) erhält man entweder genau ein ungerades Intervall oder zwei ungerade Intervalle mit einer Lücke in der Mitte. Genau diese Struktur macht die \(O(1)\)-Summenformel möglich.
Sei ein zulässiges \(w\)-Intervall gegeben durch
$$w=L,L+2,\dots,H,$$
wobei \(L\) und \(H\) ungerade sind. Definiere
$$m=\frac{H-L}{2}+1,\qquad w_j=L+2j\quad (0\le j\le m-1).$$
Dann gilt
$$\sum_{j=0}^{m-1} j=\frac{m(m-1)}{2},\qquad \sum_{j=0}^{m-1} j^2=\frac{(m-1)m(2m-1)}{6},$$
also
$$\sum_{j=0}^{m-1} w_j=mL+2\sum_{j=0}^{m-1}j,$$
$$\sum_{j=0}^{m-1} w_j^2=mL^2+4L\sum_{j=0}^{m-1}j+4\sum_{j=0}^{m-1}j^2.$$
Schreibt man den von \(w\) unabhängigen Teil als
$$K(u,v)=u^2+v^2+2u+2v+3,$$
dann liefert das gesamte Intervall den Beitrag
$$\sum_{j=0}^{m-1} T(u,v,w_j)=\frac{mK(u,v)+\sum w_j^2+2\sum w_j}{2}.$$
Damit wird eine lange innere Schleife durch wenige arithmetische Operationen ersetzt.
Ist die zentrale Ausschlussbedingung inaktiv, genügt eine einzige Auswertung. Ist sie aktiv, zerfallen die zulässigen ungeraden Werte in einen negativen und einen positiven Abschnitt:
$$[L,H]\cap\{w:w\equiv 1\pmod 2\}=[L,-c]\cup[c,H]$$
für die kleinste zulässige ungerade Schwelle \(c\). Beide Teilintervalle werden mit derselben Summenformel ausgewertet und anschließend modulo \(433494437\) addiert.
Genau dadurch iteriert der Algorithmus niemals einzeln über alle \(w\)-Werte. Diese Optimierung ist der gemeinsame Kern der C++-, Python- und Java-Implementierungen.
Für \(n=5\) gilt \(R=40\). Die reduzierte Suche liefert genau die folgenden zulässigen ungeraden Tripel:
$$\begin{aligned} (1,1,-3)&\mapsto T=6,\\ (3,-1,-1)&\mapsto T=8,\\ (3,1,-3)&\mapsto T=12,\\ (3,1,-1)&\mapsto T=10,\\ (3,1,1)&\mapsto T=12. \end{aligned}$$
Daraus folgt
$$S(5)=6+8+12+10+12=48,$$
genau der kleine Kontrollwert, den die Gesamtstrategie reproduzieren muss.
Die C++-, Python- und Java-Implementierungen benutzen alle dieselbe mathematische Pipeline. Zuerst berechnen sie \(R=8n\), bestimmen die größte zulässige ungerade äußere Koordinate und durchlaufen dann alle zulässigen ungeraden Paare \((u,v)\). Die oberen Schranken werden dabei mit ganzzahligen Quadratwurzeln scharf bestimmt, nicht durch blindes Testen.
Für jedes äußere Paar konstruiert die Implementierung den zulässigen ungeraden Bereich der inneren Koordinate. Ist das zentrale Loch nicht aktiv, wird genau ein Intervall ausgewertet. Ist es aktiv, werden ein negativer und ein positiver Teilbereich getrennt summiert. In beiden Fällen werden nur die geschlossenen Formeln für \(\sum w\) und \(\sum w^2\) benutzt, sodass die innerste Arbeit konstant bleibt.
Alle Rechenschritte werden modulo \(433494437\) reduziert. Die C++-Implementierung parallelisiert die äußere Schleife, weil verschiedene ungerade \(u\)-Scheiben unabhängig sind; Python und Java verwenden dieselben Schranken und Formeln sequentiell. Die C++-Variante prüft außerdem die Zwischenwerte \(S(5)=48\) und \(S(10^3)=37048340\), bevor sie das eigentliche Ziel auswertet.
Die äußere Koordinate nimmt \(O(\sqrt{n})\) ungerade Werte an, und für jeden solchen Wert besitzt auch die zweite Koordinate höchstens \(O(\sqrt{n})\) ungerade Möglichkeiten. Daher gibt es insgesamt \(O(n)\) zulässige äußere Paare. Da jedes Paar mit höchstens zwei Intervallauswertungen in konstanter Zeit behandelt wird, beträgt die Gesamtlaufzeit \(O(n)\). Die sequentiellen Varianten verwenden \(O(1)\) Hilfsspeicher, die parallele C++-Variante \(O(P)\) Teilsummen für \(P\) Worker-Threads.
Problem 791, ortalaması varyansına eşit olan sıralı pozitif tamsayı dörtlülerini \((a,b,c,d)\) inceler. Burada
$$\mu=\frac{a+b+c+d}{4},\qquad V=\frac{(a-\mu)^2+(b-\mu)^2+(c-\mu)^2+(d-\mu)^2}{4}$$
tanımları kullanılır. Aranan şey, \(\mu=V\) ve \(\mu\le n\) koşullarını sağlayan tüm dörtlüler için toplamların \(a+b+c+d=4\mu\) birikimli toplamı olan \(S(n)\)'dir. \(n=10^8\) için dört değişken üzerinde doğrudan tarama pratik değildir; bu yüzden implementasyonlar problemi üç tek koordinatlı bir kafes taramasına indirger ve en içteki toplamı kapalı formülle hesaplar.
Implementasyonların kodladığı temel gerçek şudur: “ortalama = varyans” koşulu, üç tek sayılı değişkene sahip eşdeğer bir probleme dönüştürülebilir. Bu indirgeme yapıldıktan sonra geriye yalnızca etkili tamsayı aritmetiği kalır.
Dörtlü sıralandıktan, gereksiz serbestlik elimine edildikten ve implementasyonların kullandığı lineer değişken dönüşümü uygulandıktan sonra her geçerli yapı, \((u,v,w)\) tek tamsayılarıyla temsil edilir ve
$$u\equiv v\equiv w\equiv 1\pmod 2$$
olur. Bu yapının \(S(n)\)'ye katkısı
$$T(u,v,w)=\frac{u^2+v^2+w^2+2u+2v+2w+3}{2}$$
şeklindedir. Yani implementasyonlar artık orijinal dört sayıyı tek tek üretmez; bütün hesap bu indirgenmiş \((u,v,w)\) uzayında yapılır.
Şunu tanımlayalım:
$$R=8n.$$
Dış koordinat yalnızca
$$1\le u\le \left\lfloor\sqrt{R+3}\right\rfloor-2,\qquad u\equiv 1\pmod 2$$
aralığındaki tek değerleri alabilir. Sabit bir \(u\) için ikinci koordinat ise
$$-1\le v\le \min\!\left(u,\left\lfloor\sqrt{R-u^2-4u-1}\right\rfloor-2\right),\qquad v\equiv 1\pmod 2$$
koşuluna tabidir. Bu sınırlar, arama uzayının büyük kısmını baştan siler ve dört boyutlu kaba tarama yerine eğrisel iki boyutlu bir dış bölge bırakır.
Her uygun \((u,v)\) çifti için
$$w_{\max}=\left\lfloor\sqrt{R-u^2-v^2-4u-4v-5}\right\rfloor$$
tanımlanır. O zaman \(w\) için temel aralık
$$\max(-w_{\max},-v-2)\le w\le \min(w_{\max},v),\qquad w\equiv 1\pmod 2$$
olur. Fakat bir ek kesme daha vardır. Eğer
$$11-u^2-v^2>0$$
ise orta bölge yasaktır ve
$$|w|\ge \left\lceil\sqrt{11-u^2-v^2}\right\rceil$$
şartı gerekir. Böylece sabit \((u,v)\) için iç küme dağınık bir nokta listesi değil, ya tek bir tek-sayı aralığı ya da ortasında boşluk bulunan iki tek-sayı aralığı olur. Sabit zamanlı toplam formülünü mümkün kılan yapı tam olarak budur.
Uygun bir \(w\)-aralığı
$$w=L,L+2,\dots,H$$
şeklinde olsun ve \(L,H\) tek olsun. Şimdi
$$m=\frac{H-L}{2}+1,\qquad w_j=L+2j\quad (0\le j\le m-1)$$
tanımını yapalım. O zaman
$$\sum_{j=0}^{m-1} j=\frac{m(m-1)}{2},\qquad \sum_{j=0}^{m-1} j^2=\frac{(m-1)m(2m-1)}{6}$$
ve dolayısıyla
$$\sum_{j=0}^{m-1} w_j=mL+2\sum_{j=0}^{m-1}j,$$
$$\sum_{j=0}^{m-1} w_j^2=mL^2+4L\sum_{j=0}^{m-1}j+4\sum_{j=0}^{m-1}j^2$$
elde edilir. \(w\)'den bağımsız kısmı
$$K(u,v)=u^2+v^2+2u+2v+3$$
ile gösterirsek, bütün aralık katkısı
$$\sum_{j=0}^{m-1} T(u,v,w_j)=\frac{mK(u,v)+\sum w_j^2+2\sum w_j}{2}$$
olur. Böylece uzun iç döngü birkaç aritmetik işleme indirgenir.
Ortadaki yasak bölge aktif değilse tek bir kapalı form hesabı yeterlidir. Aktifse uygun tek değerler bir negatif kuyruk ve bir pozitif kuyruk olarak ayrılır:
$$[L,H]\cap\{w:w\equiv 1\pmod 2\}=[L,-c]\cup[c,H]$$
burada \(c\), izin verilen en küçük tek eşik değeridir. Her iki kuyruk da aynı aralık formülüyle toplanır ve sonuçlar \(433494437\) modunda birleştirilir.
Yani algoritma hiçbir zaman geçerli \(w\) değerlerini tek tek dolaşmaz. C++, Python ve Java implementasyonlarının ortak kritik optimizasyonu budur.
\(n=5\) için \(R=40\) olur. İndirgenmiş arama şu geçerli tek üçlüleri üretir:
$$\begin{aligned} (1,1,-3)&\mapsto T=6,\\ (3,-1,-1)&\mapsto T=8,\\ (3,1,-3)&\mapsto T=12,\\ (3,1,-1)&\mapsto T=10,\\ (3,1,1)&\mapsto T=12. \end{aligned}$$
Böylece
$$S(5)=6+8+12+10+12=48$$
sonucuna ulaşılır. Bu da çözüm stratejisinin küçük kontrol değeridir.
C++, Python ve Java implementasyonları aynı matematiksel hattı izler. Önce \(R=8n\) hesaplanır, sonra en büyük uygun dış tek koordinat bulunur ve geçerli tüm tek \((u,v)\) çiftleri dolaşılır. Üst sınırlar, deneme yanılma ile değil, tamsayı karekök hesaplarıyla keskin biçimde elde edilir.
Her dış çift için iç koordinatın uygun tek aralığı kurulup incelenir. Ortadaki boşluk yoksa tek aralık toplanır; boşluk varsa negatif ve pozitif parça ayrı ayrı hesaplanır. Her durumda yalnızca \(\sum w\) ve \(\sum w^2\) için kapalı formüller kullanıldığı için en içteki iş sabit zamanda tamamlanır.
Tüm aritmetik \(433494437\) modunda tutulur. C++ implementasyonu dış döngüyü paralelleştirir çünkü farklı tek \(u\) dilimleri birbirinden bağımsızdır; Python ve Java ise aynı sınırlar ve formüllerle ardışık çalışır. C++ sürümü ayrıca gerçek hedefi hesaplamadan önce \(S(5)=48\) ve \(S(10^3)=37048340\) kontrol noktalarını doğrular.
Dış koordinat \(O(\sqrt{n})\) adet tek değer alır ve her biri için ikinci koordinat da en fazla \(O(\sqrt{n})\) adet tek değere sahiptir. Bu nedenle uygun dış çiftlerin sayısı \(O(n)\) mertebesindedir. Her çift en fazla iki sabit-zamanlı aralık değerlendirmesiyle işlendiğinden toplam zaman karmaşıklığı \(O(n)\) olur. Ardışık sürümler \(O(1)\) ek bellek kullanırken, paralel C++ sürümü \(P\) iş parçacığı için \(O(P)\) kısmi toplam saklar.
El problema 791 estudia cuádruplas no decrecientes de enteros positivos \((a,b,c,d)\) cuyo promedio es igual a su varianza. Definiendo
$$\mu=\frac{a+b+c+d}{4},\qquad V=\frac{(a-\mu)^2+(b-\mu)^2+(c-\mu)^2+(d-\mu)^2}{4},$$
buscamos todas las cuádruplas con \(\mu=V\) y \(\mu\le n\), y \(S(n)\) es la suma acumulada de los totales \(a+b+c+d=4\mu\). Para \(n=10^8\), una búsqueda directa sobre cuatro variables es inviable, así que las implementaciones reducen el problema a una búsqueda sobre una red tridimensional de coordenadas impares y luego suman la coordenada interna en forma cerrada.
El hecho central codificado por las implementaciones es que la condición original “promedio igual a varianza” puede reescribirse como un problema equivalente en tres variables impares. Después de esa reducción, todo el trabajo restante es aritmética entera eficiente.
Tras ordenar la cuádrupla, eliminar el grado de libertad redundante y aplicar el cambio lineal de variables usado por las implementaciones, cada configuración válida queda representada por enteros impares \((u,v,w)\) tales que
$$u\equiv v\equiv w\equiv 1\pmod 2.$$
Su contribución a \(S(n)\) pasa a ser
$$T(u,v,w)=\frac{u^2+v^2+w^2+2u+2v+2w+3}{2}.$$
A partir de ese momento ya no se enumeran explícitamente las cuádruplas originales; todo se calcula en el espacio reducido \((u,v,w)\).
Sea
$$R=8n.$$
La coordenada exterior solo puede tomar valores impares en
$$1\le u\le \left\lfloor\sqrt{R+3}\right\rfloor-2,\qquad u\equiv 1\pmod 2.$$
Para cada \(u\) fijo, la segunda coordenada debe cumplir
$$-1\le v\le \min\!\left(u,\left\lfloor\sqrt{R-u^2-4u-1}\right\rfloor-2\right),\qquad v\equiv 1\pmod 2.$$
Estas cotas eliminan de entrada la mayor parte del espacio de búsqueda. En vez de una exploración bruta en cuatro dimensiones, solo queda una región exterior bidimensional curvada sobre puntos impares de la red.
Para cada par admisible \((u,v)\), definimos
$$w_{\max}=\left\lfloor\sqrt{R-u^2-v^2-4u-4v-5}\right\rfloor.$$
Entonces \(w\) debe pertenecer al intervalo impar
$$\max(-w_{\max},-v-2)\le w\le \min(w_{\max},v),\qquad w\equiv 1\pmod 2.$$
Además hay una restricción adicional. Si
$$11-u^2-v^2>0,$$
la zona central queda prohibida y hay que imponer
$$|w|\ge \left\lceil\sqrt{11-u^2-v^2}\right\rceil.$$
Por tanto, para un \((u,v)\) fijo, el conjunto interior nunca es arbitrario: siempre es un único intervalo impar o dos intervalos impares separados por un hueco central. Esa estructura es exactamente la que permite la suma en tiempo constante.
Supongamos que un intervalo admisible para \(w\) es
$$w=L,L+2,\dots,H,$$
con \(L\) y \(H\) impares. Definimos
$$m=\frac{H-L}{2}+1,\qquad w_j=L+2j\quad (0\le j\le m-1).$$
Entonces
$$\sum_{j=0}^{m-1} j=\frac{m(m-1)}{2},\qquad \sum_{j=0}^{m-1} j^2=\frac{(m-1)m(2m-1)}{6},$$
de donde se obtiene
$$\sum_{j=0}^{m-1} w_j=mL+2\sum_{j=0}^{m-1}j,$$
$$\sum_{j=0}^{m-1} w_j^2=mL^2+4L\sum_{j=0}^{m-1}j+4\sum_{j=0}^{m-1}j^2.$$
Si abreviamos la parte independiente de \(w\) como
$$K(u,v)=u^2+v^2+2u+2v+3,$$
la contribución del intervalo completo es
$$\sum_{j=0}^{m-1} T(u,v,w_j)=\frac{mK(u,v)+\sum w_j^2+2\sum w_j}{2}.$$
Así se reemplaza un bucle interno potencialmente largo por unas pocas operaciones aritméticas.
Si la exclusión central no aparece, basta con una sola evaluación en forma cerrada. Si sí aparece, los valores impares permitidos se separan en una cola negativa y otra positiva:
$$[L,H]\cap\{w:w\equiv 1\pmod 2\}=[L,-c]\cup[c,H]$$
para el menor umbral impar admisible \(c\). Cada cola se suma con la misma fórmula de intervalo y luego ambas se combinan módulo \(433494437\).
De este modo el algoritmo nunca recorre los valores válidos de \(w\) uno por uno. Esa es la optimización decisiva compartida por las implementaciones en C++, Python y Java.
Cuando \(n=5\), se tiene \(R=40\). La búsqueda reducida produce exactamente los siguientes tríos impares admisibles:
$$\begin{aligned} (1,1,-3)&\mapsto T=6,\\ (3,-1,-1)&\mapsto T=8,\\ (3,1,-3)&\mapsto T=12,\\ (3,1,-1)&\mapsto T=10,\\ (3,1,1)&\mapsto T=12. \end{aligned}$$
Por lo tanto,
$$S(5)=6+8+12+10+12=48,$$
que coincide con el valor de comprobación pequeño utilizado por la estrategia global.
Las implementaciones en C++, Python y Java siguen exactamente la misma tubería matemática. Primero calculan \(R=8n\), determinan la mayor coordenada exterior impar admisible y recorren todos los pares impares factibles \((u,v)\). Las cotas superiores se obtienen con raíces cuadradas enteras, no mediante exploración ciega.
Para cada par exterior, la implementación construye el rango impar admisible de la coordenada interior. Si el hueco central no está activo, se evalúa un solo intervalo. Si sí está activo, se evalúan por separado un intervalo negativo y uno positivo. En ambos casos se usan únicamente las fórmulas cerradas para \(\sum w\) y \(\sum w^2\), de modo que el trabajo interno es constante.
Toda la aritmética se reduce módulo \(433494437\). La implementación en C++ paraleliza el bucle exterior porque las distintas rebanadas impares de \(u\) son independientes; las versiones en Python y Java aplican las mismas cotas y fórmulas de forma secuencial. La versión en C++ también verifica \(S(5)=48\) y \(S(10^3)=37048340\) antes de evaluar el objetivo final.
La coordenada exterior recorre \(O(\sqrt{n})\) valores impares y, para cada uno, la segunda coordenada tiene a lo sumo \(O(\sqrt{n})\) posibilidades impares. Por eso el número total de pares exteriores factibles es \(O(n)\). Como cada par se resuelve con a lo sumo dos evaluaciones de intervalo en tiempo constante, el tiempo total es \(O(n)\). Las versiones secuenciales usan \(O(1)\) memoria auxiliar, mientras que la versión paralela en C++ usa \(O(P)\) almacenamiento parcial para \(P\) hilos de trabajo.
第 791 题研究的是满足“平均数等于方差”的非降正整数四元组 \((a,b,c,d)\)。记
$$\mu=\frac{a+b+c+d}{4},\qquad V=\frac{(a-\mu)^2+(b-\mu)^2+(c-\mu)^2+(d-\mu)^2}{4},$$
那么我们要找出所有满足 \(\mu=V\) 且 \(\mu\le n\) 的四元组，并把它们的总和 \(a+b+c+d=4\mu\) 累加起来，得到 \(S(n)\)。当 \(n=10^8\) 时，直接在四个原始变量上暴力搜索完全不可行，因此实现采用了三维奇数坐标下的等价表示，并把最内层的枚举改写成闭式求和。
三份实现真正依赖的关键事实是：原来的“平均数 = 方差”条件，可以经过代数消元和线性变换，改写成一个只含三个奇整数的格点问题。一旦走到这个阶段，剩下的就是如何高效地遍历可行区域并把贡献一次性求出来。
把原四元组排序、去掉冗余自由度，再做实现中使用的线性变换之后，每一个合法对象都对应于一组三个奇整数 \((u,v,w)\)，并满足
$$u\equiv v\equiv w\equiv 1\pmod 2.$$
该对象对 \(S(n)\) 的贡献变成
$$T(u,v,w)=\frac{u^2+v^2+w^2+2u+2v+2w+3}{2}.$$
这就是实现实际累加的量。也就是说，程序并不再显式枚举原来的四元组，而是只在这个缩减后的 \((u,v,w)\) 空间中工作。
先设
$$R=8n.$$
最外层坐标 \(u\) 只能取满足
$$1\le u\le \left\lfloor\sqrt{R+3}\right\rfloor-2,\qquad u\equiv 1\pmod 2$$
的奇数。对固定的 \(u\)，第二个坐标 \(v\) 只能落在
$$-1\le v\le \min\!\left(u,\left\lfloor\sqrt{R-u^2-4u-1}\right\rfloor-2\right),\qquad v\equiv 1\pmod 2$$
之内。这样一来，大部分不可能的区域在进入内层之前就被剪掉了。原本四维的粗暴枚举，被压缩成了一个弯曲的二维外层区域。
对每个可行的 \((u,v)\)，定义
$$w_{\max}=\left\lfloor\sqrt{R-u^2-v^2-4u-4v-5}\right\rfloor.$$
于是 \(w\) 首先必须位于奇数区间
$$\max(-w_{\max},-v-2)\le w\le \min(w_{\max},v),\qquad w\equiv 1\pmod 2.$$
但还要再检查一个额外限制。如果
$$11-u^2-v^2>0,$$
那么区间中间的一段要被去掉，只保留
$$|w|\ge \left\lceil\sqrt{11-u^2-v^2}\right\rceil$$
的值。这样，固定 \((u,v)\) 以后，最内层集合永远不会是杂乱无章的散点，它只会是一个奇数区间，或者两个被中央空洞隔开的奇数区间。正是这个结构，使得后面的闭式求和可以直接使用。
设某个可行的 \(w\)-区间为
$$w=L,L+2,\dots,H,$$
其中 \(L,H\) 都是奇数。定义
$$m=\frac{H-L}{2}+1,\qquad w_j=L+2j\quad (0\le j\le m-1).$$
那么
$$\sum_{j=0}^{m-1} j=\frac{m(m-1)}{2},\qquad \sum_{j=0}^{m-1} j^2=\frac{(m-1)m(2m-1)}{6},$$
从而
$$\sum_{j=0}^{m-1} w_j=mL+2\sum_{j=0}^{m-1}j,$$
$$\sum_{j=0}^{m-1} w_j^2=mL^2+4L\sum_{j=0}^{m-1}j+4\sum_{j=0}^{m-1}j^2.$$
如果把与 \(w\) 无关的部分记为
$$K(u,v)=u^2+v^2+2u+2v+3,$$
那么整个区间的贡献就是
$$\sum_{j=0}^{m-1} T(u,v,w_j)=\frac{mK(u,v)+\sum w_j^2+2\sum w_j}{2}.$$
这一步的意义非常大：原本可能很长的内层循环，被压缩成了少量的整数运算。
如果中央禁止带不存在，那么一次闭式计算就够了。如果中央禁止带存在，可行奇数值会裂成一段负半轴尾部和一段正半轴尾部：
$$[L,H]\cap\{w:w\equiv 1\pmod 2\}=[L,-c]\cup[c,H],$$
其中 \(c\) 是最小的可行奇数阈值。两段都用同一套区间公式求和，最后再按模 \(433494437\) 相加。
因此，算法从来不会把合法的 \(w\) 一个一个地枚举出来。C++、Python 和 Java 三份实现共享的决定性优化，就是把最内层彻底改写成区间求和。
当 \(n=5\) 时，\(R=40\)。缩减后的搜索空间里恰好只有下面这些可行奇数三元组：
$$\begin{aligned} (1,1,-3)&\mapsto T=6,\\ (3,-1,-1)&\mapsto T=8,\\ (3,1,-3)&\mapsto T=12,\\ (3,1,-1)&\mapsto T=10,\\ (3,1,1)&\mapsto T=12. \end{aligned}$$
所以
$$S(5)=6+8+12+10+12=48,$$
这正好与实现里使用的小规模校验值一致。
C++、Python 和 Java 三个实现遵循完全相同的数学流程。它们先计算 \(R=8n\)，求出最外层奇数坐标的最大可能值，然后遍历所有可行的奇数对 \((u,v)\)。这些边界不是靠试探得到的，而是通过整数平方根直接给出最紧的上界。
对每一个外层二元组，程序都会构造最内层坐标的可行奇数区间。如果中央空洞不出现，就直接对一个区间求和；如果中央空洞出现，就分别对负区间和正区间求和。无论哪种情况，真正使用的都只是 \(\sum w\) 和 \(\sum w^2\) 的闭式公式，因此最内层始终是常数时间。
所有运算都按模 \(433494437\) 进行。C++ 版本因为不同的奇数 \(u\) 切片互不相关，所以把外层循环并行化；Python 和 Java 版本使用同样的边界与公式顺序执行。C++ 版本在计算目标值之前，还会先验证 \(S(5)=48\) 和 \(S(10^3)=37048340\) 这两个检查点。
最外层坐标有 \(O(\sqrt{n})\) 个奇数候选值；对每一个这样的值，第二个坐标也至多有 \(O(\sqrt{n})\) 个奇数选择。因此，可行的外层二元组总数是 \(O(n)\)。每个二元组只需要至多两次常数时间的区间求值，所以总时间复杂度为 \(O(n)\)。顺序版额外空间是 \(O(1)\)，并行 C++ 版则为 \(P\) 个工作线程保存 \(O(P)\) 的部分和。
Задача 791 рассматривает неубывающие четверки положительных целых чисел \((a,b,c,d)\), для которых среднее значение равно дисперсии. Обозначим
$$\mu=\frac{a+b+c+d}{4},\qquad V=\frac{(a-\mu)^2+(b-\mu)^2+(c-\mu)^2+(d-\mu)^2}{4}.$$
Нужно найти все четверки, удовлетворяющие \(\mu=V\) и \(\mu\le n\), а затем сложить величины \(a+b+c+d=4\mu\). Эта накопленная сумма и есть \(S(n)\). При \(n=10^8\) прямой перебор по четырем исходным переменным нереален, поэтому реализации переходят к эквивалентному описанию через три нечетные координаты и заменяют внутренний перебор замкнутой формулой.
Главный факт, на котором построены реализации, состоит в том, что исходное условие «среднее равно дисперсии» можно алгебраически свести к задаче о трех нечетных целых. После этого вся работа сводится к аккуратной целочисленной арифметике.
После упорядочения четверки, исключения лишней степени свободы и линейной замены переменных, используемой в реализациях, каждая допустимая конфигурация описывается нечетными целыми \((u,v,w)\), для которых
$$u\equiv v\equiv w\equiv 1\pmod 2.$$
Ее вклад в \(S(n)\) равен
$$T(u,v,w)=\frac{u^2+v^2+w^2+2u+2v+2w+3}{2}.$$
То есть программа больше не перечисляет исходные четверки напрямую; она работает только в сокращенном пространстве \((u,v,w)\).
Положим
$$R=8n.$$
Внешняя координата \(u\) может принимать только нечетные значения из диапазона
$$1\le u\le \left\lfloor\sqrt{R+3}\right\rfloor-2,\qquad u\equiv 1\pmod 2.$$
Для фиксированного \(u\) вторая координата ограничена так:
$$-1\le v\le \min\!\left(u,\left\lfloor\sqrt{R-u^2-4u-1}\right\rfloor-2\right),\qquad v\equiv 1\pmod 2.$$
Эти границы сразу отсеивают основную часть пространства поиска. Вместо грубого четырехмерного перебора остается только искривленная двумерная внешняя область на нечетной решетке.
Для каждой допустимой пары \((u,v)\) определим
$$w_{\max}=\left\lfloor\sqrt{R-u^2-v^2-4u-4v-5}\right\rfloor.$$
Тогда \(w\) должен лежать в нечетном интервале
$$\max(-w_{\max},-v-2)\le w\le \min(w_{\max},v),\qquad w\equiv 1\pmod 2.$$
Но есть еще одно ограничение. Если
$$11-u^2-v^2>0,$$
то середина интервала запрещена, и надо сохранять только значения с условием
$$|w|\ge \left\lceil\sqrt{11-u^2-v^2}\right\rceil.$$
Поэтому при фиксированном \((u,v)\) внутренняя область никогда не превращается в хаотичный набор точек: это либо один нечетный интервал, либо два нечетных интервала, разделенных центральной дырой. Именно эта структура позволяет вычислять вклад за \(O(1)\).
Пусть некоторый допустимый интервал для \(w\) имеет вид
$$w=L,L+2,\dots,H,$$
где \(L\) и \(H\) нечетны. Введем
$$m=\frac{H-L}{2}+1,\qquad w_j=L+2j\quad (0\le j\le m-1).$$
Тогда
$$\sum_{j=0}^{m-1} j=\frac{m(m-1)}{2},\qquad \sum_{j=0}^{m-1} j^2=\frac{(m-1)m(2m-1)}{6},$$
и, следовательно,
$$\sum_{j=0}^{m-1} w_j=mL+2\sum_{j=0}^{m-1}j,$$
$$\sum_{j=0}^{m-1} w_j^2=mL^2+4L\sum_{j=0}^{m-1}j+4\sum_{j=0}^{m-1}j^2.$$
Если обозначить часть, не зависящую от \(w\), через
$$K(u,v)=u^2+v^2+2u+2v+3,$$
то полный вклад интервала равен
$$\sum_{j=0}^{m-1} T(u,v,w_j)=\frac{mK(u,v)+\sum w_j^2+2\sum w_j}{2}.$$
Тем самым длинный внутренний цикл заменяется несколькими арифметическими действиями.
Если центральное исключение отсутствует, достаточно одного замкнутого вычисления. Если оно присутствует, допустимые нечетные значения распадаются на отрицательный и положительный хвост:
$$[L,H]\cap\{w:w\equiv 1\pmod 2\}=[L,-c]\cup[c,H]$$
для минимального допустимого нечетного порога \(c\). Оба хвоста суммируются одной и той же формулой, после чего их суммы складываются по модулю \(433494437\).
Поэтому алгоритм никогда не проходит допустимые значения \(w\) по одному. Это и есть решающая оптимизация, общая для реализаций на C++, Python и Java.
При \(n=5\) имеем \(R=40\). Сокращенный поиск дает ровно следующие допустимые нечетные тройки:
$$\begin{aligned} (1,1,-3)&\mapsto T=6,\\ (3,-1,-1)&\mapsto T=8,\\ (3,1,-3)&\mapsto T=12,\\ (3,1,-1)&\mapsto T=10,\\ (3,1,1)&\mapsto T=12. \end{aligned}$$
Значит,
$$S(5)=6+8+12+10+12=48,$$
что совпадает с малой контрольной точкой, используемой решением.
Реализации на C++, Python и Java используют одну и ту же математическую схему. Сначала вычисляется \(R=8n\), затем определяется наибольшая допустимая нечетная внешняя координата, после чего перебираются все допустимые нечетные пары \((u,v)\). Верхние границы находятся через целочисленный квадратный корень, а не через слепой перебор.
Для каждой внешней пары строится допустимый нечетный диапазон внутренней координаты. Если центральная дыра не активна, вычисляется один интервал. Если активна, отдельно суммируются отрицательная и положительная части. В обоих случаях используются только замкнутые формулы для \(\sum w\) и \(\sum w^2\), так что внутренняя работа занимает постоянное время.
Все вычисления выполняются по модулю \(433494437\). Версия на C++ распараллеливает внешний цикл, потому что разные нечетные срезы по \(u\) независимы; версии на Python и Java применяют те же границы и формулы последовательно. Версия на C++ дополнительно проверяет значения \(S(5)=48\) и \(S(10^3)=37048340\), прежде чем вычислять целевой результат.
Внешняя координата принимает \(O(\sqrt{n})\) нечетных значений, и для каждого такого значения вторая координата также имеет не более \(O(\sqrt{n})\) нечетных вариантов. Поэтому число допустимых внешних пар равно \(O(n)\). Так как каждая пара обрабатывается не более чем двумя вычислениями интервалов за постоянное время, итоговая временная сложность равна \(O(n)\). Последовательные реализации используют \(O(1)\) дополнительной памяти, а параллельная реализация на C++ хранит \(O(P)\) частичных сумм для \(P\) рабочих потоков.
تتناول المسألة 791 الرباعيات غير المتناقصة من الأعداد الصحيحة الموجبة \((a,b,c,d)\) التي يكون متوسطها مساويًا لتباينها. إذا كتبنا
$$\mu=\frac{a+b+c+d}{4},\qquad V=\frac{(a-\mu)^2+(b-\mu)^2+(c-\mu)^2+(d-\mu)^2}{4},$$
فنحن نبحث عن جميع الرباعيات التي تحقق \(\mu=V\) و\(\mu\le n\)، ثم نجمع المجاميع المقابلة \(a+b+c+d=4\mu\). هذا المجموع التراكمي هو \(S(n)\). وعند \(n=10^8\) يصبح التعداد المباشر على أربعة متغيرات غير عملي إطلاقًا، لذلك تعتمد التنفيذات على صياغة مكافئة بثلاثة إحداثيات فردية وعلى جمع مغلق للمتغير الداخلي.
الحقيقة الأساسية التي تعتمد عليها التنفيذات هي أن شرط «المتوسط يساوي التباين» يمكن اختزاله جبريًا إلى مسألة شبكية بثلاثة أعداد فردية. بعد هذا الاختزال لا يبقى إلا تنفيذ الحسابات الصحيحة بكفاءة.
بعد ترتيب الرباعية، وحذف درجة الحرية الزائدة، ثم تطبيق التحويل الخطي المستخدم في التنفيذات، تصبح كل حالة صالحة ممثلة بثلاثة أعداد صحيحة فردية \((u,v,w)\) تحقق
$$u\equiv v\equiv w\equiv 1\pmod 2.$$
ويصبح إسهامها في \(S(n)\) مساويًا لـ
$$T(u,v,w)=\frac{u^2+v^2+w^2+2u+2v+2w+3}{2}.$$
أي إن التنفيذ لا يعود يعدد الرباعيات الأصلية مباشرة، بل يعمل بالكامل داخل الفضاء المختزل \((u,v,w)\).
نضع
$$R=8n.$$
عندئذٍ لا يجوز للإحداثي الخارجي \(u\) إلا أن يأخذ القيم الفردية ضمن المجال
$$1\le u\le \left\lfloor\sqrt{R+3}\right\rfloor-2,\qquad u\equiv 1\pmod 2.$$
ولكل قيمة ثابتة من \(u\)، يجب أن يحقق الإحداثي الثاني
$$-1\le v\le \min\!\left(u,\left\lfloor\sqrt{R-u^2-4u-1}\right\rfloor-2\right),\qquad v\equiv 1\pmod 2.$$
هذه الحدود تقطع معظم فضاء البحث منذ البداية. وبدل تعداد خشن رباعي الأبعاد، لا يبقى إلا نطاق خارجي ثنائي الأبعاد من نقاط فردية على شبكة منحنية.
لكل زوج مسموح \((u,v)\)، نعرّف
$$w_{\max}=\left\lfloor\sqrt{R-u^2-v^2-4u-4v-5}\right\rfloor.$$
وعندها يجب أن يقع \(w\) في المجال الفردي
$$\max(-w_{\max},-v-2)\le w\le \min(w_{\max},v),\qquad w\equiv 1\pmod 2.$$
لكن توجد أيضًا قيود إضافية. فإذا كان
$$11-u^2-v^2>0,$$
فإن منتصف المجال يصبح محظورًا، ويجب الإبقاء فقط على القيم التي تحقق
$$|w|\ge \left\lceil\sqrt{11-u^2-v^2}\right\rceil.$$
وبذلك فإن المجموعة الداخلية عند تثبيت \((u,v)\) لا تكون أبدًا مجموعة متناثرة عشوائيًا: إما مجال فردي واحد، أو مجالان فرديان يفصل بينهما فراغ مركزي. وهذه البنية هي ما يجعل الجمع بزمن ثابت ممكنًا.
لنفرض أن أحد المجالات المسموح بها لـ \(w\) هو
$$w=L,L+2,\dots,H,$$
حيث إن \(L\) و\(H\) فرديان. نعرّف
$$m=\frac{H-L}{2}+1,\qquad w_j=L+2j\quad (0\le j\le m-1).$$
إذًا
$$\sum_{j=0}^{m-1} j=\frac{m(m-1)}{2},\qquad \sum_{j=0}^{m-1} j^2=\frac{(m-1)m(2m-1)}{6},$$
ومن ثم
$$\sum_{j=0}^{m-1} w_j=mL+2\sum_{j=0}^{m-1}j,$$
$$\sum_{j=0}^{m-1} w_j^2=mL^2+4L\sum_{j=0}^{m-1}j+4\sum_{j=0}^{m-1}j^2.$$
إذا رمزنا للجزء الذي لا يعتمد على \(w\) بالرمز
$$K(u,v)=u^2+v^2+2u+2v+3,$$
فإن إسهام المجال كله يساوي
$$\sum_{j=0}^{m-1} T(u,v,w_j)=\frac{mK(u,v)+\sum w_j^2+2\sum w_j}{2}.$$
وهكذا تتحول الحلقة الداخلية الطويلة إلى عدد صغير من العمليات الحسابية.
إذا كانت منطقة المنع المركزية غير موجودة، فإن تقييمًا مغلقًا واحدًا يكفي. أما إذا كانت موجودة، فإن القيم الفردية المسموح بها تنقسم إلى ذيل سالب وذيل موجب:
$$[L,H]\cap\{w:w\equiv 1\pmod 2\}=[L,-c]\cup[c,H]$$
حيث \(c\) هو أصغر حد فردي مسموح. ويُجمع كل ذيل بالصيغة نفسها، ثم يُجمع الناتجان بترديد \(433494437\).
لهذا السبب لا يمر الخوارزمية أبدًا على قيم \(w\) الصالحة واحدة واحدة. وهذه هي الفكرة الحاسمة المشتركة بين تنفيذات C++ وPython وJava.
عندما \(n=5\)، يكون \(R=40\). وينتج البحث المختزل بالضبط الثلاثيات الفردية الصالحة التالية:
$$\begin{aligned} (1,1,-3)&\mapsto T=6,\\ (3,-1,-1)&\mapsto T=8,\\ (3,1,-3)&\mapsto T=12,\\ (3,1,-1)&\mapsto T=10,\\ (3,1,1)&\mapsto T=12. \end{aligned}$$
ومن ثم
$$S(5)=6+8+12+10+12=48,$$
وهو نفس مقدار التحقق الصغير الذي تعتمد عليه الإستراتيجية الكاملة.
تتبع تنفيذات C++ وPython وJava السلسلة الرياضية نفسها. فهي تبدأ بحساب \(R=8n\)، ثم تحدد أكبر إحداثي خارجي فردي ممكن، وبعد ذلك تمر على جميع الأزواج الفردية المسموح بها \((u,v)\). ولا تُستخرج الحدود العليا بالتجربة، بل بواسطة الجذر التربيعي الصحيح مباشرة.
لكل زوج خارجي يبني التنفيذ المجال الفردي المسموح به للإحداثي الداخلي. إذا لم تكن الفجوة المركزية فعالة، يُقيَّم مجال واحد فقط. وإذا كانت فعالة، يُقيَّم مجال سالب وآخر موجب كلٌ على حدة. وفي الحالتين لا يُستخدم إلا الصيغ المغلقة لـ \(\sum w\) و\(\sum w^2\)، ولذلك يبقى العمل الداخلي ثابت الزمن.
كل الحسابات تُختزل بترديد \(433494437\). ويوازي تنفيذ C++ الحلقة الخارجية لأن شرائح \(u\) الفردية مستقلة عن بعضها، بينما تطبق نسختا Python وJava الحدود والصيغ نفسها بشكل تسلسلي. كما تتحقق نسخة C++ من \(S(5)=48\) و\(S(10^3)=37048340\) قبل حساب القيمة المطلوبة النهائية.
يتحرك الإحداثي الخارجي عبر \(O(\sqrt{n})\) قيم فردية، ولكل قيمة منه يوجد في الإحداثي الثاني ما لا يزيد على \(O(\sqrt{n})\) خيارًا فرديًا. لذلك يكون عدد الأزواج الخارجية المسموح بها من رتبة \(O(n)\). وبما أن كل زوج يُعالَج عبر تقييم مجال واحد أو مجالين بزمن ثابت، فإن الزمن الكلي هو \(O(n)\). وتستخدم النسخ التسلسلية ذاكرة إضافية من رتبة \(O(1)\)، بينما تستخدم نسخة C++ المتوازية ذاكرة جزئية من رتبة \(O(P)\) من أجل \(P\) خيوط عاملة.