We seek the largest 10-digit number \(P\) that uses the digits \(0,1,\dots,9\) exactly once and can be written as a concatenation of decimal products
$$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$$
for some positive integer multiplier \(m\) and positive integers \(x_1,\dots,x_t\). The input-side concatenation
$$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$$
must also be 0-to-9 pandigital. All numbers are interpreted in ordinary decimal notation, so a multi-digit block may not begin with 0.
The crucial simplification is to search from the output side. Instead of guessing \(m\) and the multiplicands first, the implementation scans possible 10-digit pandigital outputs in descending order and asks whether each one can be decomposed into valid product blocks.
Take a candidate output string \(Y\). If \(Y\) is valid, then some choice of block boundaries turns it into decimal integers
$$Y=p_1\Vert p_2\Vert\cdots\Vert p_t,$$
where each block satisfies
$$p_i=m x_i.$$
So the entire problem becomes: choose a 10-digit pandigital output \(Y\), choose block boundaries, and check whether there exists a common multiplier \(m\) making the reconstructed input \(m\Vert x_1\Vert\cdots\Vert x_t\) pandigital as well.
A 10-digit string has 9 gaps between consecutive digits. Any nonempty subset of those gaps can be declared to be block boundaries, so there are
$$2^9-1=511$$
nontrivial partitions to test. This matches the decimal concatenation exactly: every valid identity produces one of these contiguous blockings, and every blocking gives a concrete list of product candidates \(p_1,\dots,p_t\).
Whenever a block would have more than one digit and start with 0, that partition is impossible in standard decimal notation and is discarded immediately.
Once a partition \(p_1,\dots,p_t\) is fixed, the multiplier is heavily constrained. Since \(p_i=m x_i\) for every \(i\), the multiplier must divide every block, hence
$$m\mid p_i\quad\text{for all }i,$$
and therefore
$$m\mid g,\qquad g=\gcd(p_1,p_2,\dots,p_t).$$
This is the key invariant used by all three implementations. It turns an open-ended search over possible multipliers into a finite divisor search. For a fixed partition, every feasible multiplier must be a divisor of one specific integer \(g\).
The gcd condition is not only necessary; it also tells us exactly what to test. If \(d\) is a divisor of \(g\), then the only possible multiplicands are
$$x_i=\frac{p_i}{d}.$$
So a fixed partition and a fixed divisor \(d\mid g\) produce exactly one candidate input concatenation:
$$I_d=d\Vert\frac{p_1}{d}\Vert\frac{p_2}{d}\Vert\cdots\Vert\frac{p_t}{d}.$$
No further freedom remains. Therefore the validation step is simple: compute \(g\), enumerate its divisors, rebuild \(I_d\), and check whether \(I_d\) uses the digits \(0\) through \(9\) exactly once. If it does, the chosen output partition is a genuine solution.
The classic 1-to-9 sample already shows the whole mechanism. Consider
$$763859124=7638\Vert59124.$$
With this partition,
$$g=\gcd(7638,59124)=6.$$
So the only possible common multipliers are the divisors of 6. Testing \(d=6\) gives
$$x_1=\frac{7638}{6}=1273,\qquad x_2=\frac{59124}{6}=9854,$$
hence the input-side concatenation
$$6\Vert1273\Vert9854=612739854,$$
which is 1-to-9 pandigital. Problem 170 asks for the same phenomenon with all ten digits \(0,\dots,9\) used exactly once. The code applies the same gcd-and-divisors argument to every 10-digit pandigital output candidate.
The outer search visits pandigital outputs in descending order. Because every candidate is a 10-digit number with nonzero leading digit, descending lexicographic order is the same as descending numeric order. The search is exhaustive for each output: every valid identity determines a unique output string, one of the 511 partitions of that string, and a multiplier among the divisors of the partition gcd. So when the algorithm finds the first valid output, no larger valid output can still be waiting later in the scan.
The C++, Python, and Java implementations all iterate over the digits \(9,8,\dots,0\) in descending permutation order and interpret each permutation as a candidate output string. Any permutation beginning with 0 is skipped, since it would not represent a 10-digit number.
For each output candidate, the implementation inspects every nonempty split mask on the 9 digit gaps. Each mask determines a contiguous partition into product blocks. Partitions that create a multi-digit block with a leading zero are rejected on the spot, and the remaining blocks are parsed as decimal integers.
After forming the product blocks, the implementation computes their gcd. It then enumerates the divisors of that gcd in descending order. For each divisor, it divides every block by that candidate multiplier, concatenates the multiplier and the resulting quotients, and performs a pandigital check on the 10-character input string.
If the reconstructed input is 0-to-9 pandigital, the output candidate is valid and the whole search stops immediately. The C++ and Java versions walk the descending permutations directly; the Python version reaches the same order by generating permutations and scanning them in reverse-sorted order. The mathematical test is identical in all three languages.
There are at most \(10!=3{,}628{,}800\) permutations of the digits \(0,\dots,9\), although candidates with leading zero are skipped. For each candidate output, the implementation examines all
$$2^9-1=511$$
nontrivial contiguous partitions. For one partition, it computes a gcd over a small number of blocks, enumerates the divisors of that gcd by trial division, and performs constant-size string checks because both the input and output concatenations always have length 10.
If \(M\) denotes the largest block value in a partition, a simple worst-case description is
$$O\!\left(10!\cdot 2^9\cdot \sqrt{M}\right),$$
with \(M\le 987654321\) because at least one split is always present. The memory usage is \(O(1)\) apart from short temporary lists of blocks and divisors. In practice the runtime is much smaller than the pessimistic bound because the scan terminates as soon as the largest valid output is found.
Gesucht ist die größte 10-stellige Zahl \(P\), die jede Ziffer \(0,1,\dots,9\) genau einmal verwendet und sich als Konkatenation von Dezimalprodukten schreiben lässt:
$$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$$
wobei \(m\) ein positiver gemeinsamer Multiplikator und \(x_1,\dots,x_t\) positive ganze Zahlen sind. Auch die Eingabeseite
$$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$$
muss 0-bis-9-pandigital sein. Alle Blöcke werden in gewöhnlicher Dezimalschreibweise gelesen; ein mehrstelliger Block darf also nicht mit 0 beginnen.
Die entscheidende Vereinfachung besteht darin, von der Ausgabeseite aus zu suchen. Statt zuerst \(m\) und die Faktoren \(x_i\) zu erraten, durchsucht die Implementierung die möglichen 10-stelligen pandigitalen Ausgaben absteigend und prüft, ob sich jede davon in gültige Produktblöcke zerlegen lässt.
Nehmen wir eine Kandidatenzeichenkette \(Y\). Ist \(Y\) gültig, dann gibt es eine Wahl von Blockgrenzen, so dass
$$Y=p_1\Vert p_2\Vert\cdots\Vert p_t$$
mit
$$p_i=m x_i$$
für alle \(i\). Damit reduziert sich das gesamte Problem auf Folgendes: Wähle eine 10-stellige pandigitale Ausgabe \(Y\), wähle Blockgrenzen und prüfe, ob es einen gemeinsamen Multiplikator \(m\) gibt, für den die rekonstruierte Eingabe \(m\Vert x_1\Vert\cdots\Vert x_t\) ebenfalls pandigital ist.
Eine 10-stellige Zeichenkette besitzt 9 Lücken zwischen aufeinanderfolgenden Ziffern. Jede nichtleere Teilmenge dieser Lücken kann als Blockgrenze gewählt werden. Also gibt es
$$2^9-1=511$$
nichttriviale Zerlegungen. Genau das bildet die Dezimalkonkatenation ab: Jede gültige Identität erzeugt eine dieser zusammenhängenden Blockungen, und jede Blockung liefert konkrete Produktkandidaten \(p_1,\dots,p_t\).
Sobald ein Block mehrstellig wäre und mit 0 beginnt, ist diese Zerlegung in normaler Dezimalschreibweise unmöglich und wird sofort verworfen.
Ist eine Zerlegung \(p_1,\dots,p_t\) fest gewählt, dann ist der Multiplikator stark eingeschränkt. Aus \(p_i=m x_i\) folgt für jedes \(i\)
$$m\mid p_i,$$
also insbesondere
$$m\mid g,\qquad g=\gcd(p_1,p_2,\dots,p_t).$$
Das ist das zentrale mathematische Invariante aller drei Implementierungen. Eine offene Suche über beliebige Multiplikatoren wird dadurch zu einer endlichen Teilersuche: Für eine feste Zerlegung kann nur ein Teiler dieses einen Wertes \(g\) überhaupt infrage kommen.
Die ggT-Bedingung ist nicht nur notwendig, sondern liefert auch genau die zu testenden Kandidaten. Ist \(d\) ein Teiler von \(g\), dann sind die einzigen möglichen Faktoren
$$x_i=\frac{p_i}{d}.$$
Damit erzeugen eine feste Zerlegung und ein fester Teiler \(d\mid g\) genau eine Eingabekonkatenation:
$$I_d=d\Vert\frac{p_1}{d}\Vert\frac{p_2}{d}\Vert\cdots\Vert\frac{p_t}{d}.$$
Es bleibt also keine weitere Freiheit mehr. Der Test lautet deshalb: ggT berechnen, seine Teiler aufzählen, \(I_d\) rekonstruieren und prüfen, ob \(I_d\) die Ziffern \(0\) bis \(9\) genau einmal verwendet. Falls ja, ist die gewählte Ausgabeblockung eine echte Lösung.
Schon das klassische 1-bis-9-Beispiel zeigt den gesamten Mechanismus:
$$763859124=7638\Vert59124.$$
Für diese Zerlegung gilt
$$g=\gcd(7638,59124)=6.$$
Also kommen nur die Teiler von 6 als gemeinsamer Multiplikator infrage. Für \(d=6\) erhält man
$$x_1=\frac{7638}{6}=1273,\qquad x_2=\frac{59124}{6}=9854,$$
also die Eingabekonkatenation
$$6\Vert1273\Vert9854=612739854,$$
und diese ist 1-bis-9-pandigital. Problem 170 verlangt dasselbe Phänomen mit allen zehn Ziffern \(0,\dots,9\). Der Code wendet daher dasselbe ggT-und-Teiler-Argument auf jede 10-stellige pandigitale Ausgabekandidatin an.
Die äußere Suche besucht die pandigitalen Ausgaben in absteigender Reihenfolge. Da jeder Kandidat eine 10-stellige Zahl mit von 0 verschiedener Anfangsziffer ist, stimmt die lexikographische Reihenfolge mit der numerischen Reihenfolge überein. Außerdem ist die Suche für jede Ausgabe vollständig: Jede echte Lösung bestimmt eindeutig ihre Ausgabefolge, eine der 511 Zerlegungen dieser Folge und einen Multiplikator unter den Teilern des entsprechenden ggT. Sobald also die erste gültige Ausgabe gefunden ist, kann es später in der Suche keine größere Lösung mehr geben.
Die C++-, Python- und Java-Implementierungen durchlaufen alle Permutationen der Ziffern \(9,8,\dots,0\) in absteigender Reihenfolge und interpretieren jede Permutation als möglichen Ausgabestring. Permutationen mit führender 0 werden übersprungen, weil sie keine 10-stellige Zahl darstellen.
Für jeden Ausgabekandidaten werden alle nichtleeren Schnittmasken auf den 9 Ziffernlücken betrachtet. Jede Maske definiert eine zusammenhängende Zerlegung in Produktblöcke. Erzeugt eine Zerlegung einen mehrstelligen Block mit führender 0, wird sie sofort verworfen; andernfalls werden die Blöcke als Dezimalzahlen eingelesen.
Nach dem Aufbau der Produktblöcke berechnet die Implementierung deren ggT. Danach werden die Teiler dieses ggT absteigend aufgezählt. Für jeden Teiler werden alle Blöcke durch den Kandidaten dividiert, der Multiplikator mit den Quotienten zusammengefügt und die resultierende 10-stellige Eingabe auf Pandigitalität geprüft.
Ist die rekonstruierte Eingabe 0-bis-9-pandigital, dann ist die Ausgabe gültig und die gesamte Suche endet sofort. C++ und Java laufen die absteigenden Permutationen direkt ab; Python erreicht dieselbe Reihenfolge, indem die Permutationen erzeugt und absteigend sortiert werden. Der mathematische Test ist in allen drei Sprachen derselbe.
Es gibt höchstens \(10!=3{,}628{,}800\) Permutationen der Ziffern \(0,\dots,9\), wobei Kandidaten mit führender 0 entfallen. Für jede Kandidatenausgabe untersucht die Implementierung alle
$$2^9-1=511$$
nichttrivialen zusammenhängenden Zerlegungen. Für eine einzelne Zerlegung wird ein ggT über wenige Blöcke berechnet, anschließend werden die Teiler dieses ggT per Probedivision bestimmt, und die Zeichenkettenprüfungen bleiben konstant klein, weil Ein- und Ausgabe stets Länge 10 haben.
Bezeichnet \(M\) den größten Blockwert einer Zerlegung, dann ist eine einfache Worst-Case-Beschreibung
$$O\!\left(10!\cdot 2^9\cdot \sqrt{M}\right),$$
wobei \(M\le 987654321\) gilt, da immer mindestens ein Schnitt vorhanden ist. Der Speicherbedarf ist \(O(1)\) abgesehen von kurzen temporären Listen für Blöcke und Teiler. Praktisch ist die Laufzeit deutlich kleiner als diese grobe Schranke, weil die Suche endet, sobald die größte gültige Ausgabe gefunden wurde.
Aranan sayı, \(0,1,\dots,9\) rakamlarının her birini tam bir kez kullanan en büyük 10 basamaklı \(P\) sayısıdır. Bu sayı, ortak bir \(m\) çarpanı ile oluşan çarpımların ardışık yazımı şeklinde olmalıdır:
$$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$$
burada \(m\) pozitif bir tamsayı, \(x_1,\dots,x_t\) de pozitif tamsayılardır. Ayrıca giriş tarafındaki birleşim
$$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$$
de 0'dan 9'a kadar tüm rakamları tam bir kez içermelidir. Bloklar olağan onluk yazımda okunur; bu yüzden çok basamaklı bir blok 0 ile başlayamaz.
Temel fikir aramayı girişten değil çıktıdan başlatmaktır. Yani önce \(m\) ve \(x_i\)'leri tahmin etmek yerine, kod 10 basamaklı pandigital çıktı adaylarını büyükten küçüğe tarar ve her adayın geçerli çarpım bloklarına ayrılıp ayrılamadığını sorar.
Bir çıktı adayı \(Y\) alalım. Eğer \(Y\) gerçekten geçerliyse, bazı kesme noktaları seçilerek
$$Y=p_1\Vert p_2\Vert\cdots\Vert p_t$$
şeklinde yazılabilir ve her blok için
$$p_i=m x_i$$
olur. Böylece problem şu hale gelir: 10 basamaklı pandigital bir çıktı \(Y\) seç, onu bitişik bloklara ayır ve bu blokları aynı anda bölen bir \(m\) bulunabiliyor mu diye kontrol et; sonra da yeniden kurulan giriş \(m\Vert x_1\Vert\cdots\Vert x_t\) pandigital mi diye bak.
10 basamaklı bir dizgede ardışık rakamlar arasında 9 boşluk vardır. Bu boşlukların boş olmayan herhangi bir alt kümesi blok sınırı seçilebilir. Dolayısıyla denenmesi gereken
$$2^9-1=511$$
adet önemsiz olmayan bölme vardır. Bu sayı tam olarak onluk birleşimin yapısına karşılık gelir: her geçerli özdeşlik, bu 511 bitişik bölmeden birini üretir ve her bölme somut çarpım adayları \(p_1,\dots,p_t\) verir.
Eğer herhangi bir blok birden fazla basamaklı olduğu halde 0 ile başlıyorsa, o bölme standart onluk gösterimde anlamsızdır ve hemen elenir.
Bir bölme \(p_1,\dots,p_t\) sabitlendiğinde, ortak çarpan çok ciddi biçimde kısıtlanır. Çünkü her \(i\) için \(p_i=m x_i\) olduğundan
$$m\mid p_i$$
olmalıdır. O halde özellikle
$$m\mid g,\qquad g=\gcd(p_1,p_2,\dots,p_t).$$
Üç çözüm dilinin de merkezindeki fikir budur. Sonsuz görünen çarpan araması, tek bir sayının bölenlerine indirgenir: sabit bir bölme için mümkün olan her \(m\), mutlaka bu \(g\)'nin bir böleni olmalıdır.
Bu EBOB koşulu yalnızca gerekli değildir; aynı zamanda test edilmesi gereken adayları tam olarak verir. Eğer \(d\), \(g\)'nin bir böleni ise mümkün olan tek girdiler
$$x_i=\frac{p_i}{d}$$
şeklindedir. Dolayısıyla sabit bir bölme ve sabit bir \(d\mid g\), tam olarak tek bir giriş birleşimi üretir:
$$I_d=d\Vert\frac{p_1}{d}\Vert\frac{p_2}{d}\Vert\cdots\Vert\frac{p_t}{d}.$$
Başka serbestlik kalmaz. Bu yüzden doğrulama adımı nettir: \(g\)'yi hesapla, bölenlerini sırala, her bölen için \(I_d\)'yi kur ve \(I_d\)'nin 0'dan 9'a kadar rakamları tam bir kez kullanıp kullanmadığını denetle. Sağlanıyorsa seçilen çıktı bölmesi gerçek bir çözümdür.
Klasik 1'den 9'a örneği bile bütün mekanizmayı gösterir:
$$763859124=7638\Vert59124.$$
Bu bölmede
$$g=\gcd(7638,59124)=6$$
olur. Demek ki ortak çarpan olarak yalnızca 6'nın bölenleri denenmelidir. \(d=6\) seçildiğinde
$$x_1=\frac{7638}{6}=1273,\qquad x_2=\frac{59124}{6}=9854$$
ve dolayısıyla
$$6\Vert1273\Vert9854=612739854$$
elde edilir; bu da 1'den 9'a pandigitaldir. Problem 170 aynı olguyu bu kez \(0,\dots,9\) rakamlarının tamamı için ister. Kod tam da bu nedenle aynı EBOB ve bölen yaklaşımını her 10 basamaklı pandigital çıktı adayına uygular.
Dış döngü çıktı adaylarını azalan sırada gezer. Her aday 10 basamaklı ve ilk basamağı sıfır olmayan bir sayı olduğu için, leksikografik sıralama ile sayısal sıralama aynıdır. Ayrıca arama her aday için eksiksizdir: gerçek bir çözüm, kendi çıktı dizgesini, bu dizgenin 511 bölmesinden birini ve o bölmenin EBOB'unun bölenlerinden biri olan gerçek çarpanı belirler. Bu yüzden ilk kabul edilen çıktı bulunduğu anda, daha büyük başka bir çözümün ileride kalmış olması imkansızdır.
C++, Python ve Java uygulamaları \(9,8,\dots,0\) rakamlarının permütasyonlarını azalan sırada gezer ve her permütasyonu bir çıktı dizgesi olarak yorumlar. İlk rakamı 0 olan permütasyonlar 10 basamaklı sayı vermediği için atlanır.
Her çıktı adayı için, 9 rakam boşluğu üzerindeki tüm boş olmayan kesme maskeleri denenir. Her maske, çıktıyı bitişik çarpım bloklarına ayırır. Bir maske çok basamaklı bir bloğu 0 ile başlatıyorsa anında reddedilir; aksi halde bloklar onluk tamsayılar olarak okunur.
Bloklar oluşturulduktan sonra uygulama bunların EBOB'unu hesaplar. Ardından bu EBOB'un bölenleri büyükten küçüğe denenir. Her bölen için bloklar bu aday çarpana bölünür, bölen ile bölüm değerleri birleştirilir ve oluşan 10 karakterlik giriş dizgesinin pandigital olup olmadığı sınanır.
Yeniden kurulan giriş 0'dan 9'a pandigitalse çıktı geçerlidir ve arama hemen durur. C++ ve Java sürümleri azalan permütasyonları doğrudan ilerletir; Python sürümü aynı sırayı tüm permütasyonları üretip ters sıralayarak elde eder. Matematiksel test üç dilde de aynıdır.
\(0,\dots,9\) rakamlarının en fazla \(10!=3{,}628{,}800\) permütasyonu vardır; başında 0 bulunanlar zaten elenir. Her çıktı adayı için uygulama
$$2^9-1=511$$
adet önemsiz olmayan bitişik bölmeyi inceler. Tek bir bölmede az sayıda blok üzerinde EBOB hesaplanır, sonra bu EBOB'un bölenleri deneme bölmesiyle üretilir ve hem giriş hem çıktı birleşimleri zaten 10 basamaklı olduğu için karakter kontrolleri sabit boyutludur.
Eğer \(M\), bir bölmedeki en büyük blok değerini gösterirse kaba bir üst sınır
$$O\!\left(10!\cdot 2^9\cdot \sqrt{M}\right)$$
şeklinde yazılabilir; burada en az bir kesme bulunduğundan \(M\le 987654321\) olur. Bellek kullanımı, kısa ömürlü blok ve bölen listeleri dışında \(O(1)\)'dir. Pratikte süre bu üst sınırdan çok daha küçüktür; çünkü arama en büyük geçerli çıktıyı bulduğu anda sonlanır.
Se busca el mayor número de 10 cifras \(P\) que use exactamente una vez cada dígito \(0,1,\dots,9\) y que pueda escribirse como concatenación de productos decimales
$$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$$
para algún multiplicador positivo \(m\) y enteros positivos \(x_1,\dots,x_t\). La concatenación de entrada
$$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$$
también debe ser pandigital de 0 a 9. Todos los bloques se interpretan en notación decimal ordinaria, así que un bloque de varias cifras no puede empezar con 0.
La simplificación decisiva consiste en buscar desde la salida. En lugar de adivinar primero \(m\) y los multiplicandos, la implementación recorre en orden descendente las posibles salidas pandigitales de 10 cifras y pregunta si cada una puede descomponerse en bloques de producto válidos.
Tomemos una cadena candidata \(Y\). Si \(Y\) es válida, entonces existe una elección de cortes tal que
$$Y=p_1\Vert p_2\Vert\cdots\Vert p_t,$$
donde cada bloque satisface
$$p_i=m x_i.$$
Por tanto, el problema completo pasa a ser: elegir una salida pandigital \(Y\), elegir una partición en bloques contiguos y comprobar si existe un multiplicador común \(m\) tal que la entrada reconstruida \(m\Vert x_1\Vert\cdots\Vert x_t\) también sea pandigital.
Una cadena de 10 cifras tiene 9 huecos entre cifras consecutivas. Cualquier subconjunto no vacío de esos huecos puede declararse frontera de bloque, de modo que hay
$$2^9-1=511$$
particiones no triviales que probar. Esto coincide exactamente con la estructura de la concatenación decimal: toda identidad válida induce una de esas particiones contiguas, y cada partición produce candidatos concretos \(p_1,\dots,p_t\).
Si una partición crea un bloque de varias cifras que empieza con 0, dicha interpretación no es válida en notación decimal estándar y se descarta inmediatamente.
Una vez fijada una partición \(p_1,\dots,p_t\), el multiplicador queda muy restringido. Como \(p_i=m x_i\) para todo \(i\), se tiene
$$m\mid p_i$$
para cada bloque, y en consecuencia
$$m\mid g,\qquad g=\gcd(p_1,p_2,\dots,p_t).$$
Este es el invariante matemático central de las tres implementaciones. La búsqueda de un multiplicador arbitrario se reduce a una búsqueda finita entre los divisores de un único número \(g\).
La condición del mcd no solo es necesaria; además dice exactamente qué hay que probar. Si \(d\) es un divisor de \(g\), entonces los únicos multiplicandos posibles son
$$x_i=\frac{p_i}{d}.$$
Por tanto, una partición fija y un divisor fijo \(d\mid g\) generan una sola concatenación de entrada:
$$I_d=d\Vert\frac{p_1}{d}\Vert\frac{p_2}{d}\Vert\cdots\Vert\frac{p_t}{d}.$$
No queda ninguna libertad adicional. Así, el paso de validación es directo: calcular \(g\), enumerar sus divisores, reconstruir \(I_d\) y comprobar si \(I_d\) usa exactamente una vez los dígitos \(0,\dots,9\). Si lo hace, la partición elegida de la salida corresponde a una solución real.
El ejemplo clásico de 1 a 9 ya contiene todo el mecanismo:
$$763859124=7638\Vert59124.$$
Con esa partición,
$$g=\gcd(7638,59124)=6.$$
Así, los únicos multiplicadores comunes posibles son los divisores de 6. Si probamos \(d=6\), obtenemos
$$x_1=\frac{7638}{6}=1273,\qquad x_2=\frac{59124}{6}=9854,$$
y por tanto
$$6\Vert1273\Vert9854=612739854,$$
que es pandigital de 1 a 9. El problema 170 pide exactamente el mismo fenómeno, pero usando ahora los diez dígitos \(0,\dots,9\). El código aplica ese mismo razonamiento de mcd y divisores a cada salida pandigital de 10 cifras.
El bucle externo visita las salidas pandigitales en orden descendente. Como todas son números de 10 cifras con primer dígito distinto de 0, el orden lexicográfico coincide con el orden numérico. Además, la búsqueda es exhaustiva para cada salida: toda identidad válida determina su cadena de salida, una de las 511 particiones de esa cadena y un multiplicador que aparece entre los divisores del mcd correspondiente. Por eso, cuando el algoritmo acepta la primera salida válida, ya se sabe que no puede existir otra mayor más adelante.
Las implementaciones en C++, Python y Java recorren las permutaciones de los dígitos \(9,8,\dots,0\) en orden descendente y tratan cada permutación como una salida candidata. Las permutaciones cuyo primer dígito es 0 se omiten porque no representan un número de 10 cifras.
Para cada salida candidata, la implementación examina todas las máscaras de corte no vacías sobre los 9 huecos entre cifras. Cada máscara determina una partición contigua en bloques de producto. Si una partición crea un bloque de varias cifras con cero inicial, se rechaza al instante; en caso contrario, los bloques se convierten en enteros decimales.
Una vez construidos los bloques, la implementación calcula su mcd. Después enumera en orden descendente los divisores de ese mcd. Para cada divisor divide todos los bloques, concatena el multiplicador con los cocientes resultantes y comprueba si la cadena de entrada de longitud 10 es pandigital.
Si la entrada reconstruida es pandigital de 0 a 9, la salida candidata es válida y la búsqueda termina inmediatamente. Las versiones en C++ y Java recorren directamente las permutaciones descendentes; la versión en Python alcanza el mismo orden generando las permutaciones y escaneándolas tras ordenarlas de mayor a menor. La prueba matemática es la misma en los tres casos.
Hay como máximo \(10!=3{,}628{,}800\) permutaciones de los dígitos \(0,\dots,9\), aunque se descartan las que empiezan por 0. Para cada salida candidata se examinan las
$$2^9-1=511$$
particiones contiguas no triviales. En una partición concreta se calcula un mcd de pocos bloques, se enumeran por división de prueba los divisores de ese mcd y se realizan comprobaciones sobre cadenas de tamaño constante, ya que tanto la entrada como la salida siempre tienen longitud 10.
Si \(M\) denota el mayor valor de bloque en una partición, una cota simple de peor caso es
$$O\!\left(10!\cdot 2^9\cdot \sqrt{M}\right),$$
con \(M\le 987654321\) porque siempre existe al menos un corte. El uso de memoria es \(O(1)\) salvo por listas temporales muy pequeñas de bloques y divisores. En la práctica el tiempo real es bastante menor, ya que el recorrido se detiene tan pronto como aparece la mayor salida válida.
题目要求寻找最大的 10 位数 \(P\)。这个数必须恰好使用数字 \(0,1,\dots,9\) 各一次，并且能够写成若干个十进制乘积的拼接：
$$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$$
其中 \(m\) 是正整数公共乘数，\(x_1,\dots,x_t\) 也是正整数。与此同时，输入侧的拼接
$$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$$
也必须是 0 到 9 的全数字数。所有块都按普通十进制解释，因此一个多位块不能以 0 开头。
真正的突破点在于从输出端反推，而不是从输入端正向枚举。也就是说，程序并不先猜测 \(m\) 和各个 \(x_i\)，而是按从大到小的顺序扫描所有 10 位全数字输出候选，判断它们能否被切分成合法的乘积块。
设某个输出候选字符串为 \(Y\)。如果它对应一个合法解，那么一定存在某种切分方式，使得
$$Y=p_1\Vert p_2\Vert\cdots\Vert p_t,$$
并且每一块都满足
$$p_i=m x_i.$$
于是整个问题就变成：选定一个 10 位全数字输出 \(Y\)，在其中选择块边界，得到若干连续块 \(p_1,\dots,p_t\)，然后检查是否存在公共乘数 \(m\)，使得重建出来的输入串 \(m\Vert x_1\Vert\cdots\Vert x_t\) 也恰好用完数字 \(0,\dots,9\) 各一次。
一个 10 位字符串在相邻数字之间共有 9 个空隙。任意非空子集都可以作为切分边界，因此需要检查的非平凡切分总数是
$$2^9-1=511.$$
这与题目中的十进制拼接完全对应：每一个真正的解都会在输出串上形成某一种连续分块，而每一种分块都会给出具体的乘积候选 \(p_1,\dots,p_t\)。
如果某个分块产生了一个多位数块且首位为 0，那么这种解释不符合通常的十进制写法，程序会立即跳过它。
一旦分块 \(p_1,\dots,p_t\) 固定，公共乘数 \(m\) 就不再是任意的。因为对每个 \(i\) 都有 \(p_i=m x_i\)，所以
$$m\mid p_i.$$
这意味着 \(m\) 一定整除所有块的最大公约数
$$m\mid g,\qquad g=\gcd(p_1,p_2,\dots,p_t).$$
这正是三份实现共同依赖的核心不变量。原本看似无限的 \(m\) 搜索，被压缩为对单个整数 \(g\) 的全部约数进行有限枚举。
最大公约数条件不仅是必要条件，而且直接给出全部应检验的候选。若 \(d\mid g\)，那么唯一可能的乘数前因子就是
$$x_i=\frac{p_i}{d}.$$
因此，固定一个分块，再固定一个约数 \(d\mid g\)，就只会得到一个输入拼接：
$$I_d=d\Vert\frac{p_1}{d}\Vert\frac{p_2}{d}\Vert\cdots\Vert\frac{p_t}{d}.$$
这一步没有任何额外自由度。于是验证流程十分直接：先求 \(g\)，再枚举 \(g\) 的约数，对每个约数构造 \(I_d\)，最后检查 \(I_d\) 是否恰好是 0 到 9 全数字。如果成立，这个输出分块就对应一个真正可行的题目构造。
经典的 1 到 9 例子已经完整展示了这种思路。考虑
$$763859124=7638\Vert59124.$$
对这个分块，有
$$g=\gcd(7638,59124)=6.$$
所以唯一可能的公共乘数只能是 6 的约数。测试 \(d=6\) 时得到
$$x_1=\frac{7638}{6}=1273,\qquad x_2=\frac{59124}{6}=9854,$$
从而输入侧拼接为
$$6\Vert1273\Vert9854=612739854,$$
它恰好是 1 到 9 的全数字数。Problem 170 只是把同一结构扩展到包含数字 0 的 10 位情形。程序所做的事情，就是把这一套“先分块，再求 gcd，再枚举约数”的逻辑应用到每一个 10 位全数字输出候选上。
外层搜索按从大到小的顺序枚举输出候选。由于每个候选都是首位非零的 10 位数，所以字典序降序与数值降序完全一致。另一方面，这个搜索对每个候选都是穷尽的：任何真实解都会确定一个输出字符串、该字符串的某一种连续切分，以及该切分 gcd 的某个约数作为真实乘数。因此，当算法第一次接受某个输出时，就已经证明不存在更大的合法输出还没有被看到。
C++、Python 和 Java 实现都会按降序处理数字 \(9,8,\dots,0\) 的排列，并把每个排列视为一个候选输出串。若排列首位为 0，则直接跳过，因为它不是一个真正的 10 位数。
对每个输出候选，程序都会枚举 9 个数字间隙上的所有非空切分掩码。每个掩码确定一种连续分块方式。若某种方式产生了以 0 开头的多位块，则立即丢弃；否则把每一块解析成整数。
得到各个乘积块后，程序先求它们的 gcd，然后按从大到小的顺序枚举这个 gcd 的所有约数。对每个约数，程序把所有块除以它，接着将该约数与所有商依次拼接，再对得到的 10 字符输入串做全数字检查。
如果重建出的输入串恰好是 0 到 9 全数字，那么当前输出候选就是合法解，搜索立即终止。C++ 和 Java 版本直接沿着降序排列向前推进；Python 版本通过生成排列并按逆序扫描来得到同样的顺序。三种语言实现的数学判定完全一致。
数字 \(0,\dots,9\) 的排列总数最多是 \(10!=3{,}628{,}800\)，其中首位为 0 的候选会被跳过。对每个输出候选，程序都要检查
$$2^9-1=511$$
种非平凡连续切分。对某一种切分，需要对少量块求 gcd，再用试除法枚举这个 gcd 的约数，并做常数规模的字符串检查，因为输入和输出的总长度始终都是 10。
如果记某个切分中的最大块值为 \(M\)，那么一个简单的最坏情况写法是
$$O\!\left(10!\cdot 2^9\cdot \sqrt{M}\right),$$
而这里由于总会至少有一个切分边界，所以 \(M\le 987654321\)。除去很短的临时块列表和约数列表外，额外空间是 \(O(1)\)。实际运行通常远小于这个悲观上界，因为一旦找到最大的合法输出，枚举就会立刻停止。
Нужно найти наибольшее 10-значное число \(P\), которое использует цифры \(0,1,\dots,9\) ровно по одному разу и представимо как конкатенация десятичных произведений
$$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$$
где \(m\) — общий положительный множитель, а \(x_1,\dots,x_t\) — положительные целые. При этом входная конкатенация
$$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$$
тоже должна быть 0-9-пандигитальной. Все блоки читаются в обычной десятичной записи, поэтому многозначный блок не может начинаться с нуля.
Главное упрощение состоит в том, чтобы искать с выходной стороны. Вместо того чтобы сначала угадывать \(m\) и множители \(x_i\), программа перебирает 10-значные пандигитальные выходы по убыванию и проверяет, можно ли разбить каждый из них на корректные блоки произведений.
Возьмем строку-кандидат \(Y\). Если она действительно является решением, то найдется такой выбор границ, что
$$Y=p_1\Vert p_2\Vert\cdots\Vert p_t,$$
причем каждый блок удовлетворяет равенству
$$p_i=m x_i.$$
Значит, вся задача сводится к следующему: выбрать пандигитальный выход \(Y\), разбить его на соседние блоки и проверить, существует ли общий множитель \(m\), при котором восстановленная входная конкатенация \(m\Vert x_1\Vert\cdots\Vert x_t\) тоже оказывается пандигитальной.
У 10-значной строки есть 9 промежутков между соседними цифрами. Любое непустое подмножество этих промежутков можно объявить границами блоков, поэтому всего требуется проверить
$$2^9-1=511$$
нетривиальных разбиений. Это в точности соответствует десятичной конкатенации: каждое реальное решение задает одно из таких непрерывных разбиений, и каждое разбиение порождает конкретные кандидаты \(p_1,\dots,p_t\).
Если какое-либо разбиение создает многозначный блок с ведущим нулем, такое толкование противоречит обычной десятичной записи и сразу отбрасывается.
После фиксации разбиения \(p_1,\dots,p_t\) общий множитель уже сильно ограничен. Из равенств \(p_i=m x_i\) следует, что
$$m\mid p_i$$
для каждого \(i\), а значит
$$m\mid g,\qquad g=\gcd(p_1,p_2,\dots,p_t).$$
Это и есть ключевой инвариант, на котором держатся все три реализации. Бесконечный на вид перебор множителей превращается в конечный перебор делителей одного числа \(g\).
Условие через НОД не только необходимо, но и полностью описывает, что нужно проверять. Если \(d\mid g\), то возможные множители \(x_i\) определяются единственным образом:
$$x_i=\frac{p_i}{d}.$$
Тем самым фиксированное разбиение и фиксированный делитель \(d\mid g\) задают ровно одну входную конкатенацию:
$$I_d=d\Vert\frac{p_1}{d}\Vert\frac{p_2}{d}\Vert\cdots\Vert\frac{p_t}{d}.$$
Никакой дополнительной свободы больше нет. Поэтому проверка проста: вычислить \(g\), перебрать его делители, построить \(I_d\) и проверить, использует ли \(I_d\) цифры \(0,\dots,9\) ровно по одному разу. Если да, выбранное разбиение выхода действительно соответствует решению.
Классический пример для цифр 1-9 уже показывает весь механизм:
$$763859124=7638\Vert59124.$$
Для такого разбиения
$$g=\gcd(7638,59124)=6.$$
Значит, общим множителем могут быть только делители числа 6. При \(d=6\) получаем
$$x_1=\frac{7638}{6}=1273,\qquad x_2=\frac{59124}{6}=9854,$$
и входная конкатенация принимает вид
$$6\Vert1273\Vert9854=612739854,$$
что является 1-9-пандигитальным числом. В задаче 170 требуется тот же самый эффект, но уже с использованием всех десяти цифр \(0,\dots,9\). Код именно это и делает: применяет одну и ту же схему «разбиение, НОД, делители» к каждому 10-значному пандигитальному выходу.
Внешний перебор идет по убыванию выходных кандидатов. Поскольку каждый кандидат — это 10-значное число с ненулевой первой цифрой, лексикографический порядок совпадает с числовым. Кроме того, проверка каждого кандидата полна: любое реальное решение определяет собственную выходную строку, одно из 511 разбиений этой строки и настоящий множитель среди делителей соответствующего НОД. Поэтому, как только алгоритм принимает первый выход, становится ясно, что большего допустимого выхода не существует.
Реализации на C++, Python и Java перебирают перестановки цифр \(9,8,\dots,0\) в порядке убывания и рассматривают каждую перестановку как выходную строку-кандидат. Перестановки с ведущим нулем пропускаются, потому что они не задают 10-значное число.
Для каждого кандидата программа рассматривает все непустые маски разрезов на 9 промежутках между цифрами. Каждая маска задает непрерывное разбиение на блоки произведений. Если разбиение создает многозначный блок с ведущим нулем, оно сразу отбрасывается; иначе блоки переводятся в десятичные целые числа.
После формирования блоков программа вычисляет их НОД, затем перечисляет делители этого НОД в порядке убывания. Для каждого делителя все блоки делятся на него, этот делитель конкатенируется с частными, а полученная входная строка длины 10 проверяется на точную пандигитальность.
Если восстановленная входная строка является 0-9-пандигитальной, то выходной кандидат корректен, и поиск завершается немедленно. В версиях на C++ и Java убывающие перестановки проходят напрямую; версия на Python получает тот же порядок, генерируя перестановки и просматривая их после обратной сортировки. Математический критерий во всех трех реализациях одинаков.
Всего существует не более \(10!=3{,}628{,}800\) перестановок цифр \(0,\dots,9\), хотя варианты с ведущим нулем отсекаются сразу. Для каждого выходного кандидата рассматриваются все
$$2^9-1=511$$
нетривиальных непрерывных разбиений. Для одного разбиения нужно вычислить НОД нескольких блоков, затем пробным делением перечислить делители этого НОД и выполнить проверки строк постоянного размера, поскольку и вход, и выход всегда имеют длину 10.
Если обозначить через \(M\) максимальное значение блока в разбиении, то простая грубая оценка сверху имеет вид
$$O\!\left(10!\cdot 2^9\cdot \sqrt{M}\right),$$
где \(M\le 987654321\), потому что хотя бы один разрез присутствует всегда. Память имеет порядок \(O(1)\), если не считать коротких временных списков блоков и делителей. На практике время гораздо меньше этого пессимистичного предела, поскольку перебор останавливается сразу после нахождения наибольшего допустимого выхода.
نريد إيجاد أكبر عدد مكوَّن من 10 خانات \(P\) يستخدم الأرقام \(0,1,\dots,9\) مرة واحدة لكل رقم، ويمكن كتابته على صورة دمج لعناصر ناتجة من ضربات عشرية:
$$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$$
حيث إن \(m\) مضاعِف موجب مشترك، و\(x_1,\dots,x_t\) أعداد صحيحة موجبة. كذلك يجب أن يكون دمج طرف الإدخال
$$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$$
عددًا بانديجيتال من 0 إلى 9 أيضًا. وكل كتلة تُقرأ بالصيغة العشرية المعتادة، لذلك لا يجوز أن تبدأ كتلة متعددة الخانات بالرقم 0.
الاختزال الحاسم هنا هو أن نبدأ من جهة الخرج لا من جهة الإدخال. بدلاً من تخمين \(m\) و\(x_i\) أولاً، يقوم الحل بفحص جميع مخارج البانديجيتال ذات العشر خانات بترتيب تنازلي، ثم يسأل: هل يمكن تقسيم هذا الخرج إلى كتل منتجات صحيحة؟
لنأخذ سلسلة خرج مرشحة \(Y\). إذا كانت هذه السلسلة تمثل حلاً صحيحًا، فلا بد أن توجد طريقة لتحديد حدود الكتل بحيث
$$Y=p_1\Vert p_2\Vert\cdots\Vert p_t,$$
مع تحقق
$$p_i=m x_i$$
لكل \(i\). إذن المسألة كلها تتحول إلى: اختيار خرج بانديجيتال \(Y\)، ثم اختيار حدود بين الخانات لتكوين كتل متجاورة، ثم التحقق مما إذا كان هناك مضاعِف مشترك \(m\) يجعل الإدخال المعاد بناؤه \(m\Vert x_1\Vert\cdots\Vert x_t\) بانديجيتال أيضًا.
السلسلة ذات العشر خانات تحتوي على 9 فراغات بين الخانات المتتالية. وكل مجموعة غير فارغة من هذه الفراغات يمكن اعتبارها حدودًا للكتل، ولذلك يوجد
$$2^9-1=511$$
تقسيمًا غير تافه يجب فحصه. وهذا يطابق معنى الدمج العشري تمامًا: كل حل حقيقي يعطي واحدًا من هذه التقسيمات المتجاورة، وكل تقسيم ينتج كتلًا محددة \(p_1,\dots,p_t\).
إذا كوَّن أي تقسيم كتلة متعددة الخانات تبدأ بصفر، فإن هذا التفسير غير مقبول في الكتابة العشرية العادية ويُرفض مباشرة.
بمجرد تثبيت التقسيم \(p_1,\dots,p_t\)، يصبح \(m\) مقيدًا بشدة. من العلاقة \(p_i=m x_i\) لكل \(i\) نحصل على
$$m\mid p_i,$$
ومن ثم
$$m\mid g,\qquad g=\gcd(p_1,p_2,\dots,p_t).$$
هذه هي الفكرة الرياضية المركزية في اللغات الثلاث. فبدلاً من البحث في جميع المضاعِفات الممكنة، يكفي أن نبحث بين قواسم عدد واحد فقط هو \(g\).
شرط القاسم المشترك الأكبر ليس مجرد شرط لازم، بل يحدد بالضبط ما ينبغي اختباره. فإذا كان \(d\) قاسمًا لـ \(g\)، فإن القيم الممكنة الوحيدة تكون
$$x_i=\frac{p_i}{d}.$$
وهكذا فإن تقسيمًا ثابتًا مع قاسم ثابت \(d\mid g\) ينتجان دمج إدخال واحدًا فقط:
$$I_d=d\Vert\frac{p_1}{d}\Vert\frac{p_2}{d}\Vert\cdots\Vert\frac{p_t}{d}.$$
ولا توجد حرية أخرى بعد ذلك. لهذا تصبح خطوة التحقق واضحة: نحسب \(g\)، نعدّد قواسمه، نبني \(I_d\) لكل قاسم، ثم نتحقق هل يستخدم \(I_d\) الأرقام \(0,\dots,9\) مرة واحدة بالضبط. إذا تحقق ذلك، فإن تقسيم الخرج المختار يمثل حلاً فعليًا.
حتى المثال الكلاسيكي للأرقام من 1 إلى 9 يكشف الآلية كاملة:
$$763859124=7638\Vert59124.$$
في هذا التقسيم نحصل على
$$g=\gcd(7638,59124)=6.$$
إذن المضاعِفات المشتركة الممكنة ليست إلا قواسم العدد 6. وعند تجربة \(d=6\) نجد
$$x_1=\frac{7638}{6}=1273,\qquad x_2=\frac{59124}{6}=9854,$$
ومن ثم يصبح طرف الإدخال
$$6\Vert1273\Vert9854=612739854,$$
وهو بانديجيتال من 1 إلى 9. في المسألة 170 نستخدم الفكرة نفسها ولكن مع جميع الأرقام \(0,\dots,9\). وهذا بالضبط ما يفعله الكود: يطبق منطق التقسيم و\(gcd\) والقواسم على كل خرج بانديجيتال مكوَّن من 10 خانات.
الحل الخارجي يمر على مخارج البانديجيتال بترتيب تنازلي. وبما أن كل مرشح هو عدد من 10 خانات ولا يبدأ بصفر، فإن الترتيب المعجمي التنازلي يساوي الترتيب العددي التنازلي. كذلك فإن الفحص لكل مرشح فحص شامل: أي حل صحيح يحدد سلسلة خرجه، ويحدد واحدًا من 511 تقسيمًا لهذه السلسلة، ويحدد مضاعِفه الحقيقي ضمن قواسم قيمة \(g\) المناسبة. لذلك، ما إن يُعثر على أول خرج صحيح حتى يكون من المستحيل أن يوجد خرج صحيح أكبر منه لم يُفحص بعد.
تقوم تطبيقات C++ وPython وJava باستعراض ترتيبات الأرقام \(9,8,\dots,0\) بترتيب تنازلي، وتتعامل مع كل ترتيب على أنه خرج مرشح. وإذا بدأ الترتيب بالرقم 0 فإنه يُتجاوز مباشرة لأنه لا يمثل عددًا من 10 خانات.
لكل خرج مرشح، يفحص التنفيذ جميع أقنعة القطع غير الفارغة على الفراغات التسعة بين الخانات. كل قناع يحدد تقسيمًا متجاورًا إلى كتل منتجات. وإذا أنشأ التقسيم كتلة متعددة الخانات تبدأ بصفر، يُرفض فورًا؛ وإلا تُحوَّل الكتل إلى أعداد صحيحة عشرية.
بعد تكوين الكتل، يحسب التنفيذ القاسم المشترك الأكبر بينها، ثم يعدد قواسم هذا القاسم بترتيب تنازلي. ولكل قاسم، يقسم جميع الكتل عليه، ثم يدمج القاسم مع نواتج القسمة، ثم يختبر هل السلسلة الناتجة ذات الطول 10 بانديجيتال من 0 إلى 9.
إذا كان الإدخال المعاد بناؤه بانديجيتال، فالخرج المرشح صحيح وتتوقف عملية البحث مباشرة. نسختا C++ وJava تتحركان مباشرة عبر الترتيبات التنازلية؛ أما نسخة Python فتصل إلى الترتيب نفسه عبر توليد الترتيبات ثم فحصها بعد ترتيبها تنازليًا. الاختبار الرياضي نفسه في اللغات الثلاث.
يوجد في أقصى الحالات \(10!=3{,}628{,}800\) ترتيبًا للأرقام \(0,\dots,9\)، مع حذف ما يبدأ بصفر. ولكل خرج مرشح يفحص التنفيذ
$$2^9-1=511$$
تقسيمًا متجاورًا غير تافه. وفي كل تقسيم يُحسب \(gcd\) لعدد صغير من الكتل، ثم تُعدَّد قواسمه بالقسمة التجريبية، ثم تُجرى اختبارات سلاسل ذات حجم ثابت لأن طول الإدخال والخرج دائمًا 10.
إذا رمزنا بأكبر قيمة كتلة في تقسيم ما إلى \(M\)، فيمكن وصف أسوأ حالة تقريبًا بالصيغة
$$O\!\left(10!\cdot 2^9\cdot \sqrt{M}\right),$$
ومع وجود قطع واحد على الأقل دائمًا نحصل على \(M\le 987654321\). واستهلاك الذاكرة هو \(O(1)\) باستثناء قوائم مؤقتة قصيرة للكتل والقواسم. عمليًا يكون الزمن أقل بكثير من هذا الحد المتحفظ، لأن الاستعراض يتوقف بمجرد العثور على أكبر خرج صحيح.