For a fixed positive integer \(n\), define
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{m-1}\right\rfloor \qquad (2\le m\le n).$$
The overall quantity of interest is
$$L(n)=\sum_{m=2}^{n} T(n,m).$$
The challenge is to evaluate \(L(10^7)\) exactly. A literal interpretation of the definition would use a nested loop: for every \(m\), we would sum over all \(k\). That quadratic approach is far too slow, so the goal is to convert each inner floor-sum into a closed form that can be evaluated in constant time.
The decisive observation is that, for fixed \(m\), the values of the floor function stay constant on long consecutive blocks. Once those blocks are counted carefully, the inner sum becomes an arithmetic-series calculation.
Set
$$d=m-1.$$
Then \(d\) runs from \(1\) to \(n-1\), and the inner term becomes
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{d}\right\rfloor.$$
This change of variable is convenient because \(d\) is exactly the width of each constant block of the floor function.
Write the Euclidean division of \(n\) by \(d\) as
$$n=ad+b,\qquad 0\le b\lt d,\qquad a=\left\lfloor\frac{n}{d}\right\rfloor.$$
Here \(a\) is the number of full blocks of width \(d\), and \(b\) is the length of the final partial block.
For \(k=0,1,\dots,n-1\), the value \(\left\lfloor k/d\right\rfloor\) behaves in a rigid pattern:
\(0\) appears exactly \(d\) times, then \(1\) appears exactly \(d\) times, and so on, up to \(a-1\), which also appears exactly \(d\) times. After those full blocks, the value \(a\) appears exactly \(b\) times.
Therefore
$$T(n,m)=d\sum_{j=0}^{a-1} j + ba.$$
The entire floor-sum has been reduced to counting repeated block values.
Using
$$\sum_{j=0}^{a-1} j=\frac{a(a-1)}{2},$$
we obtain the closed form
$$T(n,m)=\frac{d\,a(a-1)}{2}+ba,$$
where \(d=m-1\), \(a=\left\lfloor n/d\right\rfloor\), and \(b=n-ad\).
This is the key simplification: each term of \(L(n)\) can now be evaluated with a few integer operations, without any inner summation.
Since \(d=m-1\), summing over \(m=2,3,\dots,n\) is the same as summing over \(d=1,2,\dots,n-1\). Thus
$$L(n)=\sum_{d=1}^{n-1}\left(\frac{d\,a_d(a_d-1)}{2}+b_d a_d\right),$$
with
$$a_d=\left\lfloor\frac{n}{d}\right\rfloor,\qquad b_d=n-d\,a_d.$$
This formula is exactly what the implementations evaluate in one linear pass.
Take \(n=8\) and \(m=4\). Then \(d=m-1=3\), so
$$a=\left\lfloor\frac{8}{3}\right\rfloor=2,\qquad b=8-3\cdot 2=2.$$
The floor values are
$$\left\lfloor\frac{0}{3}\right\rfloor,\left\lfloor\frac{1}{3}\right\rfloor,\left\lfloor\frac{2}{3}\right\rfloor,\left\lfloor\frac{3}{3}\right\rfloor,\left\lfloor\frac{4}{3}\right\rfloor,\left\lfloor\frac{5}{3}\right\rfloor,\left\lfloor\frac{6}{3}\right\rfloor,\left\lfloor\frac{7}{3}\right\rfloor=0,0,0,1,1,1,2,2.$$
So
$$T(8,4)=0+0+0+1+1+1+2+2=7.$$
The closed form gives the same answer immediately:
$$T(8,4)=\frac{3\cdot 2\cdot 1}{2}+2\cdot 2=3+4=7.$$
For a tiny full sum, \(L(5)=10+4+2+1=17\). The same derivation also reproduces the checkpoint \(L(1000)=3281346\).
The C++, Python, and Java implementations all follow the same structure. They fix \(n=10^7\), iterate once over every \(d\) from \(1\) to \(n-1\), compute the quotient \(\left\lfloor n/d\right\rfloor\) and the corresponding remainder, and then add the closed-form contribution
$$\frac{d\,a(a-1)}{2}+ba$$
to the running total.
No nested loop remains, and no table needs to be precomputed. The C++ and Java versions store the answer in a 64-bit integer, while the Python version uses native arbitrary-precision integers. Mathematically, however, all three implementations are identical: each performs a direct evaluation of the derived summation formula above.
There are exactly \(n-1\) outer iterations, and each iteration performs only constant-time integer arithmetic. Therefore the total running time is
$$O(n),$$
and the extra memory usage is
$$O(1).$$
This is a major improvement over the naive interpretation of the definition, which would require \(O(n^2)\) work because each choice of \(m\) would trigger a full inner summation over \(k\).
Für eine feste positive ganze Zahl \(n\) sei
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{m-1}\right\rfloor \qquad (2\le m\le n).$$
Gesucht ist dann
$$L(n)=\sum_{m=2}^{n} T(n,m).$$
Die Aufgabe besteht darin, \(L(10^7)\) exakt zu berechnen. Eine direkte Umsetzung der Definition würde für jedes \(m\) erneut über alle \(k\) summieren und damit quadratische Laufzeit erzeugen. Der Schlüssel ist deshalb, jede innere Floorsumme in eine geschlossene Formel umzuwandeln.
Die entscheidende Beobachtung ist, dass die Werte der Floor-Funktion für festes \(m\) auf langen zusammenhängenden Intervallen konstant bleiben. Wenn man diese Blöcke sauber zählt, bleibt nur noch eine Summe einer arithmetischen Folge übrig.
Setze
$$d=m-1.$$
Dann läuft \(d\) von \(1\) bis \(n-1\), und der innere Term wird zu
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{d}\right\rfloor.$$
Diese Umparametrisierung ist nützlich, weil \(d\) genau die Länge der konstanten Blöcke der Floor-Funktion ist.
Schreibe die euklidische Division
$$n=ad+b,\qquad 0\le b\lt d,\qquad a=\left\lfloor\frac{n}{d}\right\rfloor.$$
Dabei ist \(a\) die Anzahl vollständiger Blöcke der Breite \(d\), und \(b\) ist die Länge des letzten unvollständigen Blocks.
Für \(k=0,1,\dots,n-1\) besitzt \(\left\lfloor k/d\right\rfloor\) ein sehr starres Muster:
Der Wert \(0\) tritt genau \(d\)-mal auf, danach \(1\) ebenfalls genau \(d\)-mal, und so weiter bis \(a-1\), das auch genau \(d\)-mal erscheint. Anschließend kommt der Wert \(a\) noch genau \(b\)-mal vor.
Daraus folgt unmittelbar
$$T(n,m)=d\sum_{j=0}^{a-1} j + ba.$$
Damit ist die Floorsumme auf eine reine Blockzählung reduziert.
Mit
$$\sum_{j=0}^{a-1} j=\frac{a(a-1)}{2}$$
erhält man die geschlossene Formel
$$T(n,m)=\frac{d\,a(a-1)}{2}+ba,$$
wobei \(d=m-1\), \(a=\left\lfloor n/d\right\rfloor\) und \(b=n-ad\) gilt.
Genau dieser Schritt macht das Problem effizient: Jeder Beitrag von \(L(n)\) ist nun mit wenigen Ganzzahloperationen berechenbar.
Weil \(d=m-1\) ist, entspricht die Summe über \(m=2,\dots,n\) derselben Summe über \(d=1,\dots,n-1\). Also
$$L(n)=\sum_{d=1}^{n-1}\left(\frac{d\,a_d(a_d-1)}{2}+b_d a_d\right),$$
mit
$$a_d=\left\lfloor\frac{n}{d}\right\rfloor,\qquad b_d=n-d\,a_d.$$
Das ist genau die Form, die die Implementierungen in einem einzigen linearen Durchlauf auswerten.
Nimm \(n=8\) und \(m=4\). Dann ist \(d=m-1=3\), also
$$a=\left\lfloor\frac{8}{3}\right\rfloor=2,\qquad b=8-3\cdot 2=2.$$
Die Floor-Werte lauten
$$\left\lfloor\frac{0}{3}\right\rfloor,\left\lfloor\frac{1}{3}\right\rfloor,\left\lfloor\frac{2}{3}\right\rfloor,\left\lfloor\frac{3}{3}\right\rfloor,\left\lfloor\frac{4}{3}\right\rfloor,\left\lfloor\frac{5}{3}\right\rfloor,\left\lfloor\frac{6}{3}\right\rfloor,\left\lfloor\frac{7}{3}\right\rfloor=0,0,0,1,1,1,2,2.$$
Daher
$$T(8,4)=0+0+0+1+1+1+2+2=7.$$
Die geschlossene Formel liefert sofort denselben Wert:
$$T(8,4)=\frac{3\cdot 2\cdot 1}{2}+2\cdot 2=3+4=7.$$
Für eine kleine Gesamtsumme gilt außerdem \(L(5)=10+4+2+1=17\). Dieselbe Herleitung reproduziert auch den Kontrollwert \(L(1000)=3281346\).
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe Struktur. Sie setzen \(n=10^7\), iterieren genau einmal über alle \(d\) von \(1\) bis \(n-1\), bestimmen den Quotienten \(\left\lfloor n/d\right\rfloor\) und den zugehörigen Rest und addieren dann den geschlossenen Beitrag
$$\frac{d\,a(a-1)}{2}+ba$$
zum laufenden Total.
Es gibt keine verschachtelte Schleife mehr und auch keine Vorberechnungstabelle. Die C++- und Java-Versionen verwenden einen 64-Bit-Integer für die Summe, während Python Ganzzahlen beliebiger Größe nutzt. Rechnerisch tun jedoch alle drei Varianten exakt dasselbe: Sie werten die oben hergeleitete Summenformel direkt aus.
Es gibt genau \(n-1\) Iterationen, und jede Iteration benötigt nur konstante Ganzzahlarithmetik. Daher beträgt die Laufzeit
$$O(n),$$
und der zusätzliche Speicherverbrauch ist
$$O(1).$$
Gegenüber der naiven Definition ist das ein großer Fortschritt, denn dort würde für jedes \(m\) nochmals eine komplette innere Summe über \(k\) anfallen und damit \(O(n^2)\) Arbeit entstehen.
Sabit bir pozitif tamsayı \(n\) için
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{m-1}\right\rfloor \qquad (2\le m\le n)$$
tanımını yapalım. Hesaplanmak istenen toplam ise
$$L(n)=\sum_{m=2}^{n} T(n,m).$$
Görev, \(L(10^7)\) değerini tam olarak bulmaktır. Tanımı doğrudan uygularsak her \(m\) için yeniden tüm \(k\) değerlerini dolaşmamız gerekir; bu da karesel zaman maliyeti doğurur. Bu nedenle asıl amaç, her iç toplamı sabit zamanda hesaplanabilen kapalı bir biçime dönüştürmektir.
Temel gözlem şudur: \(m\) sabitken floor fonksiyonunun değeri uzun ardışık bloklar boyunca değişmez. Bu blokların uzunluğunu ve kaç kez tekrarlandıklarını doğru sayınca, iç toplam basit bir aritmetik dizi toplamına dönüşür.
Şöyle tanımlayalım:
$$d=m-1.$$
Böylece \(d\), \(1\) ile \(n-1\) arasında dolaşır ve iç terim
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{d}\right\rfloor$$
şeklini alır. Bu değişken dönüşümü önemlidir; çünkü \(d\), floor fonksiyonunun sabit kaldığı blokların tam genişliğidir.
\(n\)'nin \(d\) ile Öklid bölmesini
$$n=ad+b,\qquad 0\le b\lt d,\qquad a=\left\lfloor\frac{n}{d}\right\rfloor$$
şeklinde yazalım. Burada \(a\), uzunluğu \(d\) olan tam blokların sayısıdır; \(b\) ise sonda kalan eksik bloğun uzunluğudur.
\(k=0,1,\dots,n-1\) için \(\left\lfloor k/d\right\rfloor\) değerleri çok düzenli ilerler:
\(0\) değeri tam \(d\) kez görülür, sonra \(1\) değeri yine tam \(d\) kez gelir, bu desen \(a-1\) değerine kadar sürer. Bu tam bloklar bittikten sonra \(a\) değeri yalnızca \(b\) kez görünür.
Dolayısıyla
$$T(n,m)=d\sum_{j=0}^{a-1} j + ba$$
olur. Yani floor-toplam problemi, tekrar eden blok değerlerini sayma problemine indirgenmiştir.
Bilinen özdeşlik
$$\sum_{j=0}^{a-1} j=\frac{a(a-1)}{2}$$
kullanılırsa kapalı form
$$T(n,m)=\frac{d\,a(a-1)}{2}+ba$$
elde edilir. Burada \(d=m-1\), \(a=\left\lfloor n/d\right\rfloor\) ve \(b=n-ad\) olduğu unutulmamalıdır.
Asıl hız kazancı tam burada gelir: \(L(n)\)'deki her terim artık birkaç tamsayı işlemiyle hesaplanabilir.
\(d=m-1\) olduğundan, \(m=2,3,\dots,n\) üzerinden toplamak ile \(d=1,2,\dots,n-1\) üzerinden toplamak aynıdır. Böylece
$$L(n)=\sum_{d=1}^{n-1}\left(\frac{d\,a_d(a_d-1)}{2}+b_d a_d\right),$$
$$a_d=\left\lfloor\frac{n}{d}\right\rfloor,\qquad b_d=n-d\,a_d$$
olur. Uygulama da tam olarak bu formülü doğrusal bir döngü içinde değerlendirir.
\(n=8\) ve \(m=4\) alalım. O zaman \(d=m-1=3\) olur. Dolayısıyla
$$a=\left\lfloor\frac{8}{3}\right\rfloor=2,\qquad b=8-3\cdot 2=2.$$
Floor değerleri sırasıyla
$$\left\lfloor\frac{0}{3}\right\rfloor,\left\lfloor\frac{1}{3}\right\rfloor,\left\lfloor\frac{2}{3}\right\rfloor,\left\lfloor\frac{3}{3}\right\rfloor,\left\lfloor\frac{4}{3}\right\rfloor,\left\lfloor\frac{5}{3}\right\rfloor,\left\lfloor\frac{6}{3}\right\rfloor,\left\lfloor\frac{7}{3}\right\rfloor=0,0,0,1,1,1,2,2$$
şeklindedir. Bu yüzden
$$T(8,4)=0+0+0+1+1+1+2+2=7.$$
Kapalı form da aynı sonucu anında verir:
$$T(8,4)=\frac{3\cdot 2\cdot 1}{2}+2\cdot 2=3+4=7.$$
Küçük bir tam toplam örneği olarak \(L(5)=10+4+2+1=17\) bulunur. Aynı türetim, kontrol değeri olan \(L(1000)=3281346\) sonucunu da üretir.
C++, Python ve Java uygulamaları aynı fikri izler. Önce \(n=10^7\) sabitlenir. Sonra \(1\)'den \(n-1\)'e kadar tüm \(d\) değerleri üzerinde tek bir döngü çalıştırılır. Her adımda \(\left\lfloor n/d\right\rfloor\) bölümü ve ilgili kalan hesaplanır; ardından
$$\frac{d\,a(a-1)}{2}+ba$$
katkısı toplam sonuca eklenir.
Böylece iç içe döngüye ihtiyaç kalmaz ve herhangi bir yardımcı tablo da tutulmaz. C++ ve Java sürümleri toplamı 64 bitlik bir tamsayıda biriktirir; Python sürümü ise doğal olarak sınırsız büyüklükte tamsayılar kullanır. Matematiksel olarak üç uygulama da aynı kapalı formülü doğrudan hesaplar.
Toplamda tam \(n-1\) adet yineleme vardır ve her yinelemede yalnızca sabit sayıda tamsayı işlemi yapılır. Bu yüzden süre karmaşıklığı
$$O(n)$$
ve ek bellek karmaşıklığı
$$O(1)$$
olur. Bu, tanımı doğrudan uygulayan ve her \(m\) için tüm \(k\) değerlerini yeniden toplayan \(O(n^2)\) yaklaşıma göre çok büyük bir iyileşmedir.
Para un entero positivo fijo \(n\), definimos
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{m-1}\right\rfloor \qquad (2\le m\le n).$$
La cantidad total buscada es
$$L(n)=\sum_{m=2}^{n} T(n,m).$$
La tarea consiste en calcular exactamente \(L(10^7)\). Si se implementa la definición de forma literal, para cada \(m\) habría que recorrer otra vez todos los valores de \(k\), lo que conduce a un costo cuadrático. Por eso el objetivo real es transformar cada suma interna con pisos en una fórmula cerrada de tiempo constante.
La observación decisiva es que, para un \(m\) fijo, la función piso permanece constante en bloques consecutivos muy regulares. Una vez contados esos bloques, la suma interna se convierte en una suma de progresión aritmética.
Tomemos
$$d=m-1.$$
Entonces \(d\) recorre los valores desde \(1\) hasta \(n-1\), y el término interior pasa a ser
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{d}\right\rfloor.$$
Esta reparametrización es natural porque \(d\) es exactamente la anchura de cada bloque en el que la función piso toma el mismo valor.
Escribimos la división euclídea
$$n=ad+b,\qquad 0\le b\lt d,\qquad a=\left\lfloor\frac{n}{d}\right\rfloor.$$
Aquí \(a\) representa la cantidad de bloques completos de longitud \(d\), mientras que \(b\) es el tamaño del bloque final incompleto.
Para \(k=0,1,\dots,n-1\), los valores de \(\left\lfloor k/d\right\rfloor\) siguen un patrón rígido:
el valor \(0\) aparece exactamente \(d\) veces, luego el valor \(1\) aparece otras \(d\) veces, y así sucesivamente hasta \(a-1\), que también aparece \(d\) veces. Después de esos bloques completos, el valor \(a\) aparece exactamente \(b\) veces.
Por lo tanto,
$$T(n,m)=d\sum_{j=0}^{a-1} j + ba.$$
La suma con pisos queda reducida a una simple contabilidad de bloques repetidos.
Usando
$$\sum_{j=0}^{a-1} j=\frac{a(a-1)}{2},$$
obtenemos la fórmula cerrada
$$T(n,m)=\frac{d\,a(a-1)}{2}+ba,$$
donde \(d=m-1\), \(a=\left\lfloor n/d\right\rfloor\) y \(b=n-ad\).
Éste es el paso que hace viable el problema: cada término de \(L(n)\) puede evaluarse ahora con unas pocas operaciones enteras.
Como \(d=m-1\), sumar para \(m=2,3,\dots,n\) es equivalente a sumar para \(d=1,2,\dots,n-1\). En consecuencia,
$$L(n)=\sum_{d=1}^{n-1}\left(\frac{d\,a_d(a_d-1)}{2}+b_d a_d\right),$$
con
$$a_d=\left\lfloor\frac{n}{d}\right\rfloor,\qquad b_d=n-d\,a_d.$$
Ésta es exactamente la fórmula que evalúan las implementaciones en un único recorrido lineal.
Tomemos \(n=8\) y \(m=4\). Entonces \(d=m-1=3\), así que
$$a=\left\lfloor\frac{8}{3}\right\rfloor=2,\qquad b=8-3\cdot 2=2.$$
Los valores de la función piso son
$$\left\lfloor\frac{0}{3}\right\rfloor,\left\lfloor\frac{1}{3}\right\rfloor,\left\lfloor\frac{2}{3}\right\rfloor,\left\lfloor\frac{3}{3}\right\rfloor,\left\lfloor\frac{4}{3}\right\rfloor,\left\lfloor\frac{5}{3}\right\rfloor,\left\lfloor\frac{6}{3}\right\rfloor,\left\lfloor\frac{7}{3}\right\rfloor=0,0,0,1,1,1,2,2.$$
Por tanto,
$$T(8,4)=0+0+0+1+1+1+2+2=7.$$
La fórmula cerrada produce el mismo resultado de inmediato:
$$T(8,4)=\frac{3\cdot 2\cdot 1}{2}+2\cdot 2=3+4=7.$$
Como ejemplo completo pequeño, \(L(5)=10+4+2+1=17\). La misma derivación también reproduce el valor de control \(L(1000)=3281346\).
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Fijan \(n=10^7\), recorren una sola vez todos los valores de \(d\) desde \(1\) hasta \(n-1\), calculan el cociente \(\left\lfloor n/d\right\rfloor\) y el resto correspondiente, y luego añaden la contribución cerrada
$$\frac{d\,a(a-1)}{2}+ba$$
al acumulador total.
Ya no queda ninguna suma interna ni hace falta una tabla auxiliar. Las versiones en C++ y Java usan un entero de 64 bits para el acumulado, mientras que Python emplea enteros de precisión arbitraria. Desde el punto de vista matemático, las tres implementaciones hacen lo mismo: evalúan directamente la fórmula obtenida en la derivación.
Hay exactamente \(n-1\) iteraciones externas y cada una realiza sólo aritmética entera de costo constante. Por ello, el tiempo total es
$$O(n),$$
y la memoria adicional es
$$O(1).$$
Esto mejora de manera decisiva a la interpretación ingenua de la definición, que exigiría \(O(n^2)\) operaciones al mantener una suma interna completa para cada valor de \(m\).
对固定的正整数 \(n\)，定义
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{m-1}\right\rfloor \qquad (2\le m\le n).$$
题目要求计算的总量是
$$L(n)=\sum_{m=2}^{n} T(n,m).$$
真正需要求的是 \(L(10^7)\) 的精确值。如果直接照定义去做，那么每个 \(m\) 都要重新遍历一次所有的 \(k\)，总工作量会是二次级别，显然无法接受。因此核心任务不是“老老实实把和式算完”，而是把每一个内部的 floor 求和化成一个可以 \(O(1)\) 计算的闭式。
关键观察是：当 \(m\) 固定时，\(\left\lfloor k/(m-1)\right\rfloor\) 的取值会在连续的长区间上保持不变。只要把这些常值区间按块统计清楚，原来的 floor 求和就会退化成一个普通的等差数列求和问题。
设
$$d=m-1.$$
于是 \(d\) 从 \(1\) 变化到 \(n-1\)，而内部项可写成
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{d}\right\rfloor.$$
这样改写很自然，因为 \(d\) 正好就是 floor 函数保持常值时每一块的宽度。
把 \(n\) 除以 \(d\)，写成
$$n=ad+b,\qquad 0\le b\lt d,\qquad a=\left\lfloor\frac{n}{d}\right\rfloor.$$
这里 \(a\) 表示有多少个完整的长度为 \(d\) 的块，\(b\) 表示最后那个不完整块的长度。
对于 \(k=0,1,\dots,n-1\)，\(\left\lfloor k/d\right\rfloor\) 的变化规律非常规整：
值 \(0\) 恰好出现 \(d\) 次，接着值 \(1\) 也恰好出现 \(d\) 次，如此继续，直到值 \(a-1\) 仍然出现 \(d\) 次。完整块结束后，值 \(a\) 会再出现 \(b\) 次。
因此有
$$T(n,m)=d\sum_{j=0}^{a-1} j + ba.$$
到这一步，原来的 floor 求和已经完全变成了“每个块的值乘以它出现的次数”的计数问题。
利用
$$\sum_{j=0}^{a-1} j=\frac{a(a-1)}{2},$$
立刻得到
$$T(n,m)=\frac{d\,a(a-1)}{2}+ba,$$
其中 \(d=m-1\)，\(a=\left\lfloor n/d\right\rfloor\)，\(b=n-ad\)。
这正是整个题目的决定性简化：每个内部和式不再需要逐项累加，只要做几次整数运算即可。
由于 \(d=m-1\)，对 \(m=2,3,\dots,n\) 求和与对 \(d=1,2,\dots,n-1\) 求和完全等价，所以
$$L(n)=\sum_{d=1}^{n-1}\left(\frac{d\,a_d(a_d-1)}{2}+b_d a_d\right),$$
其中
$$a_d=\left\lfloor\frac{n}{d}\right\rfloor,\qquad b_d=n-d\,a_d.$$
这样一来，总问题就被改写成一个单层循环中的直接求值公式，这也是实现采用的方式。
取 \(n=8\)、\(m=4\)。此时 \(d=m-1=3\)，因此
$$a=\left\lfloor\frac{8}{3}\right\rfloor=2,\qquad b=8-3\cdot 2=2.$$
对应的 floor 值序列为
$$\left\lfloor\frac{0}{3}\right\rfloor,\left\lfloor\frac{1}{3}\right\rfloor,\left\lfloor\frac{2}{3}\right\rfloor,\left\lfloor\frac{3}{3}\right\rfloor,\left\lfloor\frac{4}{3}\right\rfloor,\left\lfloor\frac{5}{3}\right\rfloor,\left\lfloor\frac{6}{3}\right\rfloor,\left\lfloor\frac{7}{3}\right\rfloor=0,0,0,1,1,1,2,2.$$
所以
$$T(8,4)=0+0+0+1+1+1+2+2=7.$$
闭式公式同样马上得到
$$T(8,4)=\frac{3\cdot 2\cdot 1}{2}+2\cdot 2=3+4=7.$$
如果看一个很小的完整总和，那么 \(L(5)=10+4+2+1=17\)。同样的推导还能复现校验值 \(L(1000)=3281346\)。
C++、Python 和 Java 三个实现的算法完全一致。它们先固定 \(n=10^7\)，然后只做一层循环，让 \(d\) 从 \(1\) 走到 \(n-1\)。在每一次迭代里，先算出 \(\left\lfloor n/d\right\rfloor\) 和相应的余数，再把闭式项
$$\frac{d\,a(a-1)}{2}+ba$$
加入累计答案。
整个过程中没有任何二重循环，也不需要预处理数组。C++ 和 Java 版本用 64 位整数保存累计结果，Python 则直接使用任意精度整数。尽管语言不同，但三份实现做的事情完全一样：直接计算上面推导出的线性求和公式。
外层一共只有 \(n-1\) 次迭代，而每次迭代只包含常数次整数运算，因此总时间复杂度为
$$O(n),$$
额外空间复杂度为
$$O(1).$$
这比朴素做法要好得多。朴素做法会对每个 \(m\) 再执行一次完整的内部求和，因此需要 \(O(n^2)\) 的工作量。
Для фиксированного положительного целого числа \(n\) определим
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{m-1}\right\rfloor \qquad (2\le m\le n).$$
Тогда требуется вычислить
$$L(n)=\sum_{m=2}^{n} T(n,m).$$
Нужно найти точное значение \(L(10^7)\). Если понимать определение буквально, то для каждого \(m\) пришлось бы заново проходить все значения \(k\), то есть возникла бы квадратичная по времени схема. Поэтому основная идея состоит в том, чтобы превратить каждую внутреннюю сумму с функцией пола в замкнутую формулу, вычисляемую за постоянное время.
Главное наблюдение таково: при фиксированном \(m\) функция \(\left\lfloor k/(m-1)\right\rfloor\) остаётся постоянной на длинных подряд идущих блоках. Если правильно посчитать эти блоки, внутренняя сумма сводится к сумме арифметической прогрессии.
Положим
$$d=m-1.$$
Тогда \(d\) пробегает значения от \(1\) до \(n-1\), а внутренний член принимает вид
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{d}\right\rfloor.$$
Такая замена удобна, потому что \(d\) и есть ширина каждого участка, на котором значение функции пола не меняется.
Запишем евклидово деление:
$$n=ad+b,\qquad 0\le b\lt d,\qquad a=\left\lfloor\frac{n}{d}\right\rfloor.$$
Здесь \(a\) обозначает число полных блоков длины \(d\), а \(b\) — длину последнего неполного блока.
Для \(k=0,1,\dots,n-1\) значения \(\left\lfloor k/d\right\rfloor\) распределяются очень регулярно:
значение \(0\) встречается ровно \(d\) раз, затем значение \(1\) тоже ровно \(d\) раз, и так далее вплоть до \(a-1\), которое также встречается ровно \(d\) раз. После этих полных блоков значение \(a\) появляется ещё ровно \(b\) раз.
Следовательно,
$$T(n,m)=d\sum_{j=0}^{a-1} j + ba.$$
То есть исходная сумма с функцией пола полностью свелась к подсчёту повторяющихся блоков.
Используя равенство
$$\sum_{j=0}^{a-1} j=\frac{a(a-1)}{2},$$
получаем
$$T(n,m)=\frac{d\,a(a-1)}{2}+ba,$$
где \(d=m-1\), \(a=\left\lfloor n/d\right\rfloor\), \(b=n-ad\).
Именно здесь появляется выигрыш: каждый вклад в \(L(n)\) теперь вычисляется несколькими целочисленными операциями без внутреннего цикла.
Так как \(d=m-1\), суммирование по \(m=2,3,\dots,n\) эквивалентно суммированию по \(d=1,2,\dots,n-1\). Поэтому
$$L(n)=\sum_{d=1}^{n-1}\left(\frac{d\,a_d(a_d-1)}{2}+b_d a_d\right),$$
где
$$a_d=\left\lfloor\frac{n}{d}\right\rfloor,\qquad b_d=n-d\,a_d.$$
Именно эту формулу реализации вычисляют одним линейным проходом.
Возьмём \(n=8\) и \(m=4\). Тогда \(d=m-1=3\), следовательно,
$$a=\left\lfloor\frac{8}{3}\right\rfloor=2,\qquad b=8-3\cdot 2=2.$$
Последовательность значений функции пола равна
$$\left\lfloor\frac{0}{3}\right\rfloor,\left\lfloor\frac{1}{3}\right\rfloor,\left\lfloor\frac{2}{3}\right\rfloor,\left\lfloor\frac{3}{3}\right\rfloor,\left\lfloor\frac{4}{3}\right\rfloor,\left\lfloor\frac{5}{3}\right\rfloor,\left\lfloor\frac{6}{3}\right\rfloor,\left\lfloor\frac{7}{3}\right\rfloor=0,0,0,1,1,1,2,2.$$
Поэтому
$$T(8,4)=0+0+0+1+1+1+2+2=7.$$
Замкнутая формула даёт тот же результат мгновенно:
$$T(8,4)=\frac{3\cdot 2\cdot 1}{2}+2\cdot 2=3+4=7.$$
Для маленькой полной суммы имеем \(L(5)=10+4+2+1=17\). Та же формула также воспроизводит контрольное значение \(L(1000)=3281346\).
Реализации на C++, Python и Java устроены одинаково. Они фиксируют \(n=10^7\), затем один раз проходят все значения \(d\) от \(1\) до \(n-1\), вычисляют частное \(\left\lfloor n/d\right\rfloor\) и соответствующий остаток, после чего прибавляют к ответу замкнутый вклад
$$\frac{d\,a(a-1)}{2}+ba.$$
Внутреннего цикла больше нет, никакие вспомогательные таблицы не нужны. В версиях на C++ и Java сумма хранится в 64-битном целом типе, а Python использует целые числа произвольной длины. С математической точки зрения все три реализации совпадают: они напрямую вычисляют выведенную выше формулу.
Всего выполняется ровно \(n-1\) итераций, и каждая итерация содержит только константное число целочисленных операций. Следовательно, время работы равно
$$O(n),$$
а дополнительная память равна
$$O(1).$$
Это существенно лучше наивного подхода, который для каждого \(m\) заново вычислял бы всю внутреннюю сумму и потому требовал бы \(O(n^2)\) операций.
لعدد صحيح موجب ثابت \(n\)، نعرّف
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{m-1}\right\rfloor \qquad (2\le m\le n).$$
والكمية المطلوبة هي
$$L(n)=\sum_{m=2}^{n} T(n,m).$$
المطلوب حساب القيمة الدقيقة لـ \(L(10^7)\). إذا طبقنا التعريف حرفياً فسنحسب لكل قيمة من \(m\) مجموعاً داخلياً كاملاً على جميع قيم \(k\)، وهذا يعطي زمناً تربيعياً غير عملي. لذلك الفكرة الأساسية هي تحويل كل مجموع داخلي يحتوي على دالة الجزء الصحيح إلى صيغة مغلقة يمكن تقييمها بزمن ثابت.
الملاحظة الحاسمة هي أن قيمة \(\left\lfloor k/(m-1)\right\rfloor\) تبقى ثابتة على كتل متتالية طويلة عندما تكون \(m\) ثابتة. وإذا أحصينا هذه الكتل بدقة، فإن المجموع الداخلي يتحول إلى مجموع متتالية حسابية بسيطة.
لنضع
$$d=m-1.$$
عندها تتحرك \(d\) من \(1\) إلى \(n-1\)، ويصبح الحد الداخلي
$$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{d}\right\rfloor.$$
هذا التحويل مناسب لأن \(d\) تمثل بالضبط عرض كل كتلة يكون فيها ناتج دالة الجزء الصحيح ثابتاً.
نكتب القسمة الإقليدية بالشكل
$$n=ad+b,\qquad 0\le b\lt d,\qquad a=\left\lfloor\frac{n}{d}\right\rfloor.$$
هنا تمثل \(a\) عدد الكتل الكاملة ذات الطول \(d\)، بينما تمثل \(b\) طول الكتلة الجزئية الأخيرة.
عندما يتحرك \(k\) من \(0\) إلى \(n-1\)، فإن القيم \(\left\lfloor k/d\right\rfloor\) تسير بنمط منتظم جداً:
القيمة \(0\) تظهر بالضبط \(d\) مرة، ثم القيمة \(1\) تظهر أيضاً \(d\) مرة، ويستمر هذا حتى القيمة \(a-1\) التي تظهر هي الأخرى \(d\) مرة. وبعد انتهاء الكتل الكاملة، تظهر القيمة \(a\) بالضبط \(b\) مرة.
ومن ثم نحصل على
$$T(n,m)=d\sum_{j=0}^{a-1} j + ba.$$
بهذا نكون قد حوّلنا مجموع دالة الجزء الصحيح إلى مسألة عدّ بسيطة لقيم مكررة على كتل.
باستخدام العلاقة
$$\sum_{j=0}^{a-1} j=\frac{a(a-1)}{2},$$
نصل إلى الصيغة
$$T(n,m)=\frac{d\,a(a-1)}{2}+ba,$$
حيث \(d=m-1\)، و\(a=\left\lfloor n/d\right\rfloor\)، و\(b=n-ad\).
وهذه هي النقطة المفصلية في الحل، لأن كل حد من حدود \(L(n)\) أصبح يُحسب مباشرة بعدد قليل من العمليات الصحيحة فقط.
بما أن \(d=m-1\)، فإن الجمع على \(m=2,3,\dots,n\) يكافئ تماماً الجمع على \(d=1,2,\dots,n-1\). لذلك
$$L(n)=\sum_{d=1}^{n-1}\left(\frac{d\,a_d(a_d-1)}{2}+b_d a_d\right),$$
حيث
$$a_d=\left\lfloor\frac{n}{d}\right\rfloor,\qquad b_d=n-d\,a_d.$$
وهذه هي الصيغة التي تنفذها التطبيقات مباشرة في مرور خطي واحد.
خذ \(n=8\) و\(m=4\). عندئذٍ \(d=m-1=3\)، وبالتالي
$$a=\left\lfloor\frac{8}{3}\right\rfloor=2,\qquad b=8-3\cdot 2=2.$$
وتكون قيم دالة الجزء الصحيح
$$\left\lfloor\frac{0}{3}\right\rfloor,\left\lfloor\frac{1}{3}\right\rfloor,\left\lfloor\frac{2}{3}\right\rfloor,\left\lfloor\frac{3}{3}\right\rfloor,\left\lfloor\frac{4}{3}\right\rfloor,\left\lfloor\frac{5}{3}\right\rfloor,\left\lfloor\frac{6}{3}\right\rfloor,\left\lfloor\frac{7}{3}\right\rfloor=0,0,0,1,1,1,2,2.$$
إذن
$$T(8,4)=0+0+0+1+1+1+2+2=7.$$
والصيغة المغلقة تعطي النتيجة نفسها فوراً:
$$T(8,4)=\frac{3\cdot 2\cdot 1}{2}+2\cdot 2=3+4=7.$$
وبالنسبة إلى مجموع كامل صغير، نجد أن \(L(5)=10+4+2+1=17\). كما أن الاشتقاق نفسه يعيد إنتاج قيمة الفحص \(L(1000)=3281346\).
تتبع تطبيقات C++ وPython وJava الفكرة نفسها تماماً. فهي تثبّت \(n=10^7\)، ثم تمر مرة واحدة فقط على جميع قيم \(d\) من \(1\) إلى \(n-1\). وفي كل دورة تحسب خارج القسمة \(\left\lfloor n/d\right\rfloor\) والباقي الموافق له، ثم تضيف المساهمة المغلقة
$$\frac{d\,a(a-1)}{2}+ba$$
إلى المجموع الكلي.
لا توجد أي حلقة داخلية بعد ذلك، ولا حاجة إلى جداول مساعدة. يستخدم تنفيذَا C++ وJava عدداً صحيحاً بعرض 64 بت لتخزين الناتج، بينما تستخدم Python أعداداً صحيحة غير محدودة عملياً. لكن من الناحية الرياضية، تنفذ اللغات الثلاث الصيغة نفسها بشكل مباشر.
يوجد بالضبط \(n-1\) تكراراً في الحلقة الخارجية، وكل تكرار يتطلب عدداً ثابتاً من العمليات الصحيحة. لذلك يكون زمن التنفيذ
$$O(n),$$
أما الذاكرة الإضافية فهي
$$O(1).$$
وهذا أفضل بكثير من التفسير الساذج للتعريف، لأنه كان سيحتفظ بمجموع داخلي كامل لكل قيمة من \(m\)، أي أنه كان سيتطلب عملاً من رتبة \(O(n^2)\).