Let \(S(n)\) be the minimum exposed surface area of a connected solid made from \(n\) unit cubes in the cubic lattice. If the cubes were wrapped separately, they would use \(6n\) unit squares of paper, so the saved paper is
$$g(n)=6n-S(n).$$
The task is to compute
$$G(N)=\sum_{n=1}^{N} g(n)\pmod{10^9+7}$$
for \(N=10^{16}\). A direct search over all \(n\) or over all polycubes is hopeless, so the solution exploits the fact that optimal shapes stay as balanced as possible and differ from a box only by a thin extra layer on one face.
The entire method comes from turning a three-dimensional minimum-surface problem into a sequence of two-dimensional minimum-perimeter problems.
Suppose a box already exists and we attach \(t\) more unit cubes to one of its faces. The contact faces disappear inside the solid, the new cubes contribute top faces, and the only net increase along the boundary comes from the perimeter of the footprint drawn on that face.
Therefore the key two-dimensional quantity is the minimum perimeter \(B(t)\) of a connected polyomino with area \(t\). The optimal footprint is as square as possible, so
$$B(0)=0,\qquad B(t)=2\left\lceil 2\sqrt{t}\right\rceil \quad (t\ge 1).$$
Equivalently, if \(a=\lfloor\sqrt{t}\rfloor\), then the perimeter jumps only when we cross square or almost-square thresholds:
$$B(t)=\begin{cases} 4a, & t=a^2,\\ 4a+2, & a^2<t\le a(a+1),\\ 4a+4, & a(a+1)<t\le (a+1)^2. \end{cases}$$
Fix \(m=\lfloor \sqrt[3]{n}\rfloor\). Then \(n\) lies in the shell
$$m^3\le n<(m+1)^3.$$
Inside this shell the best side lengths stay as equal as possible, so the optimal box grows through the sequence
$$m\times m\times m,\qquad m\times m\times (m+1),\qquad m\times (m+1)\times (m+1),\qquad (m+1)\times (m+1)\times (m+1).$$
That creates three natural phases:
$$m^3\le n\le m^2(m+1),$$
$$m^2(m+1)<n\le m(m+1)^2,$$
$$m(m+1)^2<n<(m+1)^3.$$
In those three ranges the extra layer lies on a face of size \(m^2\), \(m(m+1)\), and \((m+1)^2\), respectively.
Write \(n\) as a base box plus a remainder layer.
If
$$n=m^3+t,\qquad 0\le t\le m^2,$$
then we start from the cube \(m\times m\times m\), whose surface area is \(6m^2\), so
$$S(n)=6m^2+B(t).$$
If
$$n=m^2(m+1)+t,\qquad 1\le t\le m(m+1),$$
then the base box is \(m\times m\times(m+1)\), whose surface area is
$$2\bigl(m^2+2m(m+1)\bigr),$$
hence
$$S(n)=2\bigl(m^2+2m(m+1)\bigr)+B(t).$$
If
$$n=m(m+1)^2+t,\qquad 1\le t\le (m+1)^2-1,$$
then the base box is \(m\times(m+1)\times(m+1)\), whose surface area is
$$2\bigl(2m(m+1)+(m+1)^2\bigr),$$
so
$$S(n)=2\bigl(2m(m+1)+(m+1)^2\bigr)+B(t).$$
Since \(g(n)=6n-S(n)\), the three phase formulas become
$$g(n)=6n-6m^2-B(n-m^3),\qquad m^3\le n\le m^2(m+1),$$
$$g(n)=6n-2\bigl(m^2+2m(m+1)\bigr)-B\bigl(n-m^2(m+1)\bigr),\qquad m^2(m+1)<n\le m(m+1)^2,$$
$$g(n)=6n-2\bigl(2m(m+1)+(m+1)^2\bigr)-B\bigl(n-m(m+1)^2\bigr),\qquad m(m+1)^2<n<(m+1)^3.$$
The remaining problem is now purely arithmetic: sum these formulas over intervals instead of handling each \(n\) one by one.
Define the prefix sum
$$Q(r)=\sum_{t=1}^{r} B(t).$$
Within the block where \(s=\lceil\sqrt{t}\rceil\), the first \(s-1\) values contribute \(4s-2\) and the next \(s\) values contribute \(4s\). Therefore complete square blocks can be summed exactly.
Let
$$s=\left\lceil\sqrt{r}\right\rceil,\qquad k=s-1,\qquad u=r-k^2,$$
and split the partial block into
$$u_1=\min(u,s-1),\qquad u_2=u-u_1.$$
Then
$$Q(r)=\frac{8k^3+3k^2+k}{3}+u_1(4s-2)+u_2(4s).$$
So any correction sum on a phase interval is obtained by one subtraction of two prefix values.
Take \(n=10\). Since
$$2^3=8\le 10\le 2^2\cdot 3=12,$$
we are in the first phase with \(m=2\) and \(t=10-8=2\). The two-dimensional correction is
$$B(2)=2\left\lceil 2\sqrt{2}\right\rceil=6.$$
Therefore
$$S(10)=6\cdot 2^2+6=30,$$
and the saved paper is
$$g(10)=6\cdot 10-30=30.$$
A second example from the next phase is \(n=14\). Here
$$14=2^2\cdot 3+2,$$
so
$$S(14)=2(4+12)+B(2)=32+6=38,$$
which gives
$$g(14)=84-38=46.$$
Summing the resulting values from \(n=1\) to \(18\) yields \(G(18)=530\), matching the small checkpoint used by the implementation.
The C++, Python, and Java implementations all follow the same structure. First they compute the exact integer cube root of \(N\), because only shells with \(m^3\le N\) need to be processed. Then for each \(m\) they evaluate the three phase intervals described above.
For each interval, the contribution is written as
$$6\sum_{n=L}^{R} n - C(R-L+1) - \sum_{t=A}^{B} B(t),$$
where \(C\) is the base surface area of the current box and the last term is handled by the prefix formula \(Q\). The arithmetic progression \(\sum n\) is computed in closed form, the correction term is obtained by a difference of two prefix values, and every operation is reduced modulo \(10^9+7\).
No implementation enumerates polycubes, no implementation performs dynamic programming over volumes, and no implementation stores large tables. The whole speedup comes from recognizing the geometric shell pattern and converting it into constant-time arithmetic per shell phase.
The outer loop runs for
$$m=1,2,\dots,\left\lfloor N^{1/3}\right\rfloor.$$
Each \(m\) contributes exactly three constant-time phase updates, because both the linear sum and the two-dimensional correction sum have closed forms. Hence the total running time is
$$O\!\left(N^{1/3}\right),$$
and the auxiliary memory usage is
$$O(1).$$
Sei \(S(n)\) die minimale äußere Oberfläche eines zusammenhängenden Körpers aus \(n\) Einheitswürfeln im kubischen Gitter. Würde man alle Würfel einzeln einpacken, bräuchte man \(6n\) Flächeneinheiten Papier. Die Papiereinsparung ist also
$$g(n)=6n-S(n).$$
Gesucht ist
$$G(N)=\sum_{n=1}^{N} g(n)\pmod{10^9+7}$$
für \(N=10^{16}\). Weder die Volumina \(1,\dots,N\) noch alle möglichen Polykuben lassen sich direkt durchsuchen. Der entscheidende Beobachtungspunkt ist deshalb: optimale Formen bleiben möglichst würfelnah und unterscheiden sich von einem Quader nur durch eine dünne Zusatzschicht auf einer Fläche.
Der dreidimensionale Minimalflächen-Term wird auf eine Folge zweidimensionaler Minimalumfangs-Probleme zurückgeführt.
Fügt man einer vorhandenen Box \(t\) weitere Einheitswürfel auf einer Fläche hinzu, verschwinden die Kontaktflächen im Inneren. Der Nettozuwachs der Oberfläche ist genau der Umfang der Grundrissfigur auf dieser Fläche.
Damit benötigen wir die minimale Perimeterfunktion \(B(t)\) einer zusammenhängenden Polyomino-Fläche mit Inhalt \(t\). Optimal ist eine möglichst quadratische Form, also
$$B(0)=0,\qquad B(t)=2\left\lceil 2\sqrt{t}\right\rceil \quad (t\ge 1).$$
Äquivalent gilt für \(a=\lfloor\sqrt{t}\rfloor\)
$$B(t)=\begin{cases} 4a, & t=a^2,\\ 4a+2, & a^2<t\le a(a+1),\\ 4a+4, & a(a+1)<t\le (a+1)^2. \end{cases}$$
Setze \(m=\lfloor\sqrt[3]{n}\rfloor\). Dann liegt \(n\) in der Schale
$$m^3\le n<(m+1)^3.$$
Damit die Seitenlängen möglichst ausgeglichen bleiben, wächst die optimale Box in der Reihenfolge
$$m\times m\times m,\qquad m\times m\times (m+1),\qquad m\times (m+1)\times (m+1),\qquad (m+1)\times (m+1)\times (m+1).$$
Daraus entstehen drei Phasen:
$$m^3\le n\le m^2(m+1),$$
$$m^2(m+1)<n\le m(m+1)^2,$$
$$m(m+1)^2<n<(m+1)^3.$$
In diesen Bereichen liegt die Zusatzschicht jeweils auf einer Fläche der Größe \(m^2\), \(m(m+1)\) bzw. \((m+1)^2\).
Schreibe \(n\) als Grundquader plus Restschicht.
Wenn
$$n=m^3+t,\qquad 0\le t\le m^2,$$
dann startet man vom Würfel \(m\times m\times m\) mit Oberfläche \(6m^2\). Also
$$S(n)=6m^2+B(t).$$
Wenn
$$n=m^2(m+1)+t,\qquad 1\le t\le m(m+1),$$
dann ist die Grundform \(m\times m\times(m+1)\) mit Oberfläche
$$2\bigl(m^2+2m(m+1)\bigr),$$
also
$$S(n)=2\bigl(m^2+2m(m+1)\bigr)+B(t).$$
Wenn
$$n=m(m+1)^2+t,\qquad 1\le t\le (m+1)^2-1,$$
dann ist die Grundform \(m\times(m+1)\times(m+1)\) mit Oberfläche
$$2\bigl(2m(m+1)+(m+1)^2\bigr),$$
und damit
$$S(n)=2\bigl(2m(m+1)+(m+1)^2\bigr)+B(t).$$
Mit \(g(n)=6n-S(n)\) erhält man sofort die stückweisen Formeln
$$g(n)=6n-6m^2-B(n-m^3),\qquad m^3\le n\le m^2(m+1),$$
$$g(n)=6n-2\bigl(m^2+2m(m+1)\bigr)-B\bigl(n-m^2(m+1)\bigr),\qquad m^2(m+1)<n\le m(m+1)^2,$$
$$g(n)=6n-2\bigl(2m(m+1)+(m+1)^2\bigr)-B\bigl(n-m(m+1)^2\bigr),\qquad m(m+1)^2<n<(m+1)^3.$$
Damit ist das geometrische Problem auf Summen geschlossener Formeln reduziert.
Definiere
$$Q(r)=\sum_{t=1}^{r} B(t).$$
In dem Block mit \(s=\lceil\sqrt{t}\rceil\) liefern die ersten \(s-1\) Werte den Umfang \(4s-2\), die nächsten \(s\) Werte den Umfang \(4s\). Vollständige Quadratblöcke lassen sich deshalb exakt aufsummieren.
Setze
$$s=\left\lceil\sqrt{r}\right\rceil,\qquad k=s-1,\qquad u=r-k^2,$$
sowie
$$u_1=\min(u,s-1),\qquad u_2=u-u_1.$$
Dann folgt
$$Q(r)=\frac{8k^3+3k^2+k}{3}+u_1(4s-2)+u_2(4s).$$
Jede Korrektursumme auf einem Intervall ist also nur noch die Differenz zweier Präfixwerte.
Betrachte \(n=10\). Wegen
$$2^3=8\le 10\le 2^2\cdot 3=12$$
liegen wir in Phase 1 mit \(m=2\) und \(t=2\). Es gilt
$$B(2)=2\left\lceil 2\sqrt{2}\right\rceil=6.$$
Daher
$$S(10)=6\cdot 2^2+6=30,$$
und folglich
$$g(10)=6\cdot 10-30=30.$$
Ein Beispiel aus der nächsten Phase ist \(n=14\). Dann
$$14=2^2\cdot 3+2,$$
also
$$S(14)=2(4+12)+B(2)=32+6=38,$$
und damit
$$g(14)=84-38=46.$$
Die Summe der so erhaltenen Werte von \(n=1\) bis \(18\) ergibt \(G(18)=530\), genau den kleinen Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen derselben Strategie. Zuerst wird die exakte ganzzahlige Kubikwurzel von \(N\) bestimmt, denn nur Schalen mit \(m^3\le N\) müssen betrachtet werden. Danach werden für jedes \(m\) genau die drei oben beschriebenen Phasen verarbeitet.
Jeder Phasenbeitrag wird in die Form
$$6\sum_{n=L}^{R} n - C(R-L+1) - \sum_{t=A}^{B} B(t)$$
gebracht. Hier ist \(C\) die Oberfläche des jeweiligen Grundquaders. Die lineare Summe \(\sum n\) wird direkt als arithmetische Reihe berechnet, und der Korrekturterm \(\sum B(t)\) wird mit zwei Präfixwerten von \(Q\) ausgewertet. Alle Zwischenergebnisse werden sofort modulo \(10^9+7\) reduziert.
Keine Implementierung enumeriert Polykuben, keine verwendet Volumen-Dynamik über \(1,\dots,N\), und keine speichert große Tabellen. Die Effizienz kommt allein aus der Schalenzerlegung und aus der geschlossenen Formel für die zweidimensionale Randkorrektur.
Die äußere Schleife läuft über
$$m=1,2,\dots,\left\lfloor N^{1/3}\right\rfloor.$$
Für jedes \(m\) gibt es genau drei konstante Phasenupdates. Sowohl die Summe \(\sum n\) als auch die Korrektur \(\sum B(t)\) sind geschlossene Formeln. Daher beträgt die Gesamtlaufzeit
$$O\!\left(N^{1/3}\right),$$
und der zusätzliche Speicherbedarf bleibt
$$O(1).$$
\(S(n)\), kübik kafeste yer alan \(n\) birim küpten oluşan bağlı bir cismin en küçük dış yüzey alanı olsun. Küpleri tek tek kaplasaydık \(6n\) birim kare kâğıt gerekirdi. Bu yüzden tasarruf edilen kâğıt miktarı
$$g(n)=6n-S(n)$$
olur. İstenen büyüklük
$$G(N)=\sum_{n=1}^{N} g(n)\pmod{10^9+7}$$
ve problemde \(N=10^{16}\) alınır. Ne tüm \(n\) değerleri için doğrudan arama yapılabilir ne de tüm olası poliküp şekilleri taranabilir. Çözüm, en iyi şekillerin mümkün olduğunca küpe yakın kaldığını ve kutuya sadece tek bir yüzde ince bir ek tabaka koyarak büyüdüğünü kullanır.
Üç boyutlu en küçük yüzey problemi, iki boyutlu en küçük çevre problemine indirgenir.
Elimizde bir kutu varken bir yüzüne \(t\) tane daha birim küp eklediğimizi düşünelim. Temas eden yüzler cismin içinde kaybolur. Yeni yüzey alanındaki net artış, yalnızca o yüzde oluşan izdüşümün çevresidir.
Bu nedenle temel iki boyutlu fonksiyon, alanı \(t\) olan bağlı bir poliominonun en küçük çevresi \(B(t)\)'dir. En iyi şekil kareye olabildiğince yakın olduğundan
$$B(0)=0,\qquad B(t)=2\left\lceil 2\sqrt{t}\right\rceil \quad (t\ge 1).$$
Eşdeğer olarak \(a=\lfloor\sqrt{t}\rfloor\) için
$$B(t)=\begin{cases} 4a, & t=a^2,\\ 4a+2, & a^2<t\le a(a+1),\\ 4a+4, & a(a+1)<t\le (a+1)^2. \end{cases}$$
\(m=\lfloor\sqrt[3]{n}\rfloor\) olsun. O zaman
$$m^3\le n<(m+1)^3$$
olur. Yan uzunlukları olabildiğince dengede tutmak için en iyi kutu şu sırayla büyür:
$$m\times m\times m,\qquad m\times m\times (m+1),\qquad m\times (m+1)\times (m+1),\qquad (m+1)\times (m+1)\times (m+1).$$
Böylece üç faz ortaya çıkar:
$$m^3\le n\le m^2(m+1),$$
$$m^2(m+1)<n\le m(m+1)^2,$$
$$m(m+1)^2<n<(m+1)^3.$$
Bu fazlarda ek tabaka sırasıyla \(m^2\), \(m(m+1)\) ve \((m+1)^2\) alanlı bir yüz üzerine yerleşir.
\(n\)'yi bir temel kutu ile artan tabaka olarak yazalım.
Eğer
$$n=m^3+t,\qquad 0\le t\le m^2,$$
ise başlangıç kutusu \(m\times m\times m\) küpüdür ve yüzeyi \(6m^2\)'dir. Dolayısıyla
$$S(n)=6m^2+B(t).$$
Eğer
$$n=m^2(m+1)+t,\qquad 1\le t\le m(m+1),$$
ise temel kutu \(m\times m\times(m+1)\) olur. Bunun yüzeyi
$$2\bigl(m^2+2m(m+1)\bigr)$$
olduğundan
$$S(n)=2\bigl(m^2+2m(m+1)\bigr)+B(t).$$
Eğer
$$n=m(m+1)^2+t,\qquad 1\le t\le (m+1)^2-1,$$
ise temel kutu \(m\times(m+1)\times(m+1)\) olur. Bunun yüzeyi
$$2\bigl(2m(m+1)+(m+1)^2\bigr)$$
ve sonuç
$$S(n)=2\bigl(2m(m+1)+(m+1)^2\bigr)+B(t)$$
şeklindedir.
\(g(n)=6n-S(n)\) olduğundan, parça parça şu ifadeleri elde ederiz:
$$g(n)=6n-6m^2-B(n-m^3),\qquad m^3\le n\le m^2(m+1),$$
$$g(n)=6n-2\bigl(m^2+2m(m+1)\bigr)-B\bigl(n-m^2(m+1)\bigr),\qquad m^2(m+1)<n\le m(m+1)^2,$$
$$g(n)=6n-2\bigl(2m(m+1)+(m+1)^2\bigr)-B\bigl(n-m(m+1)^2\bigr),\qquad m(m+1)^2<n<(m+1)^3.$$
Böylece geometrik soru, kapalı formda toplanabilen aritmetik ifadelere dönüşür.
Şunu tanımlayalım:
$$Q(r)=\sum_{t=1}^{r} B(t).$$
\(s=\lceil\sqrt{t}\rceil\) olan blokta ilk \(s-1\) değer \(4s-2\), sonraki \(s\) değer \(4s\) katkı verir. Bu yüzden tam kare blokları kapalı biçimde toplanabilir.
Şimdi
$$s=\left\lceil\sqrt{r}\right\rceil,\qquad k=s-1,\qquad u=r-k^2$$
ve
$$u_1=\min(u,s-1),\qquad u_2=u-u_1$$
olsun. O zaman
$$Q(r)=\frac{8k^3+3k^2+k}{3}+u_1(4s-2)+u_2(4s).$$
Demek ki herhangi bir faz aralığındaki düzeltme toplamı yalnızca iki önek değerinin farkıdır.
\(n=10\) için
$$2^3=8\le 10\le 2^2\cdot 3=12$$
olduğundan birinci fazdayız; \(m=2\) ve \(t=2\). İki boyutlu düzeltme
$$B(2)=2\left\lceil 2\sqrt{2}\right\rceil=6$$
olur. Böylece
$$S(10)=6\cdot 2^2+6=30,$$
ve tasarruf
$$g(10)=6\cdot 10-30=30$$
çıkar. Bir sonraki fazdan \(n=14\) örneğinde
$$14=2^2\cdot 3+2,$$
yani
$$S(14)=2(4+12)+B(2)=32+6=38,$$
dolayısıyla
$$g(14)=84-38=46.$$
Bu şekilde elde edilen değerler \(n=1\) ile \(18\) arasında toplandığında \(G(18)=530\) bulunur; bu da uygulamadaki küçük doğrulama değeridir.
C++, Python ve Java uygulamalarının mantığı aynıdır. Önce \(N\)'nin tam tamsayı küpkökü hesaplanır; çünkü yalnızca \(m^3\le N\) olan kabuklar işlenmelidir. Sonra her \(m\) için yukarıdaki üç faz sırayla ele alınır.
Her fazın katkısı
$$6\sum_{n=L}^{R} n - C(R-L+1) - \sum_{t=A}^{B} B(t)$$
biçimine getirilir. Burada \(C\), o fazdaki temel kutunun yüzey alanıdır. Aritmetik dizi toplamı kapalı formülle alınır; \(\sum B(t)\) düzeltmesi ise \(Q\) fonksiyonunun iki önek değeri çıkarılarak bulunur. Tüm işlemler boyunca sonuçlar \(10^9+7\) modunda tutulur.
Uygulama poliküp üretmez, hacim üzerinde dinamik programlama yapmaz ve büyük tablolar saklamaz. Hız kazanımı tamamen geometrik kabuk düzenini görüp her fazı sabit zamanda hesaplayabilmekten gelir.
Dış döngü
$$m=1,2,\dots,\left\lfloor N^{1/3}\right\rfloor$$
üzerinde çalışır. Her \(m\) için tam üç adet sabit maliyetli faz güncellemesi vardır. Hem \(\sum n\) hem de \(\sum B(t)\) kapalı formülle hesaplandığı için toplam süre
$$O\!\left(N^{1/3}\right),$$
ek bellek ise
$$O(1)$$
olur.
Sea \(S(n)\) el área superficial expuesta mínima de un sólido conectado formado por \(n\) cubos unitarios en la red cúbica. Si cada cubo se envolviera por separado, harían falta \(6n\) cuadrados unitarios de papel, así que el ahorro de papel es
$$g(n)=6n-S(n).$$
La cantidad pedida es
$$G(N)=\sum_{n=1}^{N} g(n)\pmod{10^9+7}$$
con \(N=10^{16}\). No se puede recorrer ni todos los volúmenes ni todos los policubos posibles. La solución aprovecha que la forma óptima se mantiene lo más cercana posible a un cubo y solo difiere de una caja equilibrada por una capa delgada añadida sobre una cara.
La idea central es transformar un problema tridimensional de superficie mínima en una familia de problemas bidimensionales de perímetro mínimo.
Supongamos que ya tenemos una caja y añadimos \(t\) cubos unitarios sobre una de sus caras. Las caras de contacto desaparecen dentro del sólido. El aumento neto de superficie coincide exactamente con el perímetro de la huella bidimensional dibujada sobre esa cara.
Por tanto necesitamos la función \(B(t)\), el perímetro mínimo de un poliominó conectado de área \(t\). La mejor huella es lo más cuadrada posible, así que
$$B(0)=0,\qquad B(t)=2\left\lceil 2\sqrt{t}\right\rceil \quad (t\ge 1).$$
De manera equivalente, si \(a=\lfloor\sqrt{t}\rfloor\), entonces
$$B(t)=\begin{cases} 4a, & t=a^2,\\ 4a+2, & a^2<t\le a(a+1),\\ 4a+4, & a(a+1)<t\le (a+1)^2. \end{cases}$$
Tomemos \(m=\lfloor\sqrt[3]{n}\rfloor\). Entonces
$$m^3\le n<(m+1)^3.$$
Para mantener equilibradas las tres dimensiones, la caja óptima crece siguiendo
$$m\times m\times m,\qquad m\times m\times (m+1),\qquad m\times (m+1)\times (m+1),\qquad (m+1)\times (m+1)\times (m+1).$$
Esto divide la capa en tres fases:
$$m^3\le n\le m^2(m+1),$$
$$m^2(m+1)<n\le m(m+1)^2,$$
$$m(m+1)^2<n<(m+1)^3.$$
En esas fases la capa adicional se apoya sobre caras de tamaño \(m^2\), \(m(m+1)\) y \((m+1)^2\), respectivamente.
Escribimos \(n\) como una caja base más una capa residual.
Si
$$n=m^3+t,\qquad 0\le t\le m^2,$$
partimos del cubo \(m\times m\times m\), cuya superficie es \(6m^2\), de modo que
$$S(n)=6m^2+B(t).$$
Si
$$n=m^2(m+1)+t,\qquad 1\le t\le m(m+1),$$
la caja base es \(m\times m\times(m+1)\), con superficie
$$2\bigl(m^2+2m(m+1)\bigr),$$
y por tanto
$$S(n)=2\bigl(m^2+2m(m+1)\bigr)+B(t).$$
Si
$$n=m(m+1)^2+t,\qquad 1\le t\le (m+1)^2-1,$$
la caja base es \(m\times(m+1)\times(m+1)\), con superficie
$$2\bigl(2m(m+1)+(m+1)^2\bigr),$$
de donde
$$S(n)=2\bigl(2m(m+1)+(m+1)^2\bigr)+B(t).$$
Como \(g(n)=6n-S(n)\), obtenemos
$$g(n)=6n-6m^2-B(n-m^3),\qquad m^3\le n\le m^2(m+1),$$
$$g(n)=6n-2\bigl(m^2+2m(m+1)\bigr)-B\bigl(n-m^2(m+1)\bigr),\qquad m^2(m+1)<n\le m(m+1)^2,$$
$$g(n)=6n-2\bigl(2m(m+1)+(m+1)^2\bigr)-B\bigl(n-m(m+1)^2\bigr),\qquad m(m+1)^2<n<(m+1)^3.$$
Así, el problema geométrico queda convertido en sumas de expresiones cerradas.
Definimos el prefijo
$$Q(r)=\sum_{t=1}^{r} B(t).$$
Dentro del bloque en que \(s=\lceil\sqrt{t}\rceil\), los primeros \(s-1\) valores aportan \(4s-2\) y los siguientes \(s\) valores aportan \(4s\). Por eso los bloques completos entre cuadrados perfectos se pueden sumar exactamente.
Sea
$$s=\left\lceil\sqrt{r}\right\rceil,\qquad k=s-1,\qquad u=r-k^2,$$
y además
$$u_1=\min(u,s-1),\qquad u_2=u-u_1.$$
Entonces
$$Q(r)=\frac{8k^3+3k^2+k}{3}+u_1(4s-2)+u_2(4s).$$
Cualquier suma de corrección sobre una fase se obtiene restando dos valores de este prefijo.
Tomemos \(n=10\). Como
$$2^3=8\le 10\le 2^2\cdot 3=12,$$
estamos en la primera fase con \(m=2\) y \(t=2\). La corrección bidimensional es
$$B(2)=2\left\lceil 2\sqrt{2}\right\rceil=6.$$
Por tanto
$$S(10)=6\cdot 2^2+6=30,$$
y el ahorro es
$$g(10)=6\cdot 10-30=30.$$
Un ejemplo de la fase siguiente es \(n=14\). Aquí
$$14=2^2\cdot 3+2,$$
de modo que
$$S(14)=2(4+12)+B(2)=32+6=38,$$
y entonces
$$g(14)=84-38=46.$$
Si se suman los valores obtenidos desde \(n=1\) hasta \(n=18\), se llega a \(G(18)=530\), que coincide con la comprobación pequeña de la implementación.
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Primero calculan la raíz cúbica entera exacta de \(N\), porque solo deben procesarse las capas con \(m^3\le N\). Después, para cada \(m\), recorren las tres fases geométricas descritas arriba.
Cada contribución de fase se escribe como
$$6\sum_{n=L}^{R} n - C(R-L+1) - \sum_{t=A}^{B} B(t),$$
donde \(C\) es la superficie de la caja base de esa fase. La suma aritmética \(\sum n\) se evalúa en forma cerrada, y la corrección \(\sum B(t)\) se obtiene como diferencia de dos valores del prefijo \(Q\). Todas las operaciones se reducen módulo \(10^9+7\).
La implementación no enumera policubos, no hace programación dinámica por volumen y no mantiene tablas grandes. Toda la aceleración viene de reconocer la estructura por capas y de convertir cada fase en unas pocas operaciones aritméticas.
El bucle exterior recorre
$$m=1,2,\dots,\left\lfloor N^{1/3}\right\rfloor.$$
Cada \(m\) aporta exactamente tres actualizaciones de costo constante. Tanto \(\sum n\) como \(\sum B(t)\) tienen fórmulas cerradas, así que el tiempo total es
$$O\!\left(N^{1/3}\right),$$
y la memoria auxiliar es
$$O(1).$$
设 \(S(n)\) 表示由 \(n\) 个单位立方体在三维整数格中拼成的连通立体所能达到的最小外表面积。如果把这 \(n\) 个立方体分别包起来，需要 \(6n\) 个单位面积的纸，因此节省的纸张数量为
$$g(n)=6n-S(n).$$
题目要求计算
$$G(N)=\sum_{n=1}^{N} g(n)\pmod{10^9+7}$$
其中 \(N=10^{16}\)。无论是逐个枚举 \(n\)，还是枚举所有可能的多立方体形状，规模都完全不可行。真正可用的结构性事实是：最优形状始终尽量接近立方体，只是在某一个面上额外加上一层很薄的方块。
整套做法的核心，是把三维最小表面积问题化成一系列二维最小周长问题。
假设我们已经有一个长方体，现在在它的某个面上再贴上 \(t\) 个单位立方体。与原立体接触的那些面会消失到内部，新增加的外表面积净增量，恰好等于这 \(t\) 个方块在该面上投影出的二维图形的周长。
因此需要研究二维函数 \(B(t)\)：面积为 \(t\) 的连通多连方形的最小周长。最优形状总是尽量接近正方形，所以有
$$B(0)=0,\qquad B(t)=2\left\lceil 2\sqrt{t}\right\rceil \quad (t\ge 1).$$
如果记 \(a=\lfloor\sqrt{t}\rfloor\)，也可以写成分段形式
$$B(t)=\begin{cases} 4a, & t=a^2,\\ 4a+2, & a^2<t\le a(a+1),\\ 4a+4, & a(a+1)<t\le (a+1)^2. \end{cases}$$
这说明周长只会在越过正方形或“差一行的长方形”边界时发生跳变。
令 \(m=\lfloor\sqrt[3]{n}\rfloor\)。则 \(n\) 一定满足
$$m^3\le n<(m+1)^3.$$
在这个壳层里，要让外表面积尽可能小，三条边应该尽可能接近，因此最优底盒会依次经过
$$m\times m\times m,\qquad m\times m\times (m+1),\qquad m\times (m+1)\times (m+1),\qquad (m+1)\times (m+1)\times (m+1).$$
于是壳层自然被分成三段：
$$m^3\le n\le m^2(m+1),$$
$$m^2(m+1)<n\le m(m+1)^2,$$
$$m(m+1)^2<n<(m+1)^3.$$
这三段中，额外那一层分别放在面积为 \(m^2\)、\(m(m+1)\) 和 \((m+1)^2\) 的面上。
把 \(n\) 写成“基础长方体 + 一层剩余方块”的形式。
若
$$n=m^3+t,\qquad 0\le t\le m^2,$$
则基础形状是边长为 \(m\) 的立方体，表面积为 \(6m^2\)，因此
$$S(n)=6m^2+B(t).$$
若
$$n=m^2(m+1)+t,\qquad 1\le t\le m(m+1),$$
则基础长方体是 \(m\times m\times (m+1)\)，其表面积为
$$2\bigl(m^2+2m(m+1)\bigr),$$
所以
$$S(n)=2\bigl(m^2+2m(m+1)\bigr)+B(t).$$
若
$$n=m(m+1)^2+t,\qquad 1\le t\le (m+1)^2-1,$$
则基础长方体是 \(m\times (m+1)\times (m+1)\)，其表面积为
$$2\bigl(2m(m+1)+(m+1)^2\bigr),$$
从而
$$S(n)=2\bigl(2m(m+1)+(m+1)^2\bigr)+B(t).$$
由 \(g(n)=6n-S(n)\)，立刻得到三段对应的表达式：
$$g(n)=6n-6m^2-B(n-m^3),\qquad m^3\le n\le m^2(m+1),$$
$$g(n)=6n-2\bigl(m^2+2m(m+1)\bigr)-B\bigl(n-m^2(m+1)\bigr),\qquad m^2(m+1)<n\le m(m+1)^2,$$
$$g(n)=6n-2\bigl(2m(m+1)+(m+1)^2\bigr)-B\bigl(n-m(m+1)^2\bigr),\qquad m(m+1)^2<n<(m+1)^3.$$
到这里，几何最优化已经变成了若干个可以直接求和的算术公式。
定义前缀函数
$$Q(r)=\sum_{t=1}^{r} B(t).$$
当 \(s=\lceil\sqrt{t}\rceil\) 固定时，这一块中的前 \(s-1\) 个值都等于 \(4s-2\)，后 \(s\) 个值都等于 \(4s\)。因此，介于连续平方数之间的整块贡献可以一次性写成闭式。
设
$$s=\left\lceil\sqrt{r}\right\rceil,\qquad k=s-1,\qquad u=r-k^2,$$
再把最后一块拆成
$$u_1=\min(u,s-1),\qquad u_2=u-u_1.$$
则有
$$Q(r)=\frac{8k^3+3k^2+k}{3}+u_1(4s-2)+u_2(4s).$$
这样一来，任何区间上的二维修正和都只需要做两次前缀值相减。
先看 \(n=10\)。因为
$$2^3=8\le 10\le 2^2\cdot 3=12,$$
它位于第一段，所以 \(m=2\)，且 \(t=10-8=2\)。二维修正为
$$B(2)=2\left\lceil 2\sqrt{2}\right\rceil=6.$$
于是
$$S(10)=6\cdot 2^2+6=30,$$
节省的纸张是
$$g(10)=6\cdot 10-30=30.$$
再看下一段中的 \(n=14\)。此时
$$14=2^2\cdot 3+2,$$
因此
$$S(14)=2(4+12)+B(2)=32+6=38,$$
从而
$$g(14)=84-38=46.$$
把 \(n=1\) 到 \(18\) 的这些值相加，可得 \(G(18)=530\)，这正好对应实现中的小规模校验点。
C++、Python 和 Java 实现采用完全相同的思路。第一步先求出 \(N\) 的精确整数立方根，因为只需要处理满足 \(m^3\le N\) 的壳层。然后对每个 \(m\)，依次处理上面的三段区间。
每一段的贡献都被写成
$$6\sum_{n=L}^{R} n - C(R-L+1) - \sum_{t=A}^{B} B(t),$$
其中 \(C\) 是该段基础长方体的表面积。线性项 \(\sum n\) 用等差数列公式直接求出，修正项 \(\sum B(t)\) 则通过前缀函数 \(Q\) 的两个值相减得到。所有中间结果都在模 \(10^9+7\) 下维护。
实现并不会枚举多立方体，不会对体积做动态规划，也不会保存大数组。性能提升完全来自于识别出几何壳层结构，并把每个壳层阶段化成常数次算术运算。
外层循环只需遍历
$$m=1,2,\dots,\left\lfloor N^{1/3}\right\rfloor.$$
每个 \(m\) 恰好只有三个常数时间的阶段更新，而 \(\sum n\) 与 \(\sum B(t)\) 都有闭式，所以总时间复杂度为
$$O\!\left(N^{1/3}\right),$$
额外空间复杂度为
$$O(1).$$
Пусть \(S(n)\) обозначает минимальную внешнюю площадь поверхности связного тела из \(n\) единичных кубиков в кубической решетке. Если бы каждый кубик заворачивался отдельно, потребовалось бы \(6n\) единичных квадратов бумаги, поэтому экономия бумаги равна
$$g(n)=6n-S(n).$$
Нужно вычислить
$$G(N)=\sum_{n=1}^{N} g(n)\pmod{10^9+7}$$
для \(N=10^{16}\). Прямой перебор объемов или всех возможных поликубов невозможен. Решение основано на том, что оптимальная форма всегда остается максимально близкой к кубу и отличается от сбалансированного параллелепипеда только тонким дополнительным слоем на одной грани.
Трехмерная задача о минимальной поверхности сводится к последовательности двумерных задач о минимальном периметре.
Предположим, что у нас уже есть коробка, и мы добавляем к одной ее грани еще \(t\) единичных кубиков. Контактные грани уходят внутрь тела. Чистый прирост внешней поверхности равен ровно периметру двумерного следа этих \(t\) кубиков на выбранной грани.
Значит, нам нужна функция \(B(t)\): минимальный периметр связного полиомино площади \(t\). Оптимальная форма максимально близка к квадрату, поэтому
$$B(0)=0,\qquad B(t)=2\left\lceil 2\sqrt{t}\right\rceil \quad (t\ge 1).$$
Эквивалентно, если \(a=\lfloor\sqrt{t}\rfloor\), то
$$B(t)=\begin{cases} 4a, & t=a^2,\\ 4a+2, & a^2<t\le a(a+1),\\ 4a+4, & a(a+1)<t\le (a+1)^2. \end{cases}$$
Положим \(m=\lfloor\sqrt[3]{n}\rfloor\). Тогда
$$m^3\le n<(m+1)^3.$$
Чтобы три измерения оставались как можно более равными, оптимальная базовая коробка проходит через последовательность
$$m\times m\times m,\qquad m\times m\times (m+1),\qquad m\times (m+1)\times (m+1),\qquad (m+1)\times (m+1)\times (m+1).$$
Отсюда возникают три фазы:
$$m^3\le n\le m^2(m+1),$$
$$m^2(m+1)<n\le m(m+1)^2,$$
$$m(m+1)^2<n<(m+1)^3.$$
В этих трех диапазонах дополнительный слой лежит соответственно на грани площади \(m^2\), \(m(m+1)\) и \((m+1)^2\).
Представим \(n\) как объем базового параллелепипеда плюс остаточный слой.
Если
$$n=m^3+t,\qquad 0\le t\le m^2,$$
то базовая фигура - куб \(m\times m\times m\) с площадью поверхности \(6m^2\), поэтому
$$S(n)=6m^2+B(t).$$
Если
$$n=m^2(m+1)+t,\qquad 1\le t\le m(m+1),$$
то базовая фигура - прямоугольный параллелепипед \(m\times m\times (m+1)\) с площадью
$$2\bigl(m^2+2m(m+1)\bigr),$$
и тогда
$$S(n)=2\bigl(m^2+2m(m+1)\bigr)+B(t).$$
Если
$$n=m(m+1)^2+t,\qquad 1\le t\le (m+1)^2-1,$$
то базовая фигура - \(m\times (m+1)\times (m+1)\) с площадью
$$2\bigl(2m(m+1)+(m+1)^2\bigr),$$
следовательно
$$S(n)=2\bigl(2m(m+1)+(m+1)^2\bigr)+B(t).$$
Поскольку \(g(n)=6n-S(n)\), получаем кусочные формулы
$$g(n)=6n-6m^2-B(n-m^3),\qquad m^3\le n\le m^2(m+1),$$
$$g(n)=6n-2\bigl(m^2+2m(m+1)\bigr)-B\bigl(n-m^2(m+1)\bigr),\qquad m^2(m+1)<n\le m(m+1)^2,$$
$$g(n)=6n-2\bigl(2m(m+1)+(m+1)^2\bigr)-B\bigl(n-m(m+1)^2\bigr),\qquad m(m+1)^2<n<(m+1)^3.$$
После этого геометрическая часть задачи исчезает: остается только быстро суммировать эти выражения по интервалам.
Введем префикс
$$Q(r)=\sum_{t=1}^{r} B(t).$$
В блоке, где \(s=\lceil\sqrt{t}\rceil\), первые \(s-1\) значений дают вклад \(4s-2\), а следующие \(s\) значений дают вклад \(4s\). Поэтому полные блоки между соседними квадратами можно просуммировать в явном виде.
Пусть
$$s=\left\lceil\sqrt{r}\right\rceil,\qquad k=s-1,\qquad u=r-k^2,$$
и
$$u_1=\min(u,s-1),\qquad u_2=u-u_1.$$
Тогда
$$Q(r)=\frac{8k^3+3k^2+k}{3}+u_1(4s-2)+u_2(4s).$$
Любая сумма поправки на фазовом интервале сводится к разности двух таких префиксов.
Рассмотрим \(n=10\). Так как
$$2^3=8\le 10\le 2^2\cdot 3=12,$$
мы находимся в первой фазе, то есть \(m=2\) и \(t=2\). Двумерная поправка равна
$$B(2)=2\left\lceil 2\sqrt{2}\right\rceil=6.$$
Следовательно,
$$S(10)=6\cdot 2^2+6=30,$$
а экономия бумаги составляет
$$g(10)=6\cdot 10-30=30.$$
Пример из следующей фазы: \(n=14\). Здесь
$$14=2^2\cdot 3+2,$$
поэтому
$$S(14)=2(4+12)+B(2)=32+6=38,$$
и
$$g(14)=84-38=46.$$
Если просуммировать полученные значения от \(n=1\) до \(n=18\), получится \(G(18)=530\), что совпадает с малой проверкой в реализации.
Реализации на C++, Python и Java устроены одинаково. Сначала вычисляется точный целочисленный кубический корень из \(N\), потому что нужно обработать только оболочки с \(m^3\le N\). Затем для каждого \(m\) последовательно считаются три фазовых интервала, описанных выше.
Вклад каждой фазы приводится к виду
$$6\sum_{n=L}^{R} n - C(R-L+1) - \sum_{t=A}^{B} B(t),$$
где \(C\) - площадь поверхности базового параллелепипеда. Сумма \(\sum n\) берется по формуле арифметической прогрессии, а поправка \(\sum B(t)\) вычисляется как разность двух значений префикса \(Q\). Все промежуточные результаты сразу берутся по модулю \(10^9+7\).
Код не перечисляет поликубы, не делает динамику по всем объемам и не хранит большие массивы. Вся эффективность возникает из геометрического разбиения на оболочки и из того, что каждая фаза считается за константное время.
Внешний цикл проходит по
$$m=1,2,\dots,\left\lfloor N^{1/3}\right\rfloor.$$
Для каждого \(m\) выполняются ровно три обновления постоянной стоимости. И линейная сумма \(\sum n\), и двумерная поправка \(\sum B(t)\) имеют замкнутую форму, поэтому общее время работы равно
$$O\!\left(N^{1/3}\right),$$
а дополнительная память равна
$$O(1).$$
لنعرّف \(S(n)\) على أنه أقل مساحة سطح خارجية يمكن الحصول عليها من جسم متصل مكوّن من \(n\) مكعبات وحدوية على الشبكة التكعيبية. ولو قمنا بتغليف كل مكعب على حدة لاحتجنا إلى \(6n\) مربعات وحدوية من الورق، لذا فإن كمية الورق الموفَّرة هي
$$g(n)=6n-S(n).$$
والمطلوب هو حساب
$$G(N)=\sum_{n=1}^{N} g(n)\pmod{10^9+7}$$
عندما يكون \(N=10^{16}\). من المستحيل عمليًا تعداد جميع القيم أو جميع أشكال المجسمات الممكنة. الفكرة الحاسمة هي أن الشكل الأمثل يبقى قريبًا من المكعب قدر الإمكان، ولا يختلف عن صندوق متوازن إلا بإضافة طبقة رقيقة على أحد الأوجه.
الحل يحوّل مسألة ثلاثية الأبعاد عن أقل مساحة سطح إلى سلسلة من مسائل ثنائية الأبعاد عن أقل محيط.
افترض أن لدينا صندوقًا جاهزًا، ثم أضفنا \(t\) مكعبات وحدوية على أحد أوجهه. الأوجه الملامسة تختفي داخل الجسم، ولذلك فإن الزيادة الصافية في المساحة الخارجية تساوي تمامًا محيط البصمة الثنائية الأبعاد لهذه المكعبات على ذلك الوجه.
إذن نحتاج إلى الدالة \(B(t)\)، وهي أقل محيط لبوليومينو متصل مساحته \(t\). الشكل الأمثل يكون أقرب ما يمكن إلى المربع، ولذلك
$$B(0)=0,\qquad B(t)=2\left\lceil 2\sqrt{t}\right\rceil \quad (t\ge 1).$$
وبصورة مكافئة، إذا كان \(a=\lfloor\sqrt{t}\rfloor\)، فإن
$$B(t)=\begin{cases} 4a, & t=a^2,\\ 4a+2, & a^2<t\le a(a+1),\\ 4a+4, & a(a+1)<t\le (a+1)^2. \end{cases}$$
لنأخذ \(m=\lfloor\sqrt[3]{n}\rfloor\). عندئذٍ يكون
$$m^3\le n<(m+1)^3.$$
ومن أجل إبقاء الأبعاد الثلاثة متقاربة قدر الإمكان، ينمو الصندوق الأمثل عبر السلسلة
$$m\times m\times m,\qquad m\times m\times (m+1),\qquad m\times (m+1)\times (m+1),\qquad (m+1)\times (m+1)\times (m+1).$$
وهذا يقسم الغلاف إلى ثلاث مراحل:
$$m^3\le n\le m^2(m+1),$$
$$m^2(m+1)<n\le m(m+1)^2,$$
$$m(m+1)^2<n<(m+1)^3.$$
في هذه المراحل تقع الطبقة الإضافية على وجه مساحته \(m^2\) ثم \(m(m+1)\) ثم \((m+1)^2\).
نكتب \(n\) على أنه حجم صندوق أساسي مضاف إليه طبقة متبقية.
إذا كان
$$n=m^3+t,\qquad 0\le t\le m^2,$$
فإن الشكل الأساسي هو المكعب \(m\times m\times m\)، ومساحة سطحه \(6m^2\)، وبالتالي
$$S(n)=6m^2+B(t).$$
وإذا كان
$$n=m^2(m+1)+t,\qquad 1\le t\le m(m+1),$$
فإن الصندوق الأساسي هو \(m\times m\times (m+1)\)، ومساحة سطحه
$$2\bigl(m^2+2m(m+1)\bigr),$$
ومن ثم
$$S(n)=2\bigl(m^2+2m(m+1)\bigr)+B(t).$$
وإذا كان
$$n=m(m+1)^2+t,\qquad 1\le t\le (m+1)^2-1,$$
فإن الصندوق الأساسي هو \(m\times (m+1)\times (m+1)\)، ومساحة سطحه
$$2\bigl(2m(m+1)+(m+1)^2\bigr),$$
وبالتالي
$$S(n)=2\bigl(2m(m+1)+(m+1)^2\bigr)+B(t).$$
بما أن \(g(n)=6n-S(n)\)، نحصل على الصيغ القطعية التالية:
$$g(n)=6n-6m^2-B(n-m^3),\qquad m^3\le n\le m^2(m+1),$$
$$g(n)=6n-2\bigl(m^2+2m(m+1)\bigr)-B\bigl(n-m^2(m+1)\bigr),\qquad m^2(m+1)<n\le m(m+1)^2,$$
$$g(n)=6n-2\bigl(2m(m+1)+(m+1)^2\bigr)-B\bigl(n-m(m+1)^2\bigr),\qquad m(m+1)^2<n<(m+1)^3.$$
بعد هذه الخطوة يصبح الجزء الهندسي من المسألة عبارة عن جمع صيغ حسابية مغلقة على فترات.
لنعرّف المجموع التراكمي
$$Q(r)=\sum_{t=1}^{r} B(t).$$
داخل الكتلة التي يكون فيها \(s=\lceil\sqrt{t}\rceil\)، تكون أول \(s-1\) قيم مساوية لـ \(4s-2\)، وتكون القيم \(s\) التالية مساوية لـ \(4s\). لذلك يمكن جمع الكتل الكاملة الواقعة بين المربعات الكاملة بصيغة مغلقة.
خذ
$$s=\left\lceil\sqrt{r}\right\rceil,\qquad k=s-1,\qquad u=r-k^2,$$
ثم قسّم الجزء الأخير إلى
$$u_1=\min(u,s-1),\qquad u_2=u-u_1.$$
عندئذٍ
$$Q(r)=\frac{8k^3+3k^2+k}{3}+u_1(4s-2)+u_2(4s).$$
وهكذا يصبح مجموع التصحيح على أي فترة مجرد فرق بين قيمتين تراكميتين.
لنأخذ \(n=10\). بما أن
$$2^3=8\le 10\le 2^2\cdot 3=12,$$
فنحن في المرحلة الأولى، أي \(m=2\) و \(t=2\). التصحيح الثنائي الأبعاد هو
$$B(2)=2\left\lceil 2\sqrt{2}\right\rceil=6.$$
إذًا
$$S(10)=6\cdot 2^2+6=30,$$
ومن ثم يكون الورق الموفَّر
$$g(10)=6\cdot 10-30=30.$$
ومثال من المرحلة التالية هو \(n=14\)، حيث
$$14=2^2\cdot 3+2,$$
فتصبح
$$S(14)=2(4+12)+B(2)=32+6=38,$$
ولذلك
$$g(14)=84-38=46.$$
وعند جمع القيم الناتجة من \(n=1\) إلى \(n=18\) نحصل على \(G(18)=530\)، وهو نفس الاختبار الصغير المستخدم في التنفيذ.
تتبع تطبيقات C++ وPython وJava البنية نفسها تمامًا. أولًا تحسب الجذر التكعيبي الصحيح لـ \(N\)، لأننا لا نحتاج إلا إلى الأغلفة التي تحقق \(m^3\le N\). بعد ذلك تعالج لكل \(m\) المراحل الثلاث المذكورة أعلاه.
كل مساهمة مرحلية تُكتب على الصورة
$$6\sum_{n=L}^{R} n - C(R-L+1) - \sum_{t=A}^{B} B(t),$$
حيث تمثل \(C\) مساحة سطح الصندوق الأساسي في تلك المرحلة. يُحسب مجموع المتتالية الحسابية \(\sum n\) مباشرةً بصيغة مغلقة، ويُحسب تصحيح \(\sum B(t)\) بطرح قيمتين من الدالة التراكمية \(Q\). وتُختزل جميع العمليات بترديد \(10^9+7\).
لا يقوم التنفيذ بتعداد الأجسام ثلاثية الأبعاد الممكنة، ولا يستخدم برمجة ديناميكية على كل الأحجام، ولا يحتاج إلى جداول كبيرة. السرعة كلها تأتي من فهم بنية الأغلفة الهندسية وتحويل كل مرحلة إلى عدد ثابت من العمليات الحسابية.
تدور الحلقة الخارجية على
$$m=1,2,\dots,\left\lfloor N^{1/3}\right\rfloor.$$
ولكل \(m\) توجد ثلاث تحديثات فقط، وكل واحدة منها بزمن ثابت لأن كلاً من \(\sum n\) و \(\sum B(t)\) يُحسب بصيغة مغلقة. لذلك يكون الزمن الكلي
$$O\!\left(N^{1/3}\right),$$
والذاكرة الإضافية
$$O(1).$$