For every coprime pair \((u,v)\) with \(1 \le u,v \le m\), we look for the smallest positive integer whose first decimal digit can be moved to the end so that the new number becomes exactly \(\left(\frac{u}{v}\right)^3\) times the original one. If no such integer exists, that pair contributes \(0\). The required quantity is
$$T(m)=\sum_{\substack{1 \le u,v \le m\\ \gcd(u,v)=1}} M(u,v)\pmod{10^9+7},$$
where \(M(u,v)\) denotes that minimal shifted multiple. A brute-force search over decimal strings is hopeless, so the solution turns the digit shift into a divisibility problem and then solves it with multiplicative orders.
The core idea is to write the unknown number in decimal form, translate the digit shift into an equation, and then isolate the exact conditions under which an admissible length exists.
Let the desired number have \(\ell\) digits, leading digit \(d \in \{1,\dots,9\}\), and remaining tail \(r\), so
$$N=d \cdot 10^{\ell-1}+r,\qquad 0 \le r < 10^{\ell-1}.$$
After moving the first digit to the end, we obtain
$$S=10r+d.$$
Now set
$$a=u^3,\qquad b=v^3.$$
The required relation is
$$S=\frac{a}{b}N,$$
which is equivalent to
$$b(10r+d)=a(d \cdot 10^{\ell-1}+r).$$
Rearranging gives
$$r(10b-a)=d(a \cdot 10^{\ell-1}-b).$$
Define the denominator
$$\Delta = 10b-a.$$
Then
$$r=\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta}$$
and therefore
$$N=d \cdot 10^{\ell-1}+r=\frac{d\,b\,(10^{\ell}-1)}{\Delta}.$$
This already shows that only pairs with \(\Delta>0\), that is \(u^3<10v^3\), can contribute.
Because \(r \ge 0\), we must have
$$a \cdot 10^{\ell-1} \ge b.$$
So the smallest feasible digit length is
$$\ell_{\min}=\min\left\{\ell \ge 1: a \cdot 10^{\ell-1} \ge b\right\}.$$
This is exactly the magnitude test used by the implementation: it does not guess \(\ell\), it starts from the first length for which the tail \(r\) can even be nonnegative.
We also need \(r<10^{\ell-1}\), otherwise \(d\) would not really be the first digit of an \(\ell\)-digit number. Substituting the formula for \(r\) gives
$$\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta} < 10^{\ell-1}.$$
After moving terms, this becomes
$$10^{\ell-1}\bigl(a(d+1)-10b\bigr) < db.$$
If \(a(d+1)\ge 10b\), the left-hand side is nonnegative and the inequality cannot hold in the way needed for a valid leading digit. Therefore any admissible digit must satisfy
$$a(d+1)<10b.$$
Once this strict inequality holds, the upper bound on \(r\) is automatically safe, so the digit test is completely independent of \(\ell\).
Since
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta},$$
we need \(\Delta \mid d\,b\,(10^{\ell}-1)\). The coprimality hypothesis \(\gcd(u,v)=1\) implies
$$\gcd(\Delta,b)=\gcd(10v^3-u^3,v^3)=1.$$
So the factor \(b\) can be removed, and integrality simplifies to
$$\Delta \mid d(10^{\ell}-1).$$
Let
$$g=\gcd(\Delta,d),\qquad m=\frac{\Delta}{g}.$$
Then the condition is equivalent to
$$m \mid 10^{\ell}-1.$$
A length \(\ell\) satisfying \(10^{\ell}\equiv 1 \pmod m\) exists if and only if \(\gcd(10,m)=1\). In that case the valid lengths are precisely the multiples of the multiplicative order
$$\operatorname{ord}_m(10).$$
So for a fixed digit \(d\), the smallest admissible length is
$$\ell(d)=\left\lceil\frac{\ell_{\min}}{\operatorname{ord}_m(10)}\right\rceil \operatorname{ord}_m(10).$$
The pair contribution is obtained from the lexicographically smallest candidate: first minimize \(\ell\), then among equal lengths choose the smaller leading digit \(d\). If no digit survives all tests, the pair contributes \(0\).
Here
$$a=1,\qquad b=8,\qquad \Delta=10 \cdot 8 - 1 = 79.$$
The minimum possible length satisfies \(10^{\ell-1}\ge 8\), so
$$\ell_{\min}=2.$$
Try the smallest digit \(d=1\). The digit constraint is
$$a(d+1)=2<80=10b,$$
so the digit is admissible. Since \(\gcd(79,1)=1\), we get \(m=79\). Because \(79\) is coprime to \(10\), the relevant period is
$$\operatorname{ord}_{79}(10)=13.$$
Therefore the smallest valid length is
$$\ell=13.$$
Plugging this into the closed formula yields
$$M(1,2)=\frac{1 \cdot 8(10^{13}-1)}{79}=1012658227848.$$
Moving the first digit to the end produces \(126582278481\), which is exactly \(\frac{1}{8}\) of the original number, matching \(\left(\frac{1}{2}\right)^3\).
The C++, Python, and Java implementations follow the derivation above almost literally. They first build a smallest-prime-factor sieve up to \(10m^3\), which is large enough for every denominator \(\Delta\) and every totient value used in the order computation. They then enumerate all coprime pairs \((u,v)\), form the cubes \(u^3\) and \(v^3\), and immediately discard cases with \(u^3 \ge 10v^3\).
For each surviving pair, the implementation computes \(\ell_{\min}\), loops over digits \(1,\dots,9\), applies the digit inequality \(u^3(d+1)<10v^3\), reduces the denominator by \(\gcd(\Delta,d)\), and rejects the digit if the reduced modulus shares a factor with \(10\). Otherwise it computes the multiplicative order of \(10\) modulo that reduced modulus. The order is obtained by starting from Euler's totient, factoring it with the sieve, and removing prime factors one by one whenever the corresponding modular-power test still returns \(1\).
After choosing the best pair \((d,\ell)\), the implementation evaluates
$$\frac{d\,v^3\,(10^{\ell}-1)}{10v^3-u^3} \pmod{10^9+7}$$
using a modular inverse for the denominator. The arithmetic is identical across all three languages; the C++ version additionally parallelizes independent ranges of \(u\), while the Python and Java versions keep the same logic serial.
Let \(B=10m^3\). Building the smallest-prime-factor sieve costs \(O(B\log\log B)\) time and \(O(B)\) memory. The main search examines \(O(m^2)\) candidate pairs and at most \(9\) digits for each pair. Each digit trial performs a few gcd computations, several modular exponentiations, and a factor-stripping process based on the prime divisors of a totient value. So after the sieve, the remaining work is near-quadratic in \(m\) with a modest number-theoretic overhead, and the memory usage is dominated by the sieve.
Für jedes teilerfremde Paar \((u,v)\) mit \(1 \le u,v \le m\) wird die kleinste positive ganze Zahl gesucht, deren erste Dezimalziffer ans Ende verschoben werden kann, sodass die neue Zahl genau \(\left(\frac{u}{v}\right)^3\) mal so groß ist wie die ursprüngliche. Existiert keine solche Zahl, so liefert das Paar den Beitrag \(0\). Gesucht ist
$$T(m)=\sum_{\substack{1 \le u,v \le m\\ \gcd(u,v)=1}} M(u,v)\pmod{10^9+7},$$
wobei \(M(u,v)\) dieses minimale verschobene Vielfache bezeichnet. Eine naive Suche über Dezimaldarstellungen ist aussichtslos; deshalb übersetzt die Lösung die Ziffernverschiebung in eine Teilbarkeitsbedingung und benutzt anschließend multiplikative Ordnungen.
Die ganze Struktur wird sichtbar, wenn man die unbekannte Zahl in führende Ziffer und Rest zerlegt und die Verschiebung algebraisch ausschreibt.
Sei die gesuchte Zahl \(\ell\)-stellig, mit führender Ziffer \(d \in \{1,\dots,9\}\) und Rest \(r\). Dann gilt
$$N=d \cdot 10^{\ell-1}+r,\qquad 0 \le r < 10^{\ell-1}.$$
Nach dem Verschieben der ersten Ziffer ans Ende entsteht
$$S=10r+d.$$
Setze weiter
$$a=u^3,\qquad b=v^3.$$
Die Problemforderung lautet
$$S=\frac{a}{b}N,$$
also
$$b(10r+d)=a(d \cdot 10^{\ell-1}+r).$$
Nach Umformen erhält man
$$r(10b-a)=d(a \cdot 10^{\ell-1}-b).$$
Mit
$$\Delta = 10b-a$$
folgt
$$r=\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta}$$
und damit
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta}.$$
Damit ist sofort klar: Nur Paare mit \(\Delta>0\), also \(u^3<10v^3\), können überhaupt beitragen.
Wegen \(r \ge 0\) muss gelten
$$a \cdot 10^{\ell-1} \ge b.$$
Somit ist die minimale sinnvolle Stellenzahl
$$\ell_{\min}=\min\left\{\ell \ge 1: a \cdot 10^{\ell-1} \ge b\right\}.$$
Genau diese Schranke wird im Programm zuerst bestimmt: Erst ab dieser Länge kann der Rest \(r\) nichtnegativ sein.
Zusätzlich muss \(r<10^{\ell-1}\) gelten, sonst wäre \(d\) nicht wirklich die erste Ziffer einer \(\ell\)-stelligen Zahl. Einsetzen liefert
$$\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta} < 10^{\ell-1},$$
also nach Umformung
$$10^{\ell-1}\bigl(a(d+1)-10b\bigr) < db.$$
Ist \(a(d+1)\ge 10b\), ist die linke Seite nichtnegativ und die Bedingung kann nicht passend erfüllt werden. Daher muss jede zulässige führende Ziffer
$$a(d+1)<10b$$
erfüllen. Sobald diese strenge Ungleichung gilt, ist die obere Schranke für \(r\) automatisch erfüllt.
Aus
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta}$$
folgt die Teilbarkeitsbedingung \(\Delta \mid d\,b\,(10^{\ell}-1)\). Wegen \(\gcd(u,v)=1\) gilt aber
$$\gcd(\Delta,b)=\gcd(10v^3-u^3,v^3)=1.$$
Daher darf man den Faktor \(b\) eliminieren, und die Bedingung vereinfacht sich zu
$$\Delta \mid d(10^{\ell}-1).$$
Setzt man
$$g=\gcd(\Delta,d),\qquad m=\frac{\Delta}{g},$$
so ist dies äquivalent zu
$$m \mid 10^{\ell}-1.$$
Eine Lösung von \(10^{\ell}\equiv 1 \pmod m\) existiert genau dann, wenn \(\gcd(10,m)=1\). In diesem Fall sind alle gültigen Längen Vielfache der multiplikativen Ordnung
$$\operatorname{ord}_m(10).$$
Für eine feste Ziffer \(d\) ist daher die kleinste gültige Länge
$$\ell(d)=\left\lceil\frac{\ell_{\min}}{\operatorname{ord}_m(10)}\right\rceil \operatorname{ord}_m(10).$$
Unter allen Ziffern \(d\in\{1,\dots,9\}\) wählt man zuerst die kleinste Länge \(\ell\) und bei Gleichstand die kleinere Ziffer. Bleibt keine Ziffer übrig, ist der Beitrag des Paares \(0\).
Hier ist
$$a=1,\qquad b=8,\qquad \Delta=10 \cdot 8 - 1 = 79.$$
Die minimale Länge erfüllt \(10^{\ell-1}\ge 8\), also
$$\ell_{\min}=2.$$
Nimm zunächst \(d=1\). Dann lautet die Ziffernbedingung
$$a(d+1)=2<80=10b,$$
also ist die Ziffer zulässig. Da \(\gcd(79,1)=1\), gilt \(m=79\). Weil \(79\) teilerfremd zu \(10\) ist, erhält man
$$\operatorname{ord}_{79}(10)=13.$$
Die kleinste mögliche Länge ist somit
$$\ell=13.$$
Einsetzen ergibt
$$M(1,2)=\frac{1 \cdot 8(10^{13}-1)}{79}=1012658227848.$$
Verschiebt man die erste Ziffer ans Ende, entsteht \(126582278481\), also genau \(\frac{1}{8}\) der ursprünglichen Zahl und damit \(\left(\frac{1}{2}\right)^3\) mal die Ausgangszahl.
Die C++-, Python- und Java-Implementierungen folgen dieser Herleitung nahezu direkt. Zuerst wird ein Sieb der kleinsten Primfaktoren bis \(10m^3\) aufgebaut; das reicht für jeden vorkommenden Nenner \(\Delta\) und für jede Totient-Funktion, die bei der Ordnungsberechnung benötigt wird. Danach werden alle teilerfremden Paare \((u,v)\) durchlaufen, die Kuben \(u^3\) und \(v^3\) gebildet und Fälle mit \(u^3 \ge 10v^3\) sofort verworfen.
Für jedes verbleibende Paar wird \(\ell_{\min}\) berechnet, dann werden die Ziffern \(1,\dots,9\) getestet. Für jede Ziffer wird die Ungleichung \(u^3(d+1)<10v^3\) geprüft, der Nenner durch \(\gcd(\Delta,d)\) reduziert und die Ziffer verworfen, falls der reduzierte Modul einen gemeinsamen Faktor mit \(10\) besitzt. Andernfalls berechnet die Implementierung die multiplikative Ordnung von \(10\) modulo dieses Moduls. Dazu startet sie mit der Euler-Funktion, faktorisiert sie mit Hilfe des Siebs und entfernt Primfaktoren schrittweise, solange der passende modulare Potenztest weiterhin \(1\) ergibt.
Ist das beste Paar \((d,\ell)\) gefunden, wird
$$\frac{d\,v^3\,(10^{\ell}-1)}{10v^3-u^3} \pmod{10^9+7}$$
über ein modulares Inverses des Nenners ausgewertet. Die Arithmetik ist in allen drei Sprachen dieselbe; lediglich die C++-Version parallelisiert unabhängige Bereiche der äußeren Schleife über \(u\).
Mit \(B=10m^3\) kostet das Sieb der kleinsten Primfaktoren \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher. Die eigentliche Suche betrachtet \(O(m^2)\) Paare und höchstens \(9\) Ziffern pro Paar. Jeder Ziffernversuch benötigt einige ggT-Berechnungen, mehrere modulare Potenzen und ein schrittweises Kürzen anhand der Primteiler eines Totient-Werts. Nach dem Sieb ist der Rest daher nahezu quadratisch in \(m\); der Speicherverbrauch wird klar vom Sieb dominiert.
\(1 \le u,v \le m\) ve \(\gcd(u,v)=1\) olan her çift için, ilk ondalık basamağı sona taşındığında sayı tam olarak \(\left(\frac{u}{v}\right)^3\) ile çarpılmış olsun. Böyle bir özellik taşıyan en küçük pozitif tam sayıya \(M(u,v)\) diyelim; eğer hiç yoksa katkı \(0\) kabul edilir. İstenen toplam
$$T(m)=\sum_{\substack{1 \le u,v \le m\\ \gcd(u,v)=1}} M(u,v)\pmod{10^9+7}$$
şeklindedir. Doğrudan sayı aramak pratik değildir; çözüm, basamak kaydırmayı cebirsel bir eşitliğe dönüştürüp işi bölünebilirlik ve çarpımsal mertebe hesabına indirger.
Ana fikir, sayıyı “ilk basamak + kalan kuyruk” biçiminde yazmak ve bu gösterimden tam sayı olma koşullarını çıkarmaktır.
Aranan sayı \(\ell\) basamaklı olsun. İlk basamağı \(d \in \{1,\dots,9\}\), geri kalan kısmı \(r\) ile gösterelim:
$$N=d \cdot 10^{\ell-1}+r,\qquad 0 \le r < 10^{\ell-1}.$$
İlk basamak sona taşınınca oluşan sayı
$$S=10r+d$$
olur. Ayrıca
$$a=u^3,\qquad b=v^3$$
tanımlarını yapalım. Problem koşulu
$$S=\frac{a}{b}N$$
olduğundan
$$b(10r+d)=a(d \cdot 10^{\ell-1}+r)$$
eşitliğini elde ederiz. Düzenlersek
$$r(10b-a)=d(a \cdot 10^{\ell-1}-b)$$
çıkar. Şimdi
$$\Delta = 10b-a$$
yazarsak
$$r=\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta}$$
ve dolayısıyla
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta}$$
olur. Buradan hemen, yalnızca \(\Delta>0\), yani \(u^3<10v^3\) olan çiftlerin katkı verebileceği görülür.
\(r\) negatif olamayacağı için
$$a \cdot 10^{\ell-1} \ge b$$
olmalıdır. Bu yüzden mümkün olan en küçük basamak sayısı
$$\ell_{\min}=\min\left\{\ell \ge 1: a \cdot 10^{\ell-1} \ge b\right\}$$
şeklindedir. Uygulama, önce tam olarak bu alt sınırı hesaplar.
Ayrıca \(r<10^{\ell-1}\) olmalıdır; aksi halde \(d\), \(\ell\) basamaklı yazımın gerçekten ilk rakamı olmaz. Formülü yerine koyunca
$$\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta} < 10^{\ell-1}$$
ve oradan da
$$10^{\ell-1}\bigl(a(d+1)-10b\bigr) < db$$
elde edilir. Eğer \(a(d+1)\ge 10b\) ise sol taraf negatif olamaz ve gerekli yapı bozulur. Demek ki geçerli her ilk basamak
$$a(d+1)<10b$$
koşulunu sağlamalıdır. Bu sıkı eşitsizlik sağlandığında, \(r\) için üst sınır zaten otomatik olarak güvenli olur.
\(N\)'nin tam sayı olması için
$$\Delta \mid d\,b\,(10^{\ell}-1)$$
gereklidir. Fakat \(\gcd(u,v)=1\) olduğundan
$$\gcd(\Delta,b)=\gcd(10v^3-u^3,v^3)=1$$
olur. Böylece \(b\) faktörü aradan çıkar ve koşul
$$\Delta \mid d(10^{\ell}-1)$$
şekline iner. Şimdi
$$g=\gcd(\Delta,d),\qquad m=\frac{\Delta}{g}$$
tanımlanırsa gereken şey
$$m \mid 10^{\ell}-1$$
olur.
\(10^{\ell}\equiv 1 \pmod m\) biçiminde bir çözüm ancak \(\gcd(10,m)=1\) iken vardır. Bu durumda geçerli bütün uzunluklar
$$\operatorname{ord}_m(10)$$
değerinin katlarıdır. O halde sabit bir \(d\) için en küçük uygun uzunluk
$$\ell(d)=\left\lceil\frac{\ell_{\min}}{\operatorname{ord}_m(10)}\right\rceil \operatorname{ord}_m(10)$$
olur. Bütün \(d \in \{1,\dots,9\}\) adayları arasında önce en küçük \(\ell\), eşitlik varsa daha küçük \(d\) seçilir. Hiç aday kalmazsa katkı \(0\)'dır.
Bu durumda
$$a=1,\qquad b=8,\qquad \Delta=10 \cdot 8 - 1 = 79.$$
\(10^{\ell-1}\ge 8\) olması gerektiği için
$$\ell_{\min}=2.$$
En küçük basamak olarak \(d=1\) deneyelim. Basamak koşulu
$$a(d+1)=2<80=10b$$
olduğu için bu rakam uygundur. Ayrıca \(\gcd(79,1)=1\) olduğundan \(m=79\) elde edilir. \(79\) sayısı \(10\) ile aralarında asal olduğu için
$$\operatorname{ord}_{79}(10)=13$$
bulunur. Böylece en küçük geçerli uzunluk
$$\ell=13$$
olur. Sonuç sayı
$$M(1,2)=\frac{1 \cdot 8(10^{13}-1)}{79}=1012658227848$$
şeklindedir. İlk basamağı sona taşıyınca \(126582278481\) elde edilir; bu da sayının tam olarak \(\frac{1}{8}\)'i, yani \(\left(\frac{1}{2}\right)^3\) katıdır.
C++, Python ve Java uygulamaları bu türetmeyi neredeyse doğrudan izler. Önce \(10m^3\) sınırına kadar en küçük asal bölen tablosu kurulur; bu sınır, hem ortaya çıkan bütün \(\Delta\) değerleri hem de mertebe hesabında kullanılan Euler fonksiyonları için yeterlidir. Daha sonra tüm aralarında asal \((u,v)\) çiftleri dolaşılır, \(u^3\) ve \(v^3\) hesaplanır ve \(u^3 \ge 10v^3\) olan durumlar hemen elenir.
Kalan her çift için önce \(\ell_{\min}\) bulunur, sonra rakamlar \(1,\dots,9\) tek tek sınanır. Her rakamda \(u^3(d+1)<10v^3\) eşitsizliği kontrol edilir, payda \(\gcd(\Delta,d)\) ile küçültülür ve küçültülmüş modül \(10\) ile ortak bölen taşıyorsa aday reddedilir. Aksi halde uygulama, bu modül altında \(10\)'un çarpımsal mertebesini hesaplar. Bunun için Euler fonksiyonundan başlanır, o değer asal çarpanlarına ayrılır ve uygun modüler üs testleri hâlâ \(1\) verdiği sürece gereksiz asal çarpanlar tek tek atılır.
En iyi \((d,\ell)\) seçildikten sonra katkı
$$\frac{d\,v^3\,(10^{\ell}-1)}{10v^3-u^3} \pmod{10^9+7}$$
modüler ters kullanılarak hesaplanır. Üç dildeki aritmetik aynıdır; yalnızca C++ sürümü, bağımsız \(u\) aralıklarını paralel çalıştırır.
\(B=10m^3\) olsun. En küçük asal bölen tablosunu kurmak \(O(B\log\log B)\) zaman ve \(O(B)\) bellek ister. Ana arama kısmı \(O(m^2)\) çift ve her çift için en fazla \(9\) rakam inceler. Her rakam denemesinde birkaç gcd hesabı, birkaç modüler üs alma işlemi ve bir Euler fonksiyonu böleni üzerinde asal çarpan silme süreci vardır. Dolayısıyla elekten sonraki iş yükü \(m\) açısından yaklaşık kareseldir; toplam bellek maliyetini ise açık farkla elek tablosu belirler.
Para cada par coprimo \((u,v)\) con \(1 \le u,v \le m\), se busca el menor entero positivo cuya primera cifra decimal pueda moverse al final de modo que el nuevo número sea exactamente \(\left(\frac{u}{v}\right)^3\) veces el original. Si no existe tal entero, la contribución de ese par es \(0\). La suma pedida es
$$T(m)=\sum_{\substack{1 \le u,v \le m\\ \gcd(u,v)=1}} M(u,v)\pmod{10^9+7},$$
donde \(M(u,v)\) denota ese múltiplo desplazado mínimo. Buscar directamente entre cadenas decimales sería inviable, así que la solución transforma el desplazamiento de cifras en una condición de divisibilidad y luego usa orden multiplicativo.
La idea central es escribir el número desconocido por su primera cifra y su cola, y después extraer de esa identidad todas las restricciones aritméticas relevantes.
Sea \(N\) el número buscado, con \(\ell\) cifras, primera cifra \(d \in \{1,\dots,9\}\) y cola \(r\). Entonces
$$N=d \cdot 10^{\ell-1}+r,\qquad 0 \le r < 10^{\ell-1}.$$
Al mover la primera cifra al final obtenemos
$$S=10r+d.$$
Definamos además
$$a=u^3,\qquad b=v^3.$$
La condición del problema es
$$S=\frac{a}{b}N,$$
equivalentemente
$$b(10r+d)=a(d \cdot 10^{\ell-1}+r).$$
Reordenando:
$$r(10b-a)=d(a \cdot 10^{\ell-1}-b).$$
Si escribimos
$$\Delta = 10b-a,$$
entonces
$$r=\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta}$$
y por tanto
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta}.$$
Esto ya muestra que solo pueden contribuir los pares con \(\Delta>0\), es decir, con \(u^3<10v^3\).
Como \(r \ge 0\), debe cumplirse
$$a \cdot 10^{\ell-1} \ge b.$$
Luego la menor longitud posible es
$$\ell_{\min}=\min\left\{\ell \ge 1: a \cdot 10^{\ell-1} \ge b\right\}.$$
La implementación empieza precisamente por esta cota: antes de estudiar periodicidades, necesita la primera longitud en la que la cola puede ser no negativa.
También se necesita \(r<10^{\ell-1}\), pues de otro modo \(d\) no sería realmente la cifra inicial de un número de \(\ell\) cifras. Sustituyendo la expresión de \(r\), obtenemos
$$\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta} < 10^{\ell-1},$$
lo que equivale a
$$10^{\ell-1}\bigl(a(d+1)-10b\bigr) < db.$$
Si \(a(d+1)\ge 10b\), el lado izquierdo deja de tener el signo adecuado y la condición ya no puede producir una cifra inicial válida. Por eso toda cifra admisible debe satisfacer
$$a(d+1)<10b.$$
Una vez cumplida esta desigualdad estricta, la cota superior de \(r\) queda automáticamente garantizada.
La fórmula
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta}$$
exige que \(\Delta \mid d\,b\,(10^{\ell}-1)\). Pero la hipótesis \(\gcd(u,v)=1\) implica
$$\gcd(\Delta,b)=\gcd(10v^3-u^3,v^3)=1.$$
Así, el factor \(b\) puede eliminarse y la condición queda en
$$\Delta \mid d(10^{\ell}-1).$$
Si definimos
$$g=\gcd(\Delta,d),\qquad m=\frac{\Delta}{g},$$
esto se vuelve equivalente a
$$m \mid 10^{\ell}-1.$$
Una solución de \(10^{\ell}\equiv 1 \pmod m\) existe exactamente cuando \(\gcd(10,m)=1\). En ese caso, las longitudes válidas son los múltiplos de
$$\operatorname{ord}_m(10),$$
el orden multiplicativo de \(10\) módulo \(m\). Por tanto, para una cifra fija \(d\), la menor longitud válida es
$$\ell(d)=\left\lceil\frac{\ell_{\min}}{\operatorname{ord}_m(10)}\right\rceil \operatorname{ord}_m(10).$$
Entre todas las cifras \(d \in \{1,\dots,9\}\), se escoge primero la longitud más pequeña y, en caso de empate, la cifra inicial más pequeña. Si ninguna cifra sobrevive, la contribución del par es \(0\).
Aquí tenemos
$$a=1,\qquad b=8,\qquad \Delta=10 \cdot 8 - 1 = 79.$$
La mínima longitud cumple \(10^{\ell-1}\ge 8\), así que
$$\ell_{\min}=2.$$
Probemos con la menor cifra, \(d=1\). La restricción sobre la cifra es
$$a(d+1)=2<80=10b,$$
luego esa cifra es válida. Además \(\gcd(79,1)=1\), por lo que \(m=79\). Como \(79\) es coprimo con \(10\), resulta
$$\operatorname{ord}_{79}(10)=13.$$
Así, la menor longitud admisible es
$$\ell=13.$$
La fórmula cerrada da entonces
$$M(1,2)=\frac{1 \cdot 8(10^{13}-1)}{79}=1012658227848.$$
Al mover la primera cifra al final se obtiene \(126582278481\), que es exactamente \(\frac{1}{8}\) del número original, es decir, \(\left(\frac{1}{2}\right)^3\) veces el valor inicial.
Las implementaciones en C++, Python y Java siguen este razonamiento casi línea por línea. Primero construyen una criba de menor factor primo hasta \(10m^3\), suficiente para todos los denominadores \(\Delta\) y para las funciones phi que aparecen al calcular órdenes multiplicativos. Después recorren todos los pares coprimos \((u,v)\), calculan \(u^3\) y \(v^3\), y descartan inmediatamente los casos con \(u^3 \ge 10v^3\).
Para cada par que sobrevive, el algoritmo calcula \(\ell_{\min}\), prueba las cifras \(1,\dots,9\), verifica la desigualdad \(u^3(d+1)<10v^3\), reduce el denominador por \(\gcd(\Delta,d)\) y rechaza la cifra si el módulo reducido comparte factor con \(10\). En caso contrario, calcula el orden multiplicativo de \(10\) módulo ese valor reducido. Para ello parte de la función phi de Euler, la factoriza con la criba y va eliminando primos mientras la prueba de potencia modular correspondiente siga dando \(1\).
Una vez elegido el mejor par \((d,\ell)\), la contribución se evalúa como
$$\frac{d\,v^3\,(10^{\ell}-1)}{10v^3-u^3} \pmod{10^9+7}$$
mediante el inverso modular del denominador. La aritmética es la misma en los tres lenguajes; la variante en C++ además paraleliza segmentos independientes del bucle externo sobre \(u\).
Si \(B=10m^3\), la criba de menor factor primo cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria. La búsqueda principal examina \(O(m^2)\) pares y, como mucho, \(9\) cifras por par. Cada prueba de cifra realiza unos pocos gcd, varias potencias modulares y una reducción por factores primos sobre un valor tipo \(\varphi(m)\). En consecuencia, tras la criba el trabajo restante es casi cuadrático en \(m\), y la memoria está dominada claramente por la criba.
对每个满足 \(1 \le u,v \le m\) 且 \(\gcd(u,v)=1\) 的互素整数对 \((u,v)\)，我们要找最小的正整数 \(M(u,v)\)，使得把它的十进制首位数字移到末尾之后，新数恰好变成原数的 \(\left(\frac{u}{v}\right)^3\) 倍。如果这样的整数不存在，则该对的贡献记为 \(0\)。题目要求计算
$$T(m)=\sum_{\substack{1 \le u,v \le m\\ \gcd(u,v)=1}} M(u,v)\pmod{10^9+7}.$$
直接在十进制字符串上暴力搜索完全不可行，因此解法先把“首位移到末尾”的操作写成一个严格的整数方程，再把问题转化为整除性、欧拉函数和乘法阶的计算。
关键在于：不要把未知量看成一整个十进制数，而是把它拆成“首位数字”和“剩余尾部”，这样移位操作就能被精确地代数化。
设目标整数有 \(\ell\) 位，首位数字为 \(d \in \{1,\dots,9\}\)，其余部分为 \(r\)。那么
$$N=d \cdot 10^{\ell-1}+r,\qquad 0 \le r < 10^{\ell-1}.$$
把首位数字移到末尾后得到的新数为
$$S=10r+d.$$
再记
$$a=u^3,\qquad b=v^3.$$
题目的要求是
$$S=\frac{a}{b}N,$$
也就是
$$b(10r+d)=a(d \cdot 10^{\ell-1}+r).$$
整理后得到
$$r(10b-a)=d(a \cdot 10^{\ell-1}-b).$$
令
$$\Delta = 10b-a,$$
则有
$$r=\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta}$$
以及
$$N=d \cdot 10^{\ell-1}+r=\frac{d\,b\,(10^{\ell}-1)}{\Delta}.$$
由此立刻能看出，只有当 \(\Delta>0\)，也就是 \(u^3<10v^3\) 时，才可能存在正的候选数。
因为尾部 \(r\) 必须满足 \(r \ge 0\)，所以必须有
$$a \cdot 10^{\ell-1} \ge b.$$
因此最小可行位数是
$$\ell_{\min}=\min\left\{\ell \ge 1: a \cdot 10^{\ell-1} \ge b\right\}.$$
实现中正是先求出这个下界：在此之前讨论周期性没有意义，因为如果长度太短，尾部 \(r\) 连非负都做不到。
除了非负之外，还必须满足 \(r<10^{\ell-1}\)，否则 \(d\) 就不是真正的首位数字。把上面的 \(r\) 公式代入，得到
$$\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta} < 10^{\ell-1}.$$
进一步整理为
$$10^{\ell-1}\bigl(a(d+1)-10b\bigr) < db.$$
如果 \(a(d+1)\ge 10b\)，左边就不再具有我们需要的符号结构，这时不可能得到合法的首位数字。因此每个可用的首位数字都必须满足
$$a(d+1)<10b.$$
一旦这条严格不等式成立，\(r\) 的上界就自动安全，不需要再做额外的长度修补。
由
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta}$$
可知，要使 \(N\) 为整数，必须满足
$$\Delta \mid d\,b\,(10^{\ell}-1).$$
但由于 \(\gcd(u,v)=1\)，可以推出
$$\gcd(\Delta,b)=\gcd(10v^3-u^3,v^3)=1.$$
也就是说，分母与 \(b=v^3\) 没有公共因子，因此上式等价于
$$\Delta \mid d(10^{\ell}-1).$$
再设
$$g=\gcd(\Delta,d),\qquad m=\frac{\Delta}{g},$$
那么整数条件进一步化为
$$m \mid 10^{\ell}-1.$$
当且仅当 \(\gcd(10,m)=1\) 时，方程 \(10^{\ell}\equiv 1 \pmod m\) 才有解。此时所有可行的 \(\ell\) 都恰好是
$$\operatorname{ord}_m(10)$$
的倍数，其中 \(\operatorname{ord}_m(10)\) 表示 \(10\) 在模 \(m\) 意义下的乘法阶。因此，对于固定的首位数字 \(d\)，最小可行位数就是
$$\ell(d)=\left\lceil\frac{\ell_{\min}}{\operatorname{ord}_m(10)}\right\rceil \operatorname{ord}_m(10).$$
对每个 \((u,v)\)，算法遍历 \(d=1,\dots,9\)，先选最小的 \(\ell\)，如果位数相同，再选更小的首位数字。若所有数字都失败，则该对的贡献为 \(0\)。
这时
$$a=1,\qquad b=8,\qquad \Delta=10 \cdot 8 - 1 = 79.$$
因为必须有 \(10^{\ell-1}\ge 8\)，所以
$$\ell_{\min}=2.$$
先试最小首位 \(d=1\)。数字条件为
$$a(d+1)=2<80=10b,$$
因此这个首位是允许的。又因为 \(\gcd(79,1)=1\)，故 \(m=79\)。由于 \(79\) 与 \(10\) 互素，乘法阶存在，而且
$$\operatorname{ord}_{79}(10)=13.$$
所以最小可行位数为
$$\ell=13.$$
代入闭式可得
$$M(1,2)=\frac{1 \cdot 8(10^{13}-1)}{79}=1012658227848.$$
把首位数字移到末尾以后，得到 \(126582278481\)。这正好是原数的 \(\frac{1}{8}\)，也就是 \(\left(\frac{1}{2}\right)^3\) 倍，完全符合题意。
C++、Python 和 Java 三个实现都严格遵循上面的推导。首先建立一个到 \(10m^3\) 为止的最小质因子表，因为所有可能出现的分母 \(\Delta\) 以及后续乘法阶计算中用到的欧拉函数值都不会超过这个范围。随后枚举所有互素对 \((u,v)\)，计算 \(u^3\) 和 \(v^3\)，并立刻跳过 \(u^3 \ge 10v^3\) 的情形。
对每个保留下来的 pair，程序先求 \(\ell_{\min}\)，然后依次检查 \(1,\dots,9\) 这九个首位数字。每次先验证不等式 \(u^3(d+1)<10v^3\)，再用 \(\gcd(\Delta,d)\) 约分分母；如果约分后的模数和 \(10\) 不互素，则该数字不可能产生循环条件，直接丢弃。否则就计算 \(10\) 在这个模数下的乘法阶。做法是先求欧拉函数，再借助最小质因子表分解它，并在模幂测试仍然等于 \(1\) 的前提下，尽可能把候选阶中的质因子继续除掉。
最终选出最优的 \((d,\ell)\) 之后，贡献值按
$$\frac{d\,v^3\,(10^{\ell}-1)}{10v^3-u^3} \pmod{10^9+7}$$
计算，其中除法通过分母在模 \(10^9+7\) 下的逆元完成。三种语言的核心数论过程完全一致；只有 C++ 版本把外层关于 \(u\) 的独立区间做了并行化。
设 \(B=10m^3\)。建立最小质因子表需要 \(O(B\log\log B)\) 时间和 \(O(B)\) 空间。主循环要检查 \(O(m^2)\) 个候选对，而每对最多尝试 \(9\) 个首位数字。每个数字尝试包含若干次 gcd、若干次模幂，以及基于一个欧拉函数值的质因子剥离过程。因此，除去预处理以后，整体工作量对 \(m\) 来说接近二次；内存消耗则明显由最小质因子表主导。
Для каждой взаимно простой пары \((u,v)\) при \(1 \le u,v \le m\) нужно найти наименьшее положительное целое число, у которого можно перенести первую десятичную цифру в конец так, чтобы новое число стало ровно \(\left(\frac{u}{v}\right)^3\) от исходного. Если такого числа нет, вклад пары считается равным \(0\). Требуется вычислить
$$T(m)=\sum_{\substack{1 \le u,v \le m\\ \gcd(u,v)=1}} M(u,v)\pmod{10^9+7},$$
где \(M(u,v)\) обозначает это минимальное число. Прямой перебор десятичных записей невозможен, поэтому решение переводит операцию сдвига цифры в условие делимости и затем использует мультипликативный порядок.
Главная идея состоит в том, чтобы разложить неизвестное число на первую цифру и хвост, а затем полностью описать допустимые длины через модульную арифметику.
Пусть искомое число имеет \(\ell\) цифр, первую цифру \(d \in \{1,\dots,9\}\) и хвост \(r\). Тогда
$$N=d \cdot 10^{\ell-1}+r,\qquad 0 \le r < 10^{\ell-1}.$$
После переноса первой цифры в конец получаем
$$S=10r+d.$$
Обозначим
$$a=u^3,\qquad b=v^3.$$
Условие задачи имеет вид
$$S=\frac{a}{b}N,$$
то есть
$$b(10r+d)=a(d \cdot 10^{\ell-1}+r).$$
После перегруппировки получаем
$$r(10b-a)=d(a \cdot 10^{\ell-1}-b).$$
Положим
$$\Delta = 10b-a.$$
Тогда
$$r=\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta}$$
и, следовательно,
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta}.$$
Отсюда сразу видно, что вклад могут давать только пары с \(\Delta>0\), то есть с \(u^3<10v^3\).
Поскольку \(r \ge 0\), необходимо выполнение
$$a \cdot 10^{\ell-1} \ge b.$$
Значит, минимальная допустимая длина равна
$$\ell_{\min}=\min\left\{\ell \ge 1: a \cdot 10^{\ell-1} \ge b\right\}.$$
Именно эту нижнюю границу реализация вычисляет первой: до неё хвост \(r\) не может быть неотрицательным.
Кроме того, требуется \(r<10^{\ell-1}\); иначе \(d\) не была бы настоящей первой цифрой \(\ell\)-значного числа. Подставляя формулу для \(r\), получаем
$$\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta} < 10^{\ell-1},$$
а затем
$$10^{\ell-1}\bigl(a(d+1)-10b\bigr) < db.$$
Если \(a(d+1)\ge 10b\), левая часть теряет нужный знак, и корректная ведущая цифра уже невозможна. Поэтому всякая допустимая первая цифра должна удовлетворять условию
$$a(d+1)<10b.$$
Как только это строгое неравенство выполнено, верхняя граница для \(r\) автоматически становится корректной.
Из формулы
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta}$$
следует требование \(\Delta \mid d\,b\,(10^{\ell}-1)\). Но из \(\gcd(u,v)=1\) вытекает
$$\gcd(\Delta,b)=\gcd(10v^3-u^3,v^3)=1.$$
Следовательно, множитель \(b\) можно убрать, и условие упрощается до
$$\Delta \mid d(10^{\ell}-1).$$
Пусть
$$g=\gcd(\Delta,d),\qquad m=\frac{\Delta}{g}.$$
Тогда это равносильно условию
$$m \mid 10^{\ell}-1.$$
Сравнение \(10^{\ell}\equiv 1 \pmod m\) имеет решение тогда и только тогда, когда \(\gcd(10,m)=1\). В этом случае все допустимые длины являются кратными
$$\operatorname{ord}_m(10),$$
то есть мультипликативному порядку числа \(10\) по модулю \(m\). Поэтому для фиксированной цифры \(d\) минимальная допустимая длина равна
$$\ell(d)=\left\lceil\frac{\ell_{\min}}{\operatorname{ord}_m(10)}\right\rceil \operatorname{ord}_m(10).$$
Для каждой пары \((u,v)\) просматриваются все \(d=1,\dots,9\); сначала выбирается наименьшая длина \(\ell\), а при равенстве длин - меньшая первая цифра. Если ни одна цифра не подходит, вклад пары равен \(0\).
Здесь
$$a=1,\qquad b=8,\qquad \Delta=10 \cdot 8 - 1 = 79.$$
Минимальная длина должна удовлетворять \(10^{\ell-1}\ge 8\), значит
$$\ell_{\min}=2.$$
Пробуем минимальную цифру \(d=1\). Проверка цифры даёт
$$a(d+1)=2<80=10b,$$
поэтому цифра допустима. Так как \(\gcd(79,1)=1\), получаем \(m=79\). Число \(79\) взаимно просто с \(10\), следовательно, существует порядок
$$\operatorname{ord}_{79}(10)=13.$$
Значит, минимальная подходящая длина равна
$$\ell=13.$$
Тогда
$$M(1,2)=\frac{1 \cdot 8(10^{13}-1)}{79}=1012658227848.$$
Если перенести первую цифру в конец, получится \(126582278481\), то есть ровно \(\frac{1}{8}\) исходного числа, как и требует множитель \(\left(\frac{1}{2}\right)^3\).
Реализации на C++, Python и Java почти дословно повторяют это рассуждение. Сначала строится таблица наименьших простых делителей до \(10m^3\); этого достаточно для всех возникающих знаменателей \(\Delta\) и для значений функции Эйлера, используемых при вычислении порядка. Затем перебираются все взаимно простые пары \((u,v)\), вычисляются кубы \(u^3\) и \(v^3\), а случаи с \(u^3 \ge 10v^3\) сразу отбрасываются.
Для каждой оставшейся пары программа находит \(\ell_{\min}\), затем проверяет цифры \(1,\dots,9\). Для каждой цифры проверяется неравенство \(u^3(d+1)<10v^3\), знаменатель сокращается на \(\gcd(\Delta,d)\), и цифра отвергается, если сокращённый модуль имеет общий делитель с \(10\). Иначе вычисляется мультипликативный порядок числа \(10\) по этому модулю. Для этого реализация стартует с функции Эйлера, факторизует её с помощью таблицы простых делителей и поочерёдно удаляет простые множители, пока соответствующий тест модульного возведения в степень продолжает давать \(1\).
После выбора лучшей пары \((d,\ell)\) вклад вычисляется как
$$\frac{d\,v^3\,(10^{\ell}-1)}{10v^3-u^3} \pmod{10^9+7}$$
с использованием модульного обратного к знаменателю. Во всех трёх языках арифметика одинакова; версия на C++ дополнительно распараллеливает независимые диапазоны внешнего цикла по \(u\).
Пусть \(B=10m^3\). Построение таблицы наименьших простых делителей требует \(O(B\log\log B)\) времени и \(O(B)\) памяти. Основной перебор рассматривает \(O(m^2)\) пар и не более \(9\) цифр для каждой пары. Каждая проверка цифры включает несколько вычислений gcd, несколько модульных степеней и поэтапное сокращение кандидата на порядок по простым делителям значения типа \(\varphi(m)\). Поэтому после построения таблицы оставшаяся работа почти квадратична по \(m\), а память в основном расходуется именно на таблицу.
لكل زوج أولي نسبيًا \((u,v)\) بحيث \(1 \le u,v \le m\)، نبحث عن أصغر عدد صحيح موجب يمكن نقل رقمه العشري الأول إلى النهاية بحيث يصبح العدد الجديد مساويًا تمامًا لـ \(\left(\frac{u}{v}\right)^3\) من العدد الأصلي. إذا لم يوجد مثل هذا العدد فإن مساهمة هذا الزوج تساوي \(0\). المطلوب هو حساب
$$T(m)=\sum_{\substack{1 \le u,v \le m\\ \gcd(u,v)=1}} M(u,v)\pmod{10^9+7},$$
حيث تمثل \(M(u,v)\) هذا العدد الأدنى. البحث المباشر بين السلاسل العشرية غير عملي تمامًا، لذلك يحول الحل عملية الإزاحة إلى شرط قسمة دقيق ثم يستخدم الرتبة الضربية.
الفكرة الأساسية هي تفكيك العدد المجهول إلى رقم أول وبقية الذيل، ثم كتابة شرط الإزاحة على صورة معادلة عددية يمكن تحليلها بالكامل.
لنفرض أن العدد المطلوب له \(\ell\) خانات، ورقمه الأول هو \(d \in \{1,\dots,9\}\)، وبقيته هي \(r\). عندئذ
$$N=d \cdot 10^{\ell-1}+r,\qquad 0 \le r < 10^{\ell-1}.$$
وبعد نقل الرقم الأول إلى النهاية نحصل على
$$S=10r+d.$$
ولنضع أيضًا
$$a=u^3,\qquad b=v^3.$$
شرط المسألة هو
$$S=\frac{a}{b}N,$$
أي
$$b(10r+d)=a(d \cdot 10^{\ell-1}+r).$$
وبإعادة الترتيب نحصل على
$$r(10b-a)=d(a \cdot 10^{\ell-1}-b).$$
إذا عرفنا
$$\Delta = 10b-a,$$
فإن
$$r=\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta}$$
ومن ثم
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta}.$$
وهذا يبين مباشرة أن الأزواج الوحيدة التي يمكن أن تعطي مساهمة هي تلك التي تحقق \(\Delta>0\)، أي \(u^3<10v^3\).
بما أن \(r \ge 0\)، فلا بد أن يكون
$$a \cdot 10^{\ell-1} \ge b.$$
إذًا أصغر طول صالح هو
$$\ell_{\min}=\min\left\{\ell \ge 1: a \cdot 10^{\ell-1} \ge b\right\}.$$
وهذا بالضبط هو الحد الأدنى الذي تبدأ منه الخوارزمية: قبل هذه القيمة لا يمكن أن يكون الذيل \(r\) غير سالب أصلًا.
نحتاج أيضًا إلى الشرط \(r<10^{\ell-1}\)، وإلا فلن يكون \(d\) هو الرقم الأول الحقيقي لعدد ذي \(\ell\) خانات. بالتعويض عن \(r\) نحصل على
$$\frac{d(a \cdot 10^{\ell-1}-b)}{\Delta} < 10^{\ell-1}.$$
وبعد الترتيب يصبح الشرط
$$10^{\ell-1}\bigl(a(d+1)-10b\bigr) < db.$$
إذا كان \(a(d+1)\ge 10b\) فإن الطرف الأيسر لا يعود يحمل الإشارة المناسبة، وعندها لا يمكن الحصول على رقم أول صحيح. لذلك يجب أن يحقق كل رقم أول مقبول
$$a(d+1)<10b.$$
ومتى تحققت هذه المتباينة الصارمة، يصبح الحد الأعلى للذيل \(r\) مضمونًا تلقائيًا.
من الصيغة
$$N=\frac{d\,b\,(10^{\ell}-1)}{\Delta}$$
نحتاج إلى الشرط \(\Delta \mid d\,b\,(10^{\ell}-1)\). لكن لأن \(\gcd(u,v)=1\)، فإن
$$\gcd(\Delta,b)=\gcd(10v^3-u^3,v^3)=1.$$
لذلك يمكن حذف العامل \(b\)، ويصبح الشرط المكافئ هو
$$\Delta \mid d(10^{\ell}-1).$$
إذا عرفنا
$$g=\gcd(\Delta,d),\qquad m=\frac{\Delta}{g},$$
فإن المطلوب يصبح
$$m \mid 10^{\ell}-1.$$
المعادلة \(10^{\ell}\equiv 1 \pmod m\) تملك حلًا إذا وفقط إذا كان \(\gcd(10,m)=1\). في هذه الحالة تكون جميع الأطوال الصالحة مضاعفات لـ
$$\operatorname{ord}_m(10),$$
أي الرتبة الضربية للعدد \(10\) بترديد \(m\). ومن ثم فإن أصغر طول صالح لرقم أول ثابت \(d\) هو
$$\ell(d)=\left\lceil\frac{\ell_{\min}}{\operatorname{ord}_m(10)}\right\rceil \operatorname{ord}_m(10).$$
تجرب الخوارزمية الأرقام \(d=1,\dots,9\)، ثم تختار أصغر طول \(\ell\)، وعند التساوي تختار أصغر رقم أول. وإذا لم ينجح أي رقم، فإن مساهمة الزوج تساوي \(0\).
في هذه الحالة
$$a=1,\qquad b=8,\qquad \Delta=10 \cdot 8 - 1 = 79.$$
بما أن الشرط هو \(10^{\ell-1}\ge 8\)، فإن
$$\ell_{\min}=2.$$
نجرب أصغر رقم أول \(d=1\). شرط الرقم يصبح
$$a(d+1)=2<80=10b,$$
إذن هذا الرقم مقبول. كذلك \(\gcd(79,1)=1\)، ومن ثم \(m=79\). وبما أن \(79\) أولي نسبيًا مع \(10\)، فإن
$$\operatorname{ord}_{79}(10)=13.$$
إذًا أصغر طول صالح هو
$$\ell=13.$$
وعليه نحصل على
$$M(1,2)=\frac{1 \cdot 8(10^{13}-1)}{79}=1012658227848.$$
وعند نقل الرقم الأول إلى النهاية نحصل على \(126582278481\)، وهو بالضبط \(\frac{1}{8}\) من العدد الأصلي، أي يطابق \(\left(\frac{1}{2}\right)^3\).
تتبع تطبيقات C++ وPython وJava هذا الاشتقاق بشكل مباشر تقريبًا. في البداية تُبنى بنية أصغر عامل أولي حتى الحد \(10m^3\)، وهو حد يكفي لجميع القيم الممكنة لـ \(\Delta\) وكذلك لقيم دالة أويلر المستخدمة لاحقًا في حساب الرتبة. بعد ذلك تُفحَص جميع الأزواج المتباينة أوليًا \((u,v)\)، وتُحسب القيمتان \(u^3\) و\(v^3\)، وتُستبعَد فورًا الحالات التي تحقق \(u^3 \ge 10v^3\).
لكل زوج باقٍ، تحسب الشيفرة أولًا \(\ell_{\min}\)، ثم تختبر الأرقام \(1,\dots,9\). لكل رقم، تتحقق من المتباينة \(u^3(d+1)<10v^3\)، ثم تختزل المقام بواسطة \(\gcd(\Delta,d)\)، وترفض الرقم إذا كان المقام المختزل يشارك \(10\) عاملًا أوليًا. وإذا نجح الاختبار، تحسب الشيفرة الرتبة الضربية للعدد \(10\) بترديد ذلك المقام المختزل. ويتم ذلك بالانطلاق من دالة أويلر، ثم تحليلها إلى عوامل أولية باستخدام جدول العوامل الأولية الصغرى، ثم حذف هذه العوامل تدريجيًا ما دام اختبار القوى المعيارية لا يزال يعطي \(1\).
وبعد اختيار أفضل زوج \((d,\ell)\)، تُحسب المساهمة على الصورة
$$\frac{d\,v^3\,(10^{\ell}-1)}{10v^3-u^3} \pmod{10^9+7}$$
باستخدام المقلوب الضربي للمقام تحت الترديد. الحساب العددي نفسه واحد في اللغات الثلاث؛ وتضيف نسخة C++ فقط توزيعًا متوازيًا لمقاطع مستقلة من الحلقة الخارجية على \(u\).
إذا وضعنا \(B=10m^3\)، فإن بناء جدول أصغر عامل أولي يحتاج إلى زمن \(O(B\log\log B)\) وذاكرة \(O(B)\). أما البحث الرئيسي فيفحص \(O(m^2)\) زوجًا، ومع كل زوج ما لا يزيد على \(9\) أرقام أولى ممكنة. وكل محاولة تتضمن عدة حسابات gcd، وعدة أسس معيارية، وعملية اختزال لعوامل أولية مأخوذة من قيمة من نوع \(\varphi(m)\). لذلك، بعد مرحلة التمهيد، يكون الجهد المتبقي قريبًا من التربيعي في \(m\)، بينما تظل الذاكرة خاضعة أساسًا لجدول العوامل الأولية.