For each integer \(k\) from \(1\) to \(n\), let \(d_n\left(\frac{1}{k}\right)\) be the \(n\)-th digit after the decimal point in the decimal expansion of \(\frac{1}{k}\). The required quantity is
$$S(n)=\sum_{k=1}^{n} d_n\left(\frac{1}{k}\right).$$
A direct simulation of long division would advance through \(n\) decimal places for every denominator, which is far too expensive when \(n=10^7\). The implementations avoid that by jumping straight to the needed digit through modular arithmetic.
The entire problem rests on one observation: the \(n\)-th decimal digit of a reciprocal can be recovered from the remainder of \(10^{n-1}\) modulo the denominator.
If
$$\frac{1}{k}=0.a_1a_2a_3\dots,$$
then shifting the decimal point by \(n\) places gives
$$\left\lfloor \frac{10^n}{k} \right\rfloor = 10^{n-1}a_1 + 10^{n-2}a_2 + \cdots + 10a_{n-1} + a_n.$$
So the last digit of that integer is exactly the digit we want. Therefore
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10^n}{k} \right\rfloor - 10\left\lfloor \frac{10^{n-1}}{k} \right\rfloor.$$
This is the standard way to isolate one decimal digit after scaling by powers of \(10\).
Write the Euclidean division of \(10^{n-1}\) by \(k\) as
$$10^{n-1}=qk+r,\qquad 0\le r<k.$$
Then
$$\left\lfloor \frac{10^{n-1}}{k} \right\rfloor=q$$
and
$$\frac{10^n}{k}=10q+\frac{10r}{k}.$$
Taking floors yields
$$\left\lfloor \frac{10^n}{k} \right\rfloor=10q+\left\lfloor \frac{10r}{k} \right\rfloor.$$
Substituting into the previous identity gives the compact formula
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10r}{k} \right\rfloor,$$
where
$$r=10^{n-1}\bmod k.$$
This is exactly the quantity used by the implementation. It also handles terminating decimals automatically: once the remainder is \(0\), every later digit is \(0\).
For each denominator \(k\), we need only the residue
$$r \equiv 10^{n-1}\pmod{k}.$$
Computing \(10^{n-1}\) itself would be absurdly large, but repeated squaring evaluates the residue in \(O(\log n)\) modular multiplications. Every intermediate value is reduced modulo \(k\), so the numbers never grow beyond the modulus.
Once \(r\) is known, the digit is recovered immediately by the integer formula \(\left\lfloor 10r/k \right\rfloor\).
Applying the digit formula to every \(k\) from \(1\) to \(n\) gives
$$S(n)=\sum_{k=1}^{n}\left\lfloor \frac{10\left(10^{n-1}\bmod k\right)}{k} \right\rfloor.$$
The problem is therefore not about building decimal expansions; it is about evaluating one modular power for each denominator and adding the resulting digits.
The small checkpoint \(n=7\) illustrates the method clearly. We need the seventh digit after the decimal point of \(1/k\) for \(1\le k\le 7\).
For \(k=3\),
$$10^6\bmod 3 = 1,\qquad d_7\left(\frac{1}{3}\right)=\left\lfloor \frac{10\cdot 1}{3} \right\rfloor=3.$$
For \(k=6\),
$$10^6\bmod 6 = 4,\qquad d_7\left(\frac{1}{6}\right)=\left\lfloor \frac{40}{6} \right\rfloor=6.$$
For \(k=7\),
$$10^6\bmod 7 = 1,\qquad d_7\left(\frac{1}{7}\right)=\left\lfloor \frac{10}{7} \right\rfloor=1.$$
The complete digit list is
$$0,0,3,0,0,6,1,$$
so
$$S(7)=0+0+3+0+0+6+1=10.$$
This matches the checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same structure. They iterate through every denominator \(k\) from \(1\) to \(n\), compute the residue \(10^{n-1}\bmod k\) by repeated squaring, convert that residue into the required decimal digit via
$$\left\lfloor \frac{10r}{k} \right\rfloor,$$
and add the digit to a running total.
No decimal string is ever built, and no long-division table is stored. The implementation keeps only a fixed set of integers for the current modulus, current base, remaining exponent, current residue, and the cumulative sum.
For one denominator \(k\), binary exponentiation for exponent \(n-1\) needs \(O(\log n)\) modular multiplications. Repeating that for every \(k=1,2,\dots,n\) gives total time
$$O(n\log n).$$
The auxiliary space is \(O(1)\), since only a constant number of integer variables is maintained in addition to the final sum.
Für jedes \(k\) von \(1\) bis \(n\) bezeichne \(d_n\left(\frac{1}{k}\right)\) die \(n\)-te Ziffer nach dem Dezimalpunkt in der Dezimalentwicklung von \(\frac{1}{k}\). Gesucht ist
$$S(n)=\sum_{k=1}^{n} d_n\left(\frac{1}{k}\right).$$
Eine direkte Simulation der schriftlichen Division würde für jeden Nenner bis zur \(n\)-ten Nachkommastelle laufen und wäre bei \(n=10^7\) viel zu langsam. Deshalb springen die Implementierungen mit modularer Arithmetik direkt zur gesuchten Ziffer.
Der Kern der Lösung ist: Die \(n\)-te Nachkommastelle von \(\frac{1}{k}\) hängt nur vom Rest von \(10^{n-1}\) modulo \(k\) ab.
Ist
$$\frac{1}{k}=0.a_1a_2a_3\dots,$$
dann folgt nach Verschiebung des Dezimalpunkts um \(n\) Stellen
$$\left\lfloor \frac{10^n}{k} \right\rfloor = 10^{n-1}a_1 + 10^{n-2}a_2 + \cdots + 10a_{n-1} + a_n.$$
Die letzte Ziffer dieser Zahl ist also genau die gesuchte Dezimalziffer. Daher gilt
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10^n}{k} \right\rfloor - 10\left\lfloor \frac{10^{n-1}}{k} \right\rfloor.$$
Das ist die übliche Regel, mit der man nach einer Skalierung um Zehnerpotenzen eine einzelne Dezimalstelle isoliert.
Teile \(10^{n-1}\) euklidisch durch \(k\):
$$10^{n-1}=qk+r,\qquad 0\le r<k.$$
Dann ist
$$\left\lfloor \frac{10^{n-1}}{k} \right\rfloor=q$$
und zugleich
$$\frac{10^n}{k}=10q+\frac{10r}{k}.$$
Nach dem Abrunden erhält man
$$\left\lfloor \frac{10^n}{k} \right\rfloor=10q+\left\lfloor \frac{10r}{k} \right\rfloor.$$
Einsetzen liefert die kompakte Identität
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10r}{k} \right\rfloor,$$
wobei
$$r=10^{n-1}\bmod k.$$
Genau diese Formel verwenden die Implementierungen. Endliche Dezimaldarstellungen werden automatisch korrekt behandelt: Sobald der Rest \(0\) ist, sind alle folgenden Ziffern ebenfalls \(0\).
Für jeden Nenner \(k\) braucht man nur
$$r \equiv 10^{n-1}\pmod{k}.$$
Die Zahl \(10^{n-1}\) selbst wäre riesig, aber wiederholtes Quadrieren berechnet den Rest in \(O(\log n)\) modularen Multiplikationen. Nach jedem Schritt wird modulo \(k\) reduziert, sodass die Zwischenwerte klein bleiben.
Ist \(r\) bekannt, erhält man die gesuchte Ziffer sofort durch die Ganzzahlformel \(\left\lfloor 10r/k \right\rfloor\).
Wendet man die Ziffernformel auf alle \(k\) von \(1\) bis \(n\) an, so ergibt sich
$$S(n)=\sum_{k=1}^{n}\left\lfloor \frac{10\left(10^{n-1}\bmod k\right)}{k} \right\rfloor.$$
Die Aufgabe besteht also nicht darin, Dezimalentwicklungen auszuschreiben, sondern für jeden Nenner genau eine modulare Potenz zu berechnen und die resultierende Ziffer zu addieren.
Der kleine Kontrollfall \(n=7\) zeigt die Methode besonders klar. Gesucht ist jeweils die siebte Nachkommastelle von \(\frac{1}{k}\) für \(1\le k\le 7\).
Für \(k=3\) gilt
$$10^6\bmod 3 = 1,\qquad d_7\left(\frac{1}{3}\right)=\left\lfloor \frac{10\cdot 1}{3} \right\rfloor=3.$$
Für \(k=6\) gilt
$$10^6\bmod 6 = 4,\qquad d_7\left(\frac{1}{6}\right)=\left\lfloor \frac{40}{6} \right\rfloor=6.$$
Für \(k=7\) gilt
$$10^6\bmod 7 = 1,\qquad d_7\left(\frac{1}{7}\right)=\left\lfloor \frac{10}{7} \right\rfloor=1.$$
Die vollständige Ziffernfolge lautet
$$0,0,3,0,0,6,1,$$
also
$$S(7)=0+0+3+0+0+6+1=10.$$
Damit stimmt der Wert exakt mit dem Kontrollpunkt der Implementierungen überein.
Die C++-, Python- und Java-Implementierungen besitzen denselben Ablauf. Sie iterieren über alle Nenner \(k\) von \(1\) bis \(n\), berechnen den Rest \(10^{n-1}\bmod k\) per wiederholtem Quadrieren, wandeln diesen Rest mit
$$\left\lfloor \frac{10r}{k} \right\rfloor$$
in die gesuchte Dezimalziffer um und addieren diese zu einer laufenden Summe.
Es wird keine Dezimalzeichenkette aufgebaut und keine Tabelle der schriftlichen Division gespeichert. Benötigt werden nur wenige Ganzzahlen für Modulus, Basis, Restexponent, aktuellen Rest und die Gesamtsumme.
Für einen einzelnen Nenner \(k\) benötigt die binäre Exponentiation mit Exponent \(n-1\) \(O(\log n)\) modulare Multiplikationen. Über alle \(k=1,2,\dots,n\) ergibt das die Gesamtzeit
$$O(n\log n).$$
Der zusätzliche Speicherbedarf ist \(O(1)\), da neben der Endsumme nur eine konstante Anzahl von Ganzzahlvariablen gehalten wird.
\(1\) ile \(n\) arasındaki her \(k\) için, \(d_n\left(\frac{1}{k}\right)\) ifadesi \(\frac{1}{k}\) sayısının ondalık açılımında virgülden sonraki \(n\). basamağı göstersin. Hesaplanması istenen toplam
$$S(n)=\sum_{k=1}^{n} d_n\left(\frac{1}{k}\right)$$
şeklindedir. Her payda için uzun bölmeyi \(n\) basamak boyunca simüle etmek, özellikle \(n=10^7\) olduğunda fazla yavaştır. Bu yüzden uygulama doğrudan ilgili basamağa ulaşmak için modüler aritmetik kullanır.
Ana gözlem şudur: \(\frac{1}{k}\) sayısının \(n\). ondalık basamağı, yalnızca \(10^{n-1}\) sayısının \(k\) ile bölümünden kalanla belirlenir.
Eğer
$$\frac{1}{k}=0.a_1a_2a_3\dots,$$
ise, ondalık noktayı \(n\) basamak sağa kaydırınca
$$\left\lfloor \frac{10^n}{k} \right\rfloor = 10^{n-1}a_1 + 10^{n-2}a_2 + \cdots + 10a_{n-1} + a_n$$
elde edilir. Bu tamsayının son rakamı tam aradığımız basamaktır. Dolayısıyla
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10^n}{k} \right\rfloor - 10\left\lfloor \frac{10^{n-1}}{k} \right\rfloor$$
olur. Bu, bir ondalık basamağı kuvvetle ölçekleyip ayıklamanın standart yoludur.
\(10^{n-1}\) sayısını \(k\)'ye göre Öklid bölmesiyle yazalım:
$$10^{n-1}=qk+r,\qquad 0\le r<k.$$
Buradan
$$\left\lfloor \frac{10^{n-1}}{k} \right\rfloor=q$$
ve
$$\frac{10^n}{k}=10q+\frac{10r}{k}$$
çıkar. Taban alınca
$$\left\lfloor \frac{10^n}{k} \right\rfloor=10q+\left\lfloor \frac{10r}{k} \right\rfloor$$
olur. Böylece önceki ifade
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10r}{k} \right\rfloor$$
şeklinde sadeleşir; burada
$$r=10^{n-1}\bmod k.$$
Uygulamanın kullandığı temel formül budur. Sonlu ondalık açılımlar da otomatik olarak doğru işlenir; kalan \(0\) olduğunda sonraki bütün basamaklar da \(0\) olur.
Her \(k\) için aslında sadece şu değer gerekir:
$$r \equiv 10^{n-1}\pmod{k}.$$
\(10^{n-1}\) sayısını doğrudan oluşturmak imkansızdır; fakat repeated squaring yöntemiyle bu kalan \(O(\log n)\) modüler çarpımda bulunur. Her adımda \(k\) moduna indirgeme yapıldığı için ara sayılar da küçük kalır.
\(r\) bulunduğunda istenen basamak tek bir çarpma ve tam sayı bölmesiyle elde edilir.
Basamak formülünü \(1\) ile \(n\) arasındaki bütün paydalara uygularsak
$$S(n)=\sum_{k=1}^{n}\left\lfloor \frac{10\left(10^{n-1}\bmod k\right)}{k} \right\rfloor$$
sonucuna ulaşırız. Yani problem, ondalık açılım üretmekten ziyade her payda için tek bir modüler üs hesabı yapıp çıkan rakamı toplamaktır.
Küçük kontrol noktası olan \(n=7\), yöntemin nasıl çalıştığını açıkça gösterir. \(1\le k\le 7\) için \(\frac{1}{k}\) sayısının yedinci ondalık basamağını bulalım.
\(k=3\) için
$$10^6\bmod 3 = 1,\qquad d_7\left(\frac{1}{3}\right)=\left\lfloor \frac{10\cdot 1}{3} \right\rfloor=3.$$
\(k=6\) için
$$10^6\bmod 6 = 4,\qquad d_7\left(\frac{1}{6}\right)=\left\lfloor \frac{40}{6} \right\rfloor=6.$$
\(k=7\) için
$$10^6\bmod 7 = 1,\qquad d_7\left(\frac{1}{7}\right)=\left\lfloor \frac{10}{7} \right\rfloor=1.$$
Tam basamak listesi
$$0,0,3,0,0,6,1$$
olduğundan
$$S(7)=0+0+3+0+0+6+1=10$$
elde edilir. Bu değer uygulamadaki kontrol noktasıyla aynıdır.
C++, Python ve Java uygulamaları aynı akışı izler. \(k=1\) ile \(k=n\) arasındaki tüm paydalar tek tek dolaşılır, her biri için \(10^{n-1}\bmod k\) değeri ikili üs alma ile hesaplanır, sonra bu kalan
$$\left\lfloor \frac{10r}{k} \right\rfloor$$
formülüyle ilgili ondalık basamağa çevrilir ve sonuç kümülatif toplama eklenir.
Hiçbir aşamada ondalık karakter dizisi oluşturulmaz ve uzun bölme tablosu tutulmaz. Uygulama yalnızca geçerli mod, taban, kalan üs, mevcut kalan ve toplam için sabit sayıda tamsayı saklar.
Tek bir \(k\) değeri için, üs \(n-1\) olduğundan ikili üs alma \(O(\log n)\) modüler çarpım gerektirir. Bunu tüm \(k=1,2,\dots,n\) için tekrarladığımızda toplam süre
$$O(n\log n)$$
olur. Yardımcı bellek \(O(1)\)'dir; çünkü son toplam dışında yalnızca sabit sayıda tamsayı değişkeni tutulur.
Para cada entero \(k\) entre \(1\) y \(n\), sea \(d_n\left(\frac{1}{k}\right)\) la cifra situada en la posición \(n\) después del punto decimal en la expansión decimal de \(\frac{1}{k}\). Lo que se debe calcular es
$$S(n)=\sum_{k=1}^{n} d_n\left(\frac{1}{k}\right).$$
Simular la división larga para cada denominador hasta llegar a la cifra \(n\) sería demasiado costoso cuando \(n=10^7\). Por eso las implementaciones usan aritmética modular para saltar directamente a la cifra necesaria.
La observación central es que la cifra decimal \(n\)-ésima de un recíproco depende solo del resto de \(10^{n-1}\) módulo el denominador.
Si
$$\frac{1}{k}=0.a_1a_2a_3\dots,$$
entonces al desplazar el punto decimal \(n\) posiciones se obtiene
$$\left\lfloor \frac{10^n}{k} \right\rfloor = 10^{n-1}a_1 + 10^{n-2}a_2 + \cdots + 10a_{n-1} + a_n.$$
La última cifra de ese entero es exactamente la cifra buscada. Por tanto,
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10^n}{k} \right\rfloor - 10\left\lfloor \frac{10^{n-1}}{k} \right\rfloor.$$
Esta es la forma estándar de aislar una cifra decimal después de escalar por potencias de \(10\).
Escribamos la división euclídea de \(10^{n-1}\) entre \(k\):
$$10^{n-1}=qk+r,\qquad 0\le r<k.$$
Entonces
$$\left\lfloor \frac{10^{n-1}}{k} \right\rfloor=q$$
y además
$$\frac{10^n}{k}=10q+\frac{10r}{k}.$$
Tomando partes enteras,
$$\left\lfloor \frac{10^n}{k} \right\rfloor=10q+\left\lfloor \frac{10r}{k} \right\rfloor.$$
Al sustituir, la expresión se simplifica a
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10r}{k} \right\rfloor,$$
donde
$$r=10^{n-1}\bmod k.$$
Esa es exactamente la fórmula empleada por la implementación. También cubre de forma natural los decimales finitos: cuando el resto pasa a ser \(0\), todas las cifras posteriores son \(0\).
Para cada denominador \(k\) solo hace falta conocer
$$r \equiv 10^{n-1}\pmod{k}.$$
Calcular \(10^{n-1}\) como número entero sería inviable, pero el método de cuadrados sucesivos obtiene el residuo en \(O(\log n)\) multiplicaciones modulares. Como cada paso se reduce módulo \(k\), los valores intermedios permanecen acotados.
Una vez conocido \(r\), la cifra deseada se obtiene inmediatamente con la fórmula entera \(\left\lfloor 10r/k \right\rfloor\).
Aplicando la identidad anterior a todos los denominadores, resulta
$$S(n)=\sum_{k=1}^{n}\left\lfloor \frac{10\left(10^{n-1}\bmod k\right)}{k} \right\rfloor.$$
Así, el problema no consiste en construir expansiones decimales completas, sino en evaluar una potencia modular por cada \(k\) y acumular la cifra correspondiente.
El caso pequeño \(n=7\) muestra el procedimiento con claridad. Hay que tomar la séptima cifra decimal de \(\frac{1}{k}\) para \(1\le k\le 7\).
Para \(k=3\),
$$10^6\bmod 3 = 1,\qquad d_7\left(\frac{1}{3}\right)=\left\lfloor \frac{10\cdot 1}{3} \right\rfloor=3.$$
Para \(k=6\),
$$10^6\bmod 6 = 4,\qquad d_7\left(\frac{1}{6}\right)=\left\lfloor \frac{40}{6} \right\rfloor=6.$$
Para \(k=7\),
$$10^6\bmod 7 = 1,\qquad d_7\left(\frac{1}{7}\right)=\left\lfloor \frac{10}{7} \right\rfloor=1.$$
La lista completa de cifras es
$$0,0,3,0,0,6,1,$$
y por lo tanto
$$S(7)=0+0+3+0+0+6+1=10.$$
Ese valor coincide con el punto de control usado por las implementaciones.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Recorren todos los denominadores \(k\) desde \(1\) hasta \(n\), calculan el residuo \(10^{n-1}\bmod k\) mediante cuadrados sucesivos, convierten ese residuo en la cifra buscada con
$$\left\lfloor \frac{10r}{k} \right\rfloor,$$
y añaden la cifra a una suma acumulada.
No se construye ninguna cadena decimal ni se guarda una tabla de división larga. La implementación mantiene solo un conjunto fijo de enteros para el módulo actual, la base actual, el exponente restante, el residuo actual y la suma total.
Para un denominador \(k\), la exponenciación binaria con exponente \(n-1\) requiere \(O(\log n)\) multiplicaciones modulares. Repetirlo para todos los \(k=1,2,\dots,n\) produce un tiempo total de
$$O(n\log n).$$
La memoria auxiliar es \(O(1)\), porque aparte de la suma final solo se conservan unas pocas variables enteras.
对于每个 \(1\le k\le n\)，记 \(d_n\left(\frac{1}{k}\right)\) 为分数 \(\frac{1}{k}\) 的十进制展开中小数点后第 \(n\) 位数字。题目要求计算
$$S(n)=\sum_{k=1}^{n} d_n\left(\frac{1}{k}\right).$$
如果对每个分母都直接做长除法，一位一位推进到第 \(n\) 位，那么总工作量会非常大；当 \(n=10^7\) 时，这样的做法显然不可行。实现中的思路是不用真正展开小数，而是利用模运算直接定位到目标数字。
整个方法建立在一个非常关键的事实之上：\(\frac{1}{k}\) 的第 \(n\) 位小数，只取决于 \(10^{n-1}\) 除以 \(k\) 时的余数。
设
$$\frac{1}{k}=0.a_1a_2a_3\dots,$$
其中 \(a_1,a_2,\dots\) 是十进制数字。把小数点向右移动 \(n\) 位后，有
$$\left\lfloor \frac{10^n}{k} \right\rfloor = 10^{n-1}a_1 + 10^{n-2}a_2 + \cdots + 10a_{n-1} + a_n.$$
这个整数的个位正好就是第 \(n\) 位小数，因此
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10^n}{k} \right\rfloor - 10\left\lfloor \frac{10^{n-1}}{k} \right\rfloor.$$
这一步的意义是把“取第 \(n\) 位数字”转化为纯整数运算，不再需要真正构造小数字符串。
对 \(10^{n-1}\) 做欧几里得除法：
$$10^{n-1}=qk+r,\qquad 0\le r<k.$$
于是
$$\left\lfloor \frac{10^{n-1}}{k} \right\rfloor=q$$
并且
$$\frac{10^n}{k}=10q+\frac{10r}{k}.$$
再取整可得
$$\left\lfloor \frac{10^n}{k} \right\rfloor=10q+\left\lfloor \frac{10r}{k} \right\rfloor.$$
代回上式后，目标数字立刻化简为
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10r}{k} \right\rfloor,$$
其中
$$r=10^{n-1}\bmod k.$$
这正是实现所使用的核心公式。它对有限小数同样成立；一旦余数变成 \(0\)，后面的所有小数位自然都是 \(0\)。
对每个分母 \(k\)，我们真正需要的只是
$$r \equiv 10^{n-1}\pmod{k}.$$
如果先把 \(10^{n-1}\) 完整算出来，再去取模，数值会大到完全不可操作。快速幂通过“平方并按位处理指数”的方式，只用 \(O(\log n)\) 次模乘就能求出这个余数，而且每一步都会对 \(k\) 取模，所以中间值始终受控。
余数 \(r\) 一旦得到，第 \(n\) 位数字就只剩下一次乘以 \(10\) 和一次整数除法。
把上面的结果对全部 \(k=1,2,\dots,n\) 累加，就得到
$$S(n)=\sum_{k=1}^{n}\left\lfloor \frac{10\left(10^{n-1}\bmod k\right)}{k} \right\rfloor.$$
所以这道题的本质并不是“生成很多小数展开”，而是“对每个分母做一次模幂运算，再把对应的那一位数字加起来”。
小规模检查点 \(n=7\) 很适合说明算法。此时需要计算 \(\frac{1}{k}\) 在小数点后第七位的数字，其中 \(1\le k\le 7\)。
当 \(k=3\) 时，
$$10^6\bmod 3 = 1,\qquad d_7\left(\frac{1}{3}\right)=\left\lfloor \frac{10\cdot 1}{3} \right\rfloor=3.$$
当 \(k=6\) 时，
$$10^6\bmod 6 = 4,\qquad d_7\left(\frac{1}{6}\right)=\left\lfloor \frac{40}{6} \right\rfloor=6.$$
当 \(k=7\) 时，
$$10^6\bmod 7 = 1,\qquad d_7\left(\frac{1}{7}\right)=\left\lfloor \frac{10}{7} \right\rfloor=1.$$
全部数字依次为
$$0,0,3,0,0,6,1,$$
因此
$$S(7)=0+0+3+0+0+6+1=10.$$
这个结果与实现中使用的检查点完全一致。
C++、Python 和 Java 实现采用完全相同的算法结构。它们从 \(k=1\) 遍历到 \(k=n\)，对每个 \(k\) 用快速幂计算 \(10^{n-1}\bmod k\)，然后通过
$$\left\lfloor \frac{10r}{k} \right\rfloor$$
把余数变成所需的小数位，并把这个数字加入累计和中。
整个过程中不会构造任何十进制字符串，也不会保存长除法表格。实现只维护当前模数、当前底数、剩余指数状态、当前余数以及总和等少量整数。
对单个分母 \(k\) 来说，指数为 \(n-1\) 的快速幂需要 \(O(\log n)\) 次模乘。对所有 \(k=1,2,\dots,n\) 都执行一次之后，总时间复杂度为
$$O(n\log n).$$
额外空间复杂度为 \(O(1)\)，因为除最终答案外，只保存固定数量的整数变量。
Для каждого \(k\) от \(1\) до \(n\) обозначим через \(d_n\left(\frac{1}{k}\right)\) \(n\)-ю цифру после запятой в десятичной записи числа \(\frac{1}{k}\). Требуется вычислить сумму
$$S(n)=\sum_{k=1}^{n} d_n\left(\frac{1}{k}\right).$$
Если буквально выполнять деление в столбик для каждого знаменателя до \(n\)-й цифры, работа станет слишком дорогой уже при \(n=10^7\). Поэтому реализации не строят десятичные дроби целиком, а извлекают нужную цифру напрямую с помощью остатков по модулю.
Главная идея такова: \(n\)-я цифра десятичной дроби \(\frac{1}{k}\) определяется только остатком числа \(10^{n-1}\) по модулю \(k\).
Пусть
$$\frac{1}{k}=0.a_1a_2a_3\dots,$$
где \(a_1,a_2,\dots\) — десятичные цифры. После сдвига запятой на \(n\) позиций получаем
$$\left\lfloor \frac{10^n}{k} \right\rfloor = 10^{n-1}a_1 + 10^{n-2}a_2 + \cdots + 10a_{n-1} + a_n.$$
Последняя цифра этого целого числа и есть искомая цифра после запятой. Значит,
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10^n}{k} \right\rfloor - 10\left\lfloor \frac{10^{n-1}}{k} \right\rfloor.$$
Так мы переводим задачу извлечения одной десятичной цифры в чисто целочисленную формулу.
Разделим \(10^{n-1}\) на \(k\) с остатком:
$$10^{n-1}=qk+r,\qquad 0\le r<k.$$
Тогда
$$\left\lfloor \frac{10^{n-1}}{k} \right\rfloor=q$$
и
$$\frac{10^n}{k}=10q+\frac{10r}{k}.$$
Беря целую часть, получаем
$$\left\lfloor \frac{10^n}{k} \right\rfloor=10q+\left\lfloor \frac{10r}{k} \right\rfloor.$$
Подстановка в предыдущую формулу дает
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10r}{k} \right\rfloor,$$
где
$$r=10^{n-1}\bmod k.$$
Именно это равенство используется в реализации. Оно автоматически корректно работает и для конечных десятичных дробей: как только остаток становится равным \(0\), все последующие цифры равны \(0\).
Для каждого знаменателя \(k\) нужно знать только
$$r \equiv 10^{n-1}\pmod{k}.$$
Само число \(10^{n-1}\) слишком велико, чтобы строить его явно. Но метод repeated squaring позволяет получить остаток за \(O(\log n)\) модульных умножений. После каждого умножения выполняется взятие по модулю \(k\), поэтому промежуточные значения остаются ограниченными.
Когда остаток \(r\) уже найден, искомая цифра вычисляется одной целочисленной формулой \(\left\lfloor 10r/k \right\rfloor\).
Применяя полученную формулу ко всем \(k\) от \(1\) до \(n\), приходим к выражению
$$S(n)=\sum_{k=1}^{n}\left\lfloor \frac{10\left(10^{n-1}\bmod k\right)}{k} \right\rfloor.$$
Следовательно, задача сводится не к построению десятичных записей, а к вычислению одной модульной степени для каждого знаменателя и суммированию полученной цифры.
Небольшой контрольный случай \(n=7\) хорошо демонстрирует метод. Нужно взять седьмую цифру после запятой в \(\frac{1}{k}\) для \(1\le k\le 7\).
Для \(k=3\)
$$10^6\bmod 3 = 1,\qquad d_7\left(\frac{1}{3}\right)=\left\lfloor \frac{10\cdot 1}{3} \right\rfloor=3.$$
Для \(k=6\)
$$10^6\bmod 6 = 4,\qquad d_7\left(\frac{1}{6}\right)=\left\lfloor \frac{40}{6} \right\rfloor=6.$$
Для \(k=7\)
$$10^6\bmod 7 = 1,\qquad d_7\left(\frac{1}{7}\right)=\left\lfloor \frac{10}{7} \right\rfloor=1.$$
Полный список цифр таков:
$$0,0,3,0,0,6,1,$$
поэтому
$$S(7)=0+0+3+0+0+6+1=10.$$
Это совпадает с контрольным значением, используемым в реализациях.
Реализации на C++, Python и Java устроены одинаково. Они перебирают все знаменатели \(k\) от \(1\) до \(n\), для каждого вычисляют остаток \(10^{n-1}\bmod k\) методом repeated squaring, преобразуют этот остаток в нужную десятичную цифру по формуле
$$\left\lfloor \frac{10r}{k} \right\rfloor,$$
а затем прибавляют цифру к накопленной сумме.
Никакие десятичные строки не создаются и таблицы деления в столбик не сохраняются. В памяти находятся только несколько целых чисел: текущий модуль, текущая база, состояние оставшейся степени, текущий остаток и общая сумма.
Для одного знаменателя \(k\) бинарное возведение в степень с показателем \(n-1\) требует \(O(\log n)\) модульных умножений. Повторяя это для всех \(k=1,2,\dots,n\), получаем суммарное время
$$O(n\log n).$$
Дополнительная память составляет \(O(1)\), потому что помимо итоговой суммы хранится только постоянное число целочисленных переменных.
لكل عدد صحيح \(k\) من \(1\) إلى \(n\)، نرمز بـ \(d_n\left(\frac{1}{k}\right)\) إلى الرقم الواقع في المرتبة \(n\) بعد الفاصلة العشرية في التمثيل العشري للعدد \(\frac{1}{k}\). المطلوب هو حساب
$$S(n)=\sum_{k=1}^{n} d_n\left(\frac{1}{k}\right).$$
لو قمنا بمحاكاة القسمة الطويلة لكل مقام حتى نصل إلى الخانة \(n\)، فسيصبح العمل باهظًا جدًا عندما يكون \(n=10^7\). لذلك تعتمد التطبيقات على الحسابات المعيارية للوصول مباشرة إلى الرقم المطلوب من دون بناء التوسع العشري كاملًا.
الفكرة الأساسية هي أن الرقم العشري رقم \(n\) في \(\frac{1}{k}\) يعتمد فقط على باقي \(10^{n-1}\) عند القسمة على \(k\).
إذا كان
$$\frac{1}{k}=0.a_1a_2a_3\dots,$$
فإن تحريك الفاصلة \(n\) مراتب إلى اليمين يعطي
$$\left\lfloor \frac{10^n}{k} \right\rfloor = 10^{n-1}a_1 + 10^{n-2}a_2 + \cdots + 10a_{n-1} + a_n.$$
إذن الرقم الأخير في هذا العدد الصحيح هو بالضبط الرقم الذي نبحث عنه. ومن ثم
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10^n}{k} \right\rfloor - 10\left\lfloor \frac{10^{n-1}}{k} \right\rfloor.$$
وهذه هي الطريقة القياسية لعزل منزلة عشرية واحدة بعد الضرب في قوة مناسبة للعدد \(10\).
لنكتب القسمة الإقليدية للعدد \(10^{n-1}\) على \(k\):
$$10^{n-1}=qk+r,\qquad 0\le r<k.$$
وعندئذ
$$\left\lfloor \frac{10^{n-1}}{k} \right\rfloor=q$$
وكذلك
$$\frac{10^n}{k}=10q+\frac{10r}{k}.$$
وبأخذ الجزء الصحيح نحصل على
$$\left\lfloor \frac{10^n}{k} \right\rfloor=10q+\left\lfloor \frac{10r}{k} \right\rfloor.$$
لذلك تتبسط الصيغة السابقة إلى
$$d_n\left(\frac{1}{k}\right)=\left\lfloor \frac{10r}{k} \right\rfloor,$$
حيث
$$r=10^{n-1}\bmod k.$$
وهذه هي الصيغة الدقيقة التي تعتمدها التطبيقات. كما أنها تتعامل تلقائيًا مع الكسور العشرية المنتهية؛ فمتى صار الباقي \(0\)، كانت جميع الأرقام التالية مساوية للصفر.
لكل مقام \(k\) لا نحتاج إلا إلى القيمة
$$r \equiv 10^{n-1}\pmod{k}.$$
أما العدد \(10^{n-1}\) نفسه فهو ضخم جدًا ولا يمكن بناؤه مباشرة. لكن طريقة التربيع المتكرر تحسب هذا الباقي في \(O(\log n)\) من الضربات المعيارية فقط، لأننا نختزل modulo \(k\) بعد كل خطوة، فلا تكبر القيم الوسيطة خارج النطاق اللازم.
وبمجرد معرفة \(r\)، يصبح استخراج الرقم المطلوب مجرد عملية ضرب في \(10\) تليها قسمة صحيحة.
بتطبيق صيغة الرقم على كل \(k\) من \(1\) إلى \(n\)، نحصل على
$$S(n)=\sum_{k=1}^{n}\left\lfloor \frac{10\left(10^{n-1}\bmod k\right)}{k} \right\rfloor.$$
إذن جوهر المسألة ليس توليد التوسعات العشرية، بل إجراء أس معياري واحد لكل مقام ثم جمع الرقم الناتج.
الحالة الصغيرة \(n=7\) توضّح الفكرة بوضوح. نحتاج إلى الرقم السابع بعد الفاصلة في \(\frac{1}{k}\) لكل \(1\le k\le 7\).
عندما \(k=3\)،
$$10^6\bmod 3 = 1,\qquad d_7\left(\frac{1}{3}\right)=\left\lfloor \frac{10\cdot 1}{3} \right\rfloor=3.$$
وعندما \(k=6\)،
$$10^6\bmod 6 = 4,\qquad d_7\left(\frac{1}{6}\right)=\left\lfloor \frac{40}{6} \right\rfloor=6.$$
وعندما \(k=7\)،
$$10^6\bmod 7 = 1,\qquad d_7\left(\frac{1}{7}\right)=\left\lfloor \frac{10}{7} \right\rfloor=1.$$
أما القائمة الكاملة للأرقام فهي
$$0,0,3,0,0,6,1,$$
ومن ثم
$$S(7)=0+0+3+0+0+6+1=10.$$
وهذه القيمة تطابق نقطة التحقق المستخدمة في التطبيقات.
تتبع تطبيقات C++ وPython وJava البنية نفسها. فهي تمر على جميع المقامات \(k\) من \(1\) إلى \(n\)، وتحسب الباقي \(10^{n-1}\bmod k\) بطريقة التربيع المتكرر، ثم تحوله إلى الرقم العشري المطلوب عبر الصيغة
$$\left\lfloor \frac{10r}{k} \right\rfloor,$$
ثم تضيف هذا الرقم إلى مجموع تراكمي.
لا يتم إنشاء أي سلسلة عشرية، ولا يتم تخزين جدول للقسمة الطويلة. كل ما تحتفظ به الشيفرة هو عدد ثابت من القيم الصحيحة يمثل المود الحالي والأساس الحالي وحالة الأس المتبقية والباقي الحالي والمجموع الكلي.
لكل مقام \(k\)، يحتاج حساب \(10^{n-1}\) معياريًا بالأس السريع إلى \(O(\log n)\) من الضربات المعيارية. وعند تكرار ذلك لكل \(k=1,2,\dots,n\) نحصل على زمن كلي
$$O(n\log n).$$
أما الذاكرة الإضافية فهي \(O(1)\)، لأن التنفيذ لا يحتفظ إلا بعدد ثابت من المتغيرات الصحيحة إلى جانب المجموع النهائي.