We look at proper fractions built from two-digit integers, so the numerator and denominator have the form \(10a+b\) and \(10c+d\) with \(1 \le a,c \le 9\) and \(0 \le b,d \le 9\). A fraction is interesting if cancelling one common digit by a mathematically invalid shortcut still leaves an equal fraction. The classic example is \(\frac{49}{98}=\frac{4}{8}\) after cancelling the 9s.
The problem asks for every non-trivial example of this phenomenon with numerator smaller than denominator, excluding the obvious zero-ending cases such as \(\frac{30}{50}\). After finding all such fractions, we multiply them and reduce the product to lowest terms; the required output is the denominator of that reduced product.
The three implementations all work by testing every two-digit proper fraction, but the search is guided by a small amount of algebra. Writing the digits explicitly shows exactly which cancellations are possible and which ones can never produce a genuine solution.
Write
$$N=10a+b,\qquad D=10c+d,\qquad N \lt D,$$
with \(a\) and \(c\) non-zero because \(N\) and \(D\) are two-digit numbers. A digit-cancelling step can only happen when one digit in the numerator equals one digit in the denominator. There are four positional patterns:
$$a=c,\qquad a=d,\qquad b=c,\qquad b=d.$$
After cancellation, the remaining one-digit fraction is respectively \(\frac{b}{d}\), \(\frac{b}{c}\), \(\frac{a}{d}\), or \(\frac{a}{c}\). The implementation checks all four.
If the common digit sits in the tens place of both numbers, then
$$\frac{10a+b}{10a+d}=\frac{b}{d}$$
implies
$$d(10a+b)=b(10a+d)\implies 10a(d-b)=0.$$
Because \(a \neq 0\), we must have \(d=b\), so \(10a+b=10a+d\). That makes the original fraction equal to 1, which contradicts \(N \lt D\).
If the common digit sits in the units place of both numbers, then
$$\frac{10a+b}{10c+b}=\frac{a}{c}$$
gives
$$c(10a+b)=a(10c+b)\implies b(c-a)=0.$$
For a non-trivial cancellation the cancelled digit is not zero, so \(b \neq 0\), forcing \(a=c\). Again numerator and denominator are equal, so there is no proper fraction. Therefore only the mixed-position cancellations can matter.
When the numerator's tens digit matches the denominator's units digit, \(a=d\), the cancellation rule would claim
$$\frac{10a+b}{10c+a}=\frac{b}{c}.$$
Cross-multiplication gives
$$c(10a+b)=b(10c+a)\implies a(10c-b)=9bc.$$
So any valid example in this branch must make \(a=\frac{9bc}{10c-b}\) a digit from 1 to 9.
When the numerator's units digit matches the denominator's tens digit, \(b=c\), the cancellation rule becomes
$$\frac{10a+b}{10b+d}=\frac{a}{d},$$
and cross-multiplication yields
$$d(10a+b)=a(10b+d)\implies d(9a+b)=10ab.$$
Equivalently,
$$d=\frac{10ab}{9a+b}.$$
This is the branch that produces all genuine solutions in the two-digit problem.
Take \(a=4\) and \(b=9\) in the \(b=c\) branch. Then
$$d=\frac{10ab}{9a+b}=\frac{10\cdot 4\cdot 9}{9\cdot 4+9}=\frac{360}{45}=8,$$
so we obtain
$$\frac{10a+b}{10b+d}=\frac{49}{98}=\frac{4}{8}=\frac{1}{2}.$$
Scanning the digit range \(1\) through \(9\) shows that the only non-trivial fractions are
$$\frac{16}{64}=\frac{1}{4},\qquad \frac{19}{95}=\frac{1}{5},\qquad \frac{26}{65}=\frac{2}{5},\qquad \frac{49}{98}=\frac{1}{2}.$$
The mixed case \(a=d\) produces no additional examples, so these four are the complete set.
It is easiest to multiply the simplified forms:
$$\frac{1}{4}\times\frac{1}{5}\times\frac{2}{5}\times\frac{1}{2}=\frac{1}{100}.$$
So after reduction to lowest terms, the denominator is \(100\). The implementations do not hard-code this fact; they multiply the original fractions they find and then reduce the final product with a greatest-common-divisor computation.
The C++, Python, and Java implementations all follow the same constant-space exhaustive search. They use integer arithmetic throughout, so no floating-point comparison is needed anywhere.
The implementation loops over every two-digit numerator and every larger two-digit denominator. Restricting to \(N \lt D\) automatically limits the search to proper fractions and prevents counting a solution twice in reversed order.
For each candidate, the two decimal digits of the numerator and denominator are extracted. The trivial case where both numbers end in zero is rejected immediately. Then the implementation checks the four possible ways a shared digit could line up: tens with tens, tens with units, units with tens, and units with units.
Whenever one pattern applies and the cancelled denominator digit is non-zero, the equality test is performed by cross-multiplication:
$$N \cdot D' = D \cdot N'.$$
This exactly matches the algebra above and avoids any rounding issues.
Every qualifying fraction contributes its original numerator and denominator to a running product. After the full sweep, the combined numerator and denominator are divided by their greatest common divisor. The denominator of that reduced product is returned as the answer. The C++ and Java versions also include small sanity checks that confirm \(\frac{49}{98}\) is accepted while \(\frac{30}{50}\) is rejected.
There are only \(90\) two-digit numbers, so the number of candidate proper fractions is
$$\binom{90}{2}=4005.$$
Each candidate requires a fixed amount of work: digit extraction, up to four pattern tests, and a few integer multiplications. The final GCD is also constant time for numbers of this size. Therefore the running time is \(O(1)\) for the actual Project Euler input, or \(O(R^2)\) if one imagines extending the same idea to all numbers below a bound \(R\). The space usage is \(O(1)\).
Gesucht sind echte Brüche aus zweistelligen Zahlen. Schreibe also Zähler und Nenner als \(10a+b\) bzw. \(10c+d\) mit \(1 \le a,c \le 9\) und \(0 \le b,d \le 9\). Interessant ist ein Bruch dann, wenn man eine gemeinsame Ziffer auf unzulässige Weise wegkürzt und trotzdem wieder einen gleichwertigen Bruch erhält. Das klassische Beispiel ist \(\frac{49}{98}=\frac{4}{8}\), wenn man die 9 streicht.
Die Aufgabe verlangt alle nicht-trivialen Beispiele dieser Art mit Zähler kleiner als Nenner. Offensichtliche Nullfälle wie \(\frac{30}{50}\) werden ausgeschlossen. Anschließend werden alle gefundenen Brüche multipliziert, vollständig gekürzt und der Nenner des Endprodukts bestimmt.
Die drei Implementierungen testen tatsächlich alle zweistelligen echten Brüche, aber ein wenig Algebra erklärt vorher, welche Kürzungen überhaupt in Frage kommen. Sobald man die Dezimalziffern explizit notiert, zerfällt das Problem in vier sehr kleine Fälle.
Setze
$$N=10a+b,\qquad D=10c+d,\qquad N \lt D.$$
Die Zehnerziffern \(a\) und \(c\) sind ungleich null, weil \(N\) und \(D\) zweistellig sind. Eine Ziffernkürzung ist nur möglich, wenn eine Ziffer des Zählers mit einer Ziffer des Nenners übereinstimmt. Es gibt genau vier Lagen:
$$a=c,\qquad a=d,\qquad b=c,\qquad b=d.$$
Nach dem Streichen bleibt dann jeweils \(\frac{b}{d}\), \(\frac{b}{c}\), \(\frac{a}{d}\) oder \(\frac{a}{c}\). Genau diese vier Möglichkeiten prüft der Code.
Falls die gemeinsame Ziffer in beiden Zahlen die Zehnerstelle ist, müsste gelten
$$\frac{10a+b}{10a+d}=\frac{b}{d}.$$
Durch Kreuzmultiplikation folgt
$$d(10a+b)=b(10a+d)\implies 10a(d-b)=0.$$
Wegen \(a \neq 0\) bleibt nur \(d=b\). Dann sind aber Zähler und Nenner gleich, also ist der Bruch nicht echt.
Liegt die gemeinsame Ziffer in beiden Zahlen an der Einerstelle, dann
$$\frac{10a+b}{10c+b}=\frac{a}{c}$$
und damit
$$c(10a+b)=a(10c+b)\implies b(c-a)=0.$$
Im nicht-trivialen Fall ist die gestrichene Ziffer nicht null, also \(b \neq 0\), und damit muss \(a=c\) gelten. Wieder sind Zähler und Nenner identisch. Deshalb bleiben nur die beiden gemischten Lagen übrig.
Wenn die Zehnerziffer des Zählers mit der Einerziffer des Nenners übereinstimmt, also \(a=d\), behauptet die naive Kürzung
$$\frac{10a+b}{10c+a}=\frac{b}{c}.$$
Kreuzmultiplikation liefert
$$c(10a+b)=b(10c+a)\implies a(10c-b)=9bc.$$
Jedes Beispiel in diesem Zweig müsste also \(a=\frac{9bc}{10c-b}\) als Ziffer zwischen 1 und 9 ergeben.
Wenn die Einerziffer des Zählers mit der Zehnerziffer des Nenners übereinstimmt, also \(b=c\), dann erhält man
$$\frac{10a+b}{10b+d}=\frac{a}{d},$$
und daraus
$$d(10a+b)=a(10b+d)\implies d(9a+b)=10ab.$$
Also
$$d=\frac{10ab}{9a+b}.$$
Genau dieser Zweig erzeugt die echten Lösungen des Problems.
Nehmen wir im Fall \(b=c\) die Ziffern \(a=4\) und \(b=9\). Dann ist
$$d=\frac{10ab}{9a+b}=\frac{10\cdot 4\cdot 9}{9\cdot 4+9}=\frac{360}{45}=8,$$
also
$$\frac{10a+b}{10b+d}=\frac{49}{98}=\frac{4}{8}=\frac{1}{2}.$$
Durch Prüfung aller Ziffern von \(1\) bis \(9\) findet man genau vier nicht-triviale Beispiele:
$$\frac{16}{64}=\frac{1}{4},\qquad \frac{19}{95}=\frac{1}{5},\qquad \frac{26}{65}=\frac{2}{5},\qquad \frac{49}{98}=\frac{1}{2}.$$
Der Zweig \(a=d\) liefert keine weiteren Treffer; damit ist die Liste vollständig.
Am einfachsten multipliziert man die bereits gekürzten Formen:
$$\frac{1}{4}\times\frac{1}{5}\times\frac{2}{5}\times\frac{1}{2}=\frac{1}{100}.$$
Nach vollständigem Kürzen ist der gesuchte Nenner also \(100\). Die Implementierungen setzen dieses Ergebnis nicht voraus, sondern multiplizieren zunächst die gefundenen Originalbrüche und kürzen erst am Ende per ggT.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe exhaustive Suche mit konstantem Speicher. Alle Vergleiche bleiben in der Ganzzahlarithmetik; Gleitkommazahlen werden nirgends benötigt.
Die Implementierung iteriert über jeden zweistelligen Zähler und jeden größeren zweistelligen Nenner. Die Bedingung \(N \lt D\) beschränkt die Suche sofort auf echte Brüche und verhindert doppelte Erfassung derselben Lösung in umgekehrter Reihenfolge.
Für jeden Kandidaten werden Zehner- und Einerziffer von Zähler und Nenner bestimmt. Der triviale Fall, dass beide Zahlen auf null enden, wird sofort ausgeschlossen. Danach testet die Implementierung die vier möglichen Ausrichtungen einer gemeinsamen Ziffer: Zehner mit Zehner, Zehner mit Einer, Einer mit Zehner und Einer mit Einer.
Wenn ein Muster passt und die gekürzte Nennerziffer nicht null ist, wird die Gleichheit per Kreuzmultiplikation geprüft:
$$N \cdot D' = D \cdot N'.$$
Damit wird exakt die mathematische Bedingung umgesetzt, ohne Rundungsprobleme zu riskieren.
Jeder gültige Bruch wird mit seinem ursprünglichen Zähler und Nenner in ein laufendes Produkt übernommen. Nach dem vollständigen Durchlauf wird dieses Gesamtprodukt durch den größten gemeinsamen Teiler gekürzt. Zurückgegeben wird der Nenner des gekürzten Produkts. Die C++- und Java-Versionen enthalten zusätzlich kleine Plausibilitätsprüfungen: \(\frac{49}{98}\) muss akzeptiert werden, \(\frac{30}{50}\) dagegen nicht.
Es gibt nur \(90\) zweistellige Zahlen, also insgesamt
$$\binom{90}{2}=4005$$
mögliche echte Brüche mit Zähler kleiner als Nenner. Jeder Kandidat verursacht nur konstanten Aufwand: Ziffern extrahieren, höchstens vier Fallprüfungen und einige ganzzahlige Multiplikationen. Auch die abschließende ggT-Berechnung ist für diese Größen konstant. Daher ist die Laufzeit für die konkrete Aufgabe \(O(1)\), oder allgemeiner \(O(R^2)\), wenn man dieselbe Idee auf alle Zahlen unterhalb einer Schranke \(R\) übertragen würde. Der Speicherbedarf ist \(O(1)\).
Burada pay ve payda iki basamaklı sayılardır; yani kesri \(10a+b\) ve \(10c+d\) biçiminde yazabiliriz. Koşullar \(1 \le a,c \le 9\) ve \(0 \le b,d \le 9\) şeklindedir. İlginç olan durum, ortak bir rakamı yanlış biçimde sadeleştirdiğimiz halde kesrin değeri değişmiyorsa ortaya çıkar. En bilinen örnek \(\frac{49}{98}=\frac{4}{8}\) eşitliğidir.
Soruda, payı paydasından küçük olan bütün önemsiz olmayan örnekler istenir. \(\frac{30}{50}\) gibi sondaki sıfırların iptal edilmesinden doğan bariz durumlar dahil değildir. Bu kesirlerin hepsi çarpıldıktan sonra sonuç en sade hale getirilir ve istenen çıktı bu son kesrin paydasıdır.
Üç uygulamanın da yaptığı şey bütün iki basamaklı uygun kesirleri denemektir; fakat küçük bir cebirsel analiz, hangi iptal biçimlerinin gerçekten anlamlı olabileceğini hemen gösterir. Basamakları açıkça yazınca problem dört küçük duruma ayrılır.
Şöyle yazalım:
$$N=10a+b,\qquad D=10c+d,\qquad N \lt D.$$
\(a\) ve \(c\) sıfır olamaz; çünkü \(N\) ve \(D\) iki basamaklıdır. Ortak bir rakamı iptal etmek için paydaki bir rakamın paydadaki bir rakama eşit olması gerekir. Olası dört hizalanma şunlardır:
$$a=c,\qquad a=d,\qquad b=c,\qquad b=d.$$
Bunların ardından geriye sırasıyla \(\frac{b}{d}\), \(\frac{b}{c}\), \(\frac{a}{d}\) ve \(\frac{a}{c}\) kalır. Kod bu dört olasılığın hepsini test eder.
Ortak rakam iki sayıda da onlar basamağındaysa
$$\frac{10a+b}{10a+d}=\frac{b}{d}$$
olmalıdır. Çapraz çarpım
$$d(10a+b)=b(10a+d)\implies 10a(d-b)=0$$
sonucunu verir. \(a \neq 0\) olduğundan zorunlu olarak \(d=b\) olur; bu da pay ile paydayı eşit yapar. Oysa biz \(N \lt D\) istiyoruz.
Ortak rakam iki sayıda da birler basamağındaysa
$$\frac{10a+b}{10c+b}=\frac{a}{c}$$
ve buradan
$$c(10a+b)=a(10c+b)\implies b(c-a)=0$$
elde edilir. Önemsiz olmayan durumda iptal edilen rakam sıfır değildir, dolayısıyla \(b \neq 0\) ve mecburen \(a=c\) olur. Bu da yine pay ile paydayı aynı yapar. Demek ki yalnızca karışık konumlu iki durum gerçek adaydır.
Payın onlar basamağı, paydanın birler basamağıyla aynıysa \(a=d\) olur ve sözde sadeleştirme
$$\frac{10a+b}{10c+a}=\frac{b}{c}$$
şeklindedir. Çapraz çarpım
$$c(10a+b)=b(10c+a)\implies a(10c-b)=9bc$$
verir. Yani bu dalda bir çözüm olması için \(a=\frac{9bc}{10c-b}\) ifadesinin 1 ile 9 arasında tam bir rakam vermesi gerekir.
Payın birler basamağı, paydanın onlar basamağıyla aynıysa \(b=c\) olur ve bu kez
$$\frac{10a+b}{10b+d}=\frac{a}{d}$$
yazılır. Buradan
$$d(10a+b)=a(10b+d)\implies d(9a+b)=10ab$$
ve dolayısıyla
$$d=\frac{10ab}{9a+b}$$
elde edilir. Bu problemde gerçek çözümlerin tamamı bu ikinci karışık daldan gelir.
\(b=c\) dalında \(a=4\) ve \(b=9\) seçelim. O zaman
$$d=\frac{10ab}{9a+b}=\frac{10\cdot 4\cdot 9}{9\cdot 4+9}=\frac{360}{45}=8,$$
yani
$$\frac{10a+b}{10b+d}=\frac{49}{98}=\frac{4}{8}=\frac{1}{2}.$$
\(1\) ile \(9\) arasındaki rakamlar tarandığında bulunan önemsiz olmayan dört kesir şunlardır:
$$\frac{16}{64}=\frac{1}{4},\qquad \frac{19}{95}=\frac{1}{5},\qquad \frac{26}{65}=\frac{2}{5},\qquad \frac{49}{98}=\frac{1}{2}.$$
\(a=d\) dalı ek bir örnek üretmez; dolayısıyla liste tamdır.
En rahat yol, sadeleşmiş halleri çarpmaktır:
$$\frac{1}{4}\times\frac{1}{5}\times\frac{2}{5}\times\frac{1}{2}=\frac{1}{100}.$$
Böylece en sade biçimdeki sonucun paydası \(100\) olur. Uygulamalar bu sonucu hazır kabul etmez; önce bulunan asıl kesirleri çarpar, sonra toplam çarpımı EBOB ile sadeleştirir.
C++, Python ve Java uygulamaları aynı sabit-bellekli kapsamlı taramayı yapar. Karşılaştırmaların tamamı tamsayı aritmetiği ile yürütüldüğü için kayan noktalı sayılara ihtiyaç kalmaz.
Uygulama bütün iki basamaklı payları ve onlardan büyük bütün iki basamaklı paydaları dolaşır. \(N \lt D\) koşulu hem yalnızca uygun kesirleri bırakır hem de aynı çözümün ters çevrilmiş biçimde ikinci kez sayılmasını önler.
Her aday için payın ve paydanın onlar ve birler basamakları çıkarılır. Her iki sayının da sıfırla bittiği önemsiz durum hemen elenir. Sonra ortak rakamın gelebileceği dört hizalanma denenir: onlar-onlar, onlar-birler, birler-onlar ve birler-birler.
Bir hizalanma uygunsa ve sadeleştirilmiş payda sıfır değilse, eşitlik şu çapraz çarpım testiyle doğrulanır:
$$N \cdot D' = D \cdot N'.$$
Bu test, yukarıdaki cebirin doğrudan kod karşılığıdır ve yuvarlama hatası üretmez.
Geçerli her kesrin özgün payı ve paydası koşan bir çarpıma eklenir. Tüm tarama tamamlandığında bu birleşik pay ve payda en büyük ortak bölen ile sadeleştirilir. Cevap olarak sadeleşmiş ürünün paydası döndürülür. C++ ve Java sürümlerinde ayrıca \(\frac{49}{98}\) örneğinin kabul edildiğini ve \(\frac{30}{50}\) örneğinin reddedildiğini kontrol eden küçük doğrulamalar da vardır.
Yalnızca \(90\) tane iki basamaklı sayı bulunduğu için aday uygun kesir sayısı
$$\binom{90}{2}=4005$$
kadardır. Her aday için yapılan iş sabittir: basamak ayırma, en çok dört durum testi ve birkaç tamsayı çarpımı. Son EBOB hesabı da bu büyüklüklerde sabit sayılabilecek kadar küçüktür. Bu yüzden gerçek Project Euler girdisi için çalışma süresi \(O(1)\), aynı fikrin üst sınırı \(R\) olan daha genel bir aralıkta uygulanması halinde ise \(O(R^2)\) olarak düşünülebilir. Bellek kullanımı \(O(1)\) olur.
Buscamos fracciones propias formadas por números de dos cifras. Es decir, escribimos numerador y denominador como \(10a+b\) y \(10c+d\), con \(1 \le a,c \le 9\) y \(0 \le b,d \le 9\). Una fracción es interesante cuando cancelar un dígito común de una forma matemáticamente inválida deja, de todos modos, una fracción equivalente. El ejemplo clásico es \(\frac{49}{98}=\frac{4}{8}\) al cancelar los 9.
La tarea pide encontrar todos los ejemplos no triviales con numerador menor que denominador, excluyendo casos obvios con ceros finales como \(\frac{30}{50}\). Después se multiplican todas esas fracciones, se reduce el producto a términos mínimos y se devuelve el denominador final.
Las tres implementaciones prueban todas las fracciones propias de dos cifras, pero antes de eso conviene escribir el problema con álgebra elemental. Al separar las cifras decimales, se ve enseguida qué cancelaciones pueden funcionar y cuáles son imposibles.
Tomemos
$$N=10a+b,\qquad D=10c+d,\qquad N \lt D.$$
Las cifras \(a\) y \(c\) no pueden ser cero porque \(N\) y \(D\) tienen dos cifras. Para que exista una cancelación de dígitos, alguna cifra del numerador debe coincidir con alguna del denominador. Hay exactamente cuatro patrones posicionales:
$$a=c,\qquad a=d,\qquad b=c,\qquad b=d.$$
Después de cancelar, la fracción de una cifra que queda sería \(\frac{b}{d}\), \(\frac{b}{c}\), \(\frac{a}{d}\) o \(\frac{a}{c}\), respectivamente. La implementación comprueba las cuatro posibilidades.
Si el dígito común está en la posición de las decenas en ambos números, entonces
$$\frac{10a+b}{10a+d}=\frac{b}{d}.$$
Al multiplicar en cruz obtenemos
$$d(10a+b)=b(10a+d)\implies 10a(d-b)=0.$$
Como \(a \neq 0\), necesariamente \(d=b\). Eso hace que numerador y denominador sean iguales, así que la fracción ya no es propia.
Si el dígito común está en la posición de las unidades en ambos números, entonces
$$\frac{10a+b}{10c+b}=\frac{a}{c}$$
y por tanto
$$c(10a+b)=a(10c+b)\implies b(c-a)=0.$$
En una cancelación no trivial el dígito cancelado no es cero, luego \(b \neq 0\) y forzosamente \(a=c\). De nuevo numerador y denominador coinciden. Por eso solo sobreviven los dos casos mixtos.
Cuando la cifra de las decenas del numerador coincide con la cifra de las unidades del denominador, \(a=d\), la cancelación ingenua diría
$$\frac{10a+b}{10c+a}=\frac{b}{c}.$$
La multiplicación en cruz da
$$c(10a+b)=b(10c+a)\implies a(10c-b)=9bc.$$
Así, cualquier solución en esta rama debe hacer que \(a=\frac{9bc}{10c-b}\) sea un dígito entero entre 1 y 9.
Cuando la cifra de las unidades del numerador coincide con la cifra de las decenas del denominador, \(b=c\), se obtiene
$$\frac{10a+b}{10b+d}=\frac{a}{d},$$
y de ahí
$$d(10a+b)=a(10b+d)\implies d(9a+b)=10ab.$$
Por tanto
$$d=\frac{10ab}{9a+b}.$$
Esta es la rama que produce todas las soluciones reales del problema.
Tomemos \(a=4\) y \(b=9\) dentro de la rama \(b=c\). Entonces
$$d=\frac{10ab}{9a+b}=\frac{10\cdot 4\cdot 9}{9\cdot 4+9}=\frac{360}{45}=8,$$
de modo que
$$\frac{10a+b}{10b+d}=\frac{49}{98}=\frac{4}{8}=\frac{1}{2}.$$
Al recorrer las cifras de \(1\) a \(9\), aparecen exactamente cuatro fracciones no triviales:
$$\frac{16}{64}=\frac{1}{4},\qquad \frac{19}{95}=\frac{1}{5},\qquad \frac{26}{65}=\frac{2}{5},\qquad \frac{49}{98}=\frac{1}{2}.$$
La rama \(a=d\) no aporta más ejemplos, así que esta lista es completa.
La forma más limpia de multiplicarlas es usar sus versiones ya simplificadas:
$$\frac{1}{4}\times\frac{1}{5}\times\frac{2}{5}\times\frac{1}{2}=\frac{1}{100}.$$
Por tanto, una vez reducido el producto, el denominador es \(100\). Las implementaciones no codifican este resultado de antemano; multiplican las fracciones originales encontradas y solo al final aplican una reducción por máximo común divisor.
Las versiones en C++, Python y Java siguen exactamente la misma búsqueda exhaustiva con espacio constante. Todo se hace con aritmética entera, de modo que no hay comparaciones en coma flotante.
La implementación recorre todos los numeradores de dos cifras y todos los denominadores de dos cifras mayores que ellos. La restricción \(N \lt D\) deja solo fracciones propias y evita contar una misma solución dos veces en orden invertido.
Para cada candidato se extraen las cifras de decenas y unidades del numerador y del denominador. El caso trivial en que ambos terminan en cero se descarta de inmediato. Después se prueban los cuatro alineamientos posibles del dígito compartido: decenas con decenas, decenas con unidades, unidades con decenas y unidades con unidades.
Cuando un alineamiento aplica y la cifra restante del denominador no es cero, la igualdad se comprueba mediante multiplicación en cruz:
$$N \cdot D' = D \cdot N'.$$
Eso implementa exactamente la condición matemática sin introducir errores de redondeo.
Cada fracción válida aporta su numerador y denominador originales a un producto acumulado. Al terminar el barrido completo, ese producto global se reduce por su máximo común divisor. El valor devuelto es el denominador del producto ya reducido. Las implementaciones en C++ y Java incluyen además pequeñas comprobaciones de cordura: \(\frac{49}{98}\) debe aceptarse y \(\frac{30}{50}\) debe rechazarse.
Solo existen \(90\) números de dos cifras, así que el número de fracciones propias candidatas es
$$\binom{90}{2}=4005.$$
Cada candidato requiere trabajo constante: extraer cifras, probar como mucho cuatro patrones y realizar unas pocas multiplicaciones enteras. El cálculo final del máximo común divisor también es constante para estos tamaños. Por ello, el tiempo total es \(O(1)\) para la instancia concreta de Project Euler, o \(O(R^2)\) si se generaliza la misma idea a todos los números menores que una cota \(R\). El uso de memoria es \(O(1)\).
本题讨论由两位数组成的真分数。把分子和分母分别写成 \(10a+b\) 与 \(10c+d\)，其中 \(1 \le a,c \le 9\)，\(0 \le b,d \le 9\)，并且要求分子小于分母。所谓“数字约消”现象，是指把分子和分母中的一个公共数字直接删掉，虽然这种做法在一般情况下并不合法，但最后得到的分数值居然和原分数相同。最经典的例子就是 \(\frac{49}{98}=\frac{4}{8}\)。
题目要求找出所有这种非平凡的两位数例子，排除 \(\frac{30}{50}\) 这类尾零造成的显然情况。找到全部分数后，将它们相乘并约成最简分数，最终需要给出最简形式下的分母。
三个实现都采用了对所有两位数真分数进行穷举检查的方法，但在真正枚举之前，先做一点代数整理可以把问题的结构看得非常清楚。把十位和个位拆开以后，哪些约消位置根本不可能成立，哪些位置值得检查，就一目了然了。
设
$$N=10a+b,\qquad D=10c+d,\qquad N \lt D.$$
由于 \(N\) 和 \(D\) 都是两位数，所以 \(a\) 与 \(c\) 不能为零。要发生“约掉一个公共数字”的操作，必须是分子的一位数字恰好等于分母的一位数字。按位置区分，一共只有四种可能：
$$a=c,\qquad a=d,\qquad b=c,\qquad b=d.$$
删去公共数字后，剩下的一位数分数分别是 \(\frac{b}{d}\)、\(\frac{b}{c}\)、\(\frac{a}{d}\) 和 \(\frac{a}{c}\)。实现代码正是逐一检查这四种排列方式。
如果公共数字同时位于两个数的十位，那么就必须满足
$$\frac{10a+b}{10a+d}=\frac{b}{d}.$$
交叉相乘得到
$$d(10a+b)=b(10a+d)\implies 10a(d-b)=0.$$
因为 \(a \neq 0\)，只能推出 \(d=b\)。这意味着 \(10a+b=10a+d\)，也就是分子和分母相等，不可能是题目要求的真分数。
如果公共数字同时位于两个数的个位，那么
$$\frac{10a+b}{10c+b}=\frac{a}{c}$$
从而有
$$c(10a+b)=a(10c+b)\implies b(c-a)=0.$$
非平凡约消排除了把零直接删掉的情形，所以此处 \(b \neq 0\)，只能得到 \(a=c\)。这样分子和分母再次相等，仍然不符合 \(N \lt D\)。因此，真正需要检查的只有两个“交叉位置”的情况。
第一种交叉情况是分子的十位等于分母的个位，即 \(a=d\)。这时错误约消会声称
$$\frac{10a+b}{10c+a}=\frac{b}{c}.$$
交叉相乘后得到
$$c(10a+b)=b(10c+a)\implies a(10c-b)=9bc.$$
也就是说，这一支上的任何解都必须让 \(a=\frac{9bc}{10c-b}\) 恰好成为 \(1\) 到 \(9\) 之间的整数数字。
第二种交叉情况是分子的个位等于分母的十位，即 \(b=c\)。这时约消后的形式为
$$\frac{10a+b}{10b+d}=\frac{a}{d},$$
从而
$$d(10a+b)=a(10b+d)\implies d(9a+b)=10ab.$$
整理后可写成
$$d=\frac{10ab}{9a+b}.$$
本题中所有真正的非平凡解都来自这一分支。
取 \(b=c\) 这一分支中的 \(a=4\)、\(b=9\)。由上式可得
$$d=\frac{10ab}{9a+b}=\frac{10\cdot 4\cdot 9}{9\cdot 4+9}=\frac{360}{45}=8,$$
于是得到
$$\frac{10a+b}{10b+d}=\frac{49}{98}=\frac{4}{8}=\frac{1}{2}.$$
把 \(1\) 到 \(9\) 的数字全部检查一遍后，恰好只会出现四个非平凡分数：
$$\frac{16}{64}=\frac{1}{4},\qquad \frac{19}{95}=\frac{1}{5},\qquad \frac{26}{65}=\frac{2}{5},\qquad \frac{49}{98}=\frac{1}{2}.$$
\(a=d\) 那一支不会产生新的例子，因此上面四个就是完整答案集合。
最方便的做法是先乘它们约消后的形式：
$$\frac{1}{4}\times\frac{1}{5}\times\frac{2}{5}\times\frac{1}{2}=\frac{1}{100}.$$
所以最简分数的分母就是 \(100\)。不过实现并没有把这个结果写死，而是先把找到的原始分数全部乘起来，再用最大公约数把最终乘积约到最简。
C++、Python 和 Java 三个实现的核心流程完全一致，都是常数空间下的穷举搜索。整个判断过程只使用整数运算，不需要浮点比较。
实现会遍历所有两位数分子，以及所有比它更大的两位数分母。条件 \(N \lt D\) 自动保证只考虑真分数，同时也避免把同一个答案以倒置顺序重复统计。
对每一个候选分数，先取出分子和分母的十位与个位。若两者都以零结尾，则立刻判为题目排除的平凡情形。接着依次检查公共数字可能出现的四种位置关系：十位对十位、十位对个位、个位对十位、个位对个位。
只要某一种位置关系成立，并且约消后留下的分母数字不为零，就通过交叉相乘来判断两个分数是否相等：
$$N \cdot D' = D \cdot N'.$$
这样做与上面的代数推导完全一致，而且不会出现浮点误差。
每发现一个合格分数，就把它原始的分子和分母乘入累计乘积。全部候选都检查完以后，再对总分子和总分母求最大公约数，并据此约成最简分数。返回值就是最简形式下的分母。C++ 和 Java 版本还额外带有小型自检：\(\frac{49}{98}\) 必须被接受，而 \(\frac{30}{50}\) 必须被排除。
两位数总共只有 \(90\) 个，因此可能的真分数候选数为
$$\binom{90}{2}=4005.$$
每个候选只需要常数量工作：拆分数字、最多检查四种位置关系、做几次整数乘法。最后一次最大公约数计算在这样的小整数范围内也仍然是常数级成本。所以对这道具体题目来说，运行时间是 \(O(1)\)；如果把同样思路推广到所有小于某个上界 \(R\) 的数，那么时间复杂度可写成 \(O(R^2)\)。空间复杂度始终是 \(O(1)\)。
Рассматриваются правильные дроби, составленные из двузначных чисел. Значит, числитель и знаменатель можно записать как \(10a+b\) и \(10c+d\), где \(1 \le a,c \le 9\), \(0 \le b,d \le 9\), и при этом числитель меньше знаменателя. Интерес представляют те случаи, когда мы неверно “сокращаем” общую цифру, но значение дроби все равно остается тем же. Классический пример: \(\frac{49}{98}=\frac{4}{8}\).
Нужно найти все такие нетривиальные дроби, исключив очевидные случаи с конечными нулями вроде \(\frac{30}{50}\). Затем эти дроби перемножаются, результат сокращается до несократимого вида, и требуется вернуть знаменатель итоговой дроби.
Во всех трех реализациях используется полный перебор всех двузначных правильных дробей, но небольшое алгебраическое разложение заранее показывает, какие варианты сокращения вообще могут дать ответ. Если явно выписать десятки и единицы, задача распадается на четыре позиционных случая.
Обозначим
$$N=10a+b,\qquad D=10c+d,\qquad N \lt D.$$
Цифры \(a\) и \(c\) не равны нулю, поскольку \(N\) и \(D\) двузначны. Чтобы “сократить цифру”, нужно, чтобы одна цифра числителя совпадала с одной цифрой знаменателя. Есть ровно четыре взаимных расположения:
$$a=c,\qquad a=d,\qquad b=c,\qquad b=d.$$
После такого сокращения остаются соответственно дроби \(\frac{b}{d}\), \(\frac{b}{c}\), \(\frac{a}{d}\) и \(\frac{a}{c}\). Реализация проверяет все четыре варианта.
Если общая цифра стоит в разряде десятков у обоих чисел, то должно выполняться
$$\frac{10a+b}{10a+d}=\frac{b}{d}.$$
Перемножая крест-накрест, получаем
$$d(10a+b)=b(10a+d)\implies 10a(d-b)=0.$$
Так как \(a \neq 0\), отсюда следует \(d=b\). Но тогда \(10a+b=10a+d\), то есть числитель равен знаменателю, а дробь уже не является правильной.
Если общая цифра стоит в разряде единиц у обоих чисел, то
$$\frac{10a+b}{10c+b}=\frac{a}{c}$$
и потому
$$c(10a+b)=a(10c+b)\implies b(c-a)=0.$$
В нетривиальном случае сокращаемая цифра не ноль, значит \(b \neq 0\), и остается только \(a=c\). Снова числитель равен знаменателю. Следовательно, содержательными остаются лишь два смешанных случая.
Если цифра десятков числителя совпадает с цифрой единиц знаменателя, то \(a=d\), и наивное сокращение дает
$$\frac{10a+b}{10c+a}=\frac{b}{c}.$$
Крестовое умножение приводит к формуле
$$c(10a+b)=b(10c+a)\implies a(10c-b)=9bc.$$
Значит, любой ответ в этой ветви должен делать число \(a=\frac{9bc}{10c-b}\) целой цифрой от 1 до 9.
Если же цифра единиц числителя совпадает с цифрой десятков знаменателя, то \(b=c\), и мы получаем
$$\frac{10a+b}{10b+d}=\frac{a}{d},$$
откуда
$$d(10a+b)=a(10b+d)\implies d(9a+b)=10ab.$$
То есть
$$d=\frac{10ab}{9a+b}.$$
Именно эта ветвь порождает все настоящие решения в задаче о двузначных дробях.
Возьмем в ветви \(b=c\) значения \(a=4\) и \(b=9\). Тогда
$$d=\frac{10ab}{9a+b}=\frac{10\cdot 4\cdot 9}{9\cdot 4+9}=\frac{360}{45}=8,$$
поэтому
$$\frac{10a+b}{10b+d}=\frac{49}{98}=\frac{4}{8}=\frac{1}{2}.$$
Если перебрать все цифры от \(1\) до \(9\), то окажется, что нетривиальных дробей ровно четыре:
$$\frac{16}{64}=\frac{1}{4},\qquad \frac{19}{95}=\frac{1}{5},\qquad \frac{26}{65}=\frac{2}{5},\qquad \frac{49}{98}=\frac{1}{2}.$$
Ветвь \(a=d\) не дает дополнительных примеров, так что этот список полон.
Удобнее всего перемножить уже сокращенные формы:
$$\frac{1}{4}\times\frac{1}{5}\times\frac{2}{5}\times\frac{1}{2}=\frac{1}{100}.$$
Следовательно, знаменатель окончательной несократимой дроби равен \(100\). Однако реализации не опираются на заранее известный ответ: они перемножают исходные найденные дроби и только потом сокращают общий результат по НОД.
Реализации на C++, Python и Java используют один и тот же перебор с постоянным объемом памяти. Все сравнения выполняются в целых числах, поэтому плавающая точка нигде не нужна.
Программа проходит по всем двузначным числителям и всем большим двузначным знаменателям. Ограничение \(N \lt D\) сразу оставляет только правильные дроби и не позволяет дважды посчитать одно и то же решение в обратном порядке.
Для каждого кандидата извлекаются цифры десятков и единиц у числителя и знаменателя. Тривиальный случай, когда оба числа оканчиваются нулем, сразу отбрасывается. После этого проверяются все четыре способа выравнивания общей цифры: десятки с десятками, десятки с единицами, единицы с десятками и единицы с единицами.
Если некоторое расположение подходит и оставшаяся цифра знаменателя не равна нулю, равенство дробей проверяется через крестовое умножение:
$$N \cdot D' = D \cdot N'.$$
Это точная программная форма тех же алгебраических условий и при этом без ошибок округления.
Каждая подходящая дробь вносит свой исходный числитель и знаменатель в накопленное произведение. Когда перебор завершен, общий числитель и общий знаменатель делятся на их наибольший общий делитель. Возвращается знаменатель уже сокращенного произведения. В версиях на C++ и Java есть также небольшие проверки здравого смысла: \(\frac{49}{98}\) должна приниматься, а \(\frac{30}{50}\) должна отклоняться.
Двузначных чисел всего \(90\), поэтому число кандидатов на правильные дроби равно
$$\binom{90}{2}=4005.$$
На каждый кандидат тратится постоянное время: выделить цифры, проверить не более четырех случаев и сделать несколько целочисленных умножений. Финальное вычисление НОД тоже имеет постоянную стоимость для таких маленьких значений. Поэтому для конкретной задачи время работы равно \(O(1)\), а в обобщенном варианте для всех чисел ниже границы \(R\) та же идея имела бы сложность \(O(R^2)\). Использование памяти равно \(O(1)\).
نحن نبحث في كسور حقيقية مكوَّنة من أعداد ذات رقمين. لذلك يمكن كتابة البسط والمقام على الصورة \(10a+b\) و\(10c+d\)، حيث \(1 \le a,c \le 9\) و\(0 \le b,d \le 9\)، مع الشرط \(N \lt D\). الحالة المثيرة هنا هي أن نحذف رقمًا مشتركًا من البسط والمقام بطريقة غير صحيحة حسابيًا، ومع ذلك يبقى الكسر الناتج مساويًا للكسر الأصلي. المثال الأشهر هو \(\frac{49}{98}=\frac{4}{8}\).
المطلوب هو إيجاد جميع الأمثلة غير التافهة من هذا النوع، مع استبعاد الحالات الواضحة الناتجة من الأصفار النهائية مثل \(\frac{30}{50}\). بعد ذلك نضرب جميع هذه الكسور، ثم نختزل الناتج إلى أبسط صورة، والمطلوب في النهاية هو مقام هذا الناتج المختزل.
التنفيذات الثلاثة تعتمد بالفعل على فحص جميع الكسور الحقيقية ذات الرقمين، لكن قليلًا من الجبر يوضّح مسبقًا أي أنماط الإلغاء تستحق الفحص وأيها مستحيل من الأصل. عندما نكتب الأعداد من خلال خانتي العشرات والآحاد، ينقسم السؤال إلى أربع حالات موضعية صغيرة جدًا.
لنكتب
$$N=10a+b,\qquad D=10c+d,\qquad N \lt D.$$
الرقمان \(a\) و\(c\) غير صفريين لأن \(N\) و\(D\) عددان مكوَّنان من رقمين. ولكي يحدث “إلغاء رقم”، لا بد أن يساوي أحد رقمي البسط أحد رقمي المقام. توجد أربع محاذيات ممكنة فقط:
$$a=c,\qquad a=d,\qquad b=c,\qquad b=d.$$
بعد الإلغاء يبقى على الترتيب الكسر \(\frac{b}{d}\) أو \(\frac{b}{c}\) أو \(\frac{a}{d}\) أو \(\frac{a}{c}\). التنفيذ يفحص هذه الأنماط الأربعة كلها.
إذا كان الرقم المشترك في خانة العشرات في العددين معًا، فيلزم أن
$$\frac{10a+b}{10a+d}=\frac{b}{d}.$$
وبالضرب التبادلي نحصل على
$$d(10a+b)=b(10a+d)\implies 10a(d-b)=0.$$
وبما أن \(a \neq 0\)، فلا بد أن يكون \(d=b\). عندئذ يصبح البسط مساويًا للمقام، وهذا يناقض شرط أن الكسر حقيقي.
أما إذا كان الرقم المشترك في خانة الآحاد في العددين معًا، فلدينا
$$\frac{10a+b}{10c+b}=\frac{a}{c}$$
ومنها
$$c(10a+b)=a(10c+b)\implies b(c-a)=0.$$
في الحالة غير التافهة يكون الرقم المحذوف غير صفري، أي \(b \neq 0\)، ومن ثم يلزم \(a=c\). وهذا يعيدنا مرة أخرى إلى بسط يساوي المقام. لذلك لا يبقى إلا الحالتان المختلطتان.
إذا كانت خانة العشرات في البسط مساوية لخانة الآحاد في المقام، أي \(a=d\)، فإن الإلغاء الساذج يدّعي أن
$$\frac{10a+b}{10c+a}=\frac{b}{c}.$$
وبالضرب التبادلي نحصل على
$$c(10a+b)=b(10c+a)\implies a(10c-b)=9bc.$$
إذن أي حل في هذا الفرع يجب أن يجعل \(a=\frac{9bc}{10c-b}\) رقمًا صحيحًا بين 1 و9.
أما إذا كانت خانة الآحاد في البسط مساوية لخانة العشرات في المقام، أي \(b=c\)، فإن صورة الإلغاء تصبح
$$\frac{10a+b}{10b+d}=\frac{a}{d},$$
ومنها
$$d(10a+b)=a(10b+d)\implies d(9a+b)=10ab.$$
وبالتالي
$$d=\frac{10ab}{9a+b}.$$
هذا هو الفرع الذي ينتج جميع الكسور الصحيحة غير التافهة في مسألة العددين ذوي الرقمين.
لنأخذ \(a=4\) و\(b=9\) في فرع \(b=c\). عندها
$$d=\frac{10ab}{9a+b}=\frac{10\cdot 4\cdot 9}{9\cdot 4+9}=\frac{360}{45}=8,$$
ومن ثم
$$\frac{10a+b}{10b+d}=\frac{49}{98}=\frac{4}{8}=\frac{1}{2}.$$
وعند فحص جميع الأرقام من \(1\) إلى \(9\)، نجد أن الكسور غير التافهة الوحيدة هي
$$\frac{16}{64}=\frac{1}{4},\qquad \frac{19}{95}=\frac{1}{5},\qquad \frac{26}{65}=\frac{2}{5},\qquad \frac{49}{98}=\frac{1}{2}.$$
أما فرع \(a=d\) فلا ينتج أي أمثلة إضافية، ولذلك فهذه القائمة كاملة.
أسهل طريقة هي ضرب الصور المختزلة مباشرة:
$$\frac{1}{4}\times\frac{1}{5}\times\frac{2}{5}\times\frac{1}{2}=\frac{1}{100}.$$
إذن مقام الناتج في أبسط صورة هو \(100\). ومع ذلك فالتنفيذ لا يضع هذه النتيجة مسبقًا، بل يضرب الكسور الأصلية التي يعثر عليها ثم يختزل الحاصل النهائي باستعمال القاسم المشترك الأكبر.
تنفيذات C++ وPython وJava تتبع الفكرة نفسها تمامًا: تعداد شامل مع استخدام مساحة ثابتة. كل المقارنات تُجرى بالحساب الصحيح، لذلك لا توجد أي حاجة إلى الأعداد العشرية.
تدور الشيفرة على كل بسط مكوَّن من رقمين، وعلى كل مقام مكوَّن من رقمين وأكبر منه. القيد \(N \lt D\) يضمن أننا نتعامل فقط مع الكسور الحقيقية، كما يمنع عدَّ الحل نفسه مرة ثانية بترتيب معكوس.
لكل كسر مرشح، تُستخرج خانتا العشرات والآحاد في البسط والمقام. الحالة التافهة التي ينتهي فيها العددان بصفر تُستبعد مباشرة. بعد ذلك تفحص الشيفرة الأنماط الأربعة الممكنة لاصطفاف الرقم المشترك: عشرات مع عشرات، عشرات مع آحاد، آحاد مع عشرات، وآحاد مع آحاد.
إذا انطبق أحد الأنماط، وكان المقام بعد الإلغاء غير صفري، فإن اختبار التساوي يتم بالضرب التبادلي:
$$N \cdot D' = D \cdot N'.$$
هذا يطابق الجبر السابق تمامًا، ويتجنب أي مشاكل ناتجة من المقارنة العشرية.
كل كسر صالح يضيف بسطه الأصلي ومقامه الأصلي إلى حاصل ضرب تراكمي. وبعد انتهاء المسح الكامل، يُختزل البسط الكلي والمقام الكلي بواسطة القاسم المشترك الأكبر. القيمة المعادة هي مقام الحاصل المختزل. كما أن نسختي C++ وJava تحتويان على فحوصات صغيرة للتأكد من أن \(\frac{49}{98}\) يُقبل وأن \(\frac{30}{50}\) يُرفض.
عدد الأعداد ذات الرقمين هو \(90\) فقط، ولذلك فإن عدد الكسور الحقيقية المرشحة يساوي
$$\binom{90}{2}=4005.$$
كل مرشح يحتاج إلى عمل ثابت المقدار: استخراج الخانات، وتجربة ما يصل إلى أربع حالات، وتنفيذ بضع عمليات ضرب صحيحة. حتى حساب القاسم المشترك الأكبر في النهاية يبقى صغيرًا جدًا لهذه القيم. لذلك يكون الزمن \(O(1)\) بالنسبة إلى مدخل هذه المسألة بعينها، أو \(O(R^2)\) إذا تخيلنا تعميم الفكرة على جميع الأعداد الأصغر من حد أعلى \(R\). أما استخدام الذاكرة فهو \(O(1)\).