The problem asks for the denominator \(d \lt 1000\) for which the decimal expansion of \(1/d\) has the longest recurring cycle. Some reciprocals terminate, such as \(1/8 = 0.125\); others have a repeating tail, such as \(1/7 = 0.\overline{142857}\).
The key point is that decimal expansion is controlled entirely by long-division remainders. Once the same remainder appears twice, the subsequent digits must repeat as well. Therefore the real mathematical object is not the digit string itself, but the finite remainder process generated by dividing \(1\) by \(d\).
Fix a denominator \(d \ge 2\). When we perform long division for \(1/d\), each step is determined by the current remainder.
Let \(r_0 = 1 \bmod d\). At step \(k\), write
$$10r_k = q_k d + r_{k+1}, \qquad 0 \le q_k \le 9,\qquad 0 \le r_{k+1} \lt d.$$
Here \(q_k\) is the next decimal digit of \(1/d\), and \(r_{k+1}\) is the new remainder. Reducing the same identity modulo \(d\) gives the recurrence
$$r_{k+1} \equiv 10r_k \pmod{d}.$$
So the decimal digits are produced by a deterministic map on the finite set of remainders \(\{0,1,\dots,d-1\}\). The current remainder completely determines both the next digit and the next remainder.
If some step reaches remainder \(0\), then all later remainders stay \(0\), so the decimal terminates. Otherwise every remainder lies in \(\{1,2,\dots,d-1\}\), which has only \(d-1\) possibilities. By the pigeonhole principle, some remainder must repeat after at most \(d\) steps.
Suppose \(r_i = r_j\) with \(i \lt j\). Because the transition rule is deterministic, the entire future from step \(i\) onward is identical to the future from step \(j\) onward. Therefore the digits from position \(i\) onward repeat with period \(j-i\). This is exactly why storing the first position of each remainder is enough to recover the cycle length.
In particular, for every denominator \(d\), the recurring cycle length is at most \(d-1\).
Write
$$d = 2^a 5^b m,\qquad \gcd(m,10)=1.$$
The factors \(2\) and \(5\) are responsible only for a finite prefix, because powers of \(10\) contain exactly those prime factors. The genuinely recurring part comes from the reduced denominator \(m\).
If \(m=1\), then \(1/d\) terminates. If \(m \gt 1\), the recurring cycle length is the smallest positive integer \(t\) such that
$$10^t \equiv 1 \pmod{m},$$
which is the multiplicative order \(\operatorname{ord}_m(10)\). This gives a clean number-theoretic interpretation of the remainder process, even though the implementations do not compute the order by factoring \(d\).
For \(d=7\), the remainder chain is
$$1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1.$$
The corresponding digits are obtained from the equations
$$10 = 1\cdot 7 + 3,\quad 30 = 4\cdot 7 + 2,\quad 20 = 2\cdot 7 + 6,$$
$$60 = 8\cdot 7 + 4,\quad 40 = 5\cdot 7 + 5,\quad 50 = 7\cdot 7 + 1.$$
Thus
$$\frac{1}{7} = 0.\overline{142857},$$
and the first repeated remainder is \(1\), reappearing after 6 steps, so the cycle length is 6.
For \(d=12\), we have
$$10 = 0\cdot 12 + 10,\qquad 100 = 8\cdot 12 + 4,\qquad 40 = 3\cdot 12 + 4.$$
So the digits start as \(0,8,3,3,3,\dots\), which means
$$\frac{1}{12} = 0.08\overline{3}.$$
The remainder \(4\) repeats immediately, so the recurring cycle has length 1, while the initial \(08\) is a non-repeating prefix caused by the factor \(4 = 2^2\) inside the denominator.
The code checks every \(d\) from \(2\) to \(999\), computes its cycle length, and remembers the best one. Mathematically one can prove extra facts, such as the order dividing \(\varphi(m)\), but for this input size none of that is necessary. The direct remainder simulation already mirrors the long-division process exactly and is fast enough.
The C++, Python, and Java implementations all follow the same structure. They parse an optional limit, run a pair of small checkpoints, and then scan all denominators below the limit.
For a fixed \(d\), the implementation allocates an array or list of length \(d\) and fills it with \(-1\). Entry \(r\) stores the first digit position at which remainder \(r\) appeared. The process starts from remainder \(1 \bmod d\) and a position counter equal to 0.
While the current remainder is nonzero and has not been seen before, the current position is stored, the remainder is updated to \((10r) \bmod d\), and the position counter is incremented. If the loop ends because the remainder became 0, the decimal terminates and the cycle length is 0. If the loop ends because a remainder was seen earlier, the cycle length is
$$\text{current position} - \text{first position of that remainder}.$$
After computing the cycle length for one denominator, the implementation compares it with the best length found so far. If the new cycle is strictly longer, the current denominator becomes the new champion. Because the comparison is strict, ties leave the earlier denominator in place.
Before solving the full problem, the implementations verify two facts: the recurring cycle length of \(1/7\) is 6, and among denominators below 10 the best answer is 7. These checks confirm that both the remainder simulation and the outer scan behave as intended.
For a fixed denominator \(d\), the loop can visit each remainder at most once before either hitting 0 or repeating, so the work is \(O(d)\). Summing over all \(d = 2,3,\dots,L-1\) gives
$$\sum_{d=2}^{L-1} O(d) = O(L^2).$$
For \(L=1000\), this is only on the order of half a million remainder updates, which is tiny. The peak extra memory is \(O(L)\), because the largest remainder-tracking array has size at most \(L-1\).
Gesucht ist der Nenner \(d \lt 1000\), für den die Dezimalentwicklung von \(1/d\) den längsten periodischen Teil besitzt. Manche Kehrwerte enden, etwa \(1/8 = 0{,}125\); andere besitzen eine wiederkehrende Periode, etwa \(1/7 = 0.\overline{142857}\).
Entscheidend ist, dass die Dezimalentwicklung vollständig von den Resten der schriftlichen Division gesteuert wird. Sobald derselbe Rest ein zweites Mal auftaucht, müssen sich auch alle folgenden Ziffern wiederholen. Das eigentliche mathematische Objekt ist also nicht die Ziffernfolge selbst, sondern der endliche Restprozess beim Dividieren von \(1\) durch \(d\).
Fixiere einen Nenner \(d \ge 2\). Bei der schriftlichen Division von \(1/d\) wird jeder Schritt durch den aktuellen Rest bestimmt.
Setze \(r_0 = 1 \bmod d\). In Schritt \(k\) gilt
$$10r_k = q_k d + r_{k+1}, \qquad 0 \le q_k \le 9,\qquad 0 \le r_{k+1} \lt d.$$
Dabei ist \(q_k\) die nächste Dezimalziffer von \(1/d\), und \(r_{k+1}\) ist der neue Rest. Modulo \(d\) reduziert sich dieselbe Gleichung zu
$$r_{k+1} \equiv 10r_k \pmod{d}.$$
Damit entsteht die Dezimalentwicklung aus einer deterministischen Abbildung auf der endlichen Restmenge \(\{0,1,\dots,d-1\}\). Der aktuelle Rest bestimmt sowohl die nächste Ziffer als auch den nächsten Rest vollständig.
Wenn irgendwann der Rest \(0\) erreicht wird, bleiben alle späteren Reste gleich \(0\), und die Dezimalentwicklung endet. Andernfalls liegen alle Reste in \(\{1,2,\dots,d-1\}\), also gibt es nur \(d-1\) Möglichkeiten. Nach dem Schubfachprinzip muss daher spätestens nach \(d\) Schritten ein Rest erneut auftreten.
Angenommen, \(r_i = r_j\) mit \(i \lt j\). Weil die Übergangsregel deterministisch ist, stimmt die gesamte Zukunft ab Schritt \(i\) exakt mit der Zukunft ab Schritt \(j\) überein. Deshalb wiederholen sich die Ziffern ab Position \(i\) mit Periode \(j-i\). Genau deshalb reicht es im Algorithmus aus, die erste Position jedes Rests zu speichern.
Insbesondere ist die Periodenlänge für jeden Nenner \(d\) höchstens \(d-1\).
Schreibe
$$d = 2^a 5^b m,\qquad \gcd(m,10)=1.$$
Die Faktoren \(2\) und \(5\) sind nur für einen endlichen Anfangsteil verantwortlich, weil Potenzen von \(10\) genau diese Primfaktoren enthalten. Der wirklich periodische Teil kommt vom reduzierten Nenner \(m\).
Falls \(m=1\), endet die Dezimaldarstellung. Falls \(m \gt 1\), ist die Periodenlänge die kleinste positive Zahl \(t\) mit
$$10^t \equiv 1 \pmod{m},$$
also die multiplikative Ordnung \(\operatorname{ord}_m(10)\). Diese Interpretation ist mathematisch sehr sauber, auch wenn der Code die Ordnung nicht über Faktorisierung bestimmt.
Für \(d=7\) lautet die Restfolge
$$1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1.$$
Die zugehörigen Ziffern entstehen aus
$$10 = 1\cdot 7 + 3,\quad 30 = 4\cdot 7 + 2,\quad 20 = 2\cdot 7 + 6,$$
$$60 = 8\cdot 7 + 4,\quad 40 = 5\cdot 7 + 5,\quad 50 = 7\cdot 7 + 1.$$
Daher gilt
$$\frac{1}{7} = 0.\overline{142857},$$
und weil der Rest \(1\) nach 6 Schritten wiederkehrt, ist die Periodenlänge 6.
Für \(d=12\) erhält man
$$10 = 0\cdot 12 + 10,\qquad 100 = 8\cdot 12 + 4,\qquad 40 = 3\cdot 12 + 4.$$
Die Ziffern beginnen also mit \(0,8,3,3,3,\dots\), also
$$\frac{1}{12} = 0.08\overline{3}.$$
Der Rest \(4\) wiederholt sich sofort, daher hat der periodische Teil Länge 1. Die anfänglichen Ziffern \(08\) bilden einen nichtperiodischen Präfix, der vom Faktor \(4 = 2^2\) im Nenner stammt.
Der Code prüft alle Nenner \(d\) von \(2\) bis \(999\), berechnet jeweils die Periodenlänge und merkt sich den besten Kandidaten. Man kann zwar weitere Zahlentheorie verwenden, etwa dass die Ordnung \(\varphi(m)\) teilt, aber für diese Eingabegröße ist das nicht nötig. Die direkte Restsimulation bildet die schriftliche Division exakt nach und ist bereits schnell genug.
Die C++-, Python- und Java-Implementierungen haben denselben Aufbau. Sie lesen optional eine Grenze ein, führen zwei kleine Prüfschritte aus und durchsuchen dann alle Nenner unterhalb dieser Grenze.
Für einen festen Nenner \(d\) legt die Implementierung ein Array oder eine Liste der Länge \(d\) an und initialisiert alle Einträge mit \(-1\). Der Eintrag zu einem Rest \(r\) speichert die erste Ziffernposition, an der dieser Rest auftrat. Der Startzustand ist Rest \(1 \bmod d\) und Positionszähler 0.
Solange der aktuelle Rest ungleich 0 ist und noch nicht gesehen wurde, wird die aktuelle Position gespeichert, der Rest zu \((10r) \bmod d\) aktualisiert und der Positionszähler erhöht. Endet die Schleife wegen Rest 0, ist die Dezimalentwicklung endlich und die Periodenlänge 0. Endet sie wegen eines schon bekannten Rests, dann ist die Periodenlänge
$$\text{aktuelle Position} - \text{erste Position dieses Rests}.$$
Nach jeder Einzelberechnung vergleicht die Implementierung die neue Periodenlänge mit dem bisher besten Wert. Nur wenn die neue Periode strikt länger ist, wird der aktuelle Nenner zum neuen Spitzenkandidaten. Bei Gleichstand bleibt also der zuerst gefundene, kleinere Nenner erhalten.
Vor der eigentlichen Lösung werden zwei bekannte Fakten überprüft: Die Periode von \(1/7\) hat Länge 6, und unter allen Nennern kleiner als 10 ist 7 der beste Kandidat. Damit wird kontrolliert, dass sowohl die Restsimulation als auch die äußere Suche korrekt arbeiten.
Für einen festen Nenner \(d\) kann die Schleife jeden Rest höchstens einmal besuchen, bevor entweder 0 erreicht oder ein Rest wiederholt wird. Der Aufwand ist also \(O(d)\). Über alle \(d = 2,3,\dots,L-1\) summiert ergibt das
$$\sum_{d=2}^{L-1} O(d) = O(L^2).$$
Für \(L=1000\) liegt das nur in der Größenordnung von einer halben Million Restaktualisierungen. Der maximale zusätzliche Speicher ist \(O(L)\), weil das größte Restarray höchstens Größe \(L-1\) hat.
Bu problem, \(d \lt 1000\) koşulunu sağlayan paydalar arasında \(1/d\) ondalık açılımında en uzun tekrar eden döngüyü üreten değeri ister. Bazı kesirler sonlanır; örneğin \(1/8 = 0.125\). Bazıları ise sonsuza kadar tekrar eden bir parçaya sahiptir; örneğin \(1/7 = 0.\overline{142857}\).
Asıl fikir şudur: ondalık açılımı belirleyen şey rakamların kendisi değil, uzun bölme sırasında oluşan kalandır. Aynı kalan ikinci kez görüldüğünde bundan sonraki tüm rakamlar da aynı biçimde tekrar etmek zorundadır. Dolayısıyla problem, sonlu bir kalan sürecinin periyot uzunluğunu incelemeye dönüşür.
Sabit bir \(d \ge 2\) paydası seçelim. \(1/d\) için yapılan uzun bölmenin her adımı yalnızca mevcut kalana bağlıdır.
\(r_0 = 1 \bmod d\) olsun. \(k\). adımda
$$10r_k = q_k d + r_{k+1}, \qquad 0 \le q_k \le 9,\qquad 0 \le r_{k+1} \lt d$$
yazılır. Burada \(q_k\), \(1/d\)'nin bir sonraki ondalık basamağıdır; \(r_{k+1}\) ise yeni kalandır. Aynı eşitliği \(d\) modunda düşünürsek
$$r_{k+1} \equiv 10r_k \pmod{d}$$
elde edilir. Yani ondalık açılım, \(\{0,1,\dots,d-1\}\) kümesi üzerindeki deterministik bir geçiş kuralından doğar. Mevcut kalan hem bir sonraki rakamı hem de bir sonraki kalanı tek başına belirler.
Eğer bir adımda kalan \(0\) olursa, daha sonraki bütün kalanlar da \(0\) kalır ve ondalık açılım sonlanır. Aksi halde tüm kalanlar \(\{1,2,\dots,d-1\}\) kümesindedir; yani en fazla \(d-1\) farklı sıfır olmayan kalan vardır. Güvercin yuvası ilkesine göre bir kalan en geç \(d\) adım içinde yeniden görünmek zorundadır.
\(r_i = r_j\) ve \(i \lt j\) olsun. Geçiş kuralı deterministik olduğu için \(i\). adımdan sonraki gelecek ile \(j\). adımdan sonraki gelecek tamamen aynıdır. Bu yüzden \(i\). basamaktan itibaren rakamlar \(j-i\) periyodu ile tekrar eder. Kodda ilk görülme konumunun saklanmasının yeterli olmasının sebebi tam olarak budur.
Böylece her \(d\) için tekrar eden kısmın uzunluğu en fazla \(d-1\) olur.
Paydayı
$$d = 2^a 5^b m,\qquad \gcd(m,10)=1$$
şeklinde yazalım. \(2\) ve \(5\) çarpanları yalnızca sonlu bir ön ek oluşturur; çünkü \(10\)'un kuvvetleri tam olarak bu asal çarpanları taşır. Gerçek tekrar eden kısım ise indirgenmiş payda \(m\)'den gelir.
Eğer \(m=1\) ise ondalık açılım sonlanır. Eğer \(m \gt 1\) ise döngü uzunluğu,
$$10^t \equiv 1 \pmod{m}$$
eşitliğini sağlayan en küçük pozitif \(t\)'dir; yani \(\operatorname{ord}_m(10)\) değeridir. Uygulamalar bu mertebeyi asal çarpanlara ayırarak hesaplamaz, ama bu yorum kalan sürecinin neyi ölçtüğünü açıkça gösterir.
\(d=7\) için kalan zinciri
$$1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1$$
şeklindedir. Rakamlar şu eşitliklerden gelir:
$$10 = 1\cdot 7 + 3,\quad 30 = 4\cdot 7 + 2,\quad 20 = 2\cdot 7 + 6,$$
$$60 = 8\cdot 7 + 4,\quad 40 = 5\cdot 7 + 5,\quad 50 = 7\cdot 7 + 1.$$
Dolayısıyla
$$\frac{1}{7} = 0.\overline{142857}$$
olur. Kalan \(1\), 6 adım sonra yeniden görüldüğü için döngü uzunluğu 6'dır.
\(d=12\) için
$$10 = 0\cdot 12 + 10,\qquad 100 = 8\cdot 12 + 4,\qquad 40 = 3\cdot 12 + 4$$
elde edilir. Basamaklar \(0,8,3,3,3,\dots\) diye başlar; yani
$$\frac{1}{12} = 0.08\overline{3}.$$
Burada kalan \(4\) hemen tekrar eder; bu yüzden periyot uzunluğu 1'dir. Başlangıçtaki \(08\) ise paydadaki \(4 = 2^2\) çarpanından gelen tekrar etmeyen ön ektir.
Kod, \(2\)'den \(999\)'a kadar bütün paydaları tek tek dener, her biri için döngü uzunluğunu bulur ve en iyisini saklar. Teorik olarak mertebenin \(\varphi(m)\)'yi böldüğü gibi ek bilgiler kullanılabilir; fakat bu girdi boyutunda buna gerek yoktur. Doğrudan kalan simülasyonu, uzun bölmenin matematiğini bire bir izler ve zaten yeterince hızlıdır.
C++, Python ve Java uygulamalarının yapısı aynıdır. İsteğe bağlı sınır değeri okunur, iki küçük kontrol çalıştırılır ve ardından sınırın altındaki tüm paydalar taranır.
Sabit bir \(d\) için uygulama, uzunluğu \(d\) olan bir dizi oluşturur ve tüm girişleri \(-1\) yapar. Her kalan \(r\) için bu dizide, o kalanın ilk kez görüldüğü basamak konumu tutulur. Süreç \(1 \bmod d\) kalanı ve 0 konum sayacı ile başlar.
Mevcut kalan sıfır değilse ve daha önce görülmemişse, önce o anki konum kaydedilir; sonra kalan \((10r) \bmod d\) olarak güncellenir ve sayaç bir artırılır. Döngü kalan 0 olduğu için biterse sonuç 0'dır. Daha önce görülmüş bir kalan nedeniyle biterse döngü uzunluğu
$$\text{şimdiki konum} - \text{bu kalanın ilk görüldüğü konum}$$
olarak alınır.
Her payda için bulunan sonuç, o ana kadarki en iyi döngü uzunluğu ile karşılaştırılır. Yalnızca yeni değer daha büyükse şampiyon payda güncellenir. Karşılaştırma sıkı olduğu için eşitlik durumunda daha önce bulunan, yani daha küçük payda korunur.
Uygulamalar tam aramadan önce iki bilinen durumu doğrular: \(1/7\)'nin döngü uzunluğu 6'dır ve 10'dan küçük paydalar arasında en iyi cevap 7'dir. Böylece hem kalan simülasyonu hem de dış döngü hızlıca kontrol edilmiş olur.
Sabit bir \(d\) için döngü, her kalanı en fazla bir kez ziyaret eder; ardından ya 0'a ulaşır ya da bir kalanı tekrar görür. Bu nedenle maliyet \(O(d)\)'dir. Bütün \(d = 2,3,\dots,L-1\) için toplam çalışma
$$\sum_{d=2}^{L-1} O(d) = O(L^2)$$
olur. \(L=1000\) için bu, yaklaşık yarım milyon kalan güncellemesi düzeyindedir. En büyük ek bellek kullanımı \(O(L)\)'dir; çünkü en büyük izleme dizisinin boyutu en fazla \(L-1\)'dir.
El problema pide el denominador \(d \lt 1000\) para el cual la expansión decimal de \(1/d\) tiene el ciclo recurrente más largo. Algunos recíprocos terminan, como \(1/8 = 0.125\); otros tienen una cola periódica, como \(1/7 = 0.\overline{142857}\).
La idea central es que la expansión decimal está gobernada por los restos de la división larga. En cuanto un mismo resto aparece por segunda vez, los dígitos posteriores también deben repetirse. Por tanto, el objeto matemático real no es la cadena de dígitos en sí, sino el proceso finito de restos generado al dividir \(1\) entre \(d\).
Fijemos un denominador \(d \ge 2\). En la división larga de \(1/d\), cada paso depende solo del resto actual.
Tomemos \(r_0 = 1 \bmod d\). En el paso \(k\), escribimos
$$10r_k = q_k d + r_{k+1}, \qquad 0 \le q_k \le 9,\qquad 0 \le r_{k+1} \lt d.$$
Aquí \(q_k\) es el siguiente dígito decimal de \(1/d\), y \(r_{k+1}\) es el nuevo resto. Al reducir la misma igualdad módulo \(d\), obtenemos
$$r_{k+1} \equiv 10r_k \pmod{d}.$$
Así, la expansión decimal nace de una transición determinista sobre el conjunto finito de restos \(\{0,1,\dots,d-1\}\). El resto actual determina por completo tanto el siguiente dígito como el siguiente resto.
Si en algún momento el resto llega a \(0\), todos los restos posteriores siguen siendo \(0\), y el decimal termina. Si eso no ocurre, todos los restos pertenecen a \(\{1,2,\dots,d-1\}\), de modo que solo existen \(d-1\) posibilidades. Por el principio del palomar, algún resto debe repetirse después de a lo sumo \(d\) pasos.
Supongamos que \(r_i = r_j\) con \(i \lt j\). Como la regla de transición es determinista, el futuro a partir del paso \(i\) coincide exactamente con el futuro a partir del paso \(j\). Por eso los dígitos desde la posición \(i\) se repiten con período \(j-i\). Esta es la razón matemática por la que basta almacenar la primera posición de cada resto.
En particular, la longitud del ciclo recurrente nunca supera \(d-1\).
Escribamos
$$d = 2^a 5^b m,\qquad \gcd(m,10)=1.$$
Los factores \(2\) y \(5\) solo generan un prefijo finito, porque las potencias de \(10\) contienen exactamente esos factores primos. La parte verdaderamente periódica proviene del denominador reducido \(m\).
Si \(m=1\), el decimal termina. Si \(m \gt 1\), la longitud del ciclo es el menor entero positivo \(t\) que satisface
$$10^t \equiv 1 \pmod{m},$$
es decir, la orden multiplicativa \(\operatorname{ord}_m(10)\). Las implementaciones no calculan esta orden mediante factorización, pero esta interpretación explica exactamente qué mide el algoritmo.
Para \(d=7\), la cadena de restos es
$$1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1.$$
Los dígitos correspondientes salen de
$$10 = 1\cdot 7 + 3,\quad 30 = 4\cdot 7 + 2,\quad 20 = 2\cdot 7 + 6,$$
$$60 = 8\cdot 7 + 4,\quad 40 = 5\cdot 7 + 5,\quad 50 = 7\cdot 7 + 1.$$
Por tanto,
$$\frac{1}{7} = 0.\overline{142857},$$
y como el resto \(1\) reaparece tras 6 pasos, la longitud del ciclo es 6.
Para \(d=12\), obtenemos
$$10 = 0\cdot 12 + 10,\qquad 100 = 8\cdot 12 + 4,\qquad 40 = 3\cdot 12 + 4.$$
Los dígitos empiezan como \(0,8,3,3,3,\dots\), así que
$$\frac{1}{12} = 0.08\overline{3}.$$
El resto \(4\) se repite de inmediato, de modo que el ciclo recurrente tiene longitud 1. El prefijo \(08\) no se repite y proviene del factor \(4 = 2^2\) dentro del denominador.
El código recorre todos los denominadores desde \(2\) hasta \(999\), calcula su longitud de ciclo y conserva el mejor. Existen hechos teóricos adicionales, como que la orden divide a \(\varphi(m)\), pero para este tamaño de entrada no hacen falta. La simulación directa de restos reproduce exactamente la división larga y ya es suficientemente rápida.
Las implementaciones en C++, Python y Java siguen la misma estructura. Leen un límite opcional, ejecutan dos comprobaciones pequeñas y luego recorren todos los denominadores por debajo de ese límite.
Para un \(d\) fijo, la implementación crea un arreglo o lista de longitud \(d\) e inicializa todos sus valores en \(-1\). La entrada correspondiente a un resto \(r\) guarda la primera posición decimal en la que apareció ese resto. El proceso comienza con resto \(1 \bmod d\) y contador de posición igual a 0.
Mientras el resto actual no sea 0 y todavía no haya aparecido, se guarda la posición actual, se actualiza el resto a \((10r) \bmod d\) y se incrementa el contador. Si el bucle termina porque el resto se volvió 0, la expansión decimal termina y la longitud del ciclo es 0. Si termina porque el resto ya había aparecido, la longitud del ciclo es
$$\text{posición actual} - \text{primera posición de ese resto}.$$
Después de calcular cada longitud, la implementación la compara con la mejor encontrada hasta ese momento. Solo si el nuevo ciclo es estrictamente más largo, el denominador actual pasa a ser el mejor candidato. En caso de empate, se conserva el denominador anterior.
Antes de resolver el caso completo, las implementaciones verifican dos hechos conocidos: la longitud recurrente de \(1/7\) es 6 y, entre los denominadores menores que 10, el mejor es 7. Así se valida tanto la simulación de restos como el barrido exterior.
Para un denominador fijo \(d\), el bucle visita cada resto como máximo una vez antes de llegar a 0 o de repetir un resto. Por ello, el costo es \(O(d)\). Sumando sobre todos los \(d = 2,3,\dots,L-1\), obtenemos
$$\sum_{d=2}^{L-1} O(d) = O(L^2).$$
Cuando \(L=1000\), eso es solo del orden de medio millón de actualizaciones de restos. La memoria extra máxima es \(O(L)\), porque el arreglo más grande de seguimiento tiene tamaño a lo sumo \(L-1\).
这道题要求在所有 \(d \lt 1000\) 的分母中，找出使 \(1/d\) 的十进制展开拥有最长循环节的那个 \(d\)。有些倒数会终止，例如 \(1/8 = 0.125\)；有些则在某个位置之后开始无限循环，例如 \(1/7 = 0.\overline{142857}\)。
真正控制十进制展开的不是表面上的数字串，而是长除法过程中出现的余数。一旦某个余数第二次出现，之后的所有商位和余数都会完全重复。因此，这个问题本质上是在研究一个由余数构成的有限状态过程，而不是直接研究小数文本本身。
固定一个分母 \(d \ge 2\)。对 \(1/d\) 做长除法时，每一步都只由当前余数决定。
设 \(r_0 = 1 \bmod d\)。在第 \(k\) 步，可以写成
$$10r_k = q_k d + r_{k+1}, \qquad 0 \le q_k \le 9,\qquad 0 \le r_{k+1} \lt d.$$
这里 \(q_k\) 是 \(1/d\) 的下一个十进制数字，\(r_{k+1}\) 是新的余数。把同一个等式按模 \(d\) 化简，就得到
$$r_{k+1} \equiv 10r_k \pmod{d}.$$
这说明十进制展开来自 \(\{0,1,\dots,d-1\}\) 上的一个确定性转移规则。当前余数一旦确定，下一个数字和下一个余数也就同时确定了。
如果某一步出现余数 \(0\)，那么之后所有余数都保持为 \(0\)，小数也就终止了。否则，所有余数都落在 \(\{1,2,\dots,d-1\}\) 中，一共只有 \(d-1\) 种可能。根据抽屉原理，经过至多 \(d\) 步之后，必然有某个余数再次出现。
设 \(r_i = r_j\) 且 \(i \lt j\)。由于转移规则完全确定，从第 \(i\) 步往后的演化与从第 \(j\) 步往后的演化一模一样。因此，从第 \(i\) 位开始的小数数字会以 \(j-i\) 为周期重复。这就是为什么只记录每个余数第一次出现的位置，就足以求出循环节长度。
由此立刻得到一个上界：任意分母 \(d\) 的循环节长度都不会超过 \(d-1\)。
把分母写成
$$d = 2^a 5^b m,\qquad \gcd(m,10)=1.$$
其中的 \(2\) 和 \(5\) 只会制造有限长的前缀，因为 \(10\) 的幂只含有这两个素因子。真正决定循环节的，是约去这些因素之后剩下的 \(m\)。
如果 \(m=1\)，那么 \(1/d\) 就是终止小数。如果 \(m \gt 1\)，循环节长度就是满足
$$10^t \equiv 1 \pmod{m}$$
的最小正整数 \(t\)，也就是 \(\operatorname{ord}_m(10)\)。虽然实现没有通过分解质因数去直接求这个乘法阶，但这个结论准确解释了余数过程到底在测量什么。
当 \(d=7\) 时，余数链为
$$1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1.$$
对应的商位来自以下等式：
$$10 = 1\cdot 7 + 3,\quad 30 = 4\cdot 7 + 2,\quad 20 = 2\cdot 7 + 6,$$
$$60 = 8\cdot 7 + 4,\quad 40 = 5\cdot 7 + 5,\quad 50 = 7\cdot 7 + 1.$$
因此
$$\frac{1}{7} = 0.\overline{142857}.$$
余数 \(1\) 在 6 步之后再次出现，所以循环节长度是 6。
当 \(d=12\) 时，有
$$10 = 0\cdot 12 + 10,\qquad 100 = 8\cdot 12 + 4,\qquad 40 = 3\cdot 12 + 4.$$
所以数字序列以 \(0,8,3,3,3,\dots\) 开始，也就是
$$\frac{1}{12} = 0.08\overline{3}.$$
这里余数 \(4\) 立刻重复，因此循环节长度为 1；而前面的 \(08\) 是不循环的前缀，它来自分母中的 \(4 = 2^2\) 因子。
代码会把 \(2\) 到 \(999\) 的所有分母全部扫描一遍，逐个计算循环节长度，然后保留最长的那个。理论上当然还可以利用更多数论事实，例如乘法阶必定整除 \(\varphi(m)\)，但在这里完全没有必要。因为输入规模很小，直接模拟余数转移既精确对应长除法，又已经足够快。
C++、Python 和 Java 三个实现的结构完全一致。它们先读取一个可选的上界参数，接着运行两个小型校验，然后枚举所有小于该上界的分母。
对于固定的 \(d\)，实现会创建一个长度为 \(d\) 的数组或列表，并把所有位置初始化为 \(-1\)。其中下标 \(r\) 保存余数 \(r\) 第一次出现时对应的小数位位置。起始状态是余数 \(1 \bmod d\)，位置计数器为 0。
只要当前余数不是 0，并且此前还没有出现过，就先记录当前位置，再把余数更新为 \((10r) \bmod d\)，同时把位置计数器加 1。如果循环因余数变成 0 而结束，说明小数终止，循环节长度就是 0。如果循环因某个余数再次出现而结束，那么循环节长度就是
$$\text{当前位置} - \text{该余数第一次出现的位置}.$$
每算完一个分母，程序就把新得到的循环节长度与当前最佳值比较。只有当新长度严格更大时，才会更新最佳分母。也正因为比较是严格的，所以如果两者长度相同，较早遇到的那个分母会被保留下来。
在处理完整输入之前，三个实现都会先验证两个已知事实：\(1/7\) 的循环节长度为 6，而且在所有小于 10 的分母中，最佳答案是 7。这样可以同时检查余数模拟逻辑和外层枚举逻辑是否正确。
对于固定的分母 \(d\)，循环至多访问每个余数一次，然后就会遇到余数 0 或某个重复余数，因此单次计算的时间复杂度是 \(O(d)\)。对所有 \(d = 2,3,\dots,L-1\) 求和，得到
$$\sum_{d=2}^{L-1} O(d) = O(L^2).$$
当 \(L=1000\) 时，总工作量只有大约五十万次余数更新，规模非常小。额外空间的峰值是 \(O(L)\)，因为最大的余数记录数组长度最多只有 \(L-1\)。
Нужно найти такой знаменатель \(d \lt 1000\), для которого десятичная запись числа \(1/d\) имеет самый длинный период. Некоторые обратные дроби конечны, например \(1/8 = 0.125\); другие после некоторого места начинают повторяться, например \(1/7 = 0.\overline{142857}\).
Ключевое наблюдение состоит в том, что десятичная запись управляется не самими цифрами, а остатками при делении в столбик. Как только некоторый остаток встретился во второй раз, все последующие цифры тоже обязаны повторяться. Поэтому математически задача сводится к анализу конечного процесса переходов между остатками.
Зафиксируем знаменатель \(d \ge 2\). При делении \(1/d\) в столбик каждый шаг определяется текущим остатком.
Положим \(r_0 = 1 \bmod d\). На шаге \(k\) имеем
$$10r_k = q_k d + r_{k+1}, \qquad 0 \le q_k \le 9,\qquad 0 \le r_{k+1} \lt d.$$
Здесь \(q_k\) есть следующая десятичная цифра числа \(1/d\), а \(r_{k+1}\) есть новый остаток. Если ту же формулу рассмотреть по модулю \(d\), получаем
$$r_{k+1} \equiv 10r_k \pmod{d}.$$
Следовательно, десятичная запись порождается детерминированным переходом на конечном множестве остатков \(\{0,1,\dots,d-1\}\). Текущий остаток полностью задает и следующую цифру, и следующий остаток.
Если в какой-то момент остаток становится равным \(0\), то все дальнейшие остатки тоже равны \(0\), и десятичная запись заканчивается. Иначе все остатки лежат в множестве \(\{1,2,\dots,d-1\}\), то есть вариантов всего \(d-1\). По принципу Дирихле некоторый остаток обязательно повторится не позже чем через \(d\) шагов.
Пусть \(r_i = r_j\) при \(i \lt j\). Поскольку правило перехода детерминировано, все будущее начиная с шага \(i\) совпадает с будущим начиная с шага \(j\). Значит, цифры с позиции \(i\) повторяются с периодом \(j-i\). Именно поэтому в алгоритме достаточно хранить первую позицию появления каждого остатка.
В частности, длина периода для любого знаменателя \(d\) не превосходит \(d-1\).
Запишем
$$d = 2^a 5^b m,\qquad \gcd(m,10)=1.$$
Множители \(2\) и \(5\) отвечают только за конечный префикс, потому что степени числа \(10\) содержат именно эти простые множители. Настоящая периодичность определяется сокращенным знаменателем \(m\).
Если \(m=1\), дробь конечна. Если \(m \gt 1\), длина периода равна наименьшему положительному \(t\), для которого
$$10^t \equiv 1 \pmod{m},$$
то есть равна мультипликативному порядку \(\operatorname{ord}_m(10)\). В программах этот порядок не ищется напрямую через факторизацию, но такая формулировка точно описывает теоретический смысл вычисления.
Для \(d=7\) цепочка остатков имеет вид
$$1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1.$$
Соответствующие цифры получаются из равенств
$$10 = 1\cdot 7 + 3,\quad 30 = 4\cdot 7 + 2,\quad 20 = 2\cdot 7 + 6,$$
$$60 = 8\cdot 7 + 4,\quad 40 = 5\cdot 7 + 5,\quad 50 = 7\cdot 7 + 1.$$
Отсюда
$$\frac{1}{7} = 0.\overline{142857},$$
а так как остаток \(1\) снова появляется через 6 шагов, длина периода равна 6.
Для \(d=12\) имеем
$$10 = 0\cdot 12 + 10,\qquad 100 = 8\cdot 12 + 4,\qquad 40 = 3\cdot 12 + 4.$$
Поэтому цифры начинаются как \(0,8,3,3,3,\dots\), то есть
$$\frac{1}{12} = 0.08\overline{3}.$$
Остаток \(4\) повторяется сразу, значит длина периода равна 1. Начальный фрагмент \(08\) не повторяется и возникает из-за множителя \(4 = 2^2\) в знаменателе.
Код просто перебирает все знаменатели от \(2\) до \(999\), вычисляет для каждого длину периода и запоминает лучший. Теоретически можно использовать более тонкие факты, например делимость порядка на \(\varphi(m)\), но при таком размере входа это не нужно. Прямая симуляция остатков точно воспроизводит деление в столбик и работает достаточно быстро.
Реализации на C++, Python и Java устроены одинаково. Они читают необязательный предел, выполняют две небольшие проверки и затем просматривают все знаменатели ниже этого предела.
Для фиксированного \(d\) программа создает массив или список длины \(d\) и заполняет его значением \(-1\). Для каждого остатка \(r\) хранится первая позиция десятичной цифры, на которой этот остаток появился. Начальное состояние: остаток \(1 \bmod d\) и счетчик позиции, равный 0.
Пока текущий остаток не равен 0 и еще не встречался, программа сохраняет текущую позицию, обновляет остаток по формуле \((10r) \bmod d\) и увеличивает счетчик. Если цикл остановился из-за остатка 0, ответ равен 0. Если цикл остановился из-за повторного появления остатка, длина периода равна
$$\text{текущая позиция} - \text{первая позиция этого остатка}.$$
После каждой локальной оценки новая длина периода сравнивается с лучшей найденной ранее. Знаменатель обновляется только тогда, когда новый период строго длиннее. Поэтому при равенстве сохраняется более ранний, то есть меньший знаменатель.
Перед полным запуском программы проверяют два известных факта: период дроби \(1/7\) имеет длину 6, а среди знаменателей меньше 10 лучший ответ равен 7. Это быстрый контроль и функции вычисления периода, и внешнего перебора.
Для фиксированного знаменателя \(d\) цикл посещает каждый остаток не более одного раза, после чего либо приходит к 0, либо встречает повтор. Значит, стоимость равна \(O(d)\). Суммарно по всем \(d = 2,3,\dots,L-1\) получаем
$$\sum_{d=2}^{L-1} O(d) = O(L^2).$$
При \(L=1000\) это всего лишь порядка полумиллиона обновлений остатка. Пиковая дополнительная память равна \(O(L)\), потому что самый большой массив отслеживания имеет размер не более \(L-1\).
المطلوب هو إيجاد المقام \(d \lt 1000\) الذي يجعل التمثيل العشري للكسر \(1/d\) يملك أطول دورة تكرارية. بعض المقلوبات تنتهي مثل \(1/8 = 0.125\)، وبعضها يملك جزءًا دوريًا غير منتهٍ مثل \(1/7 = 0.\overline{142857}\).
الفكرة الأساسية هي أن ما يتحكم في التمثيل العشري ليس سلسلة الأرقام نفسها، بل البواقي الناتجة أثناء القسمة الطويلة. ما إن يظهر نفس الباقي مرتين حتى تصبح كل الخطوات اللاحقة متطابقة، وبالتالي تبدأ الأرقام بالتكرار. لذلك فالمسألة في جوهرها دراسة عملية منتهية على مجموعة البواقي.
لنثبت مقامًا \(d \ge 2\). عند تنفيذ القسمة الطويلة لـ \(1/d\)، كل خطوة تعتمد فقط على الباقي الحالي.
لنأخذ \(r_0 = 1 \bmod d\). في الخطوة رقم \(k\) نكتب
$$10r_k = q_k d + r_{k+1}, \qquad 0 \le q_k \le 9,\qquad 0 \le r_{k+1} \lt d.$$
العدد \(q_k\) هو الرقم العشري التالي في \(1/d\)، أما \(r_{k+1}\) فهو الباقي الجديد. وإذا أخذنا المعادلة نفسها بترديد \(d\)، نحصل على
$$r_{k+1} \equiv 10r_k \pmod{d}.$$
إذن التوسع العشري ينتج من انتقال حتمي على المجموعة المنتهية \(\{0,1,\dots,d-1\}\). الباقي الحالي يحدد بالكامل الرقم التالي والباقي التالي.
إذا وصلنا في خطوة ما إلى الباقي \(0\)، فإن كل البواقي اللاحقة تبقى \(0\)، ويكون الكسر عشريًا منتهيًا. وإذا لم يحدث ذلك، فكل البواقي تقع في \(\{1,2,\dots,d-1\}\)، أي توجد فقط \(d-1\) إمكانات غير صفرية. وبمبدأ الحمام الزاجل لا بد أن يتكرر أحد البواقي بعد عدد محدود من الخطوات لا يتجاوز \(d\).
إذا كان \(r_i = r_j\) مع \(i \lt j\)، فبسبب حتمية قاعدة الانتقال يصبح المستقبل ابتداءً من الخطوة \(i\) مطابقًا تمامًا للمستقبل ابتداءً من الخطوة \(j\). لذلك تتكرر الأرقام ابتداءً من الموضع \(i\) بدورة طولها \(j-i\). وهذا يفسر رياضيًا لماذا يكفي أن نحفظ أول موضع ظهر فيه كل باقٍ.
ومن ثم فإن طول الدورة لأي مقام \(d\) لا يمكن أن يتجاوز \(d-1\).
نكتب
$$d = 2^a 5^b m,\qquad \gcd(m,10)=1.$$
العوامل \(2\) و\(5\) مسؤولة فقط عن بادئة منتهية، لأن قوى العدد \(10\) تحتوي على هذين العاملين الأوليين تحديدًا. أما الجزء الدوري الحقيقي فيأتي من المقام المختزل \(m\).
إذا كان \(m=1\)، فإن التوسع العشري ينتهي. وإذا كان \(m \gt 1\)، فإن طول الدورة هو أصغر عدد صحيح موجب \(t\) يحقق
$$10^t \equiv 1 \pmod{m},$$
أي الرتبة الضربية \(\operatorname{ord}_m(10)\). التنفيذ لا يحسب هذه الرتبة عبر التحليل إلى عوامل أولية، لكن هذا الوصف يوضح بدقة ما الذي تقيسه عملية تتبع البواقي.
عندما يكون \(d=7\)، نحصل على سلسلة البواقي
$$1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1.$$
وتنتج الأرقام من المعادلات
$$10 = 1\cdot 7 + 3,\quad 30 = 4\cdot 7 + 2,\quad 20 = 2\cdot 7 + 6,$$
$$60 = 8\cdot 7 + 4,\quad 40 = 5\cdot 7 + 5,\quad 50 = 7\cdot 7 + 1.$$
ومن ثم
$$\frac{1}{7} = 0.\overline{142857}.$$
وبما أن الباقي \(1\) عاد بعد 6 خطوات، فإن طول الدورة يساوي 6.
عندما يكون \(d=12\)، نجد
$$10 = 0\cdot 12 + 10,\qquad 100 = 8\cdot 12 + 4,\qquad 40 = 3\cdot 12 + 4.$$
إذن الأرقام تبدأ بالشكل \(0,8,3,3,3,\dots\)، أي
$$\frac{1}{12} = 0.08\overline{3}.$$
الباقي \(4\) يتكرر مباشرة، ولذلك يكون طول الدورة 1. أما المقدمة \(08\) فهي جزء غير دوري سببه العامل \(4 = 2^2\) داخل المقام.
الكود يفحص جميع المقامات من \(2\) إلى \(999\)، ويحسب طول الدورة لكل واحد منها، ثم يحتفظ بأفضل قيمة. يمكن نظريًا استخدام حقائق عددية إضافية، مثل أن الرتبة الضربية تقسم \(\varphi(m)\)، لكن ذلك غير ضروري هنا. محاكاة البواقي نفسها تمثل القسمة الطويلة بدقة وهي سريعة بما يكفي لهذا الحجم من المدخلات.
تنفيذات C++ وPython وJava تتبع البنية نفسها. فهي تقرأ حدًا اختياريًا، وتجري اختبارين صغيرين للتأكد من الصحة، ثم تمر على كل المقامات الأصغر من هذا الحد.
للمقام الثابت \(d\)، ينشئ التنفيذ مصفوفة أو قائمة طولها \(d\) وتملأ بالقيمة \(-1\). الموضع الموافق للباقي \(r\) يخزن أول منزلة عشرية ظهر فيها هذا الباقي. تبدأ العملية من الباقي \(1 \bmod d\) ومعادّ موضع يساوي 0.
طالما أن الباقي الحالي غير صفري ولم يظهر من قبل، يتم أولًا تخزين الموضع الحالي، ثم تحديث الباقي إلى \((10r) \bmod d\)، ثم زيادة العداد بمقدار واحد. إذا انتهت الحلقة لأن الباقي صار 0، فالقيمة الناتجة هي 0. وإذا انتهت لأن الباقي ظهر سابقًا، فإن طول الدورة يساوي
$$\text{الموضع الحالي} - \text{أول موضع لذلك الباقي}.$$
بعد حساب طول الدورة لكل مقام، يقارن التنفيذ النتيجة بأفضل طول تم الوصول إليه حتى تلك اللحظة. لا يتم تحديث الجواب إلا إذا كانت الدورة الجديدة أطول بشكل صارم. ولهذا السبب، إذا حدث تعادل تبقى القيمة الأقدم، أي المقام الأصغر الذي ظهر أولًا.
قبل حل الحالة الكاملة، تتحقق البرامج من حقيقتين معروفتين: طول دورة \(1/7\) يساوي 6، وأفضل مقام أصغر من 10 هو 7. هذا يختبر صحة حساب الدورة وصحة المسح الخارجي في الوقت نفسه.
بالنسبة إلى مقام ثابت \(d\)، لا يمكن للحلقة أن تزور كل باقٍ أكثر من مرة قبل أن تصل إلى 0 أو تكتشف باقيا مكررًا، ولذلك يكون الزمن \(O(d)\). وعند الجمع على جميع القيم \(d = 2,3,\dots,L-1\) نحصل على
$$\sum_{d=2}^{L-1} O(d) = O(L^2).$$
وعندما يكون \(L=1000\)، يكون إجمالي العمل في حدود نصف مليون تحديث للباقي فقط. أما الذاكرة الإضافية العظمى فهي \(O(L)\)، لأن أكبر مصفوفة تتبع يكون طولها في الحد الأقصى \(L-1\).