Problem 13 gives one hundred 50-digit integers and asks for the first 10 digits of their total sum.
With \(S=\sum_{i=1}^{100} N_i\), the goal is to determine \(\operatorname{pref}_{10}(S)\).
The arithmetic is elementary, but the scale matters: the input is far beyond ordinary 64-bit integers. The real structure of the problem comes from decimal place value, carry propagation, and the fact that only a short leading prefix of the full sum is needed.
Every addend has 50 decimal digits, so
$$10^{49} \le N_i \lt 10^{50}.$$
Summing 100 such numbers gives
$$10^{51} \le S \lt 10^{52}.$$
Therefore the total has exactly 52 digits. The requested answer is the leading 10-digit prefix of a 52-digit integer.
Write each number in base 10 as
$$N_i = \sum_{j=0}^{49} d_{i,j}10^j,\qquad 0\le d_{i,j}\le 9,$$
where \(j=0\) is the units column. Exact schoolbook addition processes columns from right to left. If \(c_j\) is the carry entering column \(j\), then
$$u_j = c_j + \sum_{i=1}^{100} d_{i,j},\qquad r_j = u_j \bmod 10,\qquad c_{j+1} = \left\lfloor \frac{u_j}{10} \right\rfloor,$$
with \(c_0=0\).
The key invariant after finishing columns \(0,1,\dots,p-1\) is
$$\sum_{i=1}^{100}\sum_{j=0}^{p-1} d_{i,j}10^j = \sum_{j=0}^{p-1} r_j10^j + c_p10^p.$$
So the digits already written are exactly the low \(p\) digits of the processed part of the sum, and the carry stores everything that still has to move into higher positions. This is precisely the correctness argument behind the manual digit-by-digit algorithm.
The same recurrence shows why the carry itself fits comfortably into an ordinary small integer. If \(0\le c_j\le 99\), then
$$u_j \le 99 + 100\cdot 9 = 999,$$
so
$$0 \le c_{j+1} = \left\lfloor \frac{u_j}{10}\right\rfloor \le 99.$$
Since \(c_0=0\), induction gives \(0\le c_j\le 99\) for every column. The full total needs 52 digits, but the per-column state remains tiny.
The implementations compute the exact sum, but Problem 13 also admits a clean guard-digit proof. We need 10 leading digits, and there are 100 summands, so any carry coming from discarded tails has at most two decimal digits. One extra safety digit is enough, giving
$$10 + \lceil \log_{10} 100 \rceil + 1 = 13.$$
Split each addend into a 13-digit prefix and a 37-digit tail,
$$N_i = 10^{37}A_i + B_i,$$
where \(A_i\) is the first 13 digits and \(0\le B_i \lt 10^{37}\). Then
$$S = 10^{37}\sum_{i=1}^{100} A_i + \sum_{i=1}^{100} B_i.$$
The tail block satisfies
$$0 \le \sum_{i=1}^{100} B_i \lt 100\cdot 10^{37} = 10^{39},$$
so the carry from the tail into the prefix block is at most 99. Therefore only the last two digits of \(\sum A_i\) can change, and the first 10 digits are already fixed by those 13-digit prefixes. This explains, rigorously and specifically for this dataset, why a prefix-only method also works.
The C++, Python, and Java implementations all compute the same exact quantity. They differ only in how the growing sum is represented.
The C++ implementation keeps the input as decimal strings, scans from the least significant column to the most significant one, adds the 100 digits in the current column together with the incoming carry, emits the new result digit, and updates the carry. Those produced digits are collected in reverse order and reversed once at the end, which yields the full decimal expansion of \(S\); the first 10 characters are then returned.
The Python and Java implementations rely on arbitrary-precision integers provided by the language runtime. Each 50-digit line is parsed as an exact integer, all 100 values are summed, the final total is converted back to decimal text, and the first 10 digits are sliced off. Mathematically this is the same sum as in C++, just performed by a built-in big-integer type instead of manual column logic.
If there are \(m\) numbers of \(d\) digits each, exact column addition takes \(O(md)\) time. For Problem 13, \(m=100\) and \(d=50\), so the total work is only a few thousand digit operations. The big-integer implementations have the same effective scale because they still process every input digit and every digit of the final sum.
Keeping the input in memory costs \(O(md)\) space. Beyond the input itself, the manual exact addition needs \(O(d)\) extra space for the output digits and the carry, while the arbitrary-precision versions need \(O(d)\) space for the running total. A prefix-truncation strategy would reduce the working digit count to \(O(k+\log m)\), but the provided implementations do not need that optimization.
Problem 13 gibt hundert 50-stellige ganze Zahlen vor und verlangt die ersten 10 Ziffern ihrer Gesamtsumme.
Mit \(S=\sum_{i=1}^{100} N_i\) ist also \(\operatorname{pref}_{10}(S)\) gesucht.
Die zugrunde liegende Arithmetik ist elementar, aber die Größenordnung sprengt gewöhnliche 64-Bit-Typen. Die eigentliche mathematische Struktur liegt in der Dezimaldarstellung, der Übertragsfortpflanzung und der Frage, warum schon ein kurzer führender Präfix der Gesamtsumme zuverlässig bestimmt werden kann.
Jeder Summand hat 50 Dezimalstellen, also gilt
$$10^{49} \le N_i \lt 10^{50}.$$
Für die Summe von 100 solchen Zahlen folgt
$$10^{51} \le S \lt 10^{52}.$$
Damit hat die Gesamtsumme genau 52 Stellen. Gesucht ist also der 10-stellige Anfang einer 52-stelligen Zahl.
Schreibe jede Zahl zur Basis 10 als
$$N_i = \sum_{j=0}^{49} d_{i,j}10^j,\qquad 0\le d_{i,j}\le 9,$$
wobei \(j=0\) die Einerstelle ist. Die exakte Schulbuchaddition arbeitet die Spalten von rechts nach links ab. Ist \(c_j\) der Übertrag vor Spalte \(j\), dann gilt
$$u_j = c_j + \sum_{i=1}^{100} d_{i,j},\qquad r_j = u_j \bmod 10,\qquad c_{j+1} = \left\lfloor \frac{u_j}{10} \right\rfloor,$$
mit \(c_0=0\).
Die zentrale Invariante nach den Spalten \(0,1,\dots,p-1\) ist
$$\sum_{i=1}^{100}\sum_{j=0}^{p-1} d_{i,j}10^j = \sum_{j=0}^{p-1} r_j10^j + c_p10^p.$$
Die bereits ausgegebenen Ziffern sind also exakt die unteren \(p\) Stellen der bisher verarbeiteten Summe, und der Übertrag speichert alles, was noch in höhere Stellen weitergereicht werden muss. Genau darauf beruht die Korrektheit der manuellen Ziffernaddition.
Aus derselben Rekursion folgt, warum der Übertrag selbst bequem in einen kleinen gewöhnlichen Integer passt. Gilt \(0\le c_j\le 99\), dann ist
$$u_j \le 99 + 100\cdot 9 = 999,$$
also
$$0 \le c_{j+1} = \left\lfloor \frac{u_j}{10}\right\rfloor \le 99.$$
Da \(c_0=0\) ist, liefert Induktion \(0\le c_j\le 99\) für jede Spalte. Die Gesamtsumme braucht 52 Stellen, der Spaltenzustand aber bleibt winzig.
Die Implementierungen berechnen zwar die exakte Summe, aber für Problem 13 gibt es zusätzlich ein sauberes Schutzstellen-Argument. Gesucht sind 10 führende Ziffern, und es gibt 100 Summanden, also kann ein Übertrag aus den abgeschnittenen Enden höchstens zwei Dezimalstellen haben. Mit einer zusätzlichen Sicherheitsstelle ergibt das
$$10 + \lceil \log_{10} 100 \rceil + 1 = 13.$$
Teile daher jeden Summanden in einen 13-stelligen Präfix und einen 37-stelligen Rest auf:
$$N_i = 10^{37}A_i + B_i,$$
wobei \(A_i\) aus den ersten 13 Ziffern besteht und \(0\le B_i \lt 10^{37}\) gilt. Dann folgt
$$S = 10^{37}\sum_{i=1}^{100} A_i + \sum_{i=1}^{100} B_i.$$
Für den Restblock gilt
$$0 \le \sum_{i=1}^{100} B_i \lt 100\cdot 10^{37} = 10^{39},$$
sodass der Übertrag in den Präfixblock höchstens 99 ist. Damit können sich nur die letzten zwei Ziffern von \(\sum A_i\) ändern, während die ersten 10 Ziffern schon durch die 13-stelligen Präfixe festgelegt sind. Das ist eine problemgenaue Begründung dafür, warum auch eine Präfix-Methode sicher funktionieren würde.
Die C++-, Python- und Java-Implementierungen berechnen alle exakt dieselbe Größe. Der Unterschied liegt nur darin, wie die wachsende Summe repräsentiert wird.
Die C++-Implementierung hält die Eingabe als Dezimalstrings, läuft von der niederwertigsten zur höchstwertigen Spalte, addiert in jeder Spalte die 100 Ziffern zusammen mit dem eingehenden Übertrag, schreibt die neue Ergebnisziffer weg und aktualisiert den Übertrag. Diese Ziffern werden zunächst in umgekehrter Reihenfolge gesammelt und am Ende einmal umgedreht; so entsteht die vollständige Dezimaldarstellung von \(S\), aus der anschließend die ersten 10 Zeichen genommen werden.
Die Python- und Java-Implementierungen verlassen sich auf eingebaute Ganzzahlen mit beliebiger Genauigkeit. Jede 50-stellige Zeile wird als exakte ganze Zahl geparst, alle 100 Werte werden aufsummiert, das Endergebnis wird wieder in einen Dezimalstring umgewandelt, und davon wird der 10-stellige Anfang abgeschnitten. Mathematisch ist das dieselbe Summe wie in C++, nur ohne explizite Spaltenlogik.
Gibt es \(m\) Zahlen mit jeweils \(d\) Stellen, dann kostet exakte Spaltenaddition \(O(md)\) Zeit. Für Problem 13 sind \(m=100\) und \(d=50\), also nur wenige tausend Ziffernoperationen. Die Big-Integer-Varianten haben effektiv dieselbe Größenordnung, weil auch sie alle Eingabeziffern und alle Ziffern der Endsumme verarbeiten.
Das Halten der Eingabe belegt \(O(md)\) Speicher. Zusätzlich benötigt die manuelle exakte Addition \(O(d)\) Platz für Ergebnisziffern und Übertrag, während die Varianten mit beliebiger Genauigkeit \(O(d)\) Platz für die laufende Summe brauchen. Eine Präfix-Trunkierung würde die Arbeitslänge auf \(O(k+\log m)\) drücken, ist für die vorliegenden Implementierungen aber nicht nötig.
Problem 13, yüz tane 50 basamaklı tam sayının toplamının ilk 10 basamağını istemektedir.
\(S=\sum_{i=1}^{100} N_i\) olmak üzere hedef, \(\operatorname{pref}_{10}(S)\) değerini bulmaktır.
Buradaki aritmetik temel düzeydedir, fakat sayıların büyüklüğü sıradan 64 bit tamsayıları aşar. Problemin gerçek matematiksel yapısı, ondalık basamak değerleri, elde aktarımı ve toplamın yalnızca kısa bir ön ekine ihtiyaç duyulmasından gelir.
Her toplanan sayı 50 basamaklıdır; dolayısıyla
$$10^{49} \le N_i \lt 10^{50}.$$
Bu tür 100 sayının toplamı için
$$10^{51} \le S \lt 10^{52}$$
elde edilir. O halde toplam tam olarak 52 basamaklıdır. İstenen cevap, 52 basamaklı bu sayının ilk 10 basamağıdır.
Her sayıyı 10 tabanında
$$N_i = \sum_{j=0}^{49} d_{i,j}10^j,\qquad 0\le d_{i,j}\le 9$$
şeklinde yazalım; burada \(j=0\) birler basamağıdır. Tam okul yöntemi, sütunları sağdan sola işler. \(c_j\), \(j\). sütuna giren elde olsun. O zaman
$$u_j = c_j + \sum_{i=1}^{100} d_{i,j},\qquad r_j = u_j \bmod 10,\qquad c_{j+1} = \left\lfloor \frac{u_j}{10} \right\rfloor,$$
ve başlangıçta \(c_0=0\) olur.
\(0,1,\dots,p-1\) sütunları tamamlandıktan sonraki temel değişmez şudur:
$$\sum_{i=1}^{100}\sum_{j=0}^{p-1} d_{i,j}10^j = \sum_{j=0}^{p-1} r_j10^j + c_p10^p.$$
Yani üretilen rakamlar, işlenmiş kısmın en düşük \(p\) basamağını tam olarak verir; elde ise daha yüksek basamaklara taşınacak kalan kısmı tutar. El ile basamak basamak toplamanın doğruluğu doğrudan bu eşitlikten gelir.
Aynı yineleme, elde değişkeninin neden küçük kaldığını da açıklar. Eğer \(0\le c_j\le 99\) ise
$$u_j \le 99 + 100\cdot 9 = 999,$$
dolayısıyla
$$0 \le c_{j+1} = \left\lfloor \frac{u_j}{10}\right\rfloor \le 99.$$
\(c_0=0\) ile başlayınca tümevarım bütün sütunlar için \(0\le c_j\le 99\) sonucunu verir. Tam toplam 52 basamak gerektirir, fakat sütun başına tutulan durum çok küçüktür.
Uygulamalar tam toplamı hesaplar, fakat Problem 13 için koruma basamaklarıyla verilen temiz bir ispat da vardır. İstenen kısım 10 basamaklıdır ve 100 terim vardır; bu yüzden kesilen kuyruklardan gelebilecek elde en fazla iki ondalık basamak taşır. Bir ek güvenlik basamağı ile
$$10 + \lceil \log_{10} 100 \rceil + 1 = 13$$
elde edilir. Her toplananı 13 basamaklı ön ek ve 37 basamaklı kuyruk olarak ayıralım:
$$N_i = 10^{37}A_i + B_i,$$
burada \(A_i\) ilk 13 basamaktır ve \(0\le B_i \lt 10^{37}\) olur. O halde
$$S = 10^{37}\sum_{i=1}^{100} A_i + \sum_{i=1}^{100} B_i.$$
Kuyruk bloğu için
$$0 \le \sum_{i=1}^{100} B_i \lt 100\cdot 10^{37} = 10^{39}$$
olduğundan, ön ek bloğuna taşınan elde en fazla 99 olur. Demek ki yalnızca \(\sum A_i\) toplamının son iki basamağı değişebilir; ilk 10 basamak ise 13 basamaklı ön eklerle zaten kesinleşmiştir. Bu, özellikle bu veri kümesi için, yalnızca öneklerle çalışan bir yöntemin neden güvenli olduğunu açıkça gösterir.
C++, Python ve Java uygulamalarının üçü de aynı niceliği tam olarak hesaplar. Fark yalnızca büyüyen toplamın nasıl temsil edildiğindedir.
C++ uygulaması girdiyi ondalık dizgiler olarak tutar, en düşük anlamlı sütundan en yükseğe doğru gider, her sütunda bulunan 100 rakamı ve gelen elden doğan toplamı hesaplar, yeni sonuç rakamını üretir ve eldeyi günceller. Üretilen rakamlar önce ters sırada biriktirilir, sonra bir kez çevrilir; böylece \(S\) sayısının tam ondalık yazımı elde edilir ve bunun ilk 10 karakteri alınır.
Python ve Java uygulamaları ise dilin sunduğu keyfi duyarlıklı tamsayıları kullanır. Her 50 basamaklı satır tam sayı olarak ayrıştırılır, 100 değerin tamamı toplanır, son toplam yeniden ondalık metne çevrilir ve ilk 10 basamak kesilip alınır. Matematiksel olarak bu, C++ yöntemindekiyle aynı toplamdır; yalnızca basamak mantığı çalışma zamanına bırakılmıştır.
\(m\) adet \(d\) basamaklı sayı için tam sütun toplaması \(O(md)\) zamanda çalışır. Problem 13'te \(m=100\) ve \(d=50\) olduğundan toplam iş yükü yalnızca birkaç bin basamak işlemidir. Büyük tamsayı kullanan sürümler de fiilen aynı ölçektedir; çünkü onlar da tüm girdi basamaklarını ve sonucun bütün basamaklarını işler.
Girdinin bellekte tutulması \(O(md)\) alan kullanır. Bunun dışında, elle yapılan tam toplama sonucu için \(O(d)\) ek alan ve elde değişkeni gerekir; keyfi duyarlıklı sürümler de çalışan toplam için \(O(d)\) alan kullanır. Önek kesme yaklaşımı çalışma basamak sayısını \(O(k+\log m)\) düzeyine indirebilirdi, fakat verilen uygulamalarda buna ihtiyaç yoktur.
El Problema 13 da cien enteros de 50 cifras y pide las primeras 10 cifras de su suma total.
Si \(S=\sum_{i=1}^{100} N_i\), entonces lo que se busca es \(\operatorname{pref}_{10}(S)\).
La aritmética involucrada es básica, pero el tamaño de los números supera por mucho a los enteros normales de 64 bits. La estructura matemática real del problema está en el valor posicional decimal, en la propagación del acarreo y en justificar por qué basta conocer un prefijo corto del resultado final.
Cada sumando tiene 50 cifras decimales, así que
$$10^{49} \le N_i \lt 10^{50}.$$
Al sumar 100 números de ese tamaño se obtiene
$$10^{51} \le S \lt 10^{52}.$$
Por tanto, la suma total tiene exactamente 52 cifras. La respuesta pedida es el prefijo de 10 cifras de un entero de 52 cifras.
Escribimos cada número en base 10 como
$$N_i = \sum_{j=0}^{49} d_{i,j}10^j,\qquad 0\le d_{i,j}\le 9,$$
donde \(j=0\) es la columna de unidades. La suma escolar exacta procesa las columnas de derecha a izquierda. Si \(c_j\) es el acarreo que entra en la columna \(j\), entonces
$$u_j = c_j + \sum_{i=1}^{100} d_{i,j},\qquad r_j = u_j \bmod 10,\qquad c_{j+1} = \left\lfloor \frac{u_j}{10} \right\rfloor,$$
con \(c_0=0\).
La invariante central tras completar las columnas \(0,1,\dots,p-1\) es
$$\sum_{i=1}^{100}\sum_{j=0}^{p-1} d_{i,j}10^j = \sum_{j=0}^{p-1} r_j10^j + c_p10^p.$$
Es decir, los dígitos ya escritos son exactamente las \(p\) cifras bajas de la parte procesada de la suma, mientras que el acarreo guarda todo lo que aún debe subir a posiciones más altas. Ahí está la prueba de corrección del algoritmo manual por dígitos.
La misma recurrencia muestra por qué el acarreo cabe cómodamente en un entero pequeño. Si \(0\le c_j\le 99\), entonces
$$u_j \le 99 + 100\cdot 9 = 999,$$
y por tanto
$$0 \le c_{j+1} = \left\lfloor \frac{u_j}{10}\right\rfloor \le 99.$$
Como \(c_0=0\), una inducción da \(0\le c_j\le 99\) en todas las columnas. El resultado completo necesita 52 cifras, pero el estado local de cada columna permanece pequeño.
Las implementaciones calculan la suma exacta, pero el problema también admite un argumento limpio con cifras de guarda. Queremos 10 cifras iniciales y hay 100 sumandos; por eso el acarreo que puede venir de las colas descartadas tiene a lo sumo dos cifras decimales. Añadiendo una cifra de seguridad, obtenemos
$$10 + \lceil \log_{10} 100 \rceil + 1 = 13.$$
Separa cada sumando en un prefijo de 13 cifras y una cola de 37 cifras:
$$N_i = 10^{37}A_i + B_i,$$
donde \(A_i\) son las primeras 13 cifras y \(0\le B_i \lt 10^{37}\). Entonces
$$S = 10^{37}\sum_{i=1}^{100} A_i + \sum_{i=1}^{100} B_i.$$
La contribución de las colas satisface
$$0 \le \sum_{i=1}^{100} B_i \lt 100\cdot 10^{37} = 10^{39},$$
así que el acarreo desde la parte baja hacia el bloque de prefijos es como mucho 99. En consecuencia, solo pueden cambiar las dos últimas cifras de \(\sum A_i\), mientras que las primeras 10 ya quedan fijadas por esos prefijos de 13 cifras. Esto justifica de forma rigurosa por qué un método basado solo en prefijos también funcionaría para este conjunto concreto.
Las implementaciones en C++, Python y Java calculan exactamente la misma cantidad. La diferencia está solo en cómo representa cada lenguaje la suma acumulada.
La implementación en C++ mantiene la entrada como cadenas decimales, recorre las columnas desde la menos significativa hasta la más significativa, suma los 100 dígitos de la columna actual junto con el acarreo entrante, emite el nuevo dígito de resultado y actualiza el acarreo. Esos dígitos se guardan primero en orden inverso y luego se invierten una sola vez, produciendo la expansión decimal completa de \(S\); después se toman los primeros 10 caracteres.
Las implementaciones en Python y Java usan enteros de precisión arbitraria del propio lenguaje. Cada línea de 50 cifras se interpreta como un entero exacto, se suman los 100 valores, el total final se convierte otra vez en texto decimal y se extraen sus primeras 10 cifras. Matemáticamente es la misma suma que en C++, solo que realizada por un tipo de gran tamaño ya incorporado.
Si hay \(m\) números de \(d\) cifras, la suma exacta por columnas cuesta \(O(md)\) tiempo. En el Problema 13, \(m=100\) y \(d=50\), así que el trabajo total es de apenas unos miles de operaciones sobre dígitos. Las versiones con enteros grandes tienen la misma escala efectiva porque también procesan todas las cifras de la entrada y del resultado final.
Mantener la entrada en memoria cuesta \(O(md)\) espacio. Más allá de la propia entrada, la suma manual exacta necesita \(O(d)\) espacio adicional para los dígitos de salida y el acarreo, mientras que las versiones con precisión arbitraria necesitan \(O(d)\) para la suma acumulada. Una estrategia de truncamiento por prefijos reduciría la longitud de trabajo a \(O(k+\log m)\), pero las implementaciones dadas no necesitan esa optimización.
第 13 题给出 100 个 50 位十进制整数，要求求出它们总和的前 10 位数字。
记 \(S=\sum_{i=1}^{100} N_i\)，目标就是确定 \(\operatorname{pref}_{10}(S)\)。
这里的运算规则本身并不复杂，但数字规模已经远远超出普通 64 位整数。这个问题真正值得说明的数学内容，是十进制位值结构、进位如何在各列之间传播，以及为什么只关心总和的前 10 位时仍然可以给出严格论证。
每个加数都是 50 位十进制整数，因此
$$10^{49} \le N_i \lt 10^{50}.$$
把 100 个这样的数相加，就得到
$$10^{51} \le S \lt 10^{52}.$$
所以总和一定恰好有 52 位。题目要的并不是全部 52 位，而只是这个 52 位整数的前 10 位。
把每个数写成 10 进制展开
$$N_i = \sum_{j=0}^{49} d_{i,j}10^j,\qquad 0\le d_{i,j}\le 9,$$
其中 \(j=0\) 表示个位。竖式加法从最低位向最高位逐列处理。若 \(c_j\) 表示进入第 \(j\) 列时的进位，则
$$u_j = c_j + \sum_{i=1}^{100} d_{i,j},\qquad r_j = u_j \bmod 10,\qquad c_{j+1} = \left\lfloor \frac{u_j}{10} \right\rfloor,$$
并且初始条件是 \(c_0=0\)。
处理完第 \(0,1,\dots,p-1\) 列之后，核心不变量为
$$\sum_{i=1}^{100}\sum_{j=0}^{p-1} d_{i,j}10^j = \sum_{j=0}^{p-1} r_j10^j + c_p10^p.$$
这条等式的含义非常直接：已经写出的 \(r_0,r_1,\dots,r_{p-1}\) 正好就是已处理部分总和的最低 \(p\) 位，而 \(c_p\) 把还需要继续向高位传递的部分完整保留下来。这正是手工逐列相加算法的正确性依据。
同一个递推关系还能解释一个实现细节：为什么进位本身始终很小。如果 \(0\le c_j\le 99\)，那么
$$u_j \le 99 + 100\cdot 9 = 999,$$
因此
$$0 \le c_{j+1} = \left\lfloor \frac{u_j}{10}\right\rfloor \le 99.$$
由于 \(c_0=0\)，用归纳法可知每一列的进位都满足 \(0\le c_j\le 99\)。也就是说，整个总和虽然需要 52 位来表示，但逐列处理时保存的局部状态始终只是在一个很小的范围内波动。
给出的实现都直接求精确总和，但本题还可以给出一个很漂亮的“保护位”论证。题目只要前 10 位，而加数共有 100 个，所以被丢弃尾部可能产生的总进位最多只有两位十进制数。再多保留一位安全位，就得到
$$10 + \lceil \log_{10} 100 \rceil + 1 = 13.$$
把每个加数拆成 13 位前缀和 37 位尾部：
$$N_i = 10^{37}A_i + B_i,$$
其中 \(A_i\) 是前 13 位，且 \(0\le B_i \lt 10^{37}\)。于是
$$S = 10^{37}\sum_{i=1}^{100} A_i + \sum_{i=1}^{100} B_i.$$
尾部总贡献满足
$$0 \le \sum_{i=1}^{100} B_i \lt 100\cdot 10^{37} = 10^{39},$$
所以从尾部传到前缀块的进位至多是 99。这样一来，\(\sum A_i\) 只有最后两位可能被改变，前 10 位已经由这 13 位前缀完全决定。这个论证针对的正是本题的数据规模，因此它不是模板化技巧，而是对本题为什么可以只看前缀的精确说明。
C++、Python 和 Java 的实现都在计算同一个精确结果，区别只在于“正在增长的总和”是如何表示的。
C++ 实现把输入保留为十进制字符串，从最低有效位向最高有效位逐列扫描。对每一列，它把该列的 100 个数字与进入该列的进位相加，写出新的结果位，并更新下一列的进位。由于结果位是按从低到高的顺序产生的，所以先以逆序收集，最后整体翻转一次，就得到 \(S\) 的完整十进制表示；随后取出最前面的 10 个字符即可。
Python 和 Java 实现则直接使用语言提供的任意精度整数。每一行 50 位数都被解析为精确整数，然后把 100 个值全部相加，再把最后的总和转回十进制字符串，并截取前 10 位。从数学上看，这与 C++ 的逐列加法完全是同一个总和，只是把大整数的细节交给了运行时库。
如果有 \(m\) 个、每个有 \(d\) 位的十进制整数，那么精确的逐列求和需要 \(O(md)\) 时间。对本题来说，\(m=100\)、\(d=50\)，因此总工作量只是几千次数字级操作。任意精度整数版本在有效规模上也是一样的，因为它们同样必须处理所有输入位和最终结果的全部位数。
若把全部输入保存在内存中，输入本身占用 \(O(md)\) 空间。除此之外，手工逐列加法只需要 \(O(d)\) 的额外空间来保存结果位和进位；任意精度整数做法则需要 \(O(d)\) 空间来保存运行中的总和。若使用前缀截断技巧，工作位数可以降到 \(O(k+\log m)\)，但题目给出的实现并不需要这种优化。
В задаче 13 даны сто 50-значных целых чисел, и нужно найти первые 10 цифр их общей суммы.
Если обозначить \(S=\sum_{i=1}^{100} N_i\), то требуется вычислить \(\operatorname{pref}_{10}(S)\).
Сами правила сложения здесь элементарны, но масштаб чисел уже выходит далеко за пределы обычных 64-битных типов. Реальная математическая структура задачи связана с десятичной позиционной записью, переносами между разрядами и строгим объяснением того, почему достаточно знать лишь короткий старший префикс итоговой суммы.
Каждое слагаемое имеет 50 десятичных цифр, следовательно
$$10^{49} \le N_i \lt 10^{50}.$$
Сумма 100 таких чисел удовлетворяет неравенствам
$$10^{51} \le S \lt 10^{52}.$$
Значит, итоговая сумма имеет ровно 52 цифры. От нас требуется только её старший 10-значный префикс.
Представим каждое число в виде
$$N_i = \sum_{j=0}^{49} d_{i,j}10^j,\qquad 0\le d_{i,j}\le 9,$$
где \(j=0\) соответствует разряду единиц. Точное школьное сложение обрабатывает столбцы справа налево. Если \(c_j\) — перенос, входящий в столбец \(j\), то
$$u_j = c_j + \sum_{i=1}^{100} d_{i,j},\qquad r_j = u_j \bmod 10,\qquad c_{j+1} = \left\lfloor \frac{u_j}{10} \right\rfloor,$$
причём \(c_0=0\).
Ключевой инвариант после обработки столбцов \(0,1,\dots,p-1\) таков:
$$\sum_{i=1}^{100}\sum_{j=0}^{p-1} d_{i,j}10^j = \sum_{j=0}^{p-1} r_j10^j + c_p10^p.$$
Иными словами, уже выписанные цифры дают точные младшие \(p\) цифр обработанной части суммы, а перенос хранит всё, что ещё должно уйти в старшие разряды. Именно это и является строгим обоснованием ручного алгоритма сложения по цифрам.
Та же рекуррентная схема объясняет, почему перенос всегда остаётся маленьким обычным числом. Если \(0\le c_j\le 99\), то
$$u_j \le 99 + 100\cdot 9 = 999,$$
а значит
$$0 \le c_{j+1} = \left\lfloor \frac{u_j}{10}\right\rfloor \le 99.$$
Так как \(c_0=0\), по индукции получаем \(0\le c_j\le 99\) для каждого столбца. Полная сумма требует 52 цифры, но локальное состояние при переходе между столбцами остаётся очень небольшим.
Предоставленные реализации считают точную сумму, но для задачи 13 существует и аккуратный аргумент с защитными разрядами. Нужны 10 старших цифр, а слагаемых 100, поэтому перенос из отброшенных хвостов может иметь не более двух десятичных цифр. Добавляя ещё одну страховочную цифру, получаем
$$10 + \lceil \log_{10} 100 \rceil + 1 = 13.$$
Разобьём каждое слагаемое на 13-значный префикс и 37-значный хвост:
$$N_i = 10^{37}A_i + B_i,$$
где \(A_i\) — первые 13 цифр, а \(0\le B_i \lt 10^{37}\). Тогда
$$S = 10^{37}\sum_{i=1}^{100} A_i + \sum_{i=1}^{100} B_i.$$
Для хвостовой части имеем
$$0 \le \sum_{i=1}^{100} B_i \lt 100\cdot 10^{37} = 10^{39},$$
поэтому перенос из хвостового блока в блок префиксов не превосходит 99. Следовательно, измениться могут только последние две цифры числа \(\sum A_i\), а первые 10 цифр уже полностью определены 13-значными префиксами. Это точное объяснение того, почему для данного набора данных даже усечённый префиксный метод даёт правильный ответ.
Реализации на C++, Python и Java вычисляют одну и ту же точную величину. Отличается только способ представления растущей суммы.
Реализация на C++ хранит вход как десятичные строки, идёт от младшего столбца к старшему, в каждом столбце суммирует 100 цифр и входящий перенос, выдаёт новую цифру результата и обновляет перенос. Полученные цифры сначала собираются в обратном порядке, затем один раз разворачиваются, после чего получается полная десятичная запись \(S\); из неё и берутся первые 10 символов.
Реализации на Python и Java используют встроенные целые числа произвольной точности. Каждая 50-значная строка разбирается как точное целое число, все 100 значений складываются, итог переводится обратно в десятичный текст, и из него извлекаются первые 10 цифр. Математически это та же самая сумма, что и в C++, только детали длинной арифметики переданы стандартному типу больших чисел.
Если имеется \(m\) чисел по \(d\) цифр, то точное поколонное сложение работает за \(O(md)\) времени. В задаче 13 это \(m=100\) и \(d=50\), то есть всего несколько тысяч операций над цифрами. Варианты с длинной арифметикой имеют тот же эффективный масштаб, потому что они тоже обрабатывают все цифры входа и все цифры окончательной суммы.
Хранение входных данных требует \(O(md)\) памяти. Сверх этого ручное точное сложение использует \(O(d)\) дополнительного места для цифр результата и переноса, а варианты с произвольной точностью используют \(O(d)\) для текущей накопленной суммы. Подход с усечением префиксов сократил бы рабочую длину до \(O(k+\log m)\), но предоставленным реализациям такая оптимизация не нужна.
تعطي المسألة 13 مئة عدد صحيحاً عشرياً من 50 رقماً، وتطلب أول 10 أرقام من مجموعها الكلي.
إذا كتبنا \(S=\sum_{i=1}^{100} N_i\)، فالمطلوب هو إيجاد \(\operatorname{pref}_{10}(S)\).
قواعد الجمع هنا بسيطة بحد ذاتها، لكن حجم الأعداد يتجاوز كثيراً ما تتحمله الأنواع الصحيحة العادية ذات 64 بت. البنية الرياضية الحقيقية للمسألة تأتي من نظام القيمة المكانية العشري، ومن طريقة انتقال الحمل بين الأعمدة، ومن تبرير لماذا يكفي في النهاية معرفة بادئة قصيرة من المجموع الكامل.
كل حد من حدود الجمع هو عدد عشري مكوَّن من 50 رقماً، ولذلك
$$10^{49} \le N_i \lt 10^{50}.$$
وعند جمع 100 عدد من هذا النوع نحصل على
$$10^{51} \le S \lt 10^{52}.$$
إذن فالمجموع النهائي يملك بالضبط 52 رقماً. وما تطلبه المسألة هو البادئة المكوَّنة من 10 أرقام لهذا العدد ذي الـ52 رقماً.
لنكتب كل عدد على صورة
$$N_i = \sum_{j=0}^{49} d_{i,j}10^j,\qquad 0\le d_{i,j}\le 9,$$
حيث يمثّل \(j=0\) منزلة الآحاد. الجمع المدرسي الدقيق يعالج الأعمدة من اليمين إلى اليسار. إذا كان \(c_j\) هو الحمل الداخل إلى العمود \(j\)، فإن
$$u_j = c_j + \sum_{i=1}^{100} d_{i,j},\qquad r_j = u_j \bmod 10,\qquad c_{j+1} = \left\lfloor \frac{u_j}{10} \right\rfloor,$$
مع شرط البدء \(c_0=0\).
والثابت الأساسي بعد إنهاء الأعمدة \(0,1,\dots,p-1\) هو
$$\sum_{i=1}^{100}\sum_{j=0}^{p-1} d_{i,j}10^j = \sum_{j=0}^{p-1} r_j10^j + c_p10^p.$$
ومعنى ذلك أن الأرقام التي كُتبت بالفعل هي بالضبط الأرقام \(p\) الدنيا من الجزء الذي تمت معالجته من المجموع، بينما يخزن الحمل كل ما يجب أن ينتقل لاحقاً إلى المنازل الأعلى. هذا هو برهان الصحة الحقيقي لخوارزمية الجمع رقمًا رقمًا.
العلاقة نفسها تشرح أيضاً لماذا يبقى الحمل عدداً صغيراً دائماً. فإذا كان \(0\le c_j\le 99\)، فإن
$$u_j \le 99 + 100\cdot 9 = 999,$$
ومن ثم
$$0 \le c_{j+1} = \left\lfloor \frac{u_j}{10}\right\rfloor \le 99.$$
وبما أن \(c_0=0\)، نحصل بالاستقراء على \(0\le c_j\le 99\) في كل عمود. أي إن المجموع الكامل يحتاج إلى 52 رقماً، لكن الحالة المحلية التي نحملها من عمود إلى عمود تبقى صغيرة جداً.
التنفيذات المعطاة تحسب المجموع كاملاً بدقة، لكن للمسألة 13 برهاناً أنيقاً يعتمد على أرقام الحماية. نحن نريد أول 10 أرقام فقط، وهناك 100 حد في الجمع، لذا فإن الحمل القادم من الذيول المحذوفة لا يمكن أن يتجاوز عددًا عشرياً من رقمين. وإذا أضفنا رقماً احتياطياً واحداً نحصل على
$$10 + \lceil \log_{10} 100 \rceil + 1 = 13.$$
نقسم كل حد إلى بادئة من 13 رقماً وذيل من 37 رقماً:
$$N_i = 10^{37}A_i + B_i,$$
حيث \(A_i\) هو أول 13 رقماً و \(0\le B_i \lt 10^{37}\). عندئذٍ
$$S = 10^{37}\sum_{i=1}^{100} A_i + \sum_{i=1}^{100} B_i.$$
ويساوي أثر الذيول
$$0 \le \sum_{i=1}^{100} B_i \lt 100\cdot 10^{37} = 10^{39},$$
ولذلك فإن الحمل الصاعد من كتلة الذيول إلى كتلة البوادئ لا يزيد على 99. وهذا يعني أن آخر رقمين فقط من \(\sum A_i\) قد يتغيران، أما أول 10 أرقام فهي محسومة سلفاً بواسطة هذه البوادئ ذات 13 رقماً. وهذا تبرير دقيق، ومخصص لهذه البيانات نفسها، لسبب صحة الطريقة التي تعتمد على البادئات فقط.
تنفيذات C++ وPython وJava تحسب جميعها المقدار نفسه بدقة تامة. الاختلاف الوحيد هو في كيفية تمثيل المجموع المتراكم أثناء التنفيذ.
تنفيذ C++ يحتفظ بالمدخلات على هيئة سلاسل عشرية، ثم يمر على الأعمدة من الأقل أهمية إلى الأعلى، ويجمع في كل عمود الأرقام المئة الموجودة فيه مع الحمل الداخل، ويخرج رقم النتيجة الجديد ويحدّث الحمل. ولأن الأرقام تُنتَج من اليمين إلى اليسار، فإنها تُجمع أولاً بترتيب معكوس ثم تُعكس مرة واحدة في النهاية، وبذلك نحصل على التمثيل العشري الكامل لـ \(S\) ثم نأخذ أول 10 محارف منه.
أما تنفيذَا Python وJava فيعتمدان على أعداد صحيحة ذات دقة اعتباطية يوفرها وقت التشغيل. كل سطر من 50 رقماً يُحوَّل إلى عدد صحيح دقيق، ثم تُجمع القيم المئة كلها، وبعد ذلك يُعاد تحويل المجموع النهائي إلى نص عشري وتُقتطع أول 10 أرقام. رياضياً هذا هو المجموع نفسه تماماً كما في C++، لكن تفاصيل الحساب الطويل تتكفل بها البنية المدمجة للغة.
إذا كان لدينا \(m\) أعداد، وكل واحد منها يحوي \(d\) رقماً، فإن الجمع العمودي الدقيق يحتاج إلى زمن \(O(md)\). في المسألة 13 لدينا \(m=100\) و\(d=50\)، لذا فالحمل الحسابي كله لا يتجاوز بضعة آلاف من عمليات الأرقام. والتنفيذات المعتمدة على الأعداد الكبيرة تقع عملياً في المقياس نفسه لأنها تعالج أيضاً كل أرقام الإدخال وكل أرقام الناتج النهائي.
الاحتفاظ بالمدخلات في الذاكرة يكلف \(O(md)\) من المساحة. وبعد ذلك يحتاج الجمع اليدوي الدقيق إلى \(O(d)\) مساحة إضافية لأرقام الناتج والحمل، بينما تحتاج النسخ ذات الدقة الاعتباطية إلى \(O(d)\) لمساحة المجموع الجاري. ولو استُخدمت فكرة الاقتصار على البادئات لانخفض عدد الأرقام العاملة إلى \(O(k+\log m)\)، لكن التنفيذات المعطاة لا تحتاج إلى هذا التحسين.