Consider plate layouts whose pile heights are consecutive positive integers. If a layout uses exactly \(k\) piles and the smallest pile has height \(a \ge 1\), then the heights are
$$a,\ a+1,\ a+2,\ \dots,\ a+k-1.$$
The total number of plates in that layout is therefore
$$ka+\frac{k(k-1)}{2}.$$
For a limit \(n\), let \(f(n,k)\) count the valid layouts with exactly \(k\) piles and total at most \(n\). Then
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\frac{k(k-1)}{2}}{k}\right\rfloor\right).$$
Now define
$$F(n)=\sum_{k\ge 1} f(n,k),\qquad S(N)=\sum_{n=1}^{N}F(n).$$
The goal is to compute \(S(10^{16}) \bmod (10^9+7)\). A direct enumeration over \(n\), \(k\), and the starting height \(a\) would be far too slow, so the solution rewrites the count as a closed floor-sum over \(k\).
Write
$$\Delta_k=\frac{k(k-1)}{2}.$$
This is the extra number of plates forced by the consecutive increase \(0,1,\dots,k-1\) once the smallest pile height is fixed.
If the smallest pile has height \(a\), the total is \(ka+\Delta_k\). Therefore the admissible values of \(a\) satisfy
$$ka+\Delta_k\le n.$$
Equivalently,
$$a\le \frac{n-\Delta_k}{k}.$$
Since \(a\) must be a positive integer, the number of choices is exactly
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
This already explains why large \(k\) values disappear quickly: once \(\Delta_k\) is close to \(n\), there is no room left for even the smallest possible first pile.
Instead of computing \(F(n)\) for each \(n\) and then adding, sum over the number of piles first:
$$S(N)=\sum_{n=1}^{N}\sum_{k\ge 1} f(n,k)=\sum_{k\ge 1}\sum_{n=1}^{N} f(n,k).$$
For a fixed \(k\), substitute the formula from Step 1:
$$\sum_{n=1}^{N} f(n,k)=\sum_{n=1}^{N}\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
Now shift the index by setting \(m=n-\Delta_k\). Terms with \(m<k\) contribute \(0\), so the whole block becomes
$$\sum_{m=0}^{N-\Delta_k}\left\lfloor\frac{m}{k}\right\rfloor,$$
with the understanding that this contribution is zero if \(N\le \Delta_k\).
Let
$$M=N-\Delta_k.$$
If \(M>0\), divide it by \(k\):
$$M=uk+v,\qquad 0\le v<k.$$
Then the values of \(\left\lfloor m/k\right\rfloor\) appear in blocks:
$$\underbrace{0,\dots,0}_{k\text{ terms}},\ \underbrace{1,\dots,1}_{k\text{ terms}},\ \dots,\ \underbrace{u-1,\dots,u-1}_{k\text{ terms}},\ \underbrace{u,\dots,u}_{v+1\text{ terms}}.$$
Therefore
$$\sum_{m=0}^{M}\left\lfloor\frac{m}{k}\right\rfloor =k\sum_{j=0}^{u-1} j + u(v+1) =k\frac{u(u-1)}{2}+u(v+1).$$
This removes the inner sum completely.
For every \(k\) with \(\Delta_k<N\), define \(u_k\) and \(v_k\) by
$$N-\Delta_k=u_k k+v_k,\qquad 0\le v_k<k.$$
Then
$$\boxed{S(N)=\sum_{\substack{k\ge 1\\ \Delta_k<N}}\left(k\frac{u_k(u_k-1)}{2}+u_k(v_k+1)\right)\pmod{10^9+7}.}$$
Once \(\Delta_k\ge N\), all later terms vanish. Since \(\Delta_k\sim k^2/2\), only \(O(\sqrt{N})\) values of \(k\) need to be examined.
For a local example, take \(n=14\) and \(k=3\). The possible layouts have heights
$$1,2,3;\qquad 2,3,4;\qquad 3,4,5,$$
with totals \(6,9,12\). The next starting height would give \(4+5+6=15>14\), so
$$f(14,3)=3.$$
The formula agrees:
$$\Delta_3=\frac{3\cdot 2}{2}=3,\qquad \left\lfloor\frac{14-3}{3}\right\rfloor=3.$$
For a cumulative example, take \(N=10\). The nonzero contributions are
$$\begin{aligned} k=1&:&&\Delta_1=0,\ M=10=10\cdot 1+0,\ &&55,\\ k=2&:&&\Delta_2=1,\ M=9=4\cdot 2+1,\ &&20,\\ k=3&:&&\Delta_3=3,\ M=7=2\cdot 3+1,\ &&7,\\ k=4&:&&\Delta_4=6,\ M=4=1\cdot 4+0,\ &&1. \end{aligned}$$
For \(k\ge 5\), the contribution is zero. Hence
$$S(10)=55+20+7+1=83.$$
The C++, Python, and Java implementations all follow the same formula. They iterate over \(k=1,2,3,\dots\), compute the triangular offset \(\Delta_k=k(k-1)/2\), and stop as soon as \(\Delta_k\ge N\).
For each surviving \(k\), the implementation forms \(M=N-\Delta_k\), performs one integer division by \(k\), and obtains the quotient and remainder needed for
$$k\frac{u(u-1)}{2}+u(v+1).$$
Because the final answer is required modulo \(10^9+7\), the division by \(2\) is handled by multiplying with the modular inverse of \(2\). Every contribution is reduced modulo \(10^9+7\) before being added to the running total.
The C++ implementation also uses a wider integer type for intermediate products so that multiplying values near the \(10^{16}\) scale remains safe before the modular reduction. In addition, one implementation checks the closed formula against a tiny brute-force computation at \(N=100\), where both methods produce \(12656\).
The loop stops when \(k(k-1)/2\ge N\), so the number of iterations is \(O(\sqrt{N})\). Each iteration performs only constant-time arithmetic: one triangular-number computation, one subtraction, one division with remainder, a handful of modular multiplications, and one modular addition. Therefore the total running time is \(O(\sqrt{N})\), and the extra memory usage is \(O(1)\).
Betrachtet werden Plattenanordnungen, deren Stapelhöhen aufeinanderfolgende positive ganze Zahlen sind. Wenn eine Anordnung genau \(k\) Stapel besitzt und der kleinste Stapel Höhe \(a \ge 1\) hat, dann lauten die Höhen
$$a,\ a+1,\ a+2,\ \dots,\ a+k-1.$$
Die Gesamtzahl der Teller ist dann
$$ka+\frac{k(k-1)}{2}.$$
Für ein Limit \(n\) bezeichne \(f(n,k)\) die Anzahl gültiger Anordnungen mit genau \(k\) Stapeln und insgesamt höchstens \(n\) Tellern. Damit gilt
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\frac{k(k-1)}{2}}{k}\right\rfloor\right).$$
Weiter definieren wir
$$F(n)=\sum_{k\ge 1} f(n,k),\qquad S(N)=\sum_{n=1}^{N}F(n).$$
Gesucht ist \(S(10^{16}) \bmod (10^9+7)\). Eine direkte Enumeration über \(n\), \(k\) und die Startgröße \(a\) wäre viel zu langsam, also formt die Lösung die Zählung in eine geschlossene Floorsumme über \(k\) um.
Schreibe
$$\Delta_k=\frac{k(k-1)}{2}.$$
Das ist die Zusatzlast, die allein durch den aufeinanderfolgenden Anstieg \(0,1,\dots,k-1\) entsteht, sobald die kleinste Stapelhöhe feststeht.
Hat der kleinste Stapel Höhe \(a\), dann beträgt die Gesamtsumme \(ka+\Delta_k\). Zulässig sind also genau die Werte \(a\), für die
$$ka+\Delta_k\le n$$
gilt. Das ist äquivalent zu
$$a\le \frac{n-\Delta_k}{k}.$$
Da \(a\) eine positive ganze Zahl sein muss, ist die Anzahl der Möglichkeiten genau
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
Hier sieht man bereits, warum große \(k\) schnell verschwinden: Sobald \(\Delta_k\) nahe bei \(n\) liegt, bleibt nicht einmal Platz für den kleinstmöglichen ersten Stapel.
Statt erst \(F(n)\) für jedes \(n\) zu berechnen und danach zu summieren, summieren wir zunächst über die Stapelanzahl:
$$S(N)=\sum_{n=1}^{N}\sum_{k\ge 1} f(n,k)=\sum_{k\ge 1}\sum_{n=1}^{N} f(n,k).$$
Für festes \(k\) setzen wir die Formel aus Schritt 1 ein:
$$\sum_{n=1}^{N} f(n,k)=\sum_{n=1}^{N}\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
Nun verschieben wir den Index mit \(m=n-\Delta_k\). Da für \(m<k\) stets \(\lfloor m/k\rfloor=0\) gilt, wird daraus
$$\sum_{m=0}^{N-\Delta_k}\left\lfloor\frac{m}{k}\right\rfloor,$$
wobei der Beitrag als \(0\) zu verstehen ist, falls \(N\le \Delta_k\).
Setze
$$M=N-\Delta_k.$$
Falls \(M>0\), teilen wir durch \(k\):
$$M=uk+v,\qquad 0\le v<k.$$
Dann treten die Werte von \(\left\lfloor m/k\right\rfloor\) blockweise auf:
$$\underbrace{0,\dots,0}_{k\text{ Terme}},\ \underbrace{1,\dots,1}_{k\text{ Terme}},\ \dots,\ \underbrace{u-1,\dots,u-1}_{k\text{ Terme}},\ \underbrace{u,\dots,u}_{v+1\text{ Terme}}.$$
Daher gilt
$$\sum_{m=0}^{M}\left\lfloor\frac{m}{k}\right\rfloor =k\sum_{j=0}^{u-1} j + u(v+1) =k\frac{u(u-1)}{2}+u(v+1).$$
Damit ist die innere Summe vollständig eliminiert.
Für jedes \(k\) mit \(\Delta_k<N\) seien \(u_k\) und \(v_k\) durch
$$N-\Delta_k=u_k k+v_k,\qquad 0\le v_k<k$$
definiert. Dann folgt
$$\boxed{S(N)=\sum_{\substack{k\ge 1\\ \Delta_k<N}}\left(k\frac{u_k(u_k-1)}{2}+u_k(v_k+1)\right)\pmod{10^9+7}.}$$
Sobald \(\Delta_k\ge N\), verschwinden alle späteren Summanden. Da \(\Delta_k\sim k^2/2\) wächst, müssen nur \(O(\sqrt{N})\) Werte von \(k\) betrachtet werden.
Für ein lokales Beispiel nehmen wir \(n=14\) und \(k=3\). Die möglichen Anordnungen haben Höhen
$$1,2,3;\qquad 2,3,4;\qquad 3,4,5,$$
mit Summen \(6,9,12\). Die nächste Startgröße ergäbe \(4+5+6=15>14\), also
$$f(14,3)=3.$$
Die Formel liefert denselben Wert:
$$\Delta_3=\frac{3\cdot 2}{2}=3,\qquad \left\lfloor\frac{14-3}{3}\right\rfloor=3.$$
Für ein kumulatives Beispiel wählen wir \(N=10\). Die von Null verschiedenen Beiträge sind
$$\begin{aligned} k=1&:&&\Delta_1=0,\ M=10=10\cdot 1+0,\ &&55,\\ k=2&:&&\Delta_2=1,\ M=9=4\cdot 2+1,\ &&20,\\ k=3&:&&\Delta_3=3,\ M=7=2\cdot 3+1,\ &&7,\\ k=4&:&&\Delta_4=6,\ M=4=1\cdot 4+0,\ &&1. \end{aligned}$$
Für \(k\ge 5\) ist der Beitrag gleich \(0\). Also
$$S(10)=55+20+7+1=83.$$
Die C++-, Python- und Java-Implementierungen folgen alle derselben Formel. Sie iterieren über \(k=1,2,3,\dots\), berechnen den Dreieckszahl-Offset \(\Delta_k=k(k-1)/2\) und stoppen, sobald \(\Delta_k\ge N\) gilt.
Für jedes verbleibende \(k\) wird \(M=N-\Delta_k\) gebildet. Dann genügt eine ganzzahlige Division durch \(k\), um Quotient und Rest für den Ausdruck
$$k\frac{u(u-1)}{2}+u(v+1)$$
zu erhalten. Weil die Antwort modulo \(10^9+7\) verlangt ist, wird die Division durch \(2\) über das modulare Inverse von \(2\) abgewickelt. Jeder Beitrag wird vor dem Addieren modulo \(10^9+7\) reduziert.
Die C++-Implementierung verwendet außerdem einen breiteren Ganzzahltyp für Zwischenprodukte, damit Multiplikationen in der Größenordnung von \(10^{16}\) vor der Modulo-Reduktion sicher bleiben. Zusätzlich überprüft eine Implementierung die geschlossene Formel an einem kleinen Brute-Force-Fall bei \(N=100\); beide Wege liefern dort \(12656\).
Die Schleife endet bei \(k(k-1)/2\ge N\), also nach \(O(\sqrt{N})\) Iterationen. Jede Iteration enthält nur konstante Arbeit: eine Dreieckszahl, eine Subtraktion, eine Division mit Rest, einige modulare Multiplikationen und eine modulare Addition. Damit beträgt die Laufzeit insgesamt \(O(\sqrt{N})\), und der zusätzliche Speicherbedarf ist \(O(1)\).
Burada incelenen dizilimlerde yığın yükseklikleri art arda gelen pozitif tamsayılardır. Bir dizilim tam olarak \(k\) yığından oluşuyor ve en küçük yığının yüksekliği \(a \ge 1\) ise yükseklikler
$$a,\ a+1,\ a+2,\ \dots,\ a+k-1$$
şeklindedir. Bu dizilimdeki toplam tabak sayısı
$$ka+\frac{k(k-1)}{2}$$
olur. Bir \(n\) sınırı için, \(f(n,k)\) fonksiyonu tam \(k\) yığınlı ve toplam tabak sayısı en fazla \(n\) olan geçerli dizilimlerin sayısını göstersin. O zaman
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\frac{k(k-1)}{2}}{k}\right\rfloor\right).$$
Ardından
$$F(n)=\sum_{k\ge 1} f(n,k),\qquad S(N)=\sum_{n=1}^{N}F(n)$$
tanımlarını yapıyoruz. Amaç \(S(10^{16}) \bmod (10^9+7)\) değerini bulmaktır. \(n\), \(k\) ve başlangıç yüksekliği \(a\) üzerinde doğrudan dolaşmak çok yavaş olacağı için çözüm, sayımı \(k\) üzerinde kapalı bir floor-sum formuna dönüştürür.
Şunu yazalım:
$$\Delta_k=\frac{k(k-1)}{2}.$$
Bu, en küçük yığın yüksekliği sabitken sadece ardışık artış \(0,1,\dots,k-1\) nedeniyle zorunlu olarak gelen ek tabak sayısıdır.
En küçük yığının yüksekliği \(a\) ise toplam tabak sayısı \(ka+\Delta_k\) olur. Bu yüzden geçerli \(a\) değerleri
$$ka+\Delta_k\le n$$
eşitsizliğini sağlamalıdır. Bu da
$$a\le \frac{n-\Delta_k}{k}$$
anlamına gelir. \(a\) pozitif bir tamsayı olduğundan olası seçim sayısı tam olarak
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right)$$
olur. Buradan büyük \(k\) değerlerinin neden hızla yok olduğu da görülür: \(\Delta_k\), \(n\)'ye yaklaştığında en küçük ilk yığın için bile yer kalmaz.
Önce her \(n\) için \(F(n)\) hesaplayıp sonra toplamak yerine, önce yığın sayısı üzerinde toplayalım:
$$S(N)=\sum_{n=1}^{N}\sum_{k\ge 1} f(n,k)=\sum_{k\ge 1}\sum_{n=1}^{N} f(n,k).$$
Sabit bir \(k\) için, Adım 1'deki formülü yerine koyarsak
$$\sum_{n=1}^{N} f(n,k)=\sum_{n=1}^{N}\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right)$$
elde edilir. Şimdi \(m=n-\Delta_k\) kaydırmasını yapalım. \(0\le m<k\) için \(\lfloor m/k\rfloor=0\) olduğundan bu blok
$$\sum_{m=0}^{N-\Delta_k}\left\lfloor\frac{m}{k}\right\rfloor$$
şekline dönüşür. Eğer \(N\le \Delta_k\) ise bu katkı zaten sıfırdır.
$$M=N-\Delta_k$$
olsun. \(M>0\) ise \(k\)'ya bölümünden
$$M=uk+v,\qquad 0\le v<k$$
yazabiliriz. O zaman \(\left\lfloor m/k\right\rfloor\) değerleri bloklar halinde ortaya çıkar:
$$\underbrace{0,\dots,0}_{k\text{ terim}},\ \underbrace{1,\dots,1}_{k\text{ terim}},\ \dots,\ \underbrace{u-1,\dots,u-1}_{k\text{ terim}},\ \underbrace{u,\dots,u}_{v+1\text{ terim}}.$$
Dolayısıyla
$$\sum_{m=0}^{M}\left\lfloor\frac{m}{k}\right\rfloor =k\sum_{j=0}^{u-1} j + u(v+1) =k\frac{u(u-1)}{2}+u(v+1).$$
Böylece iç toplam tamamen ortadan kalkar.
\(\Delta_k<N\) olan her \(k\) için, \(u_k\) ve \(v_k\) şu şekilde tanımlansın:
$$N-\Delta_k=u_k k+v_k,\qquad 0\le v_k<k.$$
O halde
$$\boxed{S(N)=\sum_{\substack{k\ge 1\\ \Delta_k<N}}\left(k\frac{u_k(u_k-1)}{2}+u_k(v_k+1)\right)\pmod{10^9+7}.}$$
\(\Delta_k\ge N\) olduğunda sonraki tüm terimler sıfır olur. \(\Delta_k\sim k^2/2\) olduğundan sadece \(O(\sqrt{N})\) kadar \(k\) değeri incelenir.
Yerel bir örnek olarak \(n=14\) ve \(k=3\) alalım. Olası dizilimlerin yükseklikleri
$$1,2,3;\qquad 2,3,4;\qquad 3,4,5$$
olur ve toplamları \(6,9,12\)'dir. Bir sonraki başlangıç yüksekliği \(4+5+6=15>14\) verdiği için
$$f(14,3)=3$$
olur. Formül de bunu doğrular:
$$\Delta_3=\frac{3\cdot 2}{2}=3,\qquad \left\lfloor\frac{14-3}{3}\right\rfloor=3.$$
Kümülatif bir örnek olarak \(N=10\) seçelim. Sıfır olmayan katkılar
$$\begin{aligned} k=1&:&&\Delta_1=0,\ M=10=10\cdot 1+0,\ &&55,\\ k=2&:&&\Delta_2=1,\ M=9=4\cdot 2+1,\ &&20,\\ k=3&:&&\Delta_3=3,\ M=7=2\cdot 3+1,\ &&7,\\ k=4&:&&\Delta_4=6,\ M=4=1\cdot 4+0,\ &&1. \end{aligned}$$
\(k\ge 5\) için katkı sıfırdır. Bu yüzden
$$S(10)=55+20+7+1=83.$$
C++, Python ve Java uygulamaları aynı kapalı formülü izler. \(k=1,2,3,\dots\) üzerinden ilerlerler, üçgensel ofset \(\Delta_k=k(k-1)/2\) hesaplanır ve \(\Delta_k\ge N\) olur olmaz döngü durdurulur.
Her uygun \(k\) için \(M=N-\Delta_k\) bulunur. Sonra \(M\)'nin \(k\)'ya bölümünden elde edilen bölüm ve kalan kullanılarak
$$k\frac{u(u-1)}{2}+u(v+1)$$
değeri hesaplanır. Sonuç \(10^9+7\) modunda istendiği için, \(2\)'ye bölme işlemi \(2\)'nin modüler tersiyle çarpma olarak uygulanır. Her katkı toplama eklenmeden önce modulo altında indirgenir.
C++ uygulaması ayrıca ara çarpımlarda daha geniş bir tam sayı türü kullanır; böylece \(10^{16}\) ölçeğindeki sayılarla yapılan çarpımlar modulo alınmadan önce güvenli kalır. Buna ek olarak bir uygulama, optimize edilmiş formülü \(N=100\) için küçük bir kaba kuvvet hesabıyla karşılaştırır ve iki yöntem de \(12656\) sonucunu verir.
Döngü \(k(k-1)/2\ge N\) olduğunda bittiği için toplam yineleme sayısı \(O(\sqrt{N})\)'dir. Her yinelemede sadece sabit sayıda işlem vardır: bir üçgensel sayı hesabı, bir çıkarma, bir bölüm-kalan işlemi, birkaç modüler çarpma ve bir modüler toplama. Bu nedenle toplam zaman karmaşıklığı \(O(\sqrt{N})\), ek bellek kullanımı ise \(O(1)\)'dir.
Aquí se consideran disposiciones de platos cuyas alturas forman enteros positivos consecutivos. Si una disposición usa exactamente \(k\) pilas y la pila más pequeña tiene altura \(a \ge 1\), entonces las alturas son
$$a,\ a+1,\ a+2,\ \dots,\ a+k-1.$$
El número total de platos en esa disposición es
$$ka+\frac{k(k-1)}{2}.$$
Para un límite \(n\), sea \(f(n,k)\) el número de disposiciones válidas con exactamente \(k\) pilas y total a lo sumo \(n\). Entonces
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\frac{k(k-1)}{2}}{k}\right\rfloor\right).$$
Definimos además
$$F(n)=\sum_{k\ge 1} f(n,k),\qquad S(N)=\sum_{n=1}^{N}F(n).$$
La meta es calcular \(S(10^{16}) \bmod (10^9+7)\). Enumerar directamente \(n\), \(k\) y la altura inicial \(a\) sería inviable, así que la solución transforma el conteo en una suma de pisos cerrada sobre \(k\).
Escribamos
$$\Delta_k=\frac{k(k-1)}{2}.$$
Esta es la cantidad extra de platos impuesta por el incremento consecutivo \(0,1,\dots,k-1\) una vez fijada la altura mínima.
Si la pila más pequeña tiene altura \(a\), el total es \(ka+\Delta_k\). Por lo tanto, los valores admisibles de \(a\) cumplen
$$ka+\Delta_k\le n.$$
Esto equivale a
$$a\le \frac{n-\Delta_k}{k}.$$
Como \(a\) debe ser un entero positivo, el número de elecciones es exactamente
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
Esto ya muestra por qué los valores grandes de \(k\) desaparecen rápido: cuando \(\Delta_k\) se acerca a \(n\), ni siquiera queda espacio para la primera pila mínima.
En vez de calcular primero \(F(n)\) para cada \(n\) y luego sumar, conviene sumar primero sobre el número de pilas:
$$S(N)=\sum_{n=1}^{N}\sum_{k\ge 1} f(n,k)=\sum_{k\ge 1}\sum_{n=1}^{N} f(n,k).$$
Para un \(k\) fijo, sustituimos la fórmula del Paso 1:
$$\sum_{n=1}^{N} f(n,k)=\sum_{n=1}^{N}\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
Ahora desplazamos el índice con \(m=n-\Delta_k\). Como \(\lfloor m/k\rfloor=0\) para \(0\le m<k\), el bloque completo se convierte en
$$\sum_{m=0}^{N-\Delta_k}\left\lfloor\frac{m}{k}\right\rfloor,$$
entendiendo que la contribución es cero si \(N\le \Delta_k\).
Sea
$$M=N-\Delta_k.$$
Si \(M>0\), dividimos por \(k\):
$$M=uk+v,\qquad 0\le v<k.$$
Entonces los valores de \(\left\lfloor m/k\right\rfloor\) aparecen por bloques:
$$\underbrace{0,\dots,0}_{k\text{ términos}},\ \underbrace{1,\dots,1}_{k\text{ términos}},\ \dots,\ \underbrace{u-1,\dots,u-1}_{k\text{ términos}},\ \underbrace{u,\dots,u}_{v+1\text{ términos}}.$$
Por lo tanto,
$$\sum_{m=0}^{M}\left\lfloor\frac{m}{k}\right\rfloor =k\sum_{j=0}^{u-1} j + u(v+1) =k\frac{u(u-1)}{2}+u(v+1).$$
Con esto desaparece por completo la suma interna.
Para cada \(k\) con \(\Delta_k<N\), definimos \(u_k\) y \(v_k\) mediante
$$N-\Delta_k=u_k k+v_k,\qquad 0\le v_k<k.$$
Entonces
$$\boxed{S(N)=\sum_{\substack{k\ge 1\\ \Delta_k<N}}\left(k\frac{u_k(u_k-1)}{2}+u_k(v_k+1)\right)\pmod{10^9+7}.}$$
Cuando \(\Delta_k\ge N\), todos los términos siguientes se anulan. Como \(\Delta_k\sim k^2/2\), solo hace falta revisar \(O(\sqrt{N})\) valores de \(k\).
Como ejemplo local, tomemos \(n=14\) y \(k=3\). Las disposiciones posibles tienen alturas
$$1,2,3;\qquad 2,3,4;\qquad 3,4,5,$$
con sumas \(6,9,12\). La siguiente altura inicial produciría \(4+5+6=15>14\), así que
$$f(14,3)=3.$$
La fórmula coincide:
$$\Delta_3=\frac{3\cdot 2}{2}=3,\qquad \left\lfloor\frac{14-3}{3}\right\rfloor=3.$$
Para un ejemplo acumulado, tomemos \(N=10\). Las contribuciones no nulas son
$$\begin{aligned} k=1&:&&\Delta_1=0,\ M=10=10\cdot 1+0,\ &&55,\\ k=2&:&&\Delta_2=1,\ M=9=4\cdot 2+1,\ &&20,\\ k=3&:&&\Delta_3=3,\ M=7=2\cdot 3+1,\ &&7,\\ k=4&:&&\Delta_4=6,\ M=4=1\cdot 4+0,\ &&1. \end{aligned}$$
Para \(k\ge 5\), la contribución ya es cero. Por tanto,
$$S(10)=55+20+7+1=83.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma fórmula. Recorren \(k=1,2,3,\dots\), calculan el desplazamiento triangular \(\Delta_k=k(k-1)/2\) y detienen el proceso cuando \(\Delta_k\ge N\).
Para cada \(k\) válido, la implementación forma \(M=N-\Delta_k\), realiza una sola división entera por \(k\) y obtiene el cociente y el resto necesarios para
$$k\frac{u(u-1)}{2}+u(v+1).$$
Como la respuesta final se pide módulo \(10^9+7\), la división por \(2\) se maneja multiplicando por el inverso modular de \(2\). Cada contribución se reduce módulo \(10^9+7\) antes de sumarse al acumulado.
La implementación en C++ también usa un tipo entero más ancho para los productos intermedios, de modo que las multiplicaciones cercanas a \(10^{16}\) sigan siendo seguras antes de tomar el módulo. Además, una implementación compara la fórmula optimizada con un cálculo de fuerza bruta pequeño en \(N=100\), y ambos métodos dan \(12656\).
El bucle termina cuando \(k(k-1)/2\ge N\), así que el número de iteraciones es \(O(\sqrt{N})\). Cada iteración hace solo trabajo constante: una cuenta triangular, una resta, una división con resto, unas pocas multiplicaciones modulares y una suma modular. En consecuencia, el tiempo total es \(O(\sqrt{N})\) y la memoria extra es \(O(1)\).
这里考虑的是一类“盘子堆”排列：若某个排列恰好有 \(k\) 堆，并且最小那一堆的高度为 \(a \ge 1\)，那么各堆高度就是连续的正整数
$$a,\ a+1,\ a+2,\ \dots,\ a+k-1.$$
因此，这个排列使用的盘子总数为
$$ka+\frac{k(k-1)}{2}.$$
对给定上界 \(n\)，记 \(f(n,k)\) 为“恰好使用 \(k\) 堆、总盘数不超过 \(n\)”的合法排列个数，那么
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\frac{k(k-1)}{2}}{k}\right\rfloor\right).$$
再定义
$$F(n)=\sum_{k\ge 1} f(n,k),\qquad S(N)=\sum_{n=1}^{N}F(n).$$
题目要求计算的是 \(S(10^{16}) \bmod (10^9+7)\)。如果直接枚举 \(n\)、\(k\) 以及起始高度 \(a\)，计算量会非常大，所以程序必须先把计数公式改写成只依赖 \(k\) 的闭式求和。
先记
$$\Delta_k=\frac{k(k-1)}{2}.$$
它表示在最小堆高度固定之后，仅仅因为后面各堆依次多出 \(0,1,\dots,k-1\) 个盘子而额外带来的总增量。
如果最小堆高度是 \(a\)，那么总盘数就是 \(ka+\Delta_k\)。因此合法的 \(a\) 必须满足
$$ka+\Delta_k\le n.$$
改写后得到
$$a\le \frac{n-\Delta_k}{k}.$$
由于 \(a\) 必须是正整数，所以可选的起始高度个数正好是
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
这一步已经解释了为什么较大的 \(k\) 很快就不再贡献答案：当 \(\Delta_k\) 已经接近 \(n\) 时，连最小可能的第一堆都放不下。
如果按定义先逐个计算 \(F(n)\)，再把 \(n=1\) 到 \(N\) 全部相加，等于在做一层很大的外循环。更好的办法是先固定堆数 \(k\)：
$$S(N)=\sum_{n=1}^{N}\sum_{k\ge 1} f(n,k)=\sum_{k\ge 1}\sum_{n=1}^{N} f(n,k).$$
对于固定的 \(k\)，代入步骤 1 的表达式：
$$\sum_{n=1}^{N} f(n,k)=\sum_{n=1}^{N}\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
现在把下标平移，令
$$m=n-\Delta_k.$$
由于当 \(0\le m<k\) 时，\(\left\lfloor m/k\right\rfloor=0\)，所以这整块和式可以写成
$$\sum_{m=0}^{N-\Delta_k}\left\lfloor\frac{m}{k}\right\rfloor,$$
如果 \(N\le \Delta_k\)，那么这一项整体就是 \(0\)。这样一来，原来的组合计数问题被转化成了标准的 floor-sum 问题。
设
$$M=N-\Delta_k.$$
若 \(M>0\)，把它除以 \(k\)：
$$M=uk+v,\qquad 0\le v<k.$$
这时 \(\left\lfloor m/k\right\rfloor\) 的取值会按整块重复：
$$\underbrace{0,\dots,0}_{k\text{ 个}},\ \underbrace{1,\dots,1}_{k\text{ 个}},\ \dots,\ \underbrace{u-1,\dots,u-1}_{k\text{ 个}},\ \underbrace{u,\dots,u}_{v+1\text{ 个}}.$$
于是可直接求和：
$$\sum_{m=0}^{M}\left\lfloor\frac{m}{k}\right\rfloor =k\sum_{j=0}^{u-1} j + u(v+1) =k\frac{u(u-1)}{2}+u(v+1).$$
这样，原本随 \(n\) 变化的内层求和就完全消失了，每个 \(k\) 只剩下一次整数除法和一个常数时间公式。
对每个满足 \(\Delta_k<N\) 的 \(k\)，记 \(u_k\) 与 \(v_k\) 满足
$$N-\Delta_k=u_k k+v_k,\qquad 0\le v_k<k.$$
那么就有
$$\boxed{S(N)=\sum_{\substack{k\ge 1\\ \Delta_k<N}}\left(k\frac{u_k(u_k-1)}{2}+u_k(v_k+1)\right)\pmod{10^9+7}.}$$
一旦 \(\Delta_k\ge N\)，后面的所有 \(k\) 都不会再产生贡献。因为 \(\Delta_k\) 大约等于 \(k^2/2\)，所以只需要枚举到 \(k=O(\sqrt{N})\) 为止。
先看一个局部例子，取 \(n=14\)、\(k=3\)。这时合法的三堆高度分别是
$$1,2,3;\qquad 2,3,4;\qquad 3,4,5,$$
对应总盘数 \(6,9,12\)。如果起始高度再增加到 \(4\)，总数就会变成 \(4+5+6=15>14\)，所以
$$f(14,3)=3.$$
公式也给出相同结果：
$$\Delta_3=\frac{3\cdot 2}{2}=3,\qquad \left\lfloor\frac{14-3}{3}\right\rfloor=3.$$
再看累计例子 \(N=10\)。这时只有前四个 \(k\) 有非零贡献：
$$\begin{aligned} k=1&:&&\Delta_1=0,\ M=10=10\cdot 1+0,\ &&55,\\ k=2&:&&\Delta_2=1,\ M=9=4\cdot 2+1,\ &&20,\\ k=3&:&&\Delta_3=3,\ M=7=2\cdot 3+1,\ &&7,\\ k=4&:&&\Delta_4=6,\ M=4=1\cdot 4+0,\ &&1. \end{aligned}$$
当 \(k\ge 5\) 时贡献已经为零，所以
$$S(10)=55+20+7+1=83.$$
这个小例子说明了程序为什么可以把问题拆成一系列彼此独立的 \(k\)-块，然后逐块累加。
C++、Python 和 Java 实现都严格按照上面的闭式来写。它们从 \(k=1\) 开始向上枚举，先计算三角形偏移量 \(\Delta_k=k(k-1)/2\)，只要发现 \(\Delta_k\ge N\)，就可以立刻结束循环。
对每个仍然有效的 \(k\)，实现先求出
$$M=N-\Delta_k,$$
然后对 \(M\) 做一次整除与取余，得到闭式
$$k\frac{u(u-1)}{2}+u(v+1)$$
所需的商与余数。由于最终答案要求模 \(10^9+7\)，其中的除以 \(2\) 不会直接做整数除法，而是乘以 \(2\) 在该模数下的乘法逆元。
每一项贡献在加入累计答案之前都会先做模约简。C++ 实现还额外使用了更宽的整数类型来保存中间乘积，从而避免在 \(10^{16}\) 量级附近先发生溢出再取模。此外，有一个实现还把优化公式与一个很小的暴力版本在 \(N=100\) 处进行对照，两者都得到 \(12656\)，从而验证了推导没有问题。
循环在 \(k(k-1)/2\ge N\) 时结束，因此总共只会处理 \(O(\sqrt{N})\) 个 \(k\)。每个 \(k\) 仅包含常数时间操作：一次三角数计算、一次减法、一次整除与取余、若干次模乘以及一次模加。所以总体时间复杂度是 \(O(\sqrt{N})\)，额外空间复杂度是 \(O(1)\)。
Здесь рассматриваются раскладки тарелок, в которых высоты стопок образуют последовательные положительные целые числа. Если раскладка использует ровно \(k\) стопок, а самая маленькая стопка имеет высоту \(a \ge 1\), то высоты равны
$$a,\ a+1,\ a+2,\ \dots,\ a+k-1.$$
Общее число тарелок в такой раскладке равно
$$ka+\frac{k(k-1)}{2}.$$
Для ограничения \(n\) обозначим через \(f(n,k)\) число допустимых раскладок с ровно \(k\) стопками и суммарным числом тарелок не более \(n\). Тогда
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\frac{k(k-1)}{2}}{k}\right\rfloor\right).$$
Далее вводятся
$$F(n)=\sum_{k\ge 1} f(n,k),\qquad S(N)=\sum_{n=1}^{N}F(n).$$
Нужно вычислить \(S(10^{16}) \bmod (10^9+7)\). Прямой перебор по \(n\), \(k\) и стартовой высоте \(a\) был бы слишком дорогим, поэтому решение преобразует задачу в замкнутую сумму с полами по \(k\).
Обозначим
$$\Delta_k=\frac{k(k-1)}{2}.$$
Это дополнительное число тарелок, которое неизбежно появляется из-за последовательного прироста \(0,1,\dots,k-1\), когда минимальная высота уже зафиксирована.
Если минимальная стопка имеет высоту \(a\), то суммарное число тарелок равно \(ka+\Delta_k\). Значит, допустимые значения \(a\) удовлетворяют
$$ka+\Delta_k\le n.$$
Это эквивалентно условию
$$a\le \frac{n-\Delta_k}{k}.$$
Поскольку \(a\) должно быть положительным целым, число вариантов равно
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
Отсюда сразу видно, почему большие \(k\) быстро перестают влиять на ответ: когда \(\Delta_k\) становится близким к \(n\), не остается места даже для минимально возможной первой стопки.
Вместо того чтобы сначала вычислять \(F(n)\) для каждого \(n\), а потом суммировать, выгоднее сначала фиксировать число стопок:
$$S(N)=\sum_{n=1}^{N}\sum_{k\ge 1} f(n,k)=\sum_{k\ge 1}\sum_{n=1}^{N} f(n,k).$$
Для фиксированного \(k\) подставляем формулу из шага 1:
$$\sum_{n=1}^{N} f(n,k)=\sum_{n=1}^{N}\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
Теперь сдвинем индекс, положив \(m=n-\Delta_k\). Так как при \(0\le m<k\) всегда \(\lfloor m/k\rfloor=0\), весь блок переписывается как
$$\sum_{m=0}^{N-\Delta_k}\left\lfloor\frac{m}{k}\right\rfloor,$$
причем если \(N\le \Delta_k\), то этот вклад целиком равен нулю.
Положим
$$M=N-\Delta_k.$$
Если \(M>0\), разделим его на \(k\):
$$M=uk+v,\qquad 0\le v<k.$$
Тогда значения \(\left\lfloor m/k\right\rfloor\) идут блоками:
$$\underbrace{0,\dots,0}_{k\text{ членов}},\ \underbrace{1,\dots,1}_{k\text{ членов}},\ \dots,\ \underbrace{u-1,\dots,u-1}_{k\text{ членов}},\ \underbrace{u,\dots,u}_{v+1\text{ членов}}.$$
Следовательно,
$$\sum_{m=0}^{M}\left\lfloor\frac{m}{k}\right\rfloor =k\sum_{j=0}^{u-1} j + u(v+1) =k\frac{u(u-1)}{2}+u(v+1).$$
Тем самым внутренняя сумма исчезает полностью.
Для каждого \(k\), удовлетворяющего \(\Delta_k<N\), определим \(u_k\) и \(v_k\) из равенства
$$N-\Delta_k=u_k k+v_k,\qquad 0\le v_k<k.$$
Тогда получаем
$$\boxed{S(N)=\sum_{\substack{k\ge 1\\ \Delta_k<N}}\left(k\frac{u_k(u_k-1)}{2}+u_k(v_k+1)\right)\pmod{10^9+7}.}$$
Как только \(\Delta_k\ge N\), все последующие слагаемые исчезают. Поскольку \(\Delta_k\sim k^2/2\), достаточно рассмотреть только \(O(\sqrt{N})\) значений \(k\).
Для локального примера возьмем \(n=14\) и \(k=3\). Возможные высоты стопок:
$$1,2,3;\qquad 2,3,4;\qquad 3,4,5,$$
их суммы равны \(6,9,12\). Следующая стартовая высота дает \(4+5+6=15>14\), поэтому
$$f(14,3)=3.$$
Формула подтверждает это:
$$\Delta_3=\frac{3\cdot 2}{2}=3,\qquad \left\lfloor\frac{14-3}{3}\right\rfloor=3.$$
Теперь возьмем накопительный пример \(N=10\). Ненулевые вклады равны
$$\begin{aligned} k=1&:&&\Delta_1=0,\ M=10=10\cdot 1+0,\ &&55,\\ k=2&:&&\Delta_2=1,\ M=9=4\cdot 2+1,\ &&20,\\ k=3&:&&\Delta_3=3,\ M=7=2\cdot 3+1,\ &&7,\\ k=4&:&&\Delta_4=6,\ M=4=1\cdot 4+0,\ &&1. \end{aligned}$$
При \(k\ge 5\) вклад уже нулевой, значит
$$S(10)=55+20+7+1=83.$$
Реализации на C++, Python и Java используют одну и ту же замкнутую формулу. Они перебирают \(k=1,2,3,\dots\), вычисляют треугольный сдвиг \(\Delta_k=k(k-1)/2\) и останавливаются сразу, как только \(\Delta_k\ge N\).
Для каждого подходящего \(k\) вычисляется \(M=N-\Delta_k\). После этого одной операции целочисленного деления на \(k\) достаточно, чтобы получить частное и остаток для выражения
$$k\frac{u(u-1)}{2}+u(v+1).$$
Так как ответ нужен по модулю \(10^9+7\), деление на \(2\) реализуется умножением на мультипликативную обратную величину к \(2\) по этому модулю. Каждый вклад приводится по модулю до добавления к накопленной сумме.
В реализации на C++ дополнительно используется более широкий целочисленный тип для промежуточных произведений, чтобы умножения порядка \(10^{16}\) не переполнялись до взятия модуля. Кроме того, одна реализация сверяет оптимизированную формулу с маленьким полным перебором при \(N=100\); оба способа дают \(12656\).
Цикл завершается при \(k(k-1)/2\ge N\), следовательно, число итераций равно \(O(\sqrt{N})\). На каждой итерации выполняется только константный набор действий: вычисление треугольного числа, вычитание, деление с остатком, несколько умножений по модулю и одно сложение по модулю. Итак, общая временная сложность равна \(O(\sqrt{N})\), а дополнительная память составляет \(O(1)\).
نحن ندرس ترتيبات من أكوام الأطباق تكون فيها الارتفاعات أعدادًا صحيحة موجبة متتالية. فإذا كان الترتيب يستعمل بالضبط \(k\) أكوام، وكان ارتفاع أصغر كومة هو \(a \ge 1\)، فإن الارتفاعات تكون
$$a,\ a+1,\ a+2,\ \dots,\ a+k-1.$$
ومن ثم فإن العدد الكلي للأطباق في هذا الترتيب يساوي
$$ka+\frac{k(k-1)}{2}.$$
ولحد أعلى \(n\)، لتكن \(f(n,k)\) هي عدد الترتيبات الصحيحة التي تستعمل بالضبط \(k\) أكوام ويكون مجموع الأطباق فيها على الأكثر \(n\). عندئذٍ
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\frac{k(k-1)}{2}}{k}\right\rfloor\right).$$
ثم نعرّف
$$F(n)=\sum_{k\ge 1} f(n,k),\qquad S(N)=\sum_{n=1}^{N}F(n).$$
المطلوب هو حساب \(S(10^{16}) \bmod (10^9+7)\). أمّا التعداد المباشر على \(n\) و\(k\) وارتفاع البداية \(a\)، فسيكون بطيئًا جدًا، لذلك تعيد الفكرة الرياضية كتابة العد في صورة مجموع مغلق يعتمد على \(k\) فقط.
لنكتب
$$\Delta_k=\frac{k(k-1)}{2}.$$
وهذا المقدار هو الزيادة الإضافية المفروضة فقط بسبب النمط المتتالي \(0,1,\dots,k-1\) بعد تثبيت أصغر ارتفاع.
إذا كان أصغر ارتفاع يساوي \(a\)، فإن مجموع الأطباق يساوي \(ka+\Delta_k\). لذلك يجب أن تحقق القيم المسموح بها لـ \(a\)
$$ka+\Delta_k\le n.$$
وهذا يكافئ
$$a\le \frac{n-\Delta_k}{k}.$$
وبما أن \(a\) يجب أن يكون عددًا صحيحًا موجبًا، فإن عدد الخيارات يساوي بالضبط
$$f(n,k)=\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
ومن هنا يظهر مباشرةً سبب اختفاء القيم الكبيرة لـ \(k\) بسرعة: عندما تصبح \(\Delta_k\) قريبة من \(n\)، لا يبقى مجال حتى لأصغر كومة أولى ممكنة.
بدلًا من حساب \(F(n)\) لكل \(n\) أولًا ثم جمع النتائج، من الأفضل أن نثبّت عدد الأكوام أولًا:
$$S(N)=\sum_{n=1}^{N}\sum_{k\ge 1} f(n,k)=\sum_{k\ge 1}\sum_{n=1}^{N} f(n,k).$$
ولـ \(k\) ثابت، نعوّض بصيغة الخطوة الأولى:
$$\sum_{n=1}^{N} f(n,k)=\sum_{n=1}^{N}\max\left(0,\left\lfloor\frac{n-\Delta_k}{k}\right\rfloor\right).$$
والآن نحرّك الفهرس بوضع
$$m=n-\Delta_k.$$
وبما أن \(\left\lfloor m/k\right\rfloor=0\) عندما \(0\le m<k\)، فإن هذا الجزء كله يصبح
$$\sum_{m=0}^{N-\Delta_k}\left\lfloor\frac{m}{k}\right\rfloor,$$
مع فهم أن المساهمة كلها تساوي صفرًا إذا كان \(N\le \Delta_k\). وهكذا تتحول المسألة إلى مجموع من نوع floor-sum.
لنضع
$$M=N-\Delta_k.$$
إذا كان \(M>0\)، فنقسمه على \(k\):
$$M=uk+v,\qquad 0\le v<k.$$
عندئذٍ تظهر قيم \(\left\lfloor m/k\right\rfloor\) على شكل كتل متكررة:
$$\underbrace{0,\dots,0}_{k\text{ terms}},\ \underbrace{1,\dots,1}_{k\text{ terms}},\ \dots,\ \underbrace{u-1,\dots,u-1}_{k\text{ terms}},\ \underbrace{u,\dots,u}_{v+1\text{ terms}}.$$
ومن ثم
$$\sum_{m=0}^{M}\left\lfloor\frac{m}{k}\right\rfloor =k\sum_{j=0}^{u-1} j + u(v+1) =k\frac{u(u-1)}{2}+u(v+1).$$
وبذلك تختفي حلقة الجمع الداخلية تمامًا، ويبقى لكل \(k\) حساب ثابت الزمن.
لكل \(k\) يحقق \(\Delta_k<N\)، نعرّف \(u_k\) و\(v_k\) من خلال
$$N-\Delta_k=u_k k+v_k,\qquad 0\le v_k<k.$$
فنحصل على
$$\boxed{S(N)=\sum_{\substack{k\ge 1\\ \Delta_k<N}}\left(k\frac{u_k(u_k-1)}{2}+u_k(v_k+1)\right)\pmod{10^9+7}.}$$
وبمجرد أن يتحقق \(\Delta_k\ge N\)، تختفي كل الحدود اللاحقة. ولأن \(\Delta_k\) ينمو تقريبًا مثل \(k^2/2\)، فإن عدد قيم \(k\) التي نحتاج إلى فحصها هو فقط \(O(\sqrt{N})\).
لنأخذ أولًا مثالًا محليًا مع \(n=14\) و\(k=3\). الترتيبات الممكنة لارتفاعات الأكوام هي
$$1,2,3;\qquad 2,3,4;\qquad 3,4,5,$$
ومجاميعها هي \(6,9,12\). أما البداية التالية فتعطي \(4+5+6=15>14\)، ولذلك
$$f(14,3)=3.$$
والصيغة تؤكد النتيجة نفسها:
$$\Delta_3=\frac{3\cdot 2}{2}=3,\qquad \left\lfloor\frac{14-3}{3}\right\rfloor=3.$$
ولمثال تراكمي، خذ \(N=10\). المساهمات غير الصفرية هي
$$\begin{aligned} k=1&:&&\Delta_1=0,\ M=10=10\cdot 1+0,\ &&55,\\ k=2&:&&\Delta_2=1,\ M=9=4\cdot 2+1,\ &&20,\\ k=3&:&&\Delta_3=3,\ M=7=2\cdot 3+1,\ &&7,\\ k=4&:&&\Delta_4=6,\ M=4=1\cdot 4+0,\ &&1. \end{aligned}$$
وعند \(k\ge 5\) تصبح المساهمة صفرًا، لذلك
$$S(10)=55+20+7+1=83.$$
تنفذ نسخ C++ وPython وJava الصيغة المغلقة نفسها تمامًا. فهي تمر على \(k=1,2,3,\dots\)، وتحسب الإزاحة المثلثية \(\Delta_k=k(k-1)/2\)، ثم تتوقف فورًا عندما تصبح \(\Delta_k\ge N\).
لكل \(k\) صالح، يحسب التنفيذ
$$M=N-\Delta_k,$$
ثم يجري قسمة صحيحة واحدة على \(k\) للحصول على خارج القسمة والباقي اللازمين لتقييم
$$k\frac{u(u-1)}{2}+u(v+1).$$
وبما أن الجواب النهائي مطلوب بترديد \(10^9+7\)، فإن القسمة على \(2\) تُنفذ عبر الضرب في المعكوس الضربي لـ \(2\) تحت هذا الترديد. كما تُختزل كل مساهمة بترديد \(10^9+7\) قبل إضافتها إلى المجموع الجاري.
وتستخدم نسخة C++ أيضًا نوعًا عدديًا أوسع في الضربات الوسيطة حتى تبقى العمليات على القيم القريبة من \(10^{16}\) آمنة قبل أخذ الباقي. وإضافة إلى ذلك، تقوم إحدى النسخ بمقارنة الصيغة المحسّنة مع حساب brute-force صغير عند \(N=100\)، وتعطي الطريقتان القيمة \(12656\).
تنتهي الحلقة عندما يصبح \(k(k-1)/2\ge N\)، ولذلك يكون عدد التكرارات \(O(\sqrt{N})\). وكل تكرار يحتوي فقط على عمل ثابت: حساب عدد مثلثي، وطرح واحد، وقسمة مع باقي، وعدة ضربات معيارية، وجمع معياري واحد. إذًا يكون الزمن الكلي \(O(\sqrt{N})\)، بينما الذاكرة الإضافية \(O(1)\).