For each positive integer \(n\), define \(f(n)\) as the smallest positive multiple of \(n\) whose decimal digits all belong to \(\{0,1,2\}\). The task is to compute
$$\sum_{n=1}^{N}\frac{f(n)}{n}.$$
It is not obvious at first that every \(n\) has such a multiple. Write
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
For the coprime part \(m\), consider the repunits
$$R_k=\underbrace{11\dots1}_{k\text{ digits}}=\frac{10^k-1}{9}\qquad (1\le k\le m).$$
If one of these is already \(0\bmod m\), we are done. Otherwise, two of them have the same remainder modulo \(m\). Their difference is divisible by \(m\) and has decimal form
$$11\dots1100\dots0,$$
so it uses only digits \(0\) and \(1\).
Now multiply by
$$10^{\max(a,b)}.$$
This adds enough factors of \(2\) and \(5\) to make the number divisible by \(n\), and it still uses only digits \(0\) and \(1\). Therefore a multiple using digits from \(\{0,1,2\}\) always exists.
Instead of building gigantic candidates directly, the code works modulo \(n\). If a current decimal string has remainder \(r\), then appending a digit \(d\in\{0,1,2\}\) produces the new remainder
$$r'=(10r+d)\bmod n.$$
So we get a directed graph with \(n\) states, one for each residue \(0,1,\dots,n-1\), and three outgoing edges from each state.
The first digit cannot be \(0\), so the only legal one-digit starts are \(1\) and \(2\). Therefore the BFS starts from residues
$$1\bmod n\qquad\text{and}\qquad 2\bmod n.$$
Every longer legal number is obtained from one of these starts by repeatedly appending \(0\), \(1\), or \(2\).
Each edge corresponds to appending exactly one digit, so every edge has unit cost. Breadth-first search explores states in nondecreasing path length. Hence the first time BFS reaches residue \(0\), it has found a decimal string with the minimum possible number of digits among all valid multiples of \(n\).
This is the key reduction: “smallest multiple” is first turned into “shortest path to remainder \(0\)” in an unweighted graph.
Among strings with the same length, the code explores appended digits in the fixed order
$$0,\ 1,\ 2,$$
and the roots in the order \(1,2\). Because BFS processes the queue level by level, the first path reaching a given state at a given depth is the lexicographically smallest one among all shortest paths to that state. In particular, the first time we reach residue \(0\), we obtain not only the shortest valid decimal string, but also the lexicographically smallest among all strings of that minimum length.
For decimal numbers with the same length, lexicographic order and numeric order agree, so this is exactly the desired \(f(n)\).
The BFS stores, for each visited remainder:
1. its parent remainder;
2. the appended digit used to reach it.
When remainder \(0\) is found, the code backtracks through these parent pointers, reverses the digit list, and reconstructs \(f(n)\) exactly as a decimal string.
This is much cheaper than carrying the whole candidate number inside every queue entry.
Some small cases from the checkpoints make the method concrete:
$$f(2)=2,\qquad \frac{f(2)}{2}=1,$$
$$f(3)=12,\qquad \frac{f(3)}{3}=4,$$
$$f(7)=21,\qquad \frac{f(7)}{7}=3,$$
$$f(42)=210,\qquad \frac{f(42)}{42}=5.$$
The last example is a good reminder that zeros are useful: once a good core number is found, appending zeros can supply extra factors of \(2\) and \(5\).
After reconstructing \(f(n)\), the solver converts it to an arbitrary-precision integer, divides by \(n\), and adds the quotient to the running total. For example, the checkpoint in the C++ code verifies
$$\sum_{n=1}^{100}\frac{f(n)}{n}=11363107.$$
Another small manual checkpoint is
$$\sum_{n=1}^{10}\frac{f(n)}{n}=1389.$$
The function smallest_multiple_with_digits_leq_2(n) performs the residue BFS for one fixed \(n\). It keeps three arrays: seen, parent, and parent_digit. Once remainder \(0\) is dequeued, it reconstructs the digit string and returns it.
The outer solve(limit) loop simply evaluates that function for all \(1\le n\le N\), converts the returned string to a big integer, divides by \(n\), and accumulates the result.
For a fixed \(n\), the BFS visits at most \(n\) residues, and each residue has exactly three outgoing transitions. Therefore the time complexity per \(n\) is
$$O(n),$$
and the memory usage is also
$$O(n).$$
Summed over all \(1\le n\le N\), the total work is approximately quadratic:
$$O(N^2).$$
This is practical here because the branching factor is tiny and the state graph for each \(n\) is very small compared with the actual size of \(f(n)\), which may have many digits.
Für jede positive ganze Zahl \(n\) sei \(f(n)\) das kleinste positive Vielfache von \(n\), dessen Dezimaldarstellung nur Ziffern aus \(\{0,1,2\}\) enthält. Gesucht ist
$$\sum_{n=1}^{N}\frac{f(n)}{n}.$$
Zunächst ist nicht offensichtlich, dass es für jedes \(n\) überhaupt ein solches Vielfaches gibt. Schreibe
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
Für den teilerfremden Teil \(m\) betrachten wir die Repunits
$$R_k=\underbrace{11\dots1}_{k\text{ Stellen}}=\frac{10^k-1}{9}\qquad (1\le k\le m).$$
Ist eine davon bereits \(0\bmod m\), sind wir fertig. Andernfalls haben zwei dieselbe Restklasse modulo \(m\). Ihre Differenz ist durch \(m\) teilbar und hat Dezimalform
$$11\dots1100\dots0,$$
also nur die Ziffern \(0\) und \(1\).
Multipliziert man nun mit
$$10^{\max(a,b)},$$
so entstehen genügend Faktoren \(2\) und \(5\), um Teilbarkeit durch \(n\) zu erzwingen. Die Ziffern bleiben weiterhin nur \(0\) und \(1\). Also existiert immer ein Vielfaches mit Ziffern aus \(\{0,1,2\}\).
Statt gigantische Kandidaten direkt zu konstruieren, arbeitet der Code modulo \(n\). Hat eine aktuelle Ziffernfolge Rest \(r\), dann erzeugt das Anhängen einer Ziffer \(d\in\{0,1,2\}\) den neuen Rest
$$r'=(10r+d)\bmod n.$$
Damit erhält man einen gerichteten Graphen mit \(n\) Zuständen, nämlich den Restklassen \(0,1,\dots,n-1\), und mit drei ausgehenden Kanten pro Zustand.
Die erste Ziffer darf nicht \(0\) sein. Deshalb sind die einzigen zulässigen einstelligen Starts \(1\) und \(2\). Die BFS beginnt also bei den Resten
$$1\bmod n\qquad\text{und}\qquad 2\bmod n.$$
Jede längere zulässige Zahl entsteht daraus durch wiederholtes Anhängen von \(0\), \(1\) oder \(2\).
Jede Kante entspricht dem Anhängen genau einer Ziffer und hat also Kosten \(1\). Die Breitensuche besucht Zustände in nicht abnehmender Pfadlänge. Sobald BFS erstmals die Restklasse \(0\) erreicht, ist damit eine Dezimalfolge mit minimal möglicher Stellenzahl unter allen gültigen Vielfachen gefunden.
Das ist die zentrale Reduktion: „kleinstes Vielfaches“ wird zuerst zu „kürzester Weg zur Restklasse \(0\)“ in einem ungewichteten Graphen.
Unter gleich langen Folgen verarbeitet der Code die angehängten Ziffern in der festen Reihenfolge
$$0,\ 1,\ 2,$$
und die Wurzeln in der Reihenfolge \(1,2\). Weil BFS Ebene für Ebene arbeitet, ist der erste Pfad zu einem Zustand in einer festen Tiefe zugleich der lexikographisch kleinste unter allen kürzesten Pfaden zu diesem Zustand. Insbesondere erhält man beim ersten Erreichen von Rest \(0\) nicht nur die kürzeste, sondern auch die lexikographisch kleinste Folge minimaler Länge.
Bei Dezimalzahlen gleicher Länge stimmen lexikographische und numerische Ordnung überein. Genau daher ist dies das gesuchte \(f(n)\).
Für jede besuchte Restklasse speichert die BFS:
1. den Vorgängerrest,
2. die angehängte Ziffer.
Sobald Rest \(0\) gefunden ist, geht der Code diese Elternzeiger rückwärts durch, kehrt die Ziffernfolge um und rekonstruiert \(f(n)\) exakt als Dezimalzeichenkette.
Das ist deutlich billiger, als in jedem Queue-Eintrag die gesamte Kandidatenzahl mitzuschleppen.
Einige kleine Fälle aus den Checkpoints machen das Verfahren greifbar:
$$f(2)=2,\qquad \frac{f(2)}{2}=1,$$
$$f(3)=12,\qquad \frac{f(3)}{3}=4,$$
$$f(7)=21,\qquad \frac{f(7)}{7}=3,$$
$$f(42)=210,\qquad \frac{f(42)}{42}=5.$$
Das letzte Beispiel zeigt gut, warum Nullen nützlich sind: Hat man einen passenden Kern gefunden, können angehängte Nullen zusätzliche Faktoren \(2\) und \(5\) liefern.
Nach der Rekonstruktion von \(f(n)\) wandelt der Solver die Ziffernfolge in eine beliebig große Ganzzahl um, dividiert durch \(n\) und addiert den Quotienten zur Gesamtsumme. Der Checkpoint im C++-Code überprüft zum Beispiel
$$\sum_{n=1}^{100}\frac{f(n)}{n}=11363107.$$
Ein kleiner zusätzlicher Kontrollwert ist
$$\sum_{n=1}^{10}\frac{f(n)}{n}=1389.$$
Die Funktion smallest_multiple_with_digits_leq_2(n) führt die Restklassen-BFS für ein festes \(n\) aus. Sie verwendet drei Arrays: seen, parent und parent_digit. Sobald Rest \(0\) aus der Queue entnommen wird, rekonstruiert sie die Ziffernfolge und gibt sie zurück.
Die äußere Funktion solve(limit) ruft diese BFS für alle \(1\le n\le N\) auf, wandelt die zurückgegebene Zeichenkette in eine Big-Integer-Zahl um, dividiert durch \(n\) und akkumuliert die Ergebnisse.
Für festes \(n\) besucht die BFS höchstens \(n\) Restklassen, und jede hat genau drei ausgehende Übergänge. Damit gilt pro \(n\)
$$O(n)$$
Zeit und ebenso
$$O(n)$$
Speicher. Über alle \(1\le n\le N\) summiert ergibt das ungefähr
$$O(N^2).$$
Das ist hier praktikabel, weil der Verzweigungsgrad winzig ist und der Restklassengraph für jedes \(n\) viel kleiner bleibt als die tatsächliche Zahl \(f(n)\), die sehr viele Stellen haben kann.
Her pozitif \(n\) için \(f(n)\), ondalık basamakları yalnızca \(\{0,1,2\}\) kümesinden gelen en küçük pozitif \(n\) katıdır. Hesaplanacak toplam
$$\sum_{n=1}^{N}\frac{f(n)}{n}.$$
Önce, her \(n\) için böyle bir katın mutlaka var olduğunu görmek gerekir. Şöyle yazalım:
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
\(m\) için repunit sayıları düşünelim:
$$R_k=\underbrace{11\dots1}_{k\text{ basamak}}=\frac{10^k-1}{9}\qquad (1\le k\le m).$$
Bunlardan biri zaten \(0\bmod m\) ise iş biter. Değilse iki tanesi mod \(m\)'ye göre aynı kalanı verir. Farkları \(m\)'ye bölünür ve ondalık yazımı
$$11\dots1100\dots0$$
biçimindedir; yani yalnızca \(0\) ve \(1\) rakamlarını kullanır.
Şimdi bunu
$$10^{\max(a,b)}$$
ile çarparsak, yeterli sayıda \(2\) ve \(5\) çarpanı kazanırız; sayı artık \(n\)'ye de bölünür ve yine sadece \(0\) ile \(1\) rakamlarından oluşur. Dolayısıyla \(\{0,1,2\}\) rakamlarıyla yazılabilen bir kat her zaman vardır.
Kodu verimli yapan fikir, büyük aday sayıları doğrudan üretmemektir. Bir mevcut dizgenin \(n\)'ye göre kalanı \(r\) ise, sonuna \(d\in\{0,1,2\}\) rakamı eklenince yeni kalan
$$r'=(10r+d)\bmod n$$
olur. Böylece \(0,1,\dots,n-1\) kalıntılarından oluşan ve her düğümden üç çıkış kenarı bulunan yönlü bir graf elde ederiz.
İlk basamak \(0\) olamaz. Bu yüzden tek basamaklı yasal başlangıçlar yalnızca \(1\) ve \(2\)'dir. BFS şu iki kalandan başlar:
$$1\bmod n\qquad\text{ve}\qquad 2\bmod n.$$
Daha uzun tüm yasal sayılar, bunların sonuna tekrar tekrar \(0\), \(1\) veya \(2\) eklenerek oluşur.
Her kenar tam olarak bir rakam eklemeye karşılık gelir; yani tüm kenar maliyetleri \(1\)'dir. Genişlik öncelikli arama düğümleri artmayan değil, artan yol uzunluğu sırasıyla dolaşır. Bu yüzden BFS kalan \(0\)'a ilk ulaştığında, bulunan dizge geçerli tüm \(n\) katları içinde mümkün olan en kısa basamak sayısına sahiptir.
Temel indirgeme budur: “en küçük kat” problemi önce “ağırlıksız graf üzerinde kalan \(0\)'a en kısa yol” problemine çevrilir.
Aynı uzunluktaki dizgeler arasında kod, eklenen rakamları sabit sırayla dener:
$$0,\ 1,\ 2.$$
Kökler de \(1,2\) sırasıyla kuyruğa alınır. BFS seviye seviye ilerlediği için, aynı derinlikte bir duruma ulaşan ilk yol, o duruma giden tüm en kısa yollar arasında leksikografik olarak en küçüktür. Özellikle kalan \(0\)'a ilk ulaşıldığında, yalnızca en kısa çözüm değil, aynı uzunluktaki çözümler içinde leksikografik olarak en küçük çözüm de bulunmuş olur.
Ondalık sayılarda uzunluklar eşitse leksikografik sıralama sayısal sıralamayla aynıdır; dolayısıyla bu tam olarak aranan \(f(n)\)'dir.
BFS her ziyaret edilen kalan için iki bilgi tutar:
1. hangi ebeveyn kalandan geldiği,
2. hangi rakamın eklendiği.
Kalan \(0\) bulunduğunda bu ebeveyn zinciri geriye doğru izlenir, rakamlar ters çevrilir ve \(f(n)\) tam olarak ondalık dizge halinde elde edilir.
Bu, kuyruktaki her durumda tüm sayı dizgesini taşımaktan çok daha ucuzdur.
Checkpoint'lerdeki bazı küçük örnekler yöntemi somutlaştırır:
$$f(2)=2,\qquad \frac{f(2)}{2}=1,$$
$$f(3)=12,\qquad \frac{f(3)}{3}=4,$$
$$f(7)=21,\qquad \frac{f(7)}{7}=3,$$
$$f(42)=210,\qquad \frac{f(42)}{42}=5.$$
Son örnek özellikle öğreticidir: uygun bir çekirdek bulunduğunda sona eklenen sıfırlar ekstra \(2\) ve \(5\) çarpanları kazandırabilir.
\(f(n)\) dizgesi geri kurulduktan sonra çözüm bunu keyfi büyüklükte tamsayıya çevirir, \(n\)'ye böler ve bölümü toplama ekler. C++ kodundaki checkpoint şu örneği doğrular:
$$\sum_{n=1}^{100}\frac{f(n)}{n}=11363107.$$
Daha küçük bir kontrol değeri de şudur:
$$\sum_{n=1}^{10}\frac{f(n)}{n}=1389.$$
smallest_multiple_with_digits_leq_2(n) fonksiyonu sabit bir \(n\) için kalan-BFS'yi çalıştırır. Üç dizi kullanır: seen, parent ve parent_digit. Kalan \(0\) kuyruktan çıkınca rakam dizgesini geri kurup döndürür.
Dıştaki solve(limit) döngüsü ise bunu tüm \(1\le n\le N\) için çağırır, dönen dizgeyi büyük tamsayıya çevirir, \(n\)'ye böler ve toplamı biriktirir.
Sabit bir \(n\) için BFS en fazla \(n\) farklı kalanı ziyaret eder ve her kalanın tam üç geçişi vardır. Bu yüzden tek bir \(n\) için zaman karmaşıklığı
$$O(n)$$
ve bellek karmaşıklığı da
$$O(n)$$
olur. Bunu tüm \(1\le n\le N\) için toplarsak yaklaşık
$$O(N^2)$$
toplam iş çıkar. Bu pratikte uygundur; çünkü dallanma sabiti küçüktür ve her \(n\) için kalan grafı, basamak sayısı çok büyüyebilen gerçek \(f(n)\) değerinden çok daha küçüktür.
Para cada entero positivo \(n\), definimos \(f(n)\) como el menor múltiplo positivo de \(n\) cuyos dígitos decimales pertenecen todos a \(\{0,1,2\}\). Hay que calcular
$$\sum_{n=1}^{N}\frac{f(n)}{n}.$$
No es obvio al principio que tal múltiplo exista para todo \(n\). Escribimos
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
Para la parte coprima \(m\), consideramos los repunits
$$R_k=\underbrace{11\dots1}_{k\text{ dígitos}}=\frac{10^k-1}{9}\qquad (1\le k\le m).$$
Si uno ya es \(0\bmod m\), hemos terminado. Si no, dos de ellos tienen el mismo residuo módulo \(m\). Su diferencia es divisible por \(m\) y tiene la forma decimal
$$11\dots1100\dots0,$$
así que solo usa dígitos \(0\) y \(1\).
Ahora multiplicamos por
$$10^{\max(a,b)}.$$
Eso añade suficientes factores \(2\) y \(5\) para obtener divisibilidad por \(n\), y los dígitos siguen siendo únicamente \(0\) y \(1\). Por tanto, siempre existe un múltiplo formado con dígitos de \(\{0,1,2\}\).
En vez de construir números enormes directamente, el código trabaja módulo \(n\). Si una cadena actual tiene residuo \(r\), al añadir un dígito \(d\in\{0,1,2\}\) se obtiene
$$r'=(10r+d)\bmod n.$$
Así aparece un grafo dirigido con \(n\) estados, uno por cada residuo \(0,1,\dots,n-1\), y tres aristas salientes por estado.
El primer dígito no puede ser \(0\), así que los únicos comienzos válidos de una cifra son \(1\) y \(2\). Por eso el BFS arranca desde
$$1\bmod n\qquad\text{y}\qquad 2\bmod n.$$
Cualquier número válido más largo se obtiene añadiendo repetidamente \(0\), \(1\) o \(2\).
Cada arista corresponde a añadir exactamente un dígito, de modo que todas las aristas tienen coste \(1\). La búsqueda en anchura explora los estados en orden no decreciente de longitud del camino. Por eso, la primera vez que BFS alcanza el residuo \(0\), ya ha encontrado una cadena decimal con la menor longitud posible entre todos los múltiplos válidos de \(n\).
Esa es la reducción central: “el menor múltiplo” se traduce primero en “el camino más corto hasta el residuo \(0\)” dentro de un grafo no ponderado.
Entre cadenas de la misma longitud, el código recorre los dígitos añadidos en el orden fijo
$$0,\ 1,\ 2,$$
y las raíces en el orden \(1,2\). Como BFS procesa la cola nivel por nivel, el primer camino que llega a un estado a cierta profundidad es el menor lexicográficamente entre todos los caminos más cortos hacia ese estado. En particular, cuando se alcanza por primera vez el residuo \(0\), obtenemos no solo la solución de mínima longitud, sino también la menor lexicográficamente entre todas las de esa misma longitud.
Para números decimales de la misma longitud, el orden lexicográfico coincide con el orden numérico, así que eso es exactamente \(f(n)\).
Para cada residuo visitado, el BFS guarda:
1. el residuo padre,
2. el dígito añadido.
Cuando aparece el residuo \(0\), el código retrocede por esos padres, invierte la lista de dígitos y reconstruye \(f(n)\) exactamente como cadena decimal.
Esto es mucho más barato que llevar el número completo en cada entrada de la cola.
Algunos casos pequeños de los checkpoints aclaran el método:
$$f(2)=2,\qquad \frac{f(2)}{2}=1,$$
$$f(3)=12,\qquad \frac{f(3)}{3}=4,$$
$$f(7)=21,\qquad \frac{f(7)}{7}=3,$$
$$f(42)=210,\qquad \frac{f(42)}{42}=5.$$
El último ejemplo recuerda por qué los ceros son útiles: una vez encontrado un núcleo adecuado, añadir ceros puede aportar más factores \(2\) y \(5\).
Tras reconstruir \(f(n)\), el solver convierte la cadena a un entero de precisión arbitraria, divide por \(n\) y añade el cociente al total acumulado. El checkpoint del código C++ verifica, por ejemplo, que
$$\sum_{n=1}^{100}\frac{f(n)}{n}=11363107.$$
Un checkpoint manual más pequeño es
$$\sum_{n=1}^{10}\frac{f(n)}{n}=1389.$$
La función smallest_multiple_with_digits_leq_2(n) ejecuta el BFS de residuos para un \(n\) fijo. Mantiene tres arreglos: seen, parent y parent_digit. En cuanto se extrae el residuo \(0\) de la cola, reconstruye la cadena de dígitos y la devuelve.
El bucle exterior solve(limit) simplemente evalúa esa función para todos los \(1\le n\le N\), convierte la cadena devuelta en un entero grande, divide por \(n\) y acumula el resultado.
Para un \(n\) fijo, el BFS visita como mucho \(n\) residuos y cada residuo tiene exactamente tres transiciones salientes. Por tanto, el tiempo por \(n\) es
$$O(n),$$
y la memoria también es
$$O(n).$$
Sumando sobre todos los \(1\le n\le N\), el coste total es aproximadamente
$$O(N^2).$$
Esto es práctico aquí porque el factor de ramificación es diminuto y el grafo de residuos para cada \(n\) es muy pequeño comparado con el tamaño real de \(f(n)\), que puede tener muchos dígitos.
对每个正整数 \(n\)，定义 \(f(n)\) 为最小的正倍数，并且它的十进制数字全部属于 \(\{0,1,2\}\)。要求计算
$$\sum_{n=1}^{N}\frac{f(n)}{n}.$$
首先要说明：对每个 \(n\)，这种倍数一定存在。写成
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
对与 \(10\) 互素的部分 \(m\)，考虑 repunit
$$R_k=\underbrace{11\dots1}_{k\text{ 位}}=\frac{10^k-1}{9}\qquad (1\le k\le m).$$
如果其中某个已经满足 \(R_k\equiv 0\pmod m\)，那就结束。否则，必有两个 repunit 在模 \(m\) 下同余。它们的差可被 \(m\) 整除，而且十进制形式是
$$11\dots1100\dots0,$$
因此只含数字 \(0\) 和 \(1\)。
再乘上
$$10^{\max(a,b)}$$
就能补足足够多的 \(2\) 和 \(5\) 因子，使其被 \(n\) 整除，而数字仍然只包含 \(0\) 和 \(1\)。于是，使用 \(\{0,1,2\}\) 数字的倍数对每个 \(n\) 都一定存在。
代码并不直接构造非常大的候选数，而是只看模 \(n\) 的余数。如果当前十进制串的余数是 \(r\)，追加一个数字 \(d\in\{0,1,2\}\) 后，新的余数就是
$$r'=(10r+d)\bmod n.$$
于是我们得到一个有 \(n\) 个状态的有向图，状态就是 \(0,1,\dots,n-1\)，每个状态有三条出边。
首位不能是 \(0\)，因此唯一合法的一位起点只有 \(1\) 和 \(2\)。所以 BFS 从
$$1\bmod n\qquad\text{和}\qquad 2\bmod n$$
这两个状态开始。任何更长的合法数，都可以由它们不断追加 \(0\)、\(1\)、\(2\) 得到。
每条边都对应“追加一位数字”，因此每条边的代价都是 \(1\)。广度优先搜索按路径长度从小到大扩展状态，所以第一次到达余数 \(0\) 时，得到的十进制串一定具有所有合法倍数中最短的位数。
这就是核心化简：先把“最小倍数”问题转成“无权图中到余数 \(0\) 的最短路”。
在相同长度的字符串之间，代码按照固定顺序扩展追加数字
$$0,\ 1,\ 2,$$
并且根节点顺序是 \(1,2\)。因为 BFS 是逐层处理队列的，所以某个深度上第一次到达某个状态的路径，就是所有最短路径中字典序最小的那条。特别地，第一次到达余数 \(0\) 时，得到的不仅是最短长度解，还是该最短长度中字典序最小的解。
对于长度相同的十进制数，字典序最小就等于数值最小，因此这正是所求的 \(f(n)\)。
对于每个访问过的余数，BFS 都保存：
1. 它的父余数；
2. 到达它时追加的数字。
一旦找到余数 \(0\)，代码就沿着父指针回溯，再把数字序列反转，从而精确重建出 \(f(n)\) 的十进制表示。
这比在队列里的每个节点都携带完整大整数要便宜得多。
代码中的一些小 checkpoint 可以帮助理解：
$$f(2)=2,\qquad \frac{f(2)}{2}=1,$$
$$f(3)=12,\qquad \frac{f(3)}{3}=4,$$
$$f(7)=21,\qquad \frac{f(7)}{7}=3,$$
$$f(42)=210,\qquad \frac{f(42)}{42}=5.$$
最后一个例子很有代表性：一旦找到合适的“核心”，在末尾补零就可以额外提供 \(2\) 和 \(5\) 因子。
重建出 \(f(n)\) 之后，程序把它转成任意精度整数，计算 \(f(n)/n\)，再累加到总和中。C++ 代码中的 checkpoint 验证了
$$\sum_{n=1}^{100}\frac{f(n)}{n}=11363107.$$
另一个较小的人工校验值是
$$\sum_{n=1}^{10}\frac{f(n)}{n}=1389.$$
smallest_multiple_with_digits_leq_2(n) 对固定的 \(n\) 执行一次余数 BFS。它维护三个数组：seen、parent 和 parent_digit。当余数 \(0\) 被弹出队列时，就回溯并返回对应的数字串。
外层的 solve(limit) 只是对所有 \(1\le n\le N\) 调用这个函数，把返回的字符串转成大整数，除以 \(n\)，并把结果加入总和。
对固定的 \(n\)，BFS 最多访问 \(n\) 个余数，而每个余数恰好有三条转移，因此单个 \(n\) 的时间复杂度是
$$O(n),$$
空间复杂度也是
$$O(n).$$
对所有 \(1\le n\le N\) 求和后，总体复杂度大约是
$$O(N^2).$$
在这里这是可行的，因为分支因子极小，而且对每个 \(n\) 的余数图都远小于真正的 \(f(n)\) 数值规模，后者可能有非常多位。
Для каждого положительного \(n\) определяется \(f(n)\) — наименьшее положительное кратное числа \(n\), чья десятичная запись использует только цифры из множества \(\{0,1,2\}\). Требуется вычислить
$$\sum_{n=1}^{N}\frac{f(n)}{n}.$$
Сначала нужно понять, почему такой кратный вообще всегда существует. Представим
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
Для взаимно простой с \(10\) части \(m\) рассмотрим repunit-числа
$$R_k=\underbrace{11\dots1}_{k\text{ цифр}}=\frac{10^k-1}{9}\qquad (1\le k\le m).$$
Если одно из них уже даёт \(0\bmod m\), то всё готово. Иначе два из них имеют одинаковый остаток по модулю \(m\). Их разность делится на \(m\) и имеет десятичный вид
$$11\dots1100\dots0,$$
то есть использует только цифры \(0\) и \(1\).
Теперь умножим на
$$10^{\max(a,b)}.$$
Это добавит достаточно множителей \(2\) и \(5\), чтобы получить делимость на \(n\), а цифры по-прежнему будут только \(0\) и \(1\). Значит, кратное с цифрами из \(\{0,1,2\}\) существует всегда.
Код не строит гигантские кандидаты напрямую, а работает по модулю \(n\). Если текущая десятичная строка даёт остаток \(r\), то приписывание цифры \(d\in\{0,1,2\}\) переводит нас в остаток
$$r'=(10r+d)\bmod n.$$
Так возникает ориентированный граф из \(n\) состояний: \(0,1,\dots,n-1\), причём из каждого состояния выходят ровно три перехода.
Первая цифра не может быть \(0\), поэтому допустимые одноразрядные старты — только \(1\) и \(2\). Значит, BFS начинается из остатков
$$1\bmod n\qquad\text{и}\qquad 2\bmod n.$$
Любое более длинное допустимое число получается из них последовательным приписыванием \(0\), \(1\) или \(2\).
Каждое ребро соответствует добавлению ровно одной цифры, то есть имеет стоимость \(1\). Поиск в ширину проходит состояния в порядке неубывающей длины пути. Поэтому в тот момент, когда BFS впервые достигает остатка \(0\), найденная строка имеет минимально возможную длину среди всех допустимых кратных числа \(n\).
В этом и состоит ключевое преобразование: задача о «наименьшем кратном» сначала сводится к задаче о кратчайшем пути к остатку \(0\) в невзвешенном графе.
Среди строк одинаковой длины код рассматривает добавляемые цифры в фиксированном порядке
$$0,\ 1,\ 2,$$
а корни — в порядке \(1,2\). Поскольку BFS обходит граф по уровням, первый путь, приходящий в состояние на данной глубине, является лексикографически минимальным среди всех кратчайших путей в это состояние. В частности, первое достижение остатка \(0\) даёт не только кратчайшую, но и лексикографически минимальную строку среди всех решений минимальной длины.
Для десятичных чисел одинаковой длины лексикографический и числовой порядок совпадают, значит это и есть нужное \(f(n)\).
Для каждого посещённого остатка BFS запоминает:
1. родительский остаток,
2. добавленную цифру.
Когда находится остаток \(0\), код проходит по этим указателям назад, разворачивает список цифр и точно восстанавливает \(f(n)\) как десятичную строку.
Это намного дешевле, чем носить целое огромное число в каждой записи очереди.
Несколько малых случаев из checkpoint-ов делают метод наглядным:
$$f(2)=2,\qquad \frac{f(2)}{2}=1,$$
$$f(3)=12,\qquad \frac{f(3)}{3}=4,$$
$$f(7)=21,\qquad \frac{f(7)}{7}=3,$$
$$f(42)=210,\qquad \frac{f(42)}{42}=5.$$
Последний пример особенно полезен: когда найден подходящий «каркас», приписанные нули могут добавить недостающие множители \(2\) и \(5\).
После восстановления \(f(n)\) решатель переводит строку в целое произвольной точности, делит на \(n\) и прибавляет частное к общей сумме. Например, checkpoint в C++-коде проверяет равенство
$$\sum_{n=1}^{100}\frac{f(n)}{n}=11363107.$$
Ещё одна маленькая ручная проверка:
$$\sum_{n=1}^{10}\frac{f(n)}{n}=1389.$$
Функция smallest_multiple_with_digits_leq_2(n) запускает BFS по остаткам для фиксированного \(n\). Она хранит три массива: seen, parent и parent_digit. Как только из очереди извлекается остаток \(0\), соответствующая строка восстанавливается и возвращается.
Внешняя функция solve(limit) просто вызывает эту BFS для всех \(1\le n\le N\), переводит возвращённую строку в большое целое, делит на \(n\) и накапливает сумму.
Для фиксированного \(n\) BFS посещает не более \(n\) остатков, и у каждого остатка ровно три исходящих перехода. Поэтому время на одно \(n\) равно
$$O(n),$$
а память также составляет
$$O(n).$$
Если просуммировать по всем \(1\le n\le N\), получится примерно
$$O(N^2).$$
На практике это приемлемо, потому что ветвление очень мало, а граф остатков для каждого \(n\) несравнимо меньше, чем реальное значение \(f(n)\), которое может иметь очень много цифр.
لكل عدد صحيح موجب \(n\)، نعرّف \(f(n)\) بأنه أصغر مضاعف موجب لـ \(n\) تكون كل أرقامه العشرية من المجموعة \(\{0,1,2\}\). والمطلوب حساب
$$\sum_{n=1}^{N}\frac{f(n)}{n}.$$
ليس واضحًا من البداية أن مثل هذا المضاعف موجود لكل \(n\). نكتب
$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$
وبالنسبة للجزء \(m\) الموافق أوليًا مع \(10\)، ننظر إلى أعداد repunit
$$R_k=\underbrace{11\dots1}_{k\text{ خانات}}=\frac{10^k-1}{9}\qquad (1\le k\le m).$$
إذا كان أحدها يساوي \(0\bmod m\)، فقد انتهينا. وإلا فلابد أن يكون لاثنين منها نفس الباقي modulo \(m\). عندها يكون الفرق بينهما قابلًا للقسمة على \(m\)، ويأخذ شكلًا عشريًا من الصورة
$$11\dots1100\dots0,$$
أي إنه يستخدم فقط الرقمين \(0\) و\(1\).
ثم نضرب في
$$10^{\max(a,b)}.$$
هذا يضيف ما يكفي من عوامل \(2\) و\(5\) لجعل العدد قابلًا للقسمة على \(n\)، ومع ذلك تبقى الأرقام محصورة في \(0\) و\(1\). إذن يوجد دائمًا مضاعف لـ \(n\) مكوّن من أرقام في \(\{0,1,2\}\).
بدلًا من بناء أعداد هائلة مباشرة، يعمل الكود modulo \(n\). إذا كانت السلسلة الحالية تعطي باقيًا \(r\)، فإن إلحاق رقم \(d\in\{0,1,2\}\) يعطي باقيًا جديدًا
$$r'=(10r+d)\bmod n.$$
وبذلك نحصل على رسم بياني موجّه فيه \(n\) حالات، هي البواقي \(0,1,\dots,n-1\)، ولكل حالة ثلاث انتقالات خارجة.
الرقم الأول لا يمكن أن يكون \(0\)، لذلك فالبدايات الوحيدة الصالحة ذات الخانة الواحدة هي \(1\) و\(2\). ولهذا يبدأ BFS من
$$1\bmod n\qquad\text{و}\qquad 2\bmod n.$$
وأي عدد صالح أطول من ذلك يُبنى بإلحاق \(0\) أو \(1\) أو \(2\) مرارًا.
كل ضلع يمثل إلحاق رقم واحد بالضبط، أي إن كلفة كل ضلع هي \(1\). والبحث بعرض الشجرة يستكشف الحالات بحسب طول المسار غير المتناقص. لذلك فإن أول مرة يصل فيها BFS إلى الباقي \(0\)، يكون قد وجد سلسلة عشرية ذات أقل عدد ممكن من الخانات بين جميع المضاعفات الصالحة لـ \(n\).
وهذا هو الاختزال الجوهري: مسألة "أصغر مضاعف" تتحول أولًا إلى مسألة "أقصر مسار إلى الباقي \(0\)" في رسم غير موزون.
بين السلاسل ذات الطول نفسه، يوسّع الكود الأرقام بالترتيب الثابت
$$0,\ 1,\ 2,$$
ويضيف الجذور بالترتيب \(1,2\). ولأن BFS يعمل مستوىً بعد مستوى، فإن أول مسار يصل إلى حالة ما على عمق معين يكون هو الأصغر ترتيبًا معجميًا بين جميع أقصر المسارات المؤدية إلى تلك الحالة. وبالخصوص، فإن أول وصول إلى الباقي \(0\) يعطي ليس فقط أقصر حل، بل أيضًا الأصغر ترتيبًا معجميًا بين جميع الحلول ذات الطول الأدنى.
وبما أن الترتيب المعجمي يطابق الترتيب العددي عند تساوي عدد الخانات، فهذا يساوي بالضبط \(f(n)\).
يخزن BFS لكل باقٍ مزور:
1. الباقي الأب،
2. الرقم الذي أُلحق للوصول إليه.
وعندما يُعثر على الباقي \(0\)، يرجع الكود على هذه المؤشرات، ثم يعكس قائمة الأرقام، فيعيد بناء \(f(n)\) بدقة كسلسلة عشرية.
وهذا أرخص بكثير من حمل العدد الكامل داخل كل عنصر في الطابور.
بعض الحالات الصغيرة من نقاط التحقق تجعل الفكرة ملموسة:
$$f(2)=2,\qquad \frac{f(2)}{2}=1,$$
$$f(3)=12,\qquad \frac{f(3)}{3}=4,$$
$$f(7)=21,\qquad \frac{f(7)}{7}=3,$$
$$f(42)=210,\qquad \frac{f(42)}{42}=5.$$
والمثال الأخير يوضح فائدة الأصفار: بعد العثور على نواة مناسبة، يمكن للأصفار المضافة أن توفر عوامل إضافية من \(2\) و\(5\).
بعد إعادة بناء \(f(n)\)، يحوّله الحل إلى عدد صحيح كبير، ثم يحسب \(f(n)/n\)، ثم يضيف هذا الناتج إلى المجموع الجاري. وتتحقق نقطة الفحص في كود ++C مثلًا من أن
$$\sum_{n=1}^{100}\frac{f(n)}{n}=11363107.$$
وهناك قيمة تحقق صغيرة إضافية:
$$\sum_{n=1}^{10}\frac{f(n)}{n}=1389.$$
الدالة smallest_multiple_with_digits_leq_2(n) تنفذ BFS على فضاء البواقي لعدد ثابت \(n\). وهي تستخدم ثلاث مصفوفات: seen وparent وparent_digit. وبمجرد إخراج الباقي \(0\) من الطابور، تعيد بناء السلسلة الرقمية وتُرجعها.
أما الدالة الخارجية solve(limit) فتكرر ذلك لكل \(1\le n\le N\)، وتحول السلسلة الناتجة إلى عدد كبير، ثم تقسم على \(n\)، ثم تجمع النتيجة.
بالنسبة إلى \(n\) ثابت، يزور BFS على الأكثر \(n\) بواقي، ولكل باقٍ ثلاث انتقالات فقط. إذن زمن التنفيذ لكل \(n\) هو
$$O(n),$$
واستهلاك الذاكرة أيضًا
$$O(n).$$
وعند الجمع على كل \(1\le n\le N\) نحصل تقريبًا على
$$O(N^2).$$
وهذا عملي هنا لأن عامل التفرع صغير جدًا، ولأن رسم البواقي لكل \(n\) أصغر بكثير من القيمة الفعلية لـ \(f(n)\)، التي قد تحتوي على عدد كبير جدًا من الخانات.