We seek decimal integers \(N\) with at least two digits, no trailing zero, and at most 100 digits, such that moving the last digit of \(N\) to the front produces an integer multiple of \(N\). The required output is the sum of all such numbers modulo \(10^5\).
If \(N\) has digits \(x_{d-1}x_{d-2}\dots x_1x_0\), then the rotated number is \(x_0x_{d-1}x_{d-2}\dots x_1\). This rotation preserves the number of digits, so the quotient \(m=\frac{R}{N}\) must satisfy \(1\le m\le 9\). That observation already compresses the search to a small set of multipliers.
Let \(d\) be the number of digits, let \(r=x_0\) be the last digit, and write
$$N=10q+r,\qquad 1\le r\le 9.$$
The rotation of \(N\) is
$$R=r\cdot 10^{d-1}+q,$$
and the condition in the problem is
$$R=mN,\qquad m\in\{1,2,\dots,9\}.$$
The implementations use two equivalent viewpoints: a closed-form identity that shows there is at most one candidate for each triple \((d,m,r)\), and a carry recurrence that constructs that candidate digit by digit without ever forming a huge integer.
Starting from \(R=mN\), multiply by 10 and eliminate \(q\):
$$10R=r\cdot 10^d+10q=r\cdot 10^d+N-r=10mN.$$
So every solution must satisfy
$$\boxed{(10m-1)N=r(10^d-1).}$$
Therefore
$$\boxed{N=\frac{r(10^d-1)}{10m-1}.}$$
This is a crucial simplification. Once \(d\), \(m\), and \(r\) are fixed, the number \(N\) is either uniquely determined or impossible. The search is no longer “all \(d\)-digit numbers”; it is only 81 triples for each digit length.
The formula also explains familiar special cases. When \(m=1\), we get
$$N=\frac{r(10^d-1)}{9},$$
so every solution is a repdigit \(rr\dots r\), which rotation leaves unchanged.
The code does not test divisibility by building the fraction above. Instead it reads the multiplication \(mN=R\) exactly as schoolbook arithmetic. Write
$$N=x_{d-1}x_{d-2}\dots x_1x_0$$
with \(x_0=r\). Since \(R=x_0x_{d-1}\dots x_1\), the units digit of \(mN\) must be \(x_1\), the tens digit must be \(x_2\), and so on. If \(c_i\) is the carry entering step \(i\) and \(c_0=0\), then for \(0\le i\le d-2\),
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
After the last ordinary digit has been generated, the multiplication must close perfectly:
$$m x_{d-1}+c_{d-1}=x_0=r.$$
This final equality is stronger than a congruence. It says the most significant output digit is exactly \(r\) and there is no extra carry beyond it. If the generated top digit \(x_{d-1}\) were 0, the candidate would really have fewer than \(d\) digits, so it must also be rejected.
The recurrence is not an approximation; it is exactly the decimal multiplication rule for \(mN\). If it starts from \(x_0=r\), produces digits \(x_1,x_2,\dots,x_{d-1}\), and then closes back to \(r\), the resulting number satisfies \(mN=R\). Conversely, any valid rotated multiple must obey those same carry equations. So the problem is equivalent to iterating this finite-state process over all \((d,m,r)\).
That viewpoint is especially useful because the Project Euler task asks only for the sum modulo \(10^5\), not for the full decimal expansion of each solution. The implementations can therefore keep a running value of
$$N\bmod M=\sum_{i=0}^{d-1} x_i 10^i \bmod M,\qquad M=10^5,$$
while the digits are being generated, instead of storing \(N\) itself.
The classical example comes from \(d=6\), \(m=5\), and \(r=7\). The closed form gives
$$N=\frac{7(10^6-1)}{49}=142857.$$
The carry recurrence reveals the same number digit by digit:
$$5\cdot 7=5+10\cdot 3,$$
$$5\cdot 5+3=8+10\cdot 2,$$
$$5\cdot 8+2=2+10\cdot 4,$$
$$5\cdot 2+4=4+10\cdot 1,$$
$$5\cdot 4+1=1+10\cdot 2.$$
Reading the produced digits from most significant to least significant gives \(142857\), and the closure step is
$$5\cdot 1+2=7,$$
which matches the original last digit. Therefore
$$142857\longrightarrow 714285=5\cdot 142857.$$
This is exactly the mechanism the code applies to every permitted length, multiplier, and final digit.
The C++, Python, and Java implementations loop over digit lengths \(d=2,3,\dots,100\), multipliers \(m=1,2,\dots,9\), and last digits \(r=1,2,\dots,9\). Because the derivation above shows there is at most one candidate for each triple, nothing larger needs to be searched.
For each triple, the implementation starts with the known last digit \(r\), then repeatedly applies the carry rule
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
Each new digit \(x_{i+1}\) is immediately added into the running residue
$$v\leftarrow v+x_{i+1}\cdot 10^{i+1}\pmod{10^5},$$
while the current power of 10 is also maintained modulo \(10^5\). This keeps the memory footprint constant even when the actual number has 100 digits.
After \(d-1\) recurrence steps, the generated current digit is the would-be leading digit. The implementations reject the triple if that digit is 0, because then the number would not truly have \(d\) digits. They also reject it unless the final closure value \(m x_{d-1}+c_{d-1}\) is exactly \(r\). When both tests succeed, the accumulated residue is the contribution of that valid rotated multiple, and it is added to the global sum modulo \(10^5\).
For a fixed triple \((d,m,r)\), the recurrence runs for \(d-1\) steps, so the work is \(O(d)\). Summing over all digit lengths up to \(D\) gives
$$\sum_{d=2}^{D} 9\cdot 9\cdot O(d)=O(D^2).$$
For the actual problem \(D=100\), this is tiny compared with any brute-force scan over all integers below \(10^{100}\). The memory usage is \(O(1)\), because the implementation stores only the current digit, the carry, a running residue modulo \(10^5\), the current power of 10 modulo \(10^5\), and the total sum.
Gesucht sind Dezimalzahlen \(N\) mit mindestens zwei Stellen, ohne Endziffer 0 und mit höchstens 100 Stellen, für die das Verschieben der letzten Ziffer an den Anfang ein ganzzahliges Vielfaches von \(N\) ergibt. Ausgegeben werden soll die Summe aller solchen Zahlen modulo \(10^5\).
Hat \(N\) die Ziffern \(x_{d-1}x_{d-2}\dots x_1x_0\), dann lautet die rotierte Zahl \(x_0x_{d-1}x_{d-2}\dots x_1\). Da bei dieser Rotation die Stellenzahl gleich bleibt, muss der Quotient \(m=\frac{R}{N}\) einstellig sein, also \(1\le m\le 9\). Schon das reduziert den Suchraum drastisch.
Sei \(d\) die Stellenzahl, \(r=x_0\) die letzte Ziffer, und schreibe
$$N=10q+r,\qquad 1\le r\le 9.$$
Die Rotation von \(N\) ist
$$R=r\cdot 10^{d-1}+q,$$
und die Bedingung der Aufgabe lautet
$$R=mN,\qquad m\in\{1,2,\dots,9\}.$$
Die Implementierungen verwenden zwei äquivalente Blickwinkel: eine geschlossene Divisibilitätsformel, die höchstens einen Kandidaten pro Tripel \((d,m,r)\) liefert, und eine Übertragsrekurrenz, die diesen Kandidaten ziffernweise konstruiert, ohne große Ganzzahlen aufzubauen.
Aus \(R=mN\) folgt nach Multiplikation mit 10 und Eliminieren von \(q\):
$$10R=r\cdot 10^d+10q=r\cdot 10^d+N-r=10mN.$$
Also muss jede Lösung die Gleichung
$$\boxed{(10m-1)N=r(10^d-1)}$$
erfüllen. Damit ist
$$\boxed{N=\frac{r(10^d-1)}{10m-1}.}$$
Das ist der entscheidende Kollaps des Suchraums. Sind \(d\), \(m\) und \(r\) fest, dann ist \(N\) entweder eindeutig bestimmt oder unmöglich. Statt alle \(d\)-stelligen Zahlen zu durchsuchen, bleiben pro Stellenzahl nur 81 Fälle übrig.
Die Formel erklärt auch einfache Familien. Für \(m=1\) erhält man
$$N=\frac{r(10^d-1)}{9},$$
also genau die Repdigit-Zahlen \(rr\dots r\), die sich durch Rotation nicht ändern.
Der Code prüft die Teilbarkeit nicht über die obige Bruchformel, sondern liest \(mN=R\) als schriftliche Multiplikation. Schreibe
$$N=x_{d-1}x_{d-2}\dots x_1x_0$$
mit \(x_0=r\). Weil \(R=x_0x_{d-1}\dots x_1\) ist, muss die Einerstelle von \(mN\) gleich \(x_1\) sein, die Zehnerstelle gleich \(x_2\) und so weiter. Ist \(c_i\) der Übertrag vor Schritt \(i\) und \(c_0=0\), dann gilt für \(0\le i\le d-2\)
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
Nach der letzten gewöhnlichen Ziffer muss sich die Rechnung exakt schließen:
$$m x_{d-1}+c_{d-1}=x_0=r.$$
Diese Schlussbedingung ist stärker als eine bloße Kongruenz. Sie besagt, dass die führende Ausgabestelle genau \(r\) ist und kein weiterer Übertrag mehr existiert. Wenn die erzeugte höchste Ziffer \(x_{d-1}=0\) wäre, hätte der Kandidat in Wahrheit weniger als \(d\) Stellen und müsste ebenfalls verworfen werden.
Die Rekurrenz ist keine Heuristik, sondern exakt die Dezimalarithmetik von \(mN\). Startet man mit \(x_0=r\), erzeugt daraus \(x_1,x_2,\dots,x_{d-1}\) und landet am Ende wieder genau bei \(r\), dann erfüllt die konstruierte Zahl tatsächlich \(mN=R\). Umgekehrt muss jede gültige Zahl dieselben Übertragsgleichungen erfüllen. Das Problem ist also vollständig auf diese endliche Zustandsentwicklung über allen \((d,m,r)\) reduziert.
Gerade das ist praktisch, weil die Aufgabe nur die Summe modulo \(10^5\) verlangt. Deshalb halten die Implementierungen während der Konstruktion lediglich
$$N\bmod M=\sum_{i=0}^{d-1} x_i 10^i \bmod M,\qquad M=10^5,$$
statt die gesamte Zahl \(N\) abzuspeichern.
Das klassische Beispiel entsteht aus \(d=6\), \(m=5\) und \(r=7\). Die geschlossene Formel liefert
$$N=\frac{7(10^6-1)}{49}=142857.$$
Die Übertragsrekurrenz erzeugt dieselbe Zahl Ziffer für Ziffer:
$$5\cdot 7=5+10\cdot 3,$$
$$5\cdot 5+3=8+10\cdot 2,$$
$$5\cdot 8+2=2+10\cdot 4,$$
$$5\cdot 2+4=4+10\cdot 1,$$
$$5\cdot 4+1=1+10\cdot 2.$$
Liest man die erzeugten Ziffern von links nach rechts, erhält man \(142857\), und der Schluss ist
$$5\cdot 1+2=7,$$
also genau die ursprüngliche Endziffer. Damit gilt
$$142857\longrightarrow 714285=5\cdot 142857.$$
Genau dieses Muster wird im Programm für alle zulässigen Stellenzahlen, Multiplikatoren und Endziffern abgearbeitet.
Die Implementierungen in C++, Python und Java iterieren über Stellenzahlen \(d=2,3,\dots,100\), Multiplikatoren \(m=1,2,\dots,9\) und Endziffern \(r=1,2,\dots,9\). Weil die Herleitung zeigt, dass zu jedem Tripel höchstens ein Kandidat gehört, ist keine größere Suche nötig.
Für jedes Tripel beginnt die Implementierung mit der bekannten Endziffer \(r\) und wendet dann wiederholt die Übertragsgleichung
$$m x_i+c_i=x_{i+1}+10c_{i+1}$$
an. Jede neue Ziffer \(x_{i+1}\) wird sofort in den laufenden Rest
$$v\leftarrow v+x_{i+1}\cdot 10^{i+1}\pmod{10^5}$$
eingearbeitet, während auch die passende Zehnerpotenz modulo \(10^5\) fortgeschrieben wird. So bleibt der Speicherbedarf selbst für 100-stellige Zahlen konstant.
Nach \(d-1\) Rekurrenzschritten ist die aktuelle Ziffer die mögliche führende Ziffer. Ist sie 0, wird verworfen, weil die Zahl dann nicht wirklich \(d\)-stellig wäre. Ebenso wird verworfen, wenn der Schlusswert \(m x_{d-1}+c_{d-1}\) nicht exakt \(r\) ist. Nur wenn beide Tests bestehen, ist der modulare Rest tatsächlich der Beitrag einer gültigen rotierenden Zahl und wird zur Gesamtsumme modulo \(10^5\) addiert.
Für ein festes Tripel \((d,m,r)\) läuft die Rekurrenz \(d-1\) Schritte und kostet daher \(O(d)\). Über alle Stellenzahlen bis \(D\) summiert ergibt das
$$\sum_{d=2}^{D} 9\cdot 9\cdot O(d)=O(D^2).$$
Für die eigentliche Aufgabe mit \(D=100\) ist das winzig im Vergleich zu jeder Brute-Force-Suche unter allen Zahlen kleiner als \(10^{100}\). Der Speicherbedarf ist \(O(1)\), weil nur die aktuelle Ziffer, der Übertrag, ein laufender Rest modulo \(10^5\), die aktuelle Zehnerpotenz modulo \(10^5\) und die Gesamtsumme gehalten werden.
En az iki basamaklı, sonu 0 ile bitmeyen ve en çok 100 basamaklı onluk sayılar \(N\) aranıyor. Koşul şu: \(N\)'nin son basamağı başa taşındığında oluşan sayı, \(N\)'nin tam katı olmalı. İstenen çıktı, bu sayıların toplamının \(10^5\) ile bölümünden kalandır.
\(N\)'nin basamakları \(x_{d-1}x_{d-2}\dots x_1x_0\) ise döndürülmüş sayı \(x_0x_{d-1}x_{d-2}\dots x_1\) olur. Bu işlem basamak sayısını değiştirmediği için oran \(m=\frac{R}{N}\) mutlaka tek basamaklıdır; dolayısıyla yalnızca \(1\le m\le 9\) durumlarına bakmak yeterlidir.
\(d\) basamak sayısı, \(r=x_0\) son basamak olsun ve
$$N=10q+r,\qquad 1\le r\le 9$$
yazalım. \(N\)'nin döndürülmüş hali
$$R=r\cdot 10^{d-1}+q$$
olur ve problem koşulu
$$R=mN,\qquad m\in\{1,2,\dots,9\}$$
şeklindedir. Uygulamalar bu eşitliği iki eşdeğer bakışla kullanır: \((d,m,r)\) üçlüsü için en fazla bir aday olduğunu gösteren kapalı formül ve bu adayı büyük tamsayı oluşturmadan basamak basamak üreten taşıma yinelemesi.
\(R=mN\) denkleminden başlayıp 10 ile çarpalım ve \(q\)'yu yok edelim:
$$10R=r\cdot 10^d+10q=r\cdot 10^d+N-r=10mN.$$
Buradan her çözümün
$$\boxed{(10m-1)N=r(10^d-1)}$$
eşitliğini sağlaması gerektiği çıkar. Dolayısıyla
$$\boxed{N=\frac{r(10^d-1)}{10m-1}.}$$
Bu formül arama uzayını dramatik biçimde küçültür. \(d\), \(m\) ve \(r\) sabitse \(N\) ya tektir ya da hiç yoktur. Yani tüm \(d\)-basamaklı sayıları dolaşmak yerine her uzunluk için yalnızca 81 üçlü kontrol edilir.
Formül basit aileleri de açıklar. \(m=1\) olduğunda
$$N=\frac{r(10^d-1)}{9}$$
elde edilir; bunlar da döndürülünce değişmeyen \(rr\dots r\) biçimindeki aynı basamaklı sayılardır.
Kod, yukarıdaki kesri doğrudan hesaplayıp bölünebilirlik test etmek yerine \(mN=R\) eşitliğini ilkokul çarpması gibi okur. Şöyle yazalım:
$$N=x_{d-1}x_{d-2}\dots x_1x_0$$
ve \(x_0=r\) olsun. \(R=x_0x_{d-1}\dots x_1\) olduğundan, \(mN\)'nin birler basamağı \(x_1\), onlar basamağı \(x_2\), bu şekilde devam etmelidir. Eğer \(c_i\), \(i\). adıma giren taşıma ve \(c_0=0\) ise, \(0\le i\le d-2\) için
$$m x_i+c_i=x_{i+1}+10c_{i+1}$$
olur. Son sıradan basamak üretildikten sonra kapanış tam olmalıdır:
$$m x_{d-1}+c_{d-1}=x_0=r.$$
Bu son eşitlik yalnızca mod 10 bilgisi değildir. En soldaki sonuç basamağının tam olarak \(r\) olduğunu ve ekstra taşıma kalmadığını söyler. Üretilen en yüksek basamak \(x_{d-1}=0\) çıkarsa sayı gerçekte \(d\) basamaklı değildir; o yüzden o aday da atılır.
Taşıma yinelemesi bir kestirme değil, doğrudan onluk çarpma algoritmasının kendisidir. \(x_0=r\) ile başlayıp \(x_1,x_2,\dots,x_{d-1}\) basamaklarını üretir ve sonunda tekrar \(r\)'ye kapatabiliyorsak, kurulan sayı gerçekten \(mN=R\) koşulunu sağlar. Ters yönde de, geçerli her döndürme çarpanı aynı taşıma eşitliklerine uymak zorundadır. Böylece problem bütünüyle tüm \((d,m,r)\) üçlüleri üzerinde sonlu bir durum yürüyüşüne indirgenir.
Bu bakış özellikle kullanışlıdır, çünkü soruda tüm sayılar değil yalnızca toplamın \(10^5\) modundaki değeri istenir. Bu yüzden uygulamalar, sayı tamamını saklamak yerine inşa sırasında yalnızca
$$N\bmod M=\sum_{i=0}^{d-1} x_i 10^i \bmod M,\qquad M=10^5$$
değerini tutar.
Klasik örnek \(d=6\), \(m=5\), \(r=7\) seçiminden gelir. Kapalı formül
$$N=\frac{7(10^6-1)}{49}=142857$$
sonucunu verir. Aynı sayı taşıma yinelemesinden de çıkar:
$$5\cdot 7=5+10\cdot 3,$$
$$5\cdot 5+3=8+10\cdot 2,$$
$$5\cdot 8+2=2+10\cdot 4,$$
$$5\cdot 2+4=4+10\cdot 1,$$
$$5\cdot 4+1=1+10\cdot 2.$$
Üretilen basamakları soldan sağa okuyunca \(142857\) elde edilir; son kapanış adımı da
$$5\cdot 1+2=7$$
olup başlangıçtaki son basamakla tam uyuşur. Demek ki
$$142857\longrightarrow 714285=5\cdot 142857.$$
Kodun yaptığı iş, bu mekanizmayı izin verilen tüm uzunluklar, çarpanlar ve son basamaklar için tekrarlamaktır.
C++, Python ve Java uygulamaları \(d=2,3,\dots,100\), \(m=1,2,\dots,9\) ve \(r=1,2,\dots,9\) üzerinden döner. Yukarıdaki türetim her üçlü için en fazla tek bir aday olduğunu gösterdiği için daha büyük bir arama gerekmez.
Her üçlü için uygulama bilinen son basamak \(r\) ile başlar ve tekrar tekrar
$$m x_i+c_i=x_{i+1}+10c_{i+1}$$
ilişkisini uygular. Her yeni \(x_{i+1}\) basamağı hemen
$$v\leftarrow v+x_{i+1}\cdot 10^{i+1}\pmod{10^5}$$
güncellemesiyle çalışan kalana eklenir. Aynı anda 10'un uygun kuvveti de \(10^5\) modunda tutulur. Böylece sayı 100 basamaklı olsa bile bellek sabit kalır.
\(d-1\) adım sonra eldeki mevcut basamak, adayın baştaki basamağıdır. Bu basamak 0 ise sayı gerçekte \(d\) basamaklı olmadığı için üçlü reddedilir. Ayrıca kapanış değeri \(m x_{d-1}+c_{d-1}\) tam olarak \(r\) değilse yine reddedilir. İki test de geçerse, biriktirilmiş modüler değer geçerli döndürme sayısının katkısıdır ve toplam içine \(10^5\) modunda eklenir.
Sabit bir \((d,m,r)\) üçlüsü için yineleme \(d-1\) adım sürer; yani maliyet \(O(d)\)'dir. Bütün uzunluklar \(D\)'ye kadar toplandığında
$$\sum_{d=2}^{D} 9\cdot 9\cdot O(d)=O(D^2)$$
elde edilir. Gerçek problemde \(D=100\) olduğundan bu maliyet, \(10^{100}\)'den küçük sayılar üzerinde kaba kuvvet dolaşmaya göre ihmal edilecek kadar küçüktür. Bellek kullanımı \(O(1)\)'dir; çünkü yalnızca mevcut basamak, taşıma, \(10^5\) modunda çalışan kalan, yine \(10^5\) modunda 10 kuvveti ve toplam saklanır.
Se buscan enteros decimales \(N\) con al menos dos cifras, sin cero final y con como máximo 100 cifras, tales que al mover la última cifra al frente se obtenga un múltiplo entero de \(N\). La salida pedida es la suma de todos esos números módulo \(10^5\).
Si \(N\) tiene cifras \(x_{d-1}x_{d-2}\dots x_1x_0\), el número rotado es \(x_0x_{d-1}x_{d-2}\dots x_1\). Como la rotación conserva la cantidad de cifras, el cociente \(m=\frac{R}{N}\) tiene que ser de una sola cifra, es decir, \(1\le m\le 9\). Eso ya reduce el espacio de búsqueda de manera decisiva.
Sea \(d\) la cantidad de cifras, \(r=x_0\) la última cifra, y escribamos
$$N=10q+r,\qquad 1\le r\le 9.$$
La rotación de \(N\) es
$$R=r\cdot 10^{d-1}+q,$$
y la condición del problema es
$$R=mN,\qquad m\in\{1,2,\dots,9\}.$$
Las implementaciones aprovechan dos descripciones equivalentes de esta igualdad: una identidad cerrada que muestra que para cada triple \((d,m,r)\) hay como mucho un candidato, y una recurrencia con acarreo que construye ese candidato cifra a cifra sin usar enteros enormes.
Partiendo de \(R=mN\), multiplicamos por 10 y eliminamos \(q\):
$$10R=r\cdot 10^d+10q=r\cdot 10^d+N-r=10mN.$$
Así, toda solución debe satisfacer
$$\boxed{(10m-1)N=r(10^d-1).}$$
Por tanto,
$$\boxed{N=\frac{r(10^d-1)}{10m-1}.}$$
Ésta es la reducción clave. Fijados \(d\), \(m\) y \(r\), el número \(N\) queda determinado de manera única o no existe. La búsqueda deja de ser “todos los números de \(d\) cifras” y pasa a ser únicamente 81 triples por longitud.
La fórmula también aclara casos simples. Cuando \(m=1\), obtenemos
$$N=\frac{r(10^d-1)}{9},$$
que son exactamente los repdígitos \(rr\dots r\), invariantes bajo la rotación.
El código no prueba la divisibilidad construyendo la fracción anterior. En su lugar interpreta \(mN=R\) como una multiplicación decimal ordinaria. Escribimos
$$N=x_{d-1}x_{d-2}\dots x_1x_0$$
con \(x_0=r\). Como \(R=x_0x_{d-1}\dots x_1\), la unidad de \(mN\) debe ser \(x_1\), la decena debe ser \(x_2\), y así sucesivamente. Si \(c_i\) es el acarreo que entra en el paso \(i\) y \(c_0=0\), entonces para \(0\le i\le d-2\) se cumple
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
Después de generar la última cifra ordinaria, el proceso tiene que cerrarse exactamente:
$$m x_{d-1}+c_{d-1}=x_0=r.$$
Esta igualdad final es más fuerte que una congruencia. Afirma que la cifra más significativa producida es exactamente \(r\) y que no queda un acarreo extra. Si la cifra superior generada fuese \(x_{d-1}=0\), el candidato en realidad tendría menos de \(d\) cifras y debe descartarse.
La recurrencia no es un truco aproximado; es exactamente la regla de multiplicación decimal para \(mN\). Si empieza con \(x_0=r\), produce \(x_1,x_2,\dots,x_{d-1}\) y al final vuelve a cerrar en \(r\), entonces el número construido satisface \(mN=R\). Y en sentido inverso, cualquier solución válida debe obedecer esas mismas ecuaciones de acarreo. El problema completo queda reducido a recorrer este proceso finito para todos los \((d,m,r)\).
Esta perspectiva es especialmente útil porque el problema sólo pide la suma módulo \(10^5\). Por eso las implementaciones mantienen durante la construcción únicamente
$$N\bmod M=\sum_{i=0}^{d-1} x_i 10^i \bmod M,\qquad M=10^5,$$
en vez de almacenar el entero completo.
El ejemplo clásico aparece con \(d=6\), \(m=5\) y \(r=7\). La fórmula cerrada da
$$N=\frac{7(10^6-1)}{49}=142857.$$
La recurrencia con acarreo produce las mismas cifras:
$$5\cdot 7=5+10\cdot 3,$$
$$5\cdot 5+3=8+10\cdot 2,$$
$$5\cdot 8+2=2+10\cdot 4,$$
$$5\cdot 2+4=4+10\cdot 1,$$
$$5\cdot 4+1=1+10\cdot 2.$$
Al leer las cifras obtenidas de izquierda a derecha aparece \(142857\), y el cierre final es
$$5\cdot 1+2=7,$$
que coincide con la cifra final original. Por tanto,
$$142857\longrightarrow 714285=5\cdot 142857.$$
Ése es exactamente el patrón que el algoritmo aplica a todas las longitudes, multiplicadores y cifras finales permitidas.
Las implementaciones en C++, Python y Java iteran sobre longitudes \(d=2,3,\dots,100\), multiplicadores \(m=1,2,\dots,9\) y cifras finales \(r=1,2,\dots,9\). La derivación anterior garantiza que cada triple aporta como mucho un candidato, así que no hay que explorar nada mayor.
Para cada triple, la implementación comienza con la cifra final conocida \(r\) y aplica repetidamente
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
Cada nueva cifra \(x_{i+1}\) se incorpora de inmediato al residuo acumulado
$$v\leftarrow v+x_{i+1}\cdot 10^{i+1}\pmod{10^5},$$
mientras la potencia correspondiente de 10 también se actualiza módulo \(10^5\). De este modo el uso de memoria sigue siendo constante incluso cuando \(N\) tiene 100 cifras.
Tras \(d-1\) pasos, la cifra actual es la posible cifra inicial del número. Si vale 0, el triple se rechaza porque el número real tendría menos de \(d\) cifras. También se rechaza si el valor de cierre \(m x_{d-1}+c_{d-1}\) no es exactamente \(r\). Sólo cuando ambas pruebas pasan, el residuo acumulado corresponde a un múltiplo rotado válido y se suma al total módulo \(10^5\).
Para un triple fijo \((d,m,r)\), la recurrencia da \(d-1\) pasos, así que el costo es \(O(d)\). Sumando sobre todas las longitudes hasta \(D\), se obtiene
$$\sum_{d=2}^{D} 9\cdot 9\cdot O(d)=O(D^2).$$
En el problema real, con \(D=100\), esto es diminuto frente a cualquier recorrido por fuerza bruta entre todos los enteros menores que \(10^{100}\). La memoria es \(O(1)\), porque sólo se guardan la cifra actual, el acarreo, un residuo módulo \(10^5\), la potencia actual de 10 módulo \(10^5\) y la suma total.
题目要求寻找这样的十进制整数 \(N\)：它至少有两位，不以 0 结尾，位数不超过 100；把它的最后一位移到最前面以后，得到的新数必须是 \(N\) 的整数倍。最终输出的是所有这类 \(N\) 的和对 \(10^5\) 取模后的结果。
如果 \(N\) 的十进制表示是 \(x_{d-1}x_{d-2}\dots x_1x_0\)，那么旋转后的数就是 \(x_0x_{d-1}x_{d-2}\dots x_1\)。由于这种旋转不会改变位数，所以商 \(m=\frac{R}{N}\) 不可能达到两位数，必然满足 \(1\le m\le 9\)。这一步已经把搜索范围压缩到了很小的规模。
设 \(d\) 是位数，\(r=x_0\) 是末位数字，并把 \(N\) 写成
$$N=10q+r,\qquad 1\le r\le 9.$$
把末位移到最前面后得到
$$R=r\cdot 10^{d-1}+q,$$
题目条件就是
$$R=mN,\qquad m\in\{1,2,\dots,9\}.$$
三个实现都围绕这条等式展开，但它们真正依赖的是两种等价表达：一种是直接给出候选数的闭式关系，说明每个 \((d,m,r)\) 最多对应一个解；另一种是按十进制乘法逐位推进的进位递推，它让我们不必构造巨大的整数本体。
从 \(R=mN\) 出发，乘以 10 并消去 \(q\)：
$$10R=r\cdot 10^d+10q=r\cdot 10^d+N-r=10mN.$$
于是任何解都必须满足
$$\boxed{(10m-1)N=r(10^d-1).}$$
因此
$$\boxed{N=\frac{r(10^d-1)}{10m-1}.}$$
这是整道题最重要的压缩。只要位数 \(d\)、乘数 \(m\) 和末位 \(r\) 固定，\(N\) 就不是“可能有很多个”，而是“要么唯一确定，要么根本不存在”。所以真正要枚举的不是所有 \(d\) 位数，而是每个长度下仅有的 81 个三元组。
这个公式还解释了最简单的一族解。若 \(m=1\)，就得到
$$N=\frac{r(10^d-1)}{9},$$
也就是 \(rr\dots r\) 这种所有位都相同的数；把最后一位移到最前面以后当然还是它自己。
代码并不是先算出上面的分式，再去检查它是不是整数。它直接把 \(mN=R\) 当作普通十进制乘法来读。写成
$$N=x_{d-1}x_{d-2}\dots x_1x_0$$
并令 \(x_0=r\)。因为 \(R=x_0x_{d-1}\dots x_1\)，所以 \(mN\) 的个位必须是 \(x_1\)，十位必须是 \(x_2\)，依此类推。若 \(c_i\) 表示第 \(i\) 步进入时的进位，并且 \(c_0=0\)，则对 \(0\le i\le d-2\) 有
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
当普通数字都生成完以后，还必须满足严格的闭环条件：
$$m x_{d-1}+c_{d-1}=x_0=r.$$
这不是“模 10 同余”那么弱的条件，而是说最高位输出必须恰好等于 \(r\)，并且不能再出现额外进位。若最终生成的最高位 \(x_{d-1}=0\)，那说明这个候选数实际上不足 \(d\) 位，也必须丢弃。
这条递推不是近似方法，而是十进制乘法规则本身。只要从 \(x_0=r\) 出发，依次得到 \(x_1,x_2,\dots,x_{d-1}\)，最后又准确回到 \(r\)，构造出的数就一定满足 \(mN=R\)。反过来，任何合法解在逐位相乘时都必然满足同样的进位方程。因此，原题完全等价于：对所有 \((d,m,r)\) 运行这个有限状态过程，并检查它是否闭合。
这种写法特别适合本题，因为题目只要求答案对 \(10^5\) 取模，而不要求把每个 100 位解完整保存出来。所以实现中只维护
$$N\bmod M=\sum_{i=0}^{d-1} x_i 10^i \bmod M,\qquad M=10^5,$$
在每次生成新数字时即时更新，而不保存整个整数。
最经典的例子来自 \(d=6\)、\(m=5\)、\(r=7\)。闭式公式直接给出
$$N=\frac{7(10^6-1)}{49}=142857.$$
同一个结果也会从进位递推中自然长出来：
$$5\cdot 7=5+10\cdot 3,$$
$$5\cdot 5+3=8+10\cdot 2,$$
$$5\cdot 8+2=2+10\cdot 4,$$
$$5\cdot 2+4=4+10\cdot 1,$$
$$5\cdot 4+1=1+10\cdot 2.$$
把生成出来的数字从高位到低位读出，就是 \(142857\)。最后的闭环检查为
$$5\cdot 1+2=7,$$
正好回到原来的末位 \(r\)。因此
$$142857\longrightarrow 714285=5\cdot 142857.$$
程序对所有允许的长度、乘数和末位做的，正是这一套机制的系统化枚举。
C++、Python 和 Java 三个实现都枚举位数 \(d=2,3,\dots,100\)、乘数 \(m=1,2,\dots,9\) 以及末位数字 \(r=1,2,\dots,9\)。因为前面的推导已经说明，每个三元组最多只会产生一个候选数，所以完全没有必要枚举所有 \(d\) 位整数。
对于每个三元组，实现先把已知的末位 \(r\) 作为起点，然后反复应用
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
每得到一个新数字 \(x_{i+1}\)，就立刻把它并入当前的模值
$$v\leftarrow v+x_{i+1}\cdot 10^{i+1}\pmod{10^5},$$
与此同时，所需的 \(10\) 的幂也一直在 \(10^5\) 模下更新。这样即使真正的整数有 100 位，内存占用也仍然是常数级。
做完 \(d-1\) 次递推以后，当前数字就是候选数的最高位。如果它是 0，就说明这个数其实没有 \(d\) 位，必须丢弃。随后还要检查闭环值 \(m x_{d-1}+c_{d-1}\) 是否恰好等于 \(r\)。只有这两个条件都满足时，当前累计出来的模值才对应一个真正有效的旋转倍数，并被加进总和的 \(10^5\) 模值中。
对于固定的 \((d,m,r)\)，递推要运行 \(d-1\) 步，因此代价是 \(O(d)\)。把所有长度加到 \(D\) 为止，总工作量为
$$\sum_{d=2}^{D} 9\cdot 9\cdot O(d)=O(D^2).$$
在题目实际需要的 \(D=100\) 下，这个代价与对所有小于 \(10^{100}\) 的整数做暴力检查相比几乎可以忽略。空间复杂度是 \(O(1)\)，因为实现只保存当前数字、当前进位、模 \(10^5\) 的部分值、模 \(10^5\) 的当前 10 次幂，以及最终的累加和。
Нужно найти десятичные числа \(N\), у которых не меньше двух цифр, последняя цифра не равна нулю, а длина не превышает 100 цифр. Если перенести последнюю цифру в начало, полученное число должно оказаться целым кратным \(N\). Требуется сложить все такие числа и взять результат по модулю \(10^5\).
Если запись числа имеет вид \(x_{d-1}x_{d-2}\dots x_1x_0\), то после циклического переноса получаем \(x_0x_{d-1}x_{d-2}\dots x_1\). Такая операция не меняет число цифр, поэтому отношение \(m=\frac{R}{N}\) обязательно однозначно и лежит в пределах \(1\le m\le 9\). Уже это делает перебор очень маленьким.
Пусть \(d\) обозначает число цифр, \(r=x_0\) является последней цифрой, и запишем
$$N=10q+r,\qquad 1\le r\le 9.$$
Тогда повернутое число равно
$$R=r\cdot 10^{d-1}+q,$$
а условие задачи имеет вид
$$R=mN,\qquad m\in\{1,2,\dots,9\}.$$
Все реализации опираются на два эквивалентных описания этой связи: замкнутую формулу, показывающую, что для каждого тройственного набора \((d,m,r)\) существует не более одного кандидата, и рекуррентное правило с переносом, которое строит этого кандидата по цифрам без работы с огромными целыми числами.
Начнем с \(R=mN\), умножим на 10 и исключим \(q\):
$$10R=r\cdot 10^d+10q=r\cdot 10^d+N-r=10mN.$$
Значит, любое решение обязано удовлетворять
$$\boxed{(10m-1)N=r(10^d-1).}$$
Отсюда сразу следует
$$\boxed{N=\frac{r(10^d-1)}{10m-1}.}$$
Это и есть главный математический сдвиг. При фиксированных \(d\), \(m\) и \(r\) число \(N\) либо определяется однозначно, либо вовсе не существует. Следовательно, вместо перебора всех \(d\)-значных чисел остается проверить только 81 тройку на каждую длину.
Формула сразу объясняет и самые простые решения. Если \(m=1\), то
$$N=\frac{r(10^d-1)}{9},$$
то есть это просто числа вида \(rr\dots r\), которые после переноса последней цифры в начало не меняются.
Код не строит указанную дробь напрямую. Вместо этого равенство \(mN=R\) читается как обычное десятичное умножение. Запишем
$$N=x_{d-1}x_{d-2}\dots x_1x_0$$
и положим \(x_0=r\). Поскольку \(R=x_0x_{d-1}\dots x_1\), единицы числа \(mN\) должны дать \(x_1\), десятки должны дать \(x_2\), и так далее. Если \(c_i\) обозначает перенос, входящий в шаг \(i\), а \(c_0=0\), то для \(0\le i\le d-2\) имеем
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
После генерации последней обычной цифры процесс обязан точно замкнуться:
$$m x_{d-1}+c_{d-1}=x_0=r.$$
Это не просто сравнение по модулю 10. Оно означает, что старшая выходная цифра ровно равна \(r\) и дополнительного переноса больше нет. Если при этом сгенерированная старшая цифра \(x_{d-1}\) равна 0, кандидат на самом деле имеет меньше \(d\) цифр и должен быть отброшен.
Рекурсия с переносом не является эвристикой; это точное правило школьного умножения для \(mN\). Если, начиная с \(x_0=r\), она последовательно порождает \(x_1,x_2,\dots,x_{d-1}\) и затем замыкается обратно на \(r\), то построенное число действительно удовлетворяет \(mN=R\). И наоборот, любое допустимое число обязано выполнять те же самые уравнения переноса. Значит, вся задача полностью сводится к этому конечному процессу на всех тройках \((d,m,r)\).
Такой взгляд особенно удобен, потому что от решения требуется только сумма по модулю \(10^5\), а не сами полные 100-значные числа. Поэтому реализации поддерживают лишь значение
$$N\bmod M=\sum_{i=0}^{d-1} x_i 10^i \bmod M,\qquad M=10^5,$$
обновляя его по мере порождения новых цифр.
Классический пример получается при \(d=6\), \(m=5\) и \(r=7\). Замкнутая формула сразу дает
$$N=\frac{7(10^6-1)}{49}=142857.$$
Та же последовательность цифр возникает и из рекурсии переноса:
$$5\cdot 7=5+10\cdot 3,$$
$$5\cdot 5+3=8+10\cdot 2,$$
$$5\cdot 8+2=2+10\cdot 4,$$
$$5\cdot 2+4=4+10\cdot 1,$$
$$5\cdot 4+1=1+10\cdot 2.$$
Если прочитать порожденные цифры слева направо, получится \(142857\), а финальное замыкание выглядит так:
$$5\cdot 1+2=7.$$
Следовательно,
$$142857\longrightarrow 714285=5\cdot 142857.$$
Именно этот механизм алгоритм применяет ко всем допустимым длинам, множителям и последним цифрам.
Реализации на C++, Python и Java перебирают длины \(d=2,3,\dots,100\), множители \(m=1,2,\dots,9\) и последние цифры \(r=1,2,\dots,9\). Так как для каждой тройки существует не более одного кандидата, никакой более широкий перебор не нужен.
Для каждой тройки программа начинает с известной последней цифры \(r\), а затем многократно применяет равенство
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
Каждая новая цифра \(x_{i+1}\) сразу включается в накопленный остаток
$$v\leftarrow v+x_{i+1}\cdot 10^{i+1}\pmod{10^5},$$
и одновременно поддерживается текущая степень 10 по модулю \(10^5\). Благодаря этому объем памяти остается постоянным даже для 100-значных чисел.
После \(d-1\) шагов текущая цифра становится кандидатом на старшую цифру числа. Если она равна 0, тройка отбрасывается, потому что число оказалось бы короче, чем \(d\). Кроме того, тройка отбрасывается, если замыкающее значение \(m x_{d-1}+c_{d-1}\) не совпадает в точности с \(r\). Лишь при выполнении обоих условий накопленный остаток соответствует корректному вращающемуся кратному и прибавляется к общей сумме по модулю \(10^5\).
Для фиксированной тройки \((d,m,r)\) рекурсия выполняет \(d-1\) шагов, то есть требует \(O(d)\) времени. Суммируя по всем длинам до \(D\), получаем
$$\sum_{d=2}^{D} 9\cdot 9\cdot O(d)=O(D^2).$$
В реальной задаче \(D=100\), и эта стоимость ничтожна по сравнению с любым перебором всех чисел меньше \(10^{100}\). Память равна \(O(1)\), так как хранятся только текущая цифра, перенос, частичный остаток по модулю \(10^5\), текущая степень 10 по модулю \(10^5\) и итоговая сумма.
نبحث عن أعداد عشرية \(N\) لها على الأقل خانتان، ولا تنتهي بصفر، ولا يزيد طولها على 100 خانة، بحيث إن نقل الخانة الأخيرة إلى البداية يعطي عددًا يساوي مضاعفًا صحيحًا لـ \(N\). والمطلوب في النهاية هو مجموع جميع هذه الأعداد بترديد \(10^5\).
إذا كانت كتابة \(N\) هي \(x_{d-1}x_{d-2}\dots x_1x_0\)، فإن العدد بعد الدوران يصبح \(x_0x_{d-1}x_{d-2}\dots x_1\). ولأن هذه العملية لا تغيّر عدد الخانات، فإن خارج القسمة \(m=\frac{R}{N}\) لا يمكن أن يكون ذا خانتين، بل يجب أن يحقق \(1\le m\le 9\). وهذه ملاحظة أولى تقلص مجال البحث كثيرًا.
لنفرض أن \(d\) هو عدد الخانات، وأن \(r=x_0\) هي الخانة الأخيرة، ولنكتب
$$N=10q+r,\qquad 1\le r\le 9.$$
بعد تدوير الخانة الأخيرة إلى المقدمة يصبح العدد
$$R=r\cdot 10^{d-1}+q,$$
وشرط المسألة هو
$$R=mN,\qquad m\in\{1,2,\dots,9\}.$$
التطبيقات الثلاثة تبني الحل على وصفيْن متكافئين لهذه المعادلة: صيغة مغلقة تبيّن أن كل ثلاثي \((d,m,r)\) ينتج عنه على الأكثر مرشح واحد، وعلاقة تكرارية مع حمل تبني هذا المرشح خانة بعد خانة من غير الحاجة إلى تمثيل عدد ضخم كاملًا.
نبدأ من \(R=mN\)، ثم نضرب في 10 ونتخلص من \(q\):
$$10R=r\cdot 10^d+10q=r\cdot 10^d+N-r=10mN.$$
إذن لا بد لأي حل أن يحقق
$$\boxed{(10m-1)N=r(10^d-1).}$$
ومن ثم
$$\boxed{N=\frac{r(10^d-1)}{10m-1}.}$$
هذه هي النقلة الحاسمة في المسألة. فعندما تكون \(d\) و\(m\) و\(r\) معلومة، فإن \(N\) إما يكون محددًا بصورة وحيدة أو لا يوجد أصلًا. وبدلًا من فحص جميع الأعداد ذات \(d\) خانات، يكفي اختبار 81 ثلاثيًا فقط لكل طول.
كما أن الصيغة تشرح العائلة الأبسط من الحلول. فإذا كان \(m=1\)، فإن
$$N=\frac{r(10^d-1)}{9},$$
أي نحصل على الأعداد من الشكل \(rr\dots r\)، وهي أعداد لا تتغير أصلًا عند تدوير الخانة الأخيرة إلى المقدمة.
لا تقوم الشيفرة بحساب الكسر السابق مباشرة ثم اختبار كونه عددًا صحيحًا. بدلًا من ذلك، تقرأ المعادلة \(mN=R\) على أنها ضرب عشري اعتيادي. نكتب
$$N=x_{d-1}x_{d-2}\dots x_1x_0$$
مع \(x_0=r\). وبما أن \(R=x_0x_{d-1}\dots x_1\)، فإن خانة الآحاد في \(mN\) يجب أن تكون \(x_1\)، وخانة العشرات يجب أن تكون \(x_2\)، وهكذا. إذا رمزنا إلى الحمل الداخل في الخطوة \(i\) بالرمز \(c_i\)، مع \(c_0=0\)، فإننا نحصل لكل \(0\le i\le d-2\) على
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
وبعد توليد آخر خانة عادية، يجب أن تنغلق العملية تمامًا:
$$m x_{d-1}+c_{d-1}=x_0=r.$$
هذا الشرط الأخير ليس مجرد توافق modulo 10، بل يعني أن الخانة القيادية الناتجة تساوي \(r\) بالضبط، وأنه لا يوجد حمل إضافي بعد ذلك. وإذا خرجت الخانة العليا \(x_{d-1}=0\)، فهذا يعني أن المرشح الحقيقي أقل من \(d\) خانات، ولذلك يجب رفضه أيضًا.
العلاقة مع الحمل ليست تقريبًا أو حيلة تجريبية؛ إنها بالضبط قواعد الضرب العشري لـ \(mN\). فإذا بدأنا من \(x_0=r\)، ثم ولّدت لنا العلاقة الخانات \(x_1,x_2,\dots,x_{d-1}\)، ثم أغلقت الدورة في النهاية عائدة إلى \(r\)، فإن العدد الناتج يحقق فعلًا المعادلة \(mN=R\). وبالعكس، أي حل صحيح لا بد أن يحقق معادلات الحمل نفسها. ولذلك يمكن اختزال المسألة كلها إلى هذا السير المنتهي على جميع الثلاثيات \((d,m,r)\).
وهذا مهم جدًا هنا لأن المطلوب في المسألة ليس كتابة جميع الأعداد كاملة، بل فقط حساب مجموعها بترديد \(10^5\). ولهذا تحتفظ التطبيقات أثناء البناء بالقيمة
$$N\bmod M=\sum_{i=0}^{d-1} x_i 10^i \bmod M,\qquad M=10^5,$$
وتحدثها كلما ظهرت خانة جديدة، بدلًا من تخزين العدد بأكمله.
المثال الأشهر يأتي من \(d=6\) و\(m=5\) و\(r=7\). الصيغة المغلقة تعطي مباشرة
$$N=\frac{7(10^6-1)}{49}=142857.$$
والعلاقة التكرارية مع الحمل تنتج الخانات نفسها خطوة خطوة:
$$5\cdot 7=5+10\cdot 3,$$
$$5\cdot 5+3=8+10\cdot 2,$$
$$5\cdot 8+2=2+10\cdot 4,$$
$$5\cdot 2+4=4+10\cdot 1,$$
$$5\cdot 4+1=1+10\cdot 2.$$
وعند قراءة الخانات الناتجة من اليسار إلى اليمين نحصل على \(142857\)، أما خطوة الإغلاق الأخيرة فهي
$$5\cdot 1+2=7,$$
فتعود تمامًا إلى الخانة الأخيرة الأصلية. ومن ثم
$$142857\longrightarrow 714285=5\cdot 142857.$$
وهذه هي الآلية نفسها التي تطبقها الشيفرة على كل طول مسموح، وكل معامل \(m\)، وكل خانة أخيرة \(r\).
تنفذ تطبيقات C++ وPython وJava حلقات على أطوال الخانات \(d=2,3,\dots,100\)، وعلى المعاملات \(m=1,2,\dots,9\)، وعلى الخانة الأخيرة \(r=1,2,\dots,9\). وبما أن البرهان السابق يوضح أن كل ثلاثي يعطي على الأكثر مرشحًا واحدًا، فلا حاجة لأي بحث أوسع.
لكل ثلاثي تبدأ الشيفرة بالخانة الأخيرة المعروفة \(r\)، ثم تطبق مرارًا العلاقة
$$m x_i+c_i=x_{i+1}+10c_{i+1}.$$
وكلما ظهرت خانة جديدة \(x_{i+1}\) تُضاف فورًا إلى الباقي الجاري وفق
$$v\leftarrow v+x_{i+1}\cdot 10^{i+1}\pmod{10^5},$$
كما تُحدَّث قوة 10 المناسبة أيضًا بترديد \(10^5\). وبهذا يبقى استهلاك الذاكرة ثابتًا حتى لو كان العدد الحقيقي مكوّنًا من 100 خانة.
بعد \(d-1\) خطوة تصبح الخانة الحالية هي المرشحة لتكون الخانة الأولى في العدد. فإذا كانت صفرًا، يُرفض الثلاثي لأن العدد الحقيقي لن يكون بطول \(d\). ويُرفض أيضًا إذا لم تكن قيمة الإغلاق \(m x_{d-1}+c_{d-1}\) مساوية تمامًا لـ \(r\). فقط عندما ينجح الشرطان معًا يكون الباقي المتراكم مساهمةً صحيحة لعدد يحقق خاصية الدوران، وعندها يضاف إلى المجموع الكلي بترديد \(10^5\).
بالنسبة إلى ثلاثي ثابت \((d,m,r)\)، تنفذ العلاقة التكرارية \(d-1\) خطوة، ولذلك تكون الكلفة \(O(d)\). وبجمع ذلك على جميع الأطوال حتى \(D\) نحصل على
$$\sum_{d=2}^{D} 9\cdot 9\cdot O(d)=O(D^2).$$
وفي المسألة الفعلية حيث \(D=100\)، يُعد هذا صغيرًا جدًا مقارنة بأي فحص brute force لجميع الأعداد الأصغر من \(10^{100}\). أما الذاكرة فهي \(O(1)\)، لأن التنفيذ يحتفظ فقط بالخانة الحالية، والحمل الحالي، وباقٍ جزئي modulo \(10^5\)، وقوة 10 الحالية modulo \(10^5\)، والمجموع النهائي.