We must evaluate
$$F(N)=\sum_{n=1}^{N}\frac{n}{s(n)},$$
where \(s(n)\) is the sum of the decimal digits of \(n\). The target bound is a 19-digit number, so iterating over every \(n\le N\) is infeasible. The crucial observation is that the denominator depends only on the digit sum, so the whole sum can be reorganized by digit-sum classes and computed with digit dynamic programming.
Let \(L\) be the number of decimal digits of \(N\). Any \(L\)-digit decimal string has digit sum between \(0\) and \(9L\), so there are only \(9L+1\) relevant classes. The implementation uses that small state space to aggregate many numbers at once.
Define
$$A_\sigma(N)=\sum_{\substack{1\le n\le N\\ s(n)=\sigma}} n.$$
Then the original expression becomes
$$F(N)=\sum_{\sigma=1}^{9L}\frac{A_\sigma(N)}{\sigma}.$$
So we do not need to handle each value \(n/s(n)\) separately. It is enough to know, for each possible digit sum \(\sigma\), the total of all numbers up to \(N\) whose digit sum is exactly \(\sigma\).
Write the bound as decimal digits \(d_1d_2\dots d_L\). We process these digits from left to right and allow leading zeros, so every integer \(0\le n\le N\) is represented exactly once as an \(L\)-digit string.
After processing the first \(k\) positions, for every digit sum \(\sigma\) we store four quantities:
$$C_k^{\mathrm{eq}}(\sigma),\quad S_k^{\mathrm{eq}}(\sigma),\qquad C_k^{\mathrm{lt}}(\sigma),\quad S_k^{\mathrm{lt}}(\sigma).$$
The \(C\) values count how many prefixes lie in that state, and the \(S\) values store the sum of the numeric values of those prefixes. The superscript \(\mathrm{eq}\) means the processed prefix is exactly equal to the first \(k\) digits of \(N\); the superscript \(\mathrm{lt}\) means it is already smaller, so the remaining digits are unrestricted.
Initially only the empty prefix exists:
$$C_0^{\mathrm{eq}}(0)=1,\qquad S_0^{\mathrm{eq}}(0)=0,$$
and every other state is zero.
Suppose a state currently contains \(C\) prefixes with digit sum \(\sigma\) and total numeric sum \(S\). Appending a digit \(d\) transforms every old value \(x\) into \(10x+d\). Therefore the new digit sum is \(\sigma+d\), the number of resulting prefixes is still \(C\), and their total numeric sum is
$$\sum (10x+d)=10S+dC.$$
So one transition contributes
$$\Delta C=C,\qquad \Delta S=10S+dC.$$
If the current state is exact, then appending the current limit digit stays in the exact family, while appending a smaller digit moves to the smaller family. If the current state is already smaller, then any digit \(0,\dots,9\) remains in the smaller family.
A tiny example shows why the formula is correct. If a state contains the prefixes \(1\) and \(4\), then \(C=2\) and \(S=5\). Appending digit \(7\) produces \(17\) and \(47\), whose total is \(64\). The formula gives the same result immediately:
$$10S+dC=10\cdot 5+7\cdot 2=64.$$
After all \(L\) digits are processed, the total numeric sum of all values in \(0\le n\le N\) with digit sum \(\sigma\) is
$$A_\sigma(N)=S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma).$$
Leading zeros automatically include shorter numbers. The class \(\sigma=0\) contains only the number \(0\), and it must be excluded because the denominator would be zero. Hence
$$F(N)=\sum_{\sigma=1}^{9L}\frac{S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma)}{\sigma}.$$
Using two-digit strings, the integers from \(0\) to \(10\) are \(00,01,\dots,09,10\). Group the positive ones by digit sum:
$$\sigma=1:\ \{1,10\},\qquad A_1(10)=11,$$
$$\sigma=2:\ \{2\},\ A_2(10)=2,\qquad \dots,\qquad \sigma=9:\ \{9\},\ A_9(10)=9.$$
Therefore
$$F(10)=\frac{11}{1}+\frac{2}{2}+\frac{3}{3}+\cdots+\frac{9}{9}=11+8=19.$$
This matches the checkpoint used by the implementations and shows exactly why grouping by digit sum is sufficient.
The C++, Python, and Java implementations all follow the same plan. They convert the bound to a decimal string, compute \(L\) and the maximum digit sum \(9L\), and maintain two rolling tables indexed by digit sum: one for prefixes still equal to the bound and one for prefixes already below it.
Each table entry stores two exact quantities: how many prefixes are represented there, and the sum of those prefix values as integers. At every decimal position, the implementation creates fresh tables, loops over the reachable digit sums, and applies the append-a-digit rule \(10S+dC\) to build the next layer.
After the last digit, the implementation combines the exact-prefix and smaller-prefix totals for every positive digit sum \(\sigma\), divides by \(\sigma\), and accumulates the final decimal answer. Exact integer accumulation is essential because the intermediate class sums grow far beyond machine-word size, while high-precision decimal arithmetic is used only for the final divisions and output formatting.
There are \(L\) digit positions, \(9L+1\) possible digit sums, and at most \(10\) candidate digits per transition. Therefore the running time is
$$O(L\cdot 9L\cdot 10)=O(L^2).$$
The rolling tables use \(O(9L)=O(L)\) memory. Since \(L=\Theta(\log_{10} N)\), this is \(O((\log N)^2)\) time and \(O(\log N)\) memory as a function of the size of the bound.
Gesucht ist der Wert
$$F(N)=\sum_{n=1}^{N}\frac{n}{s(n)},$$
wobei \(s(n)\) die Summe der Dezimalziffern von \(n\) ist. Die obere Grenze besitzt 19 Stellen, daher ist eine direkte Schleife über alle \(n\le N\) unpraktikabel. Der entscheidende Punkt ist, dass der Nenner nur von der Ziffernsumme abhängt. Deshalb lässt sich die Summe nach Ziffernsummenklassen umordnen und mit Digit-DP berechnen.
Sei \(L\) die Anzahl der Dezimalstellen von \(N\). Eine \(L\)-stellige Dezimaldarstellung hat eine Ziffernsumme zwischen \(0\) und \(9L\), also gibt es nur \(9L+1\) relevante Klassen. Genau diese kleine Zustandsmenge nutzt die Implementierung aus.
Definiere
$$A_\sigma(N)=\sum_{\substack{1\le n\le N\\ s(n)=\sigma}} n.$$
Dann wird der ursprüngliche Ausdruck zu
$$F(N)=\sum_{\sigma=1}^{9L}\frac{A_\sigma(N)}{\sigma}.$$
Wir müssen also nicht jeden Summanden \(n/s(n)\) einzeln berechnen. Es reicht, für jede mögliche Ziffernsumme \(\sigma\) die Summe aller Zahlen bis \(N\) mit genau dieser Ziffernsumme zu kennen.
Schreibe die Schranke als Dezimalziffern \(d_1d_2\dots d_L\). Wir gehen diese Ziffern von links nach rechts durch und erlauben führende Nullen. Dadurch wird jede ganze Zahl \(0\le n\le N\) genau einmal als \(L\)-stellige Zeichenkette dargestellt.
Nach den ersten \(k\) Positionen speichern wir für jede Ziffernsumme \(\sigma\) vier Größen:
$$C_k^{\mathrm{eq}}(\sigma),\quad S_k^{\mathrm{eq}}(\sigma),\qquad C_k^{\mathrm{lt}}(\sigma),\quad S_k^{\mathrm{lt}}(\sigma).$$
Die \(C\)-Werte zählen, wie viele Präfixe in diesem Zustand liegen, und die \(S\)-Werte speichern die Summe ihrer numerischen Werte. Der Exponent \(\mathrm{eq}\) bedeutet, dass das bisherige Präfix exakt mit den ersten \(k\) Ziffern von \(N\) übereinstimmt; der Exponent \(\mathrm{lt}\) bedeutet, dass es bereits kleiner ist und die restlichen Stellen frei gewählt werden dürfen.
Am Anfang gibt es nur das leere Präfix:
$$C_0^{\mathrm{eq}}(0)=1,\qquad S_0^{\mathrm{eq}}(0)=0,$$
alle übrigen Zustände sind null.
Nehmen wir an, ein Zustand enthält \(C\) Präfixe mit Ziffernsumme \(\sigma\) und Gesamtwert \(S\). Hängt man eine Ziffer \(d\) an, wird jeder alte Wert \(x\) zu \(10x+d\). Damit steigt die Ziffernsumme auf \(\sigma+d\), die Anzahl neuer Präfixe bleibt \(C\), und ihre gesamte Zahlensumme ist
$$\sum (10x+d)=10S+dC.$$
Ein Übergang liefert also
$$\Delta C=C,\qquad \Delta S=10S+dC.$$
Aus einem exakten Zustand bleibt man nur dann im exakten Bereich, wenn man gerade die aktuelle Grenzziffer anhängt; bei einer kleineren Ziffer wechselt man in den kleineren Bereich. Ist ein Zustand bereits kleiner, dann bleiben alle Anhänge \(0,\dots,9\) im kleineren Bereich.
Ein Mini-Beispiel macht die Formel anschaulich. Enthält ein Zustand die Präfixe \(1\) und \(4\), dann ist \(C=2\) und \(S=5\). Beim Anhängen der Ziffer \(7\) entstehen \(17\) und \(47\), also Gesamtwert \(64\). Die Formel liefert sofort dasselbe:
$$10S+dC=10\cdot 5+7\cdot 2=64.$$
Nach der Verarbeitung aller \(L\) Stellen ist die Summe aller Werte \(0\le n\le N\) mit Ziffernsumme \(\sigma\)
$$A_\sigma(N)=S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma).$$
Durch die erlaubten führenden Nullen sind auch kürzere Zahlen automatisch enthalten. Die Klasse \(\sigma=0\) enthält nur die Zahl \(0\) und muss ausgeschlossen werden, weil der Nenner dort null wäre. Also gilt
$$F(N)=\sum_{\sigma=1}^{9L}\frac{S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma)}{\sigma}.$$
Mit zweistelligen Darstellungen lauten die Zahlen von \(0\) bis \(10\): \(00,01,\dots,09,10\). Gruppiert nach Ziffernsumme erhält man
$$\sigma=1:\ \{1,10\},\qquad A_1(10)=11,$$
$$\sigma=2:\ \{2\},\ A_2(10)=2,\qquad \dots,\qquad \sigma=9:\ \{9\},\ A_9(10)=9.$$
Damit folgt
$$F(10)=\frac{11}{1}+\frac{2}{2}+\frac{3}{3}+\cdots+\frac{9}{9}=11+8=19.$$
Genau dieser Kontrollwert taucht in den Implementierungen auf und zeigt, warum die Gruppierung nach Ziffernsumme ausreicht.
Die Implementierungen in C++, Python und Java verwenden denselben Ablauf. Zuerst wird die Schranke in eine Dezimalzeichenkette umgewandelt, dann werden \(L\) und die maximale Ziffernsumme \(9L\) bestimmt. Anschließend laufen zwei rollierende Tabellen über die Ziffernsummen mit: eine für Präfixe, die noch exakt an der Schranke liegen, und eine für Präfixe, die bereits darunter liegen.
Jeder Tabelleneintrag speichert zwei exakte Größen: wie viele Präfixe er repräsentiert und wie groß die Summe dieser Präfixwerte als ganze Zahlen ist. Für jede neue Dezimalstelle erzeugt die Implementierung frische Tabellen, iteriert über die erreichbaren Ziffernsummen und baut mit der Regel \(10S+dC\) die nächste Schicht auf.
Nach der letzten Stelle werden für jede positive Ziffernsumme \(\sigma\) die Summen aus beiden Familien addiert, durch \(\sigma\) geteilt und zur endgültigen Dezimalantwort aufsummiert. Exakte Ganzzahlarithmetik ist notwendig, weil die Zwischensummen der Klassen weit über normale Maschinenwortgrößen hinausgehen; hochpräzise Dezimalarithmetik wird erst beim abschließenden Dividieren und Formatieren gebraucht.
Es gibt \(L\) Stellen, \(9L+1\) mögliche Ziffernsummen und höchstens \(10\) Kandidatenziffern pro Übergang. Damit beträgt die Laufzeit
$$O(L\cdot 9L\cdot 10)=O(L^2).$$
Die rollierenden Tabellen benötigen \(O(9L)=O(L)\) Speicher. Wegen \(L=\Theta(\log_{10} N)\) entspricht das \(O((\log N)^2)\) Zeit und \(O(\log N)\) Speicher in Abhängigkeit von der Größe der Schranke.
Hesaplanması istenen ifade
$$F(N)=\sum_{n=1}^{N}\frac{n}{s(n)},$$
burada \(s(n)\), \(n\) sayısının onluk tabandaki rakamları toplamıdır. Üst sınır 19 basamaklı olduğu için tüm \(n\le N\) değerlerini tek tek dolaşmak pratik değildir. Kritik gözlem şudur: payda yalnızca rakam toplamına bağlıdır. Bu yüzden toplam, rakam toplamı sınıflarına ayrılıp digit DP ile topluca hesaplanabilir.
\(L\), \(N\) sayısının basamak sayısı olsun. \(L\) basamaklı bir onluk dizgenin rakam toplamı en fazla \(9L\) olabilir; dolayısıyla sadece \(0\) ile \(9L\) arasındaki sınıflar ilgilidir. Uygulama tam olarak bu küçük durum uzayını kullanır.
Şunu tanımlayalım:
$$A_\sigma(N)=\sum_{\substack{1\le n\le N\\ s(n)=\sigma}} n.$$
Böylece asıl ifade
$$F(N)=\sum_{\sigma=1}^{9L}\frac{A_\sigma(N)}{\sigma}$$
şeklini alır. Yani her bir \(n/s(n)\) terimini ayrı ayrı işlememize gerek yoktur. Her olası rakam toplamı \(\sigma\) için, rakam toplamı tam olarak \(\sigma\) olan sayıların toplam değerini bilmek yeterlidir.
Sınırı \(d_1d_2\dots d_L\) biçiminde yazalım. Basamakları soldan sağa işlerken baştaki sıfırlara izin veririz. Böylece \(0\le n\le N\) aralığındaki her tam sayı, uzunluğu tam \(L\) olan bir onluk dizge ile tam bir kez temsil edilir.
İlk \(k\) basamak işlendiğinde, her rakam toplamı \(\sigma\) için şu dört büyüklüğü tutarız:
$$C_k^{\mathrm{eq}}(\sigma),\quad S_k^{\mathrm{eq}}(\sigma),\qquad C_k^{\mathrm{lt}}(\sigma),\quad S_k^{\mathrm{lt}}(\sigma).$$
\(C\) değerleri o durumda kaç önek bulunduğunu, \(S\) değerleri ise bu öneklerin sayısal toplamını gösterir. \(\mathrm{eq}\) üst simgesi, işlenen önekin hâlâ \(N\)'nin ilk \(k\) basamağı ile birebir aynı olduğunu; \(\mathrm{lt}\) üst simgesi ise önekin artık daha küçük olduğunu ve kalan basamakların serbest seçilebileceğini belirtir.
Başlangıçta yalnızca boş önek vardır:
$$C_0^{\mathrm{eq}}(0)=1,\qquad S_0^{\mathrm{eq}}(0)=0,$$
diğer tüm durumlar sıfırdır.
Bir durumda rakam toplamı \(\sigma\) olan \(C\) adet önek ve bunların toplam değeri \(S\) olsun. Sonuna \(d\) rakamı eklendiğinde her eski değer \(x\), \(10x+d\) olur. Bu durumda yeni rakam toplamı \(\sigma+d\), yeni önek sayısı yine \(C\), yeni sayısal toplam ise
$$\sum (10x+d)=10S+dC$$
olur. Dolayısıyla tek bir geçişin katkısı
$$\Delta C=C,\qquad \Delta S=10S+dC$$
şeklindedir. Eğer mevcut durum eşitlik durumundaysa, yalnızca o pozisyondaki sınır rakamını seçmek eşitlikte kalmayı sağlar; daha küçük bir rakam seçmek ise küçüktür durumuna geçirir. Mevcut durum zaten küçüktür durumundaysa, \(0,\dots,9\) arasındaki her rakam yine aynı ailede kalır.
Küçük bir örnek formülü netleştirir. Bir durumda önekler \(1\) ve \(4\) olsun. O zaman \(C=2\) ve \(S=5\) olur. Sonuna \(7\) eklenirse \(17\) ve \(47\) elde edilir; toplamları \(64\)'tür. Formül de aynısını verir:
$$10S+dC=10\cdot 5+7\cdot 2=64.$$
Tüm \(L\) basamak işlendiğinde, rakam toplamı \(\sigma\) olan ve \(0\le n\le N\) aralığında kalan tüm sayıların toplamı
$$A_\sigma(N)=S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma)$$
olur. Baştaki sıfırlara izin verildiği için daha kısa sayılar da otomatik olarak kapsanır. \(\sigma=0\) sınıfı yalnızca \(0\) sayısını içerir ve payda sıfır olacağı için dışarıda bırakılır. Sonuç olarak
$$F(N)=\sum_{\sigma=1}^{9L}\frac{S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma)}{\sigma}$$
elde edilir.
İki basamaklı gösterim kullanırsak \(0\) ile \(10\) arasındaki sayılar \(00,01,\dots,09,10\) olur. Pozitif olanları rakam toplamına göre gruplarsak
$$\sigma=1:\ \{1,10\},\qquad A_1(10)=11,$$
$$\sigma=2:\ \{2\},\ A_2(10)=2,\qquad \dots,\qquad \sigma=9:\ \{9\},\ A_9(10)=9.$$
Dolayısıyla
$$F(10)=\frac{11}{1}+\frac{2}{2}+\frac{3}{3}+\cdots+\frac{9}{9}=11+8=19.$$
Bu değer, uygulamalardaki küçük doğrulama örneğiyle aynıdır ve neden rakam toplamına göre gruplayabildiğimizi açıkça gösterir.
C++, Python ve Java uygulamalarının üçü de aynı akışı izler. Önce sınır değer onluk bir dizgeye çevrilir, sonra \(L\) ve azami rakam toplamı \(9L\) hesaplanır. Ardından rakam toplamına göre indekslenen iki döner tablo tutulur: biri hâlâ sınıra eşit önekler için, diğeri ise sınıra çoktan düşmüş önekler için.
Her hücre iki kesin bilgi taşır: o durumda kaç önek bulunduğu ve bu öneklerin tam sayı olarak toplam değeri. Her yeni basamakta uygulama sıfırdan yeni tablolar kurar, erişilebilir rakam toplamları üzerinden geçer ve \(10S+dC\) kuralıyla bir sonraki katmanı oluşturur.
Son basamaktan sonra, her pozitif rakam toplamı \(\sigma\) için iki ailenin toplamları birleştirilir, \(\sigma\)'ya bölünür ve son ondalık cevap biriktirilir. Ara toplamlar normal makine tamsayılarını açıkça aştığı için tam doğruluklu büyük tamsayı birikimi gerekir; yüksek hassasiyetli ondalık aritmetik ise yalnızca en sondaki bölme ve çıktı biçimlendirmesi için kullanılır.
\(L\) adet basamak, \(9L+1\) adet olası rakam toplamı ve her geçişte en fazla \(10\) aday rakam vardır. Bu nedenle çalışma süresi
$$O(L\cdot 9L\cdot 10)=O(L^2)$$
olur. Döner tabloların kullandığı bellek \(O(9L)=O(L)\)'dir. \(L=\Theta(\log_{10} N)\) olduğundan, bu yöntem sınırın büyüklüğüne göre \(O((\log N)^2)\) zaman ve \(O(\log N)\) bellek kullanır.
Debemos evaluar
$$F(N)=\sum_{n=1}^{N}\frac{n}{s(n)},$$
donde \(s(n)\) es la suma de las cifras decimales de \(n\). El límite pedido tiene 19 cifras, así que recorrer todos los \(n\le N\) es inviable. La observación decisiva es que el denominador depende solo de la suma de cifras. Por eso la suma completa puede reagruparse por clases de suma digital y calcularse con programación dinámica sobre dígitos.
Sea \(L\) el número de cifras decimales de \(N\). Una cadena decimal de longitud \(L\) tiene suma de cifras entre \(0\) y \(9L\), así que solo existen \(9L+1\) clases relevantes. La implementación aprovecha exactamente ese espacio de estados pequeño.
Definimos
$$A_\sigma(N)=\sum_{\substack{1\le n\le N\\ s(n)=\sigma}} n.$$
Entonces la expresión original se escribe como
$$F(N)=\sum_{\sigma=1}^{9L}\frac{A_\sigma(N)}{\sigma}.$$
Así, no hace falta tratar cada término \(n/s(n)\) por separado. Basta con conocer, para cada suma de cifras posible \(\sigma\), la suma de todos los números hasta \(N\) cuya suma de cifras sea exactamente \(\sigma\).
Escribimos el límite como las cifras \(d_1d_2\dots d_L\). Recorremos esas cifras de izquierda a derecha permitiendo ceros iniciales, de modo que cada entero \(0\le n\le N\) quede representado exactamente una vez como una cadena decimal de longitud \(L\).
Después de procesar las primeras \(k\) posiciones, para cada suma de cifras \(\sigma\) guardamos cuatro cantidades:
$$C_k^{\mathrm{eq}}(\sigma),\quad S_k^{\mathrm{eq}}(\sigma),\qquad C_k^{\mathrm{lt}}(\sigma),\quad S_k^{\mathrm{lt}}(\sigma).$$
Los valores \(C\) cuentan cuántos prefijos hay en ese estado, y los valores \(S\) almacenan la suma de sus valores numéricos. El superíndice \(\mathrm{eq}\) significa que el prefijo procesado coincide exactamente con las primeras \(k\) cifras de \(N\); el superíndice \(\mathrm{lt}\) significa que ya es menor y que las cifras restantes quedan libres.
Al inicio solo existe el prefijo vacío:
$$C_0^{\mathrm{eq}}(0)=1,\qquad S_0^{\mathrm{eq}}(0)=0,$$
mientras que todos los demás estados son cero.
Supongamos que un estado contiene \(C\) prefijos con suma de cifras \(\sigma\) y suma numérica total \(S\). Si añadimos una cifra \(d\), cada valor antiguo \(x\) pasa a ser \(10x+d\). Por tanto la nueva suma de cifras es \(\sigma+d\), el número de prefijos resultantes sigue siendo \(C\) y la suma numérica total pasa a ser
$$\sum (10x+d)=10S+dC.$$
Así, una transición aporta
$$\Delta C=C,\qquad \Delta S=10S+dC.$$
Si el estado actual es exacto, añadir la cifra límite de la posición conserva la familia exacta, mientras que elegir una cifra menor envía el estado a la familia de prefijos menores. Si el estado ya es menor, cualquier cifra \(0,\dots,9\) permanece en esa segunda familia.
Un ejemplo mínimo aclara la fórmula. Si un estado contiene los prefijos \(1\) y \(4\), entonces \(C=2\) y \(S=5\). Al añadir la cifra \(7\) obtenemos \(17\) y \(47\), cuya suma es \(64\). La fórmula produce el mismo resultado de inmediato:
$$10S+dC=10\cdot 5+7\cdot 2=64.$$
Tras procesar las \(L\) cifras, la suma de todos los valores \(0\le n\le N\) cuya suma de cifras vale \(\sigma\) es
$$A_\sigma(N)=S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma).$$
Los ceros iniciales hacen que los números más cortos queden incluidos automáticamente. La clase \(\sigma=0\) contiene solo el número \(0\) y debe excluirse porque el denominador sería nulo. Por eso
$$F(N)=\sum_{\sigma=1}^{9L}\frac{S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma)}{\sigma}.$$
Usando cadenas de dos cifras, los enteros entre \(0\) y \(10\) son \(00,01,\dots,09,10\). Si agrupamos los positivos por suma de cifras, obtenemos
$$\sigma=1:\ \{1,10\},\qquad A_1(10)=11,$$
$$\sigma=2:\ \{2\},\ A_2(10)=2,\qquad \dots,\qquad \sigma=9:\ \{9\},\ A_9(10)=9.$$
Por tanto
$$F(10)=\frac{11}{1}+\frac{2}{2}+\frac{3}{3}+\cdots+\frac{9}{9}=11+8=19.$$
Ese valor coincide con la comprobación pequeña usada por las implementaciones y deja claro por qué basta con trabajar por clases de suma de cifras.
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Convierten el límite a una cadena decimal, calculan \(L\) y la suma de cifras máxima \(9L\), y mantienen dos tablas rodantes indexadas por suma de cifras: una para los prefijos que siguen igualando al límite y otra para los prefijos que ya quedaron por debajo.
Cada entrada de la tabla guarda dos cantidades exactas: cuántos prefijos representa y cuál es la suma entera de esos prefijos. En cada nueva posición decimal, la implementación crea tablas nuevas, recorre las sumas de cifras alcanzables y aplica la regla \(10S+dC\) para construir la capa siguiente.
Después de la última cifra, la implementación combina las sumas de ambas familias para cada suma de cifras positiva \(\sigma\), divide por \(\sigma\) y acumula la respuesta decimal final. La acumulación exacta con enteros grandes es esencial porque las sumas intermedias crecen mucho más allá del rango de un entero normal; la aritmética decimal de alta precisión se reserva para las divisiones finales y el formato de salida.
Hay \(L\) posiciones decimales, \(9L+1\) posibles sumas de cifras y como máximo \(10\) cifras candidatas por transición. En consecuencia, el tiempo total es
$$O(L\cdot 9L\cdot 10)=O(L^2).$$
Las tablas rodantes usan \(O(9L)=O(L)\) memoria. Como \(L=\Theta(\log_{10} N)\), esto equivale a \(O((\log N)^2)\) tiempo y \(O(\log N)\) memoria en función del tamaño del límite.
我们要求的是
$$F(N)=\sum_{n=1}^{N}\frac{n}{s(n)},$$
其中 \(s(n)\) 表示 \(n\) 的十进制数位和。题目的上界是一个 19 位整数，因此不可能对所有 \(n\le N\) 逐个计算。关键观察是：分母只由数位和决定，所以整个和式可以先按数位和分组，再用数位动态规划一次性统计每一组的总贡献。
设 \(L\) 为 \(N\) 的十进制位数。一个长度为 \(L\) 的十进制串，其数位和只可能落在 \(0\) 到 \(9L\) 之间，因此真正需要处理的状态只有 \(9L+1\) 个。实现正是围绕这组很小的数位和状态展开的。
定义
$$A_\sigma(N)=\sum_{\substack{1\le n\le N\\ s(n)=\sigma}} n.$$
那么原式就可以写成
$$F(N)=\sum_{\sigma=1}^{9L}\frac{A_\sigma(N)}{\sigma}.$$
这一步非常重要，因为它把“逐项求 \(n/s(n)\)”变成了“对每个数位和 \(\sigma\)，统计所有满足 \(s(n)=\sigma\) 的数的总和”。一旦 \(A_\sigma(N)\) 都能得到，最后的求值只是一次有限求和。
把上界写成十进制数字 \(d_1d_2\dots d_L\)。我们从左到右依次处理这些数字，并允许前导零。这样一来，每个整数 \(0\le n\le N\) 都恰好对应一个长度为 \(L\) 的十进制串，不会遗漏，也不会重复。
在处理完前 \(k\) 位之后，对每个数位和 \(\sigma\) 维护四个量：
$$C_k^{\mathrm{eq}}(\sigma),\quad S_k^{\mathrm{eq}}(\sigma),\qquad C_k^{\mathrm{lt}}(\sigma),\quad S_k^{\mathrm{lt}}(\sigma).$$
其中 \(C\) 表示当前状态里有多少个前缀，\(S\) 表示这些前缀数值本身的总和。上标 \(\mathrm{eq}\) 表示当前前缀与 \(N\) 的前 \(k\) 位完全相同；上标 \(\mathrm{lt}\) 表示当前前缀已经严格小于 \(N\) 的前 \(k\) 位，所以后面的数字不再受上界限制。
初始状态只有空前缀：
$$C_0^{\mathrm{eq}}(0)=1,\qquad S_0^{\mathrm{eq}}(0)=0,$$
其余状态全部为零。
假设某个状态里有 \(C\) 个前缀，它们的数位和都是 \(\sigma\)，这些前缀对应的数值总和为 \(S\)。如果在这些前缀后面统一添加一位数字 \(d\)，那么每个旧值 \(x\) 都会变成 \(10x+d\)。于是新状态的数位和变成 \(\sigma+d\)，新前缀的数量仍然是 \(C\)，而它们的数值总和则变成
$$\sum (10x+d)=10S+dC.$$
因此一次转移的贡献可以直接写成
$$\Delta C=C,\qquad \Delta S=10S+dC.$$
如果当前状态属于“仍然与上界前缀相等”的那一类，那么只有在本位选择当前上界数字时，下一步仍然保持在相等状态；如果本位选择更小的数字，就会转入“已经小于上界”的状态。反过来，如果当前已经处于较小状态，那么本位可以自由选择 \(0,\dots,9\)，并且仍然留在较小状态。
这个公式为什么正确，可以用一个极小的例子直观看出。假设某个状态中只有前缀 \(1\) 和 \(4\)，那么 \(C=2\)，\(S=5\)。如果统一追加数字 \(7\)，得到的新数是 \(17\) 和 \(47\)，总和为 \(64\)。而公式给出
$$10S+dC=10\cdot 5+7\cdot 2=64,$$
完全一致。
当 \(L\) 位全部处理结束后，所有满足 \(0\le n\le N\) 且数位和为 \(\sigma\) 的整数，它们的总和就是
$$A_\sigma(N)=S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma).$$
由于我们允许前导零，位数较短的正整数已经自动被包含在内。需要特别注意的是 \(\sigma=0\) 这一类，它只包含数字 \(0\)，而 \(0\) 的分母 \(s(0)\) 为零，不应该进入原式。因此最终公式是
$$F(N)=\sum_{\sigma=1}^{9L}\frac{S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma)}{\sigma}.$$
把所有数都写成两位十进制串，那么从 \(0\) 到 \(10\) 依次是 \(00,01,\dots,09,10\)。把正整数按数位和分组：
$$\sigma=1:\ \{1,10\},\qquad A_1(10)=11,$$
$$\sigma=2:\ \{2\},\ A_2(10)=2,\qquad \dots,\qquad \sigma=9:\ \{9\},\ A_9(10)=9.$$
于是
$$F(10)=\frac{11}{1}+\frac{2}{2}+\frac{3}{3}+\cdots+\frac{9}{9}=11+8=19.$$
这个结果正好对应实现中使用的小规模校验值，也说明了为什么“先按数位和汇总，再统一除以 \(\sigma\)”是正确的。
C++、Python 和 Java 三份实现采用的是完全相同的思路。它们先把上界转成十进制字符串，得到位数 \(L\) 与最大可能数位和 \(9L\)，然后维护两张按数位和索引的滚动表：一张表示“当前前缀仍然与上界前缀相等”，另一张表示“当前前缀已经严格小于上界”。
每个表项都保存两个精确量：该状态包含多少个前缀，以及这些前缀数值的整数总和。每处理一位数字，实现就新建下一层表格，遍历所有可达数位和，并按照 \(10S+dC\) 的转移规则把贡献推送到下一层。
在最后一位处理完成之后，实现把两张表中同一正数位和 \(\sigma\) 的总和合并，再除以 \(\sigma\)，逐项累加得到最终的小数答案。由于这些中间整数和远远超过普通机器整数范围，所以实现先用精确整数把所有分组总和累积出来，只有在最后一步做除法和格式化输出时才使用高精度十进制运算。
共有 \(L\) 个十进制位置，\(9L+1\) 个可能的数位和状态，每次状态转移最多尝试 \(10\) 个数字，所以总时间复杂度为
$$O(L\cdot 9L\cdot 10)=O(L^2).$$
滚动数组只保存 \(O(9L)=O(L)\) 个状态，因此空间复杂度是线性的。又因为 \(L=\Theta(\log_{10} N)\)，所以从上界大小的角度看，算法复杂度就是 \(O((\log N)^2)\) 时间和 \(O(\log N)\) 空间。
Нужно вычислить
$$F(N)=\sum_{n=1}^{N}\frac{n}{s(n)},$$
где \(s(n)\) — сумма десятичных цифр числа \(n\). Верхняя граница имеет 19 цифр, поэтому прямой перебор всех \(n\le N\) неприемлем. Ключевое наблюдение состоит в том, что знаменатель зависит только от суммы цифр. Поэтому всю сумму можно перегруппировать по классам одинаковой суммы цифр и вычислить с помощью digit DP.
Пусть \(L\) — число десятичных цифр в \(N\). Для десятичной строки длины \(L\) сумма цифр лежит между \(0\) и \(9L\), значит, существует только \(9L+1\) существенных классов. Именно это маленькое пространство состояний использует реализация.
Определим
$$A_\sigma(N)=\sum_{\substack{1\le n\le N\\ s(n)=\sigma}} n.$$
Тогда исходное выражение переписывается как
$$F(N)=\sum_{\sigma=1}^{9L}\frac{A_\sigma(N)}{\sigma}.$$
Значит, нет необходимости рассматривать каждый член \(n/s(n)\) отдельно. Достаточно для каждого возможного значения \(\sigma\) знать сумму всех чисел до \(N\), у которых сумма цифр равна \(\sigma\).
Запишем верхнюю границу в виде цифр \(d_1d_2\dots d_L\). Мы идем по ним слева направо и разрешаем ведущие нули. Тогда каждое целое число \(0\le n\le N\) представляется ровно одной десятичной строкой длины \(L\).
После обработки первых \(k\) позиций для каждой суммы цифр \(\sigma\) хранятся четыре величины:
$$C_k^{\mathrm{eq}}(\sigma),\quad S_k^{\mathrm{eq}}(\sigma),\qquad C_k^{\mathrm{lt}}(\sigma),\quad S_k^{\mathrm{lt}}(\sigma).$$
Здесь \(C\) — число префиксов в данном состоянии, а \(S\) — сумма их числовых значений. Верхний индекс \(\mathrm{eq}\) означает, что обработанный префикс точно совпадает с первыми \(k\) цифрами числа \(N\); индекс \(\mathrm{lt}\) означает, что префикс уже меньше и дальнейшие цифры можно выбирать свободно.
Изначально существует только пустой префикс:
$$C_0^{\mathrm{eq}}(0)=1,\qquad S_0^{\mathrm{eq}}(0)=0,$$
а все остальные состояния равны нулю.
Предположим, что в некотором состоянии находится \(C\) префиксов с суммой цифр \(\sigma\), а сумма их числовых значений равна \(S\). Если дописать справа цифру \(d\), то каждое старое значение \(x\) превратится в \(10x+d\). Значит, новая сумма цифр станет \(\sigma+d\), число новых префиксов останется равным \(C\), а их суммарное числовое значение будет
$$\sum (10x+d)=10S+dC.$$
Следовательно, один переход дает вклад
$$\Delta C=C,\qquad \Delta S=10S+dC.$$
Если текущее состояние точное, то выбор текущей граничной цифры оставляет нас в точной семье, а выбор меньшей цифры переводит в семью меньших префиксов. Если состояние уже меньше, то любой выбор цифры \(0,\dots,9\) оставляет его в той же семье.
Небольшой пример делает формулу прозрачной. Пусть состояние содержит префиксы \(1\) и \(4\). Тогда \(C=2\), \(S=5\). После дописывания цифры \(7\) получаются числа \(17\) и \(47\) с суммой \(64\). Формула дает точно то же самое:
$$10S+dC=10\cdot 5+7\cdot 2=64.$$
После обработки всех \(L\) цифр сумма всех значений \(0\le n\le N\) с суммой цифр \(\sigma\) равна
$$A_\sigma(N)=S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma).$$
Ведущие нули автоматически включают и более короткие числа. Класс \(\sigma=0\) содержит только число \(0\), которое нужно исключить, потому что знаменатель там равен нулю. Поэтому окончательно имеем
$$F(N)=\sum_{\sigma=1}^{9L}\frac{S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma)}{\sigma}.$$
Если использовать двухзначные строки, то числа от \(0\) до \(10\) записываются как \(00,01,\dots,09,10\). Разобьем положительные числа по сумме цифр:
$$\sigma=1:\ \{1,10\},\qquad A_1(10)=11,$$
$$\sigma=2:\ \{2\},\ A_2(10)=2,\qquad \dots,\qquad \sigma=9:\ \{9\},\ A_9(10)=9.$$
Тогда
$$F(10)=\frac{11}{1}+\frac{2}{2}+\frac{3}{3}+\cdots+\frac{9}{9}=11+8=19.$$
Это совпадает с малой контрольной проверкой в реализациях и наглядно показывает, почему достаточно суммировать по классам одинаковой суммы цифр.
Реализации на C++, Python и Java используют один и тот же алгоритм. Сначала верхняя граница переводится в десятичную строку, затем вычисляются \(L\) и максимальная сумма цифр \(9L\). После этого поддерживаются две скользящие таблицы по сумме цифр: одна для префиксов, которые все еще равны префиксу границы, и другая для префиксов, уже ставших меньше.
Каждая ячейка таблицы хранит две точные величины: сколько префиксов она описывает и какова суммарная целочисленная сумма этих префиксов. На каждой новой позиции строится следующий слой таблиц, перебираются достижимые суммы цифр, и применяется правило \(10S+dC\).
После обработки последней цифры программа для каждой положительной суммы цифр \(\sigma\) складывает вклады из обеих семей, делит на \(\sigma\) и накапливает итоговый десятичный результат. Точная целочисленная аккумуляция необходима, потому что промежуточные суммы классов намного превосходят диапазон обычных машинных целых; высокоточная десятичная арифметика нужна только на этапе последних делений и форматирования ответа.
Есть \(L\) десятичных позиций, \(9L+1\) возможных сумм цифр и не более \(10\) вариантов цифры на переход. Поэтому время работы равно
$$O(L\cdot 9L\cdot 10)=O(L^2).$$
Скользящие таблицы занимают \(O(9L)=O(L)\) памяти. Поскольку \(L=\Theta(\log_{10} N)\), это дает \(O((\log N)^2)\) времени и \(O(\log N)\) памяти как функцию от размера границы.
المطلوب حساب
$$F(N)=\sum_{n=1}^{N}\frac{n}{s(n)},$$
حيث تمثل \(s(n)\) مجموع الأرقام العشرية للعدد \(n\). الحد الأعلى في المسألة عدد مكوّن من 19 خانة، لذلك فإن المرور على جميع القيم \(n\le N\) غير عملي. الفكرة الحاسمة هي أن المقام يعتمد فقط على مجموع الأرقام، ولهذا يمكن إعادة تنظيم المجموع بحسب فئات مجموع الأرقام ثم حسابه دفعة واحدة باستخدام برمجة ديناميكية على الخانات.
ليكن \(L\) عدد الخانات العشرية في \(N\). أي سلسلة عشرية طولها \(L\) يكون مجموع أرقامها بين \(0\) و\(9L\)، أي إن عدد الفئات الممكنة هو فقط \(9L+1\). وتعتمد الخوارزمية كلها على هذا الفضاء الصغير من الحالات.
نعرّف
$$A_\sigma(N)=\sum_{\substack{1\le n\le N\\ s(n)=\sigma}} n.$$
وعندئذ يصبح المقدار المطلوب
$$F(N)=\sum_{\sigma=1}^{9L}\frac{A_\sigma(N)}{\sigma}.$$
وهذا يعني أننا لا نحتاج إلى معالجة كل حد \(n/s(n)\) على حدة، بل يكفي أن نعرف لكل قيمة ممكنة لـ \(\sigma\) مجموع جميع الأعداد حتى \(N\) التي يكون مجموع أرقامها مساويًا لها.
نكتب الحد الأعلى على صورة الأرقام \(d_1d_2\dots d_L\). ثم نعالج هذه الخانات من اليسار إلى اليمين مع السماح بالأصفار البادئة، وبذلك يُمثَّل كل عدد صحيح \(0\le n\le N\) مرة واحدة بالضبط كسلسلة عشرية طولها \(L\).
بعد معالجة أول \(k\) خانات، نحتفظ لكل مجموع أرقام \(\sigma\) بأربع كميات:
$$C_k^{\mathrm{eq}}(\sigma),\quad S_k^{\mathrm{eq}}(\sigma),\qquad C_k^{\mathrm{lt}}(\sigma),\quad S_k^{\mathrm{lt}}(\sigma).$$
القيم \(C\) تمثل عدد البوادئ الموجودة في تلك الحالة، أما القيم \(S\) فتمثل مجموع قيم هذه البوادئ نفسها. والرمز \(\mathrm{eq}\) يعني أن البادئة الحالية لا تزال مساوية تمامًا لأول \(k\) خانات من \(N\)، بينما الرمز \(\mathrm{lt}\) يعني أنها أصبحت أصغر بالفعل، وبالتالي تصبح الخانات اللاحقة غير مقيّدة بالحد الأعلى.
في البداية لا يوجد إلا البادئة الفارغة:
$$C_0^{\mathrm{eq}}(0)=1,\qquad S_0^{\mathrm{eq}}(0)=0,$$
وجميع الحالات الأخرى تساوي صفرًا.
افترض أن حالة ما تحتوي على \(C\) بوادئ مجموع أرقامها \(\sigma\)، وأن مجموع قيمها العددية هو \(S\). إذا أضفنا رقمًا \(d\) إلى يمين كل بادئة، فإن كل قيمة قديمة \(x\) تتحول إلى \(10x+d\). وعندئذ يصبح مجموع الأرقام الجديد \(\sigma+d\)، ويبقى عدد البوادئ الجديدة مساويًا لـ \(C\)، بينما يصبح مجموع قيمها
$$\sum (10x+d)=10S+dC.$$
إذًا مساهمة انتقال واحد هي
$$\Delta C=C,\qquad \Delta S=10S+dC.$$
إذا كانت الحالة الحالية من نوع المطابقة التامة، فإن اختيار الرقم الحدّي في هذه الخانة يبقي الحالة في عائلة المطابقة، أما اختيار رقم أصغر فينقلها إلى عائلة القيم الأصغر من الحد. وإذا كانت الحالة أصلًا أصغر من الحد، فإن أي رقم من \(0\) إلى \(9\) يبقيها في تلك العائلة.
مثال صغير يوضح صحة الصيغة. إذا كانت الحالة تحتوي على البادئتين \(1\) و\(4\)، فلدينا \(C=2\) و\(S=5\). وعند إضافة الرقم \(7\) نحصل على \(17\) و\(47\)، ومجموعهما \(64\). والصيغة تعطي مباشرة
$$10S+dC=10\cdot 5+7\cdot 2=64,$$
وهو نفس الناتج تمامًا.
بعد الانتهاء من معالجة جميع الخانات \(L\)، فإن مجموع كل القيم \(0\le n\le N\) التي يكون مجموع أرقامها \(\sigma\) يساوي
$$A_\sigma(N)=S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma).$$
السماح بالأصفار البادئة يضمن دخول الأعداد الأقصر تلقائيًا. أما الفئة \(\sigma=0\) فهي تحتوي فقط على العدد \(0\)، ويجب استبعادها لأن المقام سيكون صفرًا. لذلك نحصل في النهاية على
$$F(N)=\sum_{\sigma=1}^{9L}\frac{S_L^{\mathrm{eq}}(\sigma)+S_L^{\mathrm{lt}}(\sigma)}{\sigma}.$$
إذا استعملنا تمثيلات من خانتين، فإن الأعداد من \(0\) إلى \(10\) هي \(00,01,\dots,09,10\). وعند تجميع الأعداد الموجبة بحسب مجموع الأرقام نحصل على
$$\sigma=1:\ \{1,10\},\qquad A_1(10)=11,$$
$$\sigma=2:\ \{2\},\ A_2(10)=2,\qquad \dots,\qquad \sigma=9:\ \{9\},\ A_9(10)=9.$$
ومن ثم
$$F(10)=\frac{11}{1}+\frac{2}{2}+\frac{3}{3}+\cdots+\frac{9}{9}=11+8=19.$$
وهذا يطابق قيمة التحقق الصغيرة المستعملة في التنفيذ، ويبين بوضوح لماذا يكفي العمل على مستوى فئات مجموع الأرقام بدلًا من التعداد المباشر.
تتبع تطبيقات C++ وPython وJava الخطة نفسها تمامًا. فهي تحول الحد الأعلى إلى سلسلة عشرية، وتحسب \(L\) وأكبر مجموع أرقام ممكن \(9L\)، ثم تحتفظ بجدولين دائريين مفهرسين بحسب مجموع الأرقام: أحدهما للبوادئ التي لا تزال مساوية للحد، والآخر للبوادئ التي أصبحت أصغر منه.
كل خانة في الجدول تخزن قيمتين دقيقتين: عدد البوادئ الموجودة في تلك الحالة، ومجموع قيم هذه البوادئ كأعداد صحيحة. وعند معالجة كل خانة جديدة، ينشئ التنفيذ طبقة جديدة من الجداول، ويمر على جميع مجاميع الأرقام الممكنة، ثم يطبق قاعدة \(10S+dC\) لبناء الطبقة التالية.
بعد الخانة الأخيرة، يجمع التنفيذ مساهمات العائلتين لكل مجموع أرقام موجب \(\sigma\)، ثم يقسم على \(\sigma\) ويجمع الناتج في جواب عشري نهائي. ويظل التراكم صحيحًا تمامًا باستخدام أعداد صحيحة كبيرة لأن المجاميع الوسيطة أكبر بكثير من حدود الأعداد القياسية، في حين تُستخدم الحسابات العشرية عالية الدقة فقط في القسمة الأخيرة وتنسيق المخرجات.
لدينا \(L\) خانات عشرية، و\(9L+1\) حالة ممكنة لمجموع الأرقام، وبحد أقصى \(10\) أرقام مرشحة في كل انتقال. لذلك يكون التعقيد الزمني
$$O(L\cdot 9L\cdot 10)=O(L^2).$$
أما الذاكرة المستخدمة من قبل الجداول الدائرية فهي \(O(9L)=O(L)\). وبما أن \(L=\Theta(\log_{10} N)\)، فإن الخوارزمية تعمل بزمن \(O((\log N)^2)\) وذاكرة \(O(\log N)\) بدلالة حجم الحد الأعلى.