Define \(L(n)\) as the length of the repeating part in the decimal expansion of \(1/n\). The task is to compute
$$S(N)=\sum_{n=3}^{N} L(n)$$
for a very large bound \(N\). A direct simulation of long division for every denominator is much too slow, so the implementations reorganize the sum using multiplicative order and a grouping argument over powers of \(2\) and \(5\).
Every denominator can be written uniquely as
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
The powers of \(2\) and \(5\) only create the finite prefix of the decimal expansion. The recurring part depends entirely on the remaining factor \(m\).
If \(m=1\), then \(1/n\) is a terminating decimal and therefore \(L(n)=0\). If \(m>1\), the repetend length is the multiplicative order of \(10\) modulo \(m\):
$$L(n)=\operatorname{ord}_m(10),$$
where \(\operatorname{ord}_m(10)\) is the smallest positive integer \(k\) such that
$$10^k\equiv 1 \pmod m.$$
This is the standard number-theoretic description of repeating decimals.
Fix an odd integer \(m\) with \(5 \nmid m\). Every denominator of the form
$$n=m\,s,\qquad s=2^a5^b,$$
has exactly the same recurring-cycle length, namely \(\operatorname{ord}_m(10)\), because multiplying by \(2\) and \(5\) changes only the terminating prefix.
For a given quotient \(Q\), define the count of \(2\)-\(5\)-smooth multipliers by
$$C(Q)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2:2^a5^b\le Q\right\}.$$
Then the denominators whose odd core is \(m\) contribute
$$\operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
Summing over all admissible cores gives the central identity used by the fast solver:
$$\boxed{S(N)=\sum_{\substack{m\le N\\ 2\nmid m,\, 5\nmid m}} \operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).}$$
The missing case \(m=1\) can be ignored because its cycle length is \(0\).
Write the odd core as
$$m=\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\neq 2,5.$$
Since the prime-power factors are pairwise coprime, the Chinese remainder theorem implies that the order modulo the product is the least common multiple of the orders modulo each prime power:
$$\operatorname{ord}_m(10)=\mathrm{lcm}\!\left(\operatorname{ord}_{p_1^{e_1}}(10),\dots,\operatorname{ord}_{p_r^{e_r}}(10)\right).$$
So the problem reduces to computing \(\operatorname{ord}_{p^e}(10)\) efficiently for each prime-power factor.
For an odd prime \(p\neq 5\), Fermat's little theorem gives
$$10^{p-1}\equiv 1 \pmod p,$$
so \(\operatorname{ord}_p(10)\) must divide \(p-1\). The implementations therefore start from \(p-1\), factor that number, and try to divide away each prime factor as long as the congruence test still succeeds. In other words, if \(d\) is the current candidate order and \(q\mid d\), then one checks whether
$$10^{d/q}\equiv 1 \pmod p.$$
If the test is true, the order was not minimal and the candidate can be reduced to \(d/q\). Repeating this process yields the exact order modulo \(p\).
Once the order modulo \(p\) is known, the order modulo higher powers of \(p\) is obtained incrementally. If
$$t=\operatorname{ord}_{p^{k-1}}(10),$$
then the next order satisfies
$$\operatorname{ord}_{p^k}(10)\in\{t,pt\}.$$
We distinguish the two cases by testing whether
$$10^t\equiv 1 \pmod{p^k}.$$
If that congruence already holds, the order stays equal to \(t\); otherwise it grows by a factor \(p\). This is exactly the lifting rule used by the implementations when building prime-power orders.
Only primes with \(p\le \sqrt{N}\) need tables for exponents \(e\ge 2\), because if \(p>\sqrt{N}\) then \(p^2>N\) and such a prime can appear only to the first power in any core \(m\le N\).
The admissible odd cores are \(m=3,7,9\). For \(m=3\), the smooth multipliers satisfying \(3s\le 10\) are \(s=1,2\), so the multiplicity is \(2\). Since \(\operatorname{ord}_3(10)=1\), this contributes \(2\).
For \(m=7\), only \(s=1\) is possible, and \(\operatorname{ord}_7(10)=6\), so the contribution is \(6\).
For \(m=9\), again only \(s=1\) is possible, and \(10\equiv 1 \pmod 9\), so \(\operatorname{ord}_9(10)=1\), contributing \(1\).
Therefore
$$S(10)=2+6+1=9,$$
which matches the direct sum of cycle lengths for \(1/3,1/4,\dots,1/10\).
The C++, Python, and Java implementations follow the same arithmetic pipeline. They first build an odd-only smallest-prime-factor sieve, which is enough because only odd cores coprime to \(10\) matter. They then enumerate all odd primes other than \(5\), compute \(\operatorname{ord}_p(10)\) by stripping factors from \(p-1\), and precompute prime-power orders wherever higher powers can still occur below the bound.
In parallel, the implementation generates the sorted list of all numbers of the form \(2^a5^b\le N\). For each odd core \(m\) with \(5\nmid m\), it reconstructs \(\operatorname{ord}_m(10)\) from the prime-power factors using repeated \(\mathrm{lcm}\), counts the valid smooth multipliers with a binary search in that list, and adds the product to the running total. The Python version serves as a thin launcher around the compiled fast solver, while the Java version reproduces the same number-theoretic computation directly.
The preprocessing sieve is near-linear, usually summarized as \(O(N\log\log N)\) time with \(O(N)\) stored state, although the odd-only representation roughly halves the memory footprint. The list of \(2^a5^b\) values has size only \(O((\log N)^2)\), so it is negligible compared with the sieve.
After preprocessing, each admissible core is factorized quickly from the sieve and combined from only a few prime-power orders. The total work is dominated by the sieve construction, the prime-order precomputation, and the single pass over odd cores not divisible by \(5\). This is dramatically faster than simulating decimal periods denominator by denominator, and it is practical for \(N=10^8\).
Sei \(L(n)\) die Länge der periodischen Dezimalstelle von \(1/n\). Gesucht ist
$$S(N)=\sum_{n=3}^{N} L(n)$$
für eine sehr große Schranke \(N\). Direkte Langdivision für jeden Nenner wäre viel zu langsam, daher ordnen die Implementierungen die Summe mit Hilfe der multiplikativen Ordnung und einer Gruppierung nach Potenzen von \(2\) und \(5\) neu.
Jeder Nenner lässt sich eindeutig schreiben als
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
Die Faktoren \(2\) und \(5\) erzeugen nur den endlichen Anfang des Dezimalbruchs. Die eigentliche Periodenlänge hängt ausschließlich vom Restfaktor \(m\) ab.
Falls \(m=1\), ist \(1/n\) ein endlicher Dezimalbruch und somit \(L(n)=0\). Für \(m>1\) gilt
$$L(n)=\operatorname{ord}_m(10),$$
wobei \(\operatorname{ord}_m(10)\) die kleinste positive Zahl \(k\) mit
$$10^k\equiv 1 \pmod m$$
bezeichnet. Genau das ist die klassische Beschreibung periodischer Dezimalbrüche über Kongruenzen.
Fixiere ein ungerades \(m\) mit \(5\nmid m\). Jeder Nenner der Form
$$n=m\,s,\qquad s=2^a5^b,$$
hat dieselbe Periodenlänge \(\operatorname{ord}_m(10)\), denn Multiplikation mit \(2\)- und \(5\)-Potenzen verändert nur den endlichen Vorspann.
Für einen Quotienten \(Q\) definieren wir die Anzahl der \(2\)-\(5\)-glatten Faktoren durch
$$C(Q)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2:2^a5^b\le Q\right\}.$$
Dann tragen alle Nenner mit Kern \(m\) gemeinsam
$$\operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
zur Gesamtsumme bei. Damit erhält man die zentrale Formel des schnellen Verfahrens:
$$\boxed{S(N)=\sum_{\substack{m\le N\\ 2\nmid m,\, 5\nmid m}} \operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).}$$
Der Fall \(m=1\) wird nicht benötigt, weil dort die Periodenlänge ohnehin \(0\) ist.
Schreibe den Kern als
$$m=\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\neq 2,5.$$
Da diese Primzahlpotenzen paarweise teilerfremd sind, liefert der chinesische Restsatz
$$\operatorname{ord}_m(10)=\mathrm{lcm}\!\left(\operatorname{ord}_{p_1^{e_1}}(10),\dots,\operatorname{ord}_{p_r^{e_r}}(10)\right).$$
Somit genügt es, die Ordnungen modulo \(p^e\) effizient zu bestimmen und anschließend per kgV zusammenzusetzen.
Für eine ungerade Primzahl \(p\neq 5\) folgt aus dem kleinen Satz von Fermat:
$$10^{p-1}\equiv 1 \pmod p.$$
Also teilt \(\operatorname{ord}_p(10)\) die Zahl \(p-1\). Die Implementierungen beginnen deshalb mit \(p-1\), faktorisieren diesen Wert und testen nacheinander, welche Primfaktoren entfernt werden können. Ist \(d\) der aktuelle Kandidat und \(q\mid d\), so prüft man
$$10^{d/q}\equiv 1 \pmod p.$$
Ist die Kongruenz erfüllt, war \(d\) nicht minimal und kann zu \(d/q\) verkleinert werden. Wiederholt man das systematisch, bleibt am Ende die exakte Ordnung übrig.
Kennt man die Ordnung modulo \(p\), so erhält man höhere Primzahlpotenzen schrittweise. Ist
$$t=\operatorname{ord}_{p^{k-1}}(10),$$
dann gilt
$$\operatorname{ord}_{p^k}(10)\in\{t,pt\}.$$
Zur Unterscheidung prüft man, ob
$$10^t\equiv 1 \pmod{p^k}$$
bereits gilt. Falls ja, bleibt die Ordnung gleich; andernfalls wird sie mit \(p\) multipliziert. Genau diese Heberegel wird beim Vorberechnen der Primzahlpotenz-Ordnungen benutzt.
Tabellen für Exponenten \(e\ge 2\) braucht man nur für \(p\le \sqrt{N}\), denn bei \(p>\sqrt{N}\) ist bereits \(p^2>N\), also kann eine solche Primzahl in keinem Kern \(m\le N\) höher als einmal auftreten.
Die zulässigen ungeraden Kerne sind \(m=3,7,9\). Für \(m=3\) sind die glatten Faktoren mit \(3s\le 10\) gerade \(s=1,2\), also ist die Multiplizität \(2\). Da \(\operatorname{ord}_3(10)=1\), ergibt das den Beitrag \(2\).
Für \(m=7\) ist nur \(s=1\) möglich, und \(\operatorname{ord}_7(10)=6\), also beträgt der Beitrag \(6\).
Für \(m=9\) ist wieder nur \(s=1\) zulässig, und wegen \(10\equiv 1 \pmod 9\) gilt \(\operatorname{ord}_9(10)=1\), also kommt \(1\) hinzu.
Damit folgt
$$S(10)=2+6+1=9,$$
genau wie bei direkter Auswertung der Periodenlängen von \(1/3,1/4,\dots,1/10\).
Die C++-, Python- und Java-Implementierungen folgen demselben zahlentheoretischen Ablauf. Zuerst wird ein Sieb für den kleinsten Primfaktor nur auf ungeraden Zahlen aufgebaut, weil nur ungerade Kerne teilerfremd zu \(10\) relevant sind. Danach werden alle ungeraden Primzahlen außer \(5\) durchlaufen, ihre Primordnungen aus Teilern von \(p-1\) bestimmt und überall dort Primzahlpotenz-Tabellen vorbereitet, wo höhere Potenzen unterhalb der Schranke noch auftreten können.
Parallel dazu erzeugt die Implementierung die sortierte Liste aller Zahlen \(2^a5^b\le N\). Für jeden ungeraden Kern \(m\) mit \(5\nmid m\) wird \(\operatorname{ord}_m(10)\) aus den Primzahlpotenz-Beiträgen per kgV rekonstruiert, die Anzahl zulässiger glatter Faktoren per binärer Suche bestimmt und das Produkt zur Summe addiert. Die Python-Version ist ein schlanker Starter für den kompilierten schnellen Löser, während Java denselben Rechengang direkt nachbildet.
Das vorberechnende Sieb ist nahezu linear, üblich beschrieben als \(O(N\log\log N)\) Zeit bei \(O(N)\) gespeichertem Zustand, wobei die Beschränkung auf ungerade Indizes den Speicher ungefähr halbiert. Die Menge der Zahlen \(2^a5^b\) hat nur Größe \(O((\log N)^2)\) und ist gegenüber dem Sieb praktisch vernachlässigbar.
Nach der Vorverarbeitung wird jeder zulässige Kern schnell über das Sieb faktorisiert und aus wenigen Primzahlpotenz-Ordnungen zusammengesetzt. Die Hauptkosten entstehen also durch das Sieb, die Vorberechnung der Primordnungen und den einen Durchlauf über alle ungeraden Kerne, die nicht durch \(5\) teilbar sind. Gegenüber naiver Periodensuche ist das ein drastischer Gewinn und für \(N=10^8\) gut praktikabel.
\(L(n)\), \(1/n\) ondalık açılımındaki tekrar eden kısmın uzunluğu olsun. Hesaplanmak istenen toplam
$$S(N)=\sum_{n=3}^{N} L(n)$$
şeklindedir ve \(N\) çok büyüktür. Her payda için tek tek uzun bölme yapmak fazla maliyetli olduğundan, uygulama bu toplamı çarpımsal mertebe ve \(2\) ile \(5\) kuvvetlerine göre gruplayarak yeniden düzenler.
Her payda tekil olarak
$$n=2^a5^b m,\qquad \gcd(m,10)=1$$
biçiminde yazılabilir. Buradaki \(2\) ve \(5\) çarpanları sadece ondalık açılımın sonlanan ön kısmını üretir; asıl periyot uzunluğu kalan \(m\) tarafından belirlenir.
Eğer \(m=1\) ise \(1/n\) sonlu ondalıktır ve \(L(n)=0\). Eğer \(m>1\) ise periyot uzunluğu
$$L(n)=\operatorname{ord}_m(10)$$
olur; burada \(\operatorname{ord}_m(10)\),
$$10^k\equiv 1 \pmod m$$
eşitliğini sağlayan en küçük pozitif \(k\)'dır. Tekrarlı ondalıkların standart sayı kuramı açıklaması budur.
\(5\) ile bölünmeyen sabit bir tek \(m\) için
$$n=m\,s,\qquad s=2^a5^b$$
şeklindeki tüm paydalar aynı periyot uzunluğunu taşır; çünkü \(2\) ve \(5\) kuvvetleri yalnızca sonlanan ön eki değiştirir.
Verilen bir \(Q\) için \(2\)-\(5\) düzgün çarpan sayısını
$$C(Q)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2:2^a5^b\le Q\right\}$$
diye tanımlayalım. O zaman çekirdeği \(m\) olan tüm paydaların toplam katkısı
$$\operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right)$$
olur. Böylece hızlı çözücünün kullandığı ana formül elde edilir:
$$\boxed{S(N)=\sum_{\substack{m\le N\\ 2\nmid m,\, 5\nmid m}} \operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).}$$
\(m=1\) durumu ayrıca toplanmaz; çünkü o durumda çevrim uzunluğu zaten sıfırdır.
Tek çekirdeği
$$m=\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\neq 2,5$$
şeklinde çarpanlarına ayıralım. Farklı asal kuvvetler aralarında asal olduğundan, Çin kalan teoremi sayesinde çarpım modülündeki mertebe, tek tek asal kuvvetlerdeki mertebelerin ekokudur:
$$\operatorname{ord}_m(10)=\mathrm{lcm}\!\left(\operatorname{ord}_{p_1^{e_1}}(10),\dots,\operatorname{ord}_{p_r^{e_r}}(10)\right).$$
Dolayısıyla temel alt problem, her \(p^e\) için \(\operatorname{ord}_{p^e}(10)\) değerini hızlı biçimde bulmaktır.
\(p\neq 2,5\) olan tek bir asal için Fermat'nın küçük teoremi
$$10^{p-1}\equiv 1 \pmod p$$
sonucunu verir; yani \(\operatorname{ord}_p(10)\), \(p-1\)'i böler. Bu nedenle uygulamalar önce \(p-1\)'den başlar, onu çarpanlarına ayırır ve mertebenin gereksiz bölenlerini test ederek indirger. Eğer \(d\) mevcut aday ve \(q\mid d\) ise şu test yapılır:
$$10^{d/q}\equiv 1 \pmod p.$$
Bu doğruysa aday \(d/q\)'ya düşürülebilir. Aynı işlem tekrarlandığında geriye tam mertebe kalır.
Asal modülündeki mertebe bulunduktan sonra daha yüksek kuvvetlere geçiş artımlı yapılır. Eğer
$$t=\operatorname{ord}_{p^{k-1}}(10)$$
ise bir sonraki mertebe
$$\operatorname{ord}_{p^k}(10)\in\{t,pt\}$$
kümesindedir. Hangisinin geçerli olduğunu anlamak için
$$10^t\equiv 1 \pmod{p^k}$$
kontrol edilir. Eşitlik sağlanıyorsa mertebe değişmez; sağlanmıyorsa \(p\) ile çarpılır. Uygulamanın asal kuvvet tablolarını oluştururken kullandığı kural tam olarak budur.
Üs \(e\ge 2\) tabloları yalnızca \(p\le \sqrt{N}\) için gerekir; çünkü \(p>\sqrt{N}\) olduğunda \(p^2>N\) olur ve böyle bir asal, \(m\le N\) olan çekirdekte ancak bir kez bulunabilir.
Uygun tek çekirdekler \(m=3,7,9\)'dur. \(m=3\) için \(3s\le 10\) sağlayan düzgün çarpanlar \(s=1,2\) olduğundan çokluk \(2\)'dir. \(\operatorname{ord}_3(10)=1\) olduğu için katkı \(2\) eder.
\(m=7\) için yalnızca \(s=1\) mümkündür ve \(\operatorname{ord}_7(10)=6\), dolayısıyla katkı \(6\)'dır.
\(m=9\) için yine yalnızca \(s=1\) vardır ve \(10\equiv 1 \pmod 9\) olduğundan \(\operatorname{ord}_9(10)=1\), yani katkı \(1\)'dir.
Böylece
$$S(10)=2+6+1=9$$
elde edilir; bu da \(1/3,1/4,\dots,1/10\) için doğrudan hesaplanan çevrim uzunluklarıyla tam uyumludur.
C++, Python ve Java uygulamaları aynı sayı kuramsal hattı izler. Önce yalnızca tek sayılar üzerinde çalışan bir en küçük asal bölen süzgeci kurulur; çünkü sadece \(10\) ile aralarında asal olan tek çekirdekler önemlidir. Ardından \(5\) dışındaki tüm tek asallar taranır, \(\operatorname{ord}_p(10)\) değerleri \(p-1\)'in bölenleri üzerinden küçültülerek bulunur ve üst kuvvetlerin sınırın altında kalabildiği durumlarda asal kuvvet tabloları hazırlanır.
Bunun yanında tüm \(2^a5^b\le N\) sayılarının sıralı listesi üretilir. Sonra \(5\) ile bölünmeyen her tek çekirdek \(m\) için \(\operatorname{ord}_m(10)\) asal kuvvet katkılarından ekok alınarak kurulur, geçerli düzgün çarpan sayısı bu listede ikili arama ile bulunur ve çarpım toplam değere eklenir. Python tarafı ağır hesabı derlenmiş hızlı çözücüye bırakırken, Java aynı hesabı doğrudan yeniden uygular.
Ön işleme süzgeci yaklaşık lineerdir; tipik olarak \(O(N\log\log N)\) zaman ve \(O(N)\) durum belleği ile ifade edilir, ancak yalnızca tek indisleri tutmak belleği yaklaşık yarıya indirir. \(2^a5^b\) listesinin boyutu ise yalnızca \(O((\log N)^2)\) olduğu için bu maliyet ihmal edilebilir.
Hazırlık tamamlandıktan sonra her uygun çekirdek süzgeç yardımıyla hızlıca çarpanlarına ayrılır ve az sayıda asal kuvvet mertebesinden birleştirilir. Toplam süreyi esas olarak süzgeç, asal mertebe ön hesabı ve \(5\) ile bölünmeyen tek çekirdekler üzerinde yapılan tek tarama belirler. Bu yöntem, her payda için dönem aramaya göre çok daha hızlıdır ve \(N=10^8\) için uygundur.
Sea \(L(n)\) la longitud del período decimal de \(1/n\). Hay que calcular
$$S(N)=\sum_{n=3}^{N} L(n)$$
para un límite \(N\) muy grande. Simular la división larga para cada denominador sería demasiado costoso, así que las implementaciones reorganizan la suma mediante orden multiplicativo y una agrupación por potencias de \(2\) y \(5\).
Cada denominador puede escribirse de forma única como
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
Los factores \(2\) y \(5\) solo producen el prefijo finito del decimal. La parte periódica depende únicamente del factor restante \(m\).
Si \(m=1\), entonces \(1/n\) es un decimal terminante y por tanto \(L(n)=0\). Si \(m>1\), la longitud del período viene dada por
$$L(n)=\operatorname{ord}_m(10),$$
donde \(\operatorname{ord}_m(10)\) es el menor entero positivo \(k\) tal que
$$10^k\equiv 1 \pmod m.$$
Esta es la caracterización clásica de los decimales periódicos en teoría de números.
Fijemos un entero impar \(m\) con \(5 \nmid m\). Todo denominador de la forma
$$n=m\,s,\qquad s=2^a5^b,$$
tiene exactamente la misma longitud de ciclo, \(\operatorname{ord}_m(10)\), porque multiplicar por potencias de \(2\) y \(5\) solo modifica la parte terminante.
Para un cociente \(Q\), definimos el número de multiplicadores suaves \(2\)-\(5\) por
$$C(Q)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2:2^a5^b\le Q\right\}.$$
Entonces todos los denominadores cuyo núcleo es \(m\) aportan en conjunto
$$\operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
Así se obtiene la identidad central usada por el algoritmo rápido:
$$\boxed{S(N)=\sum_{\substack{m\le N\\ 2\nmid m,\, 5\nmid m}} \operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).}$$
El caso \(m=1\) no necesita tratarse aparte porque su contribución es \(0\).
Escribamos el núcleo como
$$m=\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\neq 2,5.$$
Como las potencias primas son coprimas entre sí, el teorema chino del resto implica que el orden módulo \(m\) es el mínimo común múltiplo de los órdenes módulo cada potencia prima:
$$\operatorname{ord}_m(10)=\mathrm{lcm}\!\left(\operatorname{ord}_{p_1^{e_1}}(10),\dots,\operatorname{ord}_{p_r^{e_r}}(10)\right).$$
Por tanto, el subproblema esencial es calcular con rapidez \(\operatorname{ord}_{p^e}(10)\) para cada factor primo.
Si \(p\neq 2,5\) es primo impar, el pequeño teorema de Fermat da
$$10^{p-1}\equiv 1 \pmod p,$$
de modo que \(\operatorname{ord}_p(10)\) divide a \(p-1\). Las implementaciones parten entonces de \(p-1\), factorizan ese valor y van eliminando factores primos mientras las pruebas de congruencia sigan funcionando. Si \(d\) es el candidato actual y \(q\mid d\), se comprueba si
$$10^{d/q}\equiv 1 \pmod p.$$
Si la respuesta es afirmativa, el orden aún no era mínimo y el candidato puede reducirse a \(d/q\). Repetido de forma sistemática, este proceso produce el orden exacto.
Conocido el orden módulo \(p\), los órdenes módulo potencias mayores se obtienen paso a paso. Si
$$t=\operatorname{ord}_{p^{k-1}}(10),$$
entonces se cumple
$$\operatorname{ord}_{p^k}(10)\in\{t,pt\}.$$
Para decidir cuál es el valor correcto, se verifica si
$$10^t\equiv 1 \pmod{p^k}.$$
Si ya se cumple, el orden permanece igual; en caso contrario, se multiplica por \(p\). Esa es exactamente la regla de elevación que usan las implementaciones al construir las tablas de potencias primas.
Solo hacen falta tablas con \(e\ge 2\) para \(p\le \sqrt{N}\), porque si \(p>\sqrt{N}\), entonces \(p^2>N\) y ese primo solo puede aparecer con exponente \(1\) en cualquier núcleo \(m\le N\).
Los núcleos impares admisibles son \(m=3,7,9\). Para \(m=3\), los multiplicadores suaves con \(3s\le 10\) son \(s=1,2\), así que la multiplicidad es \(2\). Como \(\operatorname{ord}_3(10)=1\), la contribución es \(2\).
Para \(m=7\), solo es posible \(s=1\), y \(\operatorname{ord}_7(10)=6\), de modo que la contribución es \(6\).
Para \(m=9\), nuevamente solo vale \(s=1\), y como \(10\equiv 1 \pmod 9\), se tiene \(\operatorname{ord}_9(10)=1\), con contribución \(1\).
Por tanto,
$$S(10)=2+6+1=9,$$
en perfecto acuerdo con la suma directa de los períodos de \(1/3,1/4,\dots,1/10\).
Las implementaciones en C++, Python y Java siguen la misma tubería aritmética. Primero construyen una criba de menor factor primo solo sobre índices impares, porque solo importan los núcleos impares coprimos con \(10\). Después enumeran todos los primos impares distintos de \(5\), calculan \(\operatorname{ord}_p(10)\) reduciendo divisores de \(p-1\) y precalculan órdenes para potencias primas siempre que tales potencias puedan seguir apareciendo por debajo del límite.
En paralelo, la implementación genera la lista ordenada de todos los valores \(2^a5^b\le N\). Luego recorre cada núcleo impar \(m\) con \(5\nmid m\), recompone \(\operatorname{ord}_m(10)\) a partir de sus factores primos usando \(\mathrm{lcm}\), cuenta por búsqueda binaria cuántos multiplicadores suaves satisfacen \(ms\le N\) y suma el producto correspondiente. En la práctica, Python actúa como un lanzador ligero del solucionador compilado, mientras que Java reproduce directamente los mismos pasos de teoría de números.
La criba previa es casi lineal; normalmente se resume como \(O(N\log\log N)\) tiempo y \(O(N)\) memoria almacenada, aunque la representación solo con impares reduce de hecho el consumo. La lista de números \(2^a5^b\) tiene tamaño \(O((\log N)^2)\), así que resulta diminuta frente a la criba.
Tras esa preparación, cada núcleo admisible se factoriza rápidamente a partir de la criba y se combina desde muy pocos órdenes de potencias primas. El tiempo total queda dominado por la criba, la precalculación de órdenes primos y la pasada única sobre los núcleos impares no divisibles por \(5\). Eso hace viable el caso \(N=10^8\), mientras que la simulación ingenua de períodos sería demasiado lenta.
设 \(L(n)\) 表示 \(1/n\) 的十进制循环节长度。题目要求计算
$$S(N)=\sum_{n=3}^{N} L(n)$$
其中 \(N\) 很大。若对每个分母都直接做长除法，代价会非常高，因此实现采用乘法阶与按 \(2\) 和 \(5\) 的幂分组的方法来重写这整个求和。
每个分母都能唯一写成
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
\(2\) 和 \(5\) 的幂只会产生有限小数前缀，真正决定循环节长度的是剩下的因子 \(m\)。
若 \(m=1\)，则 \(1/n\) 是有限小数，所以 \(L(n)=0\)。若 \(m>1\)，则循环节长度满足
$$L(n)=\operatorname{ord}_m(10),$$
这里 \(\operatorname{ord}_m(10)\) 是满足
$$10^k\equiv 1 \pmod m$$
的最小正整数 \(k\)。这正是循环小数在数论中的标准刻画。
固定一个满足 \(5 \nmid m\) 的奇数 \(m\)。所有形如
$$n=m\,s,\qquad s=2^a5^b$$
的分母，都有完全相同的循环节长度 \(\operatorname{ord}_m(10)\)，因为乘上 \(2\) 与 \(5\) 的幂只会改变有限前缀，不会改变循环部分。
对给定的 \(Q\)，定义 \(2\)-\(5\)-平滑乘子的个数为
$$C(Q)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2:2^a5^b\le Q\right\}.$$
于是核心为 \(m\) 的所有分母合起来贡献
$$\operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
从而得到快速算法使用的核心恒等式：
$$\boxed{S(N)=\sum_{\substack{m\le N\\ 2\nmid m,\, 5\nmid m}} \operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).}$$
\(m=1\) 的情况可以直接忽略，因为它的循环节长度为 \(0\)。
将奇数核心写成
$$m=\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\neq 2,5.$$
由于这些素数幂两两互素，按中国剩余定理，模 \(m\) 的乘法阶等于各个素数幂模数下乘法阶的最小公倍数：
$$\operatorname{ord}_m(10)=\mathrm{lcm}\!\left(\operatorname{ord}_{p_1^{e_1}}(10),\dots,\operatorname{ord}_{p_r^{e_r}}(10)\right).$$
因此关键子问题变成如何快速求出每个 \(\operatorname{ord}_{p^e}(10)\)。
对奇素数 \(p\neq 5\)，费马小定理给出
$$10^{p-1}\equiv 1 \pmod p,$$
因此 \(\operatorname{ord}_p(10)\) 一定整除 \(p-1\)。实现中先从 \(p-1\) 出发，对它做因数分解，然后尝试不断去掉其中的素因子。若 \(d\) 是当前候选值且 \(q\mid d\)，就测试
$$10^{d/q}\equiv 1 \pmod p$$
是否成立。若成立，说明当前候选还不是最小值，可以缩小到 \(d/q\)。不断重复这一过程，就得到真正的模 \(p\) 乘法阶。
已知模 \(p\) 的阶以后，可以逐步求出更高素数幂的阶。若
$$t=\operatorname{ord}_{p^{k-1}}(10),$$
那么下一层满足
$$\operatorname{ord}_{p^k}(10)\in\{t,pt\}.$$
要区分这两种情况，只需检验
$$10^t\equiv 1 \pmod{p^k}$$
是否已经成立。若成立，则阶保持为 \(t\)；否则要再乘一个 \(p\)。这正是实现中构造素数幂阶表时所用的提升规则。
只有当 \(p\le \sqrt{N}\) 时，才需要为 \(e\ge 2\) 建表；因为若 \(p>\sqrt{N}\)，则 \(p^2>N\)，这样的素数在任何 \(m\le N\) 的核心中都只能出现一次。
可行的奇数核心是 \(m=3,7,9\)。对 \(m=3\)，满足 \(3s\le 10\) 的平滑乘子只有 \(s=1,2\)，所以重数是 \(2\)。又因为 \(\operatorname{ord}_3(10)=1\)，故贡献为 \(2\)。
对 \(m=7\)，只有 \(s=1\) 可用，而 \(\operatorname{ord}_7(10)=6\)，所以贡献为 \(6\)。
对 \(m=9\)，同样只有 \(s=1\)，并且 \(10\equiv 1 \pmod 9\)，因此 \(\operatorname{ord}_9(10)=1\)，贡献为 \(1\)。
于是
$$S(10)=2+6+1=9,$$
这与直接把 \(1/3,1/4,\dots,1/10\) 的循环节长度相加完全一致。
C++、Python 和 Java 实现遵循同一条数论计算流程。首先构建只覆盖奇数下标的最小素因子筛，因为真正需要处理的只有与 \(10\) 互素的奇数核心。然后枚举所有不等于 \(5\) 的奇素数，通过不断约简 \(p-1\) 的因子来求出 \(\operatorname{ord}_p(10)\)，并在更高幂仍可能不超过上界时预先建立相应的素数幂阶表。
与此同时，实现还会生成所有 \(2^a5^b\le N\) 的有序列表。接着扫描每个满足 \(5\nmid m\) 的奇数核心 \(m\)，把各个素数幂的贡献用 \(\mathrm{lcm}\) 合成为 \(\operatorname{ord}_m(10)\)，再在平滑数列表中通过二分查找统计满足 \(ms\le N\) 的乘子个数，并将对应乘积加入总和。Python 版本本质上是已编译快速求解器的薄封装，而 Java 版本则直接复现相同的数论步骤。
预处理筛法近似线性，通常记为 \(O(N\log\log N)\) 时间和 \(O(N)\) 存储状态，而只保存奇数位置会把常数因子显著压低。所有 \(2^a5^b\) 的列表大小只有 \(O((\log N)^2)\)，与筛法相比可以忽略。
在预处理完成后，每个可行核心都能借助筛表快速分解，并由少量素数幂阶合成出最终结果。总体时间主要消耗在筛法、素数阶预计算，以及对所有不被 \(5\) 整除的奇数核心做一次扫描上。与逐个分母做长除法相比，这个方法快得多，并且足以处理 \(N=10^8\) 的规模。
Пусть \(L(n)\) обозначает длину периода десятичной записи числа \(1/n\). Требуется вычислить
$$S(N)=\sum_{n=3}^{N} L(n)$$
для очень большого предела \(N\). Прямое моделирование деления столбиком для каждого знаменателя слишком дорого, поэтому реализации перестраивают сумму через мультипликативный порядок и группировку по степеням \(2\) и \(5\).
Любой знаменатель единственным образом представляется в виде
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
Множители \(2\) и \(5\) отвечают только за конечный префикс десятичной дроби. Длина периода определяется исключительно остаточным множителем \(m\).
Если \(m=1\), то \(1/n\) является конечной десятичной дробью, следовательно \(L(n)=0\). Если \(m>1\), то длина периода равна
$$L(n)=\operatorname{ord}_m(10),$$
где \(\operatorname{ord}_m(10)\) есть наименьшее положительное \(k\), для которого
$$10^k\equiv 1 \pmod m.$$
Именно так периодические десятичные дроби описываются в терминах теории чисел.
Зафиксируем нечётное число \(m\), не делящееся на \(5\). Тогда любой знаменатель вида
$$n=m\,s,\qquad s=2^a5^b,$$
имеет ту же длину периода \(\operatorname{ord}_m(10)\), потому что степени \(2\) и \(5\) меняют только конечную часть записи.
Для заданного \(Q\) введём количество \(2\)-\(5\)-гладких множителей:
$$C(Q)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2:2^a5^b\le Q\right\}.$$
Тогда все знаменатели с ядром \(m\) дают суммарный вклад
$$\operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
Отсюда получается основная формула быстрого решения:
$$\boxed{S(N)=\sum_{\substack{m\le N\\ 2\nmid m,\, 5\nmid m}} \operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).}$$
Случай \(m=1\) можно не учитывать, потому что там период равен нулю.
Представим ядро в виде
$$m=\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\neq 2,5.$$
Так как эти простые степени попарно взаимно просты, китайская теорема об остатках даёт
$$\operatorname{ord}_m(10)=\mathrm{lcm}\!\left(\operatorname{ord}_{p_1^{e_1}}(10),\dots,\operatorname{ord}_{p_r^{e_r}}(10)\right).$$
Следовательно, задача сводится к быстрому вычислению \(\operatorname{ord}_{p^e}(10)\) для каждой простой степени.
Для нечётного простого \(p\neq 5\) малая теорема Ферма утверждает, что
$$10^{p-1}\equiv 1 \pmod p,$$
поэтому \(\operatorname{ord}_p(10)\) делит \(p-1\). Реализации начинают с числа \(p-1\), раскладывают его на множители и последовательно пробуют убрать из кандидата лишние простые множители. Если \(d\) — текущий кандидат и \(q\mid d\), проверяется условие
$$10^{d/q}\equiv 1 \pmod p.$$
Если оно выполняется, кандидат можно уменьшить до \(d/q\). Повторяя этот процесс, получаем точный порядок по модулю \(p\).
Зная порядок по модулю \(p\), можно последовательно перейти к более высоким степеням. Если
$$t=\operatorname{ord}_{p^{k-1}}(10),$$
то следующий порядок удовлетворяет
$$\operatorname{ord}_{p^k}(10)\in\{t,pt\}.$$
Чтобы понять, какой из двух вариантов верен, проверяют, выполняется ли
$$10^t\equiv 1 \pmod{p^k}.$$
Если да, порядок не меняется; если нет, он умножается на \(p\). Именно это правило подъёма используется при построении таблиц для простых степеней.
Таблицы для показателей \(e\ge 2\) нужны только при \(p\le \sqrt{N}\), поскольку при \(p>\sqrt{N}\) уже \(p^2>N\), и такой простой делитель может входить в ядро \(m\le N\) только в первой степени.
Допустимые нечётные ядра: \(m=3,7,9\). Для \(m=3\) гладкие множители с условием \(3s\le 10\) равны \(s=1,2\), значит кратность равна \(2\). Поскольку \(\operatorname{ord}_3(10)=1\), вклад равен \(2\).
Для \(m=7\) возможен только \(s=1\), а \(\operatorname{ord}_7(10)=6\), поэтому вклад равен \(6\).
Для \(m=9\) снова допустим только \(s=1\), и так как \(10\equiv 1 \pmod 9\), имеем \(\operatorname{ord}_9(10)=1\), то есть вклад равен \(1\).
Итак,
$$S(10)=2+6+1=9,$$
что полностью совпадает с прямой суммой периодов для \(1/3,1/4,\dots,1/10\).
Реализации на C++, Python и Java используют одну и ту же арифметическую схему. Сначала строится решето наименьшего простого делителя только по нечётным индексам, поскольку важны лишь нечётные ядра, взаимно простые с \(10\). Затем перебираются все нечётные простые, кроме \(5\), для каждого из них вычисляется \(\operatorname{ord}_p(10)\) через сокращение делителей числа \(p-1\), и заранее подготавливаются порядки для степеней простых там, где более высокие степени ещё могут появляться ниже границы.
Одновременно реализация строит отсортированный список всех чисел вида \(2^a5^b\le N\). После этого она проходит по каждому нечётному ядру \(m\), не делящемуся на \(5\), восстанавливает \(\operatorname{ord}_m(10)\) из вкладов простых степеней через \(\mathrm{lcm}\), двоичным поиском находит число допустимых гладких множителей и добавляет соответствующее произведение к ответу. Версия на Python является тонкой обёрткой над скомпилированным быстрым решателем, а Java воспроизводит те же шаги напрямую.
Предварительное решето почти линейно; обычно его оценивают как \(O(N\log\log N)\) по времени и \(O(N)\) по памяти, хотя хранение только нечётных позиций заметно уменьшает константу. Список чисел \(2^a5^b\) имеет размер лишь \(O((\log N)^2)\), поэтому по сравнению с решетом он очень мал.
После предобработки каждое допустимое ядро быстро раскладывается с помощью решета и собирается из малого числа порядков простых степеней. Основная стоимость приходится на решето, предварительное вычисление простых порядков и единственный проход по нечётным ядрам, не кратным \(5\). Благодаря этому метод подходит для \(N=10^8\), тогда как наивный поиск периода для каждого знаменателя был бы слишком медленным.
لتكن \(L(n)\) هي طول الجزء الدوري في التمثيل العشري للكسر \(1/n\). المطلوب هو حساب
$$S(N)=\sum_{n=3}^{N} L(n)$$
عند حد كبير جدًا \(N\). تنفيذ القسمة الطويلة لكل مقام على حدة سيكون بطيئًا للغاية، لذلك تعيد التطبيقات ترتيب المجموع باستخدام الرتبة الضربية وتجميع المقامات بحسب قوى \(2\) و\(5\).
يمكن كتابة كل مقام بصورة وحيدة على الشكل
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
العاملان \(2\) و\(5\) لا يصنعان إلا المقدمة العشرية المنتهية، أما طول الدورة نفسها فيعتمد فقط على العامل المتبقي \(m\).
إذا كان \(m=1\) فإن \(1/n\) كسر عشري منتهٍ، وبالتالي \(L(n)=0\). وإذا كان \(m>1\) فإن طول الدورة يساوي
$$L(n)=\operatorname{ord}_m(10),$$
حيث \(\operatorname{ord}_m(10)\) هو أصغر عدد صحيح موجب \(k\) يحقق
$$10^k\equiv 1 \pmod m.$$
وهذا هو الوصف القياسي للكسور العشرية الدورية في نظرية الأعداد.
لنثبت عددًا فرديًا \(m\) بحيث \(5 \nmid m\). كل مقام من الصورة
$$n=m\,s,\qquad s=2^a5^b$$
يمتلك طول الدورة نفسه \(\operatorname{ord}_m(10)\)، لأن الضرب في قوى \(2\) و\(5\) يغيّر المقدمة المنتهية فقط.
ولأجل قيمة \(Q\) نعرّف عدد المضاعفات الملساء بالنسبة إلى \(2\) و\(5\) كما يلي:
$$C(Q)=\#\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2:2^a5^b\le Q\right\}.$$
وعندئذ يكون إسهام جميع المقامات ذات النواة \(m\) مساويًا لـ
$$\operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).$$
ومن هنا نحصل على الهوية الأساسية التي يعتمدها الحل السريع:
$$\boxed{S(N)=\sum_{\substack{m\le N\\ 2\nmid m,\, 5\nmid m}} \operatorname{ord}_m(10)\,C\!\left(\left\lfloor\frac{N}{m}\right\rfloor\right).}$$
أما الحالة \(m=1\) فلا حاجة إلى إدخالها في الجمع، لأن طول الدورة فيها يساوي الصفر.
نكتب النواة على الصورة
$$m=\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\neq 2,5.$$
وبما أن هذه القوى الأولية متباينة أوليًا فيما بينها، فإن مبرهنة البواقي الصينية تعطي أن الرتبة modulo \(m\) هي المضاعف المشترك الأصغر للرتب modulo كل قوة أولية:
$$\operatorname{ord}_m(10)=\mathrm{lcm}\!\left(\operatorname{ord}_{p_1^{e_1}}(10),\dots,\operatorname{ord}_{p_r^{e_r}}(10)\right).$$
إذن المسألة الجوهرية تصبح حساب \(\operatorname{ord}_{p^e}(10)\) بسرعة لكل عامل أولي.
إذا كان \(p\neq 2,5\) عددًا أوليًا فرديًا، فإن مبرهنة فيرما الصغرى تعطينا
$$10^{p-1}\equiv 1 \pmod p,$$
ومن ثم فإن \(\operatorname{ord}_p(10)\) يقسم العدد \(p-1\). لذلك تبدأ التطبيقات من \(p-1\)، ثم تفككه إلى عوامله الأولية، وتحاول حذف العوامل غير الضرورية ما دامت اختبارات التطابق تنجح. فإذا كان \(d\) هو المرشح الحالي و\(q\mid d\)، نختبر ما إذا كان
$$10^{d/q}\equiv 1 \pmod p.$$
إذا تحقق ذلك، فإن المرشح لم يكن أصغر رتبة ممكنة بعد، ويمكن تقليصه إلى \(d/q\). وتكرار هذه العملية يعطي الرتبة الدقيقة modulo \(p\).
بعد معرفة الرتبة modulo \(p\)، يمكن الانتقال إلى القوى الأعلى تدريجيًا. إذا كان
$$t=\operatorname{ord}_{p^{k-1}}(10),$$
فإن الرتبة التالية تحقق
$$\operatorname{ord}_{p^k}(10)\in\{t,pt\}.$$
ولتمييز الحالتين نتحقق مما إذا كان
$$10^t\equiv 1 \pmod{p^k}$$
صحيحًا بالفعل. إذا كان صحيحًا تبقى الرتبة كما هي، وإلا فإنها تُضرب في \(p\). وهذه هي قاعدة الرفع التي تعتمدها التطبيقات عند بناء رتب القوى الأولية.
ولا نحتاج إلى جداول للأسس \(e\ge 2\) إلا عندما يكون \(p\le \sqrt{N}\)، لأن \(p>\sqrt{N}\) يعني \(p^2>N\)، وعندها لا يمكن لهذا العدد الأولي أن يظهر إلا بأس \(1\) داخل أي نواة \(m\le N\).
النوى الفردية المسموح بها هي \(m=3,7,9\). بالنسبة إلى \(m=3\)، فإن المضاعفات الملساء التي تحقق \(3s\le 10\) هي \(s=1,2\)، ولذلك تكون المضاعفية \(2\). وبما أن \(\operatorname{ord}_3(10)=1\)، فالإسهام يساوي \(2\).
وبالنسبة إلى \(m=7\)، لا يوجد إلا \(s=1\)، ومع \(\operatorname{ord}_7(10)=6\) يكون الإسهام \(6\).
أما \(m=9\)، فلدينا أيضًا \(s=1\) فقط، ولأن \(10\equiv 1 \pmod 9\) فإن \(\operatorname{ord}_9(10)=1\)، ومن ثم يكون الإسهام \(1\).
إذن
$$S(10)=2+6+1=9,$$
وهو ما يطابق تمامًا مجموع أطوال الدورات للكسر \(1/3,1/4,\dots,1/10\).
تتبع تطبيقات C++ وPython وJava السلسلة الحسابية نفسها. فهي تبدأ ببناء غربال لأصغر عامل أولي على الفهارس الفردية فقط، لأن المهم هو النوى الفردية الموافقة نسبيًا للعدد \(10\). بعد ذلك تُحصى جميع الأعداد الأولية الفردية عدا \(5\)، وتُحسب \(\operatorname{ord}_p(10)\) عبر تقليص قواسم \(p-1\)، كما تُجهز رتب القوى الأولية مسبقًا كلما كان من الممكن أن تظهر قوى أعلى تحت الحد المطلوب.
وفي الوقت نفسه يولد التنفيذ القائمة المرتبة لكل القيم \(2^a5^b\le N\). ثم يمر على كل نواة فردية \(m\) لا تقبل القسمة على \(5\)، ويعيد تركيب \(\operatorname{ord}_m(10)\) من عواملها الأولية باستخدام \(\mathrm{lcm}\)، ويحسب بعد ذلك بعدد من عمليات البحث الثنائي كم عدد المضاعفات الملساء التي تحقق \(ms\le N\)، ثم يضيف حاصل الضرب إلى المجموع الكلي. نسخة Python عبارة عن غلاف خفيف فوق الحل السريع المترجم، أما Java فتعيد تنفيذ الخطوات العددية نفسها مباشرة.
الغربال التمهيدي شبه خطي، ويُختصر عادة في \(O(N\log\log N)\) زمنًا و\(O(N)\) ذاكرةً مخزنةً، مع ملاحظة أن تخزين الفهارس الفردية فقط يقلل عامل الثابت بشكل ملحوظ. أما قائمة الأعداد \(2^a5^b\) فحجمها لا يتجاوز \(O((\log N)^2)\)، ولذلك فهي صغيرة جدًا مقارنة بالغربال.
بعد مرحلة التهيئة، يمكن تحليل كل نواة مسموح بها بسرعة بواسطة الغربال، ثم تركيب الرتبة من عدد صغير من رتب القوى الأولية. ولهذا تتركز الكلفة الإجمالية في بناء الغربال، والتمهيد لرتب الأعداد الأولية، والمرور مرة واحدة على جميع النوى الفردية غير القابلة للقسمة على \(5\). هذه البنية تجعل الحساب عمليًا عند \(N=10^8\)، بينما يكون الأسلوب الساذج القائم على القسمة الطويلة بطيئًا جدًا.