For a base \(b\), write \(k\) in base \(b\) and cut its digit string into contiguous blocks. Interpret each block as a base-\(b\) integer and replace \(k\) by the sum of those block values. Let \(f_b(k)\) be the minimum number of such moves needed to make the value \(< b\).
The problem asks for
$$g(n,b_1,b_2)=\sum_{k=1}^{n}[f_{b_1}(k)=f_{b_2}(k)]\,k,$$
and the required output is \(g(10^7,10,3)\). The difficulty is that every number admits many different contiguous partitions, so a naive search over all reduction sequences would explode.
The solution computes \(f_b(k)\) for every \(k\le n\) and for each required base separately. The key observation is that every useful move produces a strictly smaller number, which turns the problem into a dynamic program over increasing \(k\).
Let the base-\(b\) expansion of \(k\) be a digit string. A partition of that string into contiguous blocks \(P_1,\dots,P_r\) produces the next value
$$T_b(k;P_1,\dots,P_r)=\sum_{j=1}^{r} V_b(P_j),$$
where \(V_b(P_j)\) is the ordinary integer value of block \(P_j\) in base \(b\). Then
$$f_b(k)=0\qquad (0\le k < b),$$
and for \(k\ge b\),
$$f_b(k)=1+\min_{P_1|\cdots|P_r} f_b\!\left(T_b(k;P_1,\dots,P_r)\right).$$
The one-block partition leaves the number unchanged, so it never improves the optimum; all useful partitions create a strict reduction.
Let \(s_b(k)\) be the sum of the base-\(b\) digits of \(k\). Every block value is at least the sum of the digits inside that block, so any partition satisfies
$$s_b(k)\le T_b(k;P_1,\dots,P_r)\le k.$$
The left equality occurs when every digit is separated into its own block. The right equality occurs only when the whole digit string is kept as one block. Therefore every useful transition satisfies
$$s_b(k)\le T_b(k;P_1,\dots,P_r)<k.$$
This immediately gives a valid first candidate:
$$f_b(k)\le 1+f_b(s_b(k)).$$
Because all useful targets are smaller than \(k\), the values \(f_b(0),f_b(1),\dots,f_b(k-1)\) can be finalized before computing \(f_b(k)\).
After the dynamic-programming order is fixed, the remaining task for a given \(k\) is to enumerate its possible block sums. The implementation scans the digits from least significant to most significant.
At each new digit there are exactly two structural choices:
$$\text{start a new block}\qquad \text{or} \qquad \text{extend the current block}.$$
Those two choices generate the full binary partition tree. If the base-\(b\) expansion of \(k\) has \(d\) digits, then the raw search tree has \(2^{d-1}\) leaves, one for each placement of separators between adjacent digits. No partition is missed and none is counted twice.
During the depth-first search, part of the digit string has already been processed. Suppose a state stores
$$A=\text{sum of finished blocks},\qquad C=\text{value of the current open block},\qquad R=\text{sum of the digits not processed yet}.$$
Then every completion of that state produces a total \(T\) satisfying
$$T\ge A+C+R.$$
Why? The unfinished higher digits contribute at least their digit sum \(R\) if they are split as single digits, and any merging can only increase their contribution. Likewise, closing the current block as it stands gives \(C\), while extending that block can only make it larger. Hence
$$L=A+C+R$$
is an optimistic lower bound on every descendant of the current DFS node.
Let
$$\Phi_k(L)=\min_{L\le x<k} f_b(x).$$
Because all useful next values are smaller than \(k\), this minimum only ranges over already solved states. If the best answer found so far for the current number is \(B\), then every completion of the current DFS node needs at least
$$1+\Phi_k(L)$$
moves. Therefore, if
$$1+\Phi_k(L)\ge B,$$
the whole subtree can be pruned safely. This is the central speedup: the search does not need to finish a partition once the lower bound proves that it cannot beat the current best value.
In base \(10\), the digit string is \(13\). The two partitions are
$$13\qquad\text{and}\qquad 1|3\mapsto 1+3=4.$$
The nontrivial move sends \(13\) to \(4<10\), so
$$f_{10}(13)=1.$$
In base \(3\), we have \(13=(111)_3\). The contiguous partitions give
$$111_3=13,\qquad 1|11_3=1+4=5,\qquad 11|1_3=4+1=5,\qquad 1|1|1_3=3.$$
The best first move is therefore \(13\to 3\). But \(3=(10)_3\) is still not below \(3\), and one more move \(10_3\to 1\) finishes the reduction. Hence
$$f_{3}(13)=2.$$
So \(13\) does not contribute to \(g(n,10,3)\), because its optimal step counts in the two bases are different.
The implementation builds the table of step counts for one base at a time. It first precomputes the base-\(b\) digit sum of every number up to \(n\) using the recurrence
$$s_b(k)=s_b\!\left(\left\lfloor\frac{k}{b}\right\rfloor\right)+(k\bmod b).$$
All values below \(b\) are initialized with step count \(0\), while larger values start with a large provisional bound. For each \(k\ge b\), the first candidate is the all-single-digit partition, namely \(1+f_b(s_b(k))\).
Next, a depth-first search scans the digits from right to left and enumerates all contiguous partitions by repeatedly choosing between closing the current block and starting a new one, or extending the current block with the next digit. At each node it evaluates the lower bound \(L=A+C+R\), updates the best answer using the already known value at \(L\), and then asks for the minimum solved step count on the suffix \([L,k)\). If even that optimistic suffix minimum cannot beat the current best, the branch is discarded.
A compact suffix-minimum summary supports those queries efficiently: for each attained step count it remembers how far to the right that value has already occurred among solved numbers. This is enough to recover \(\Phi_k(L)\) quickly without scanning the whole interval.
Once the table is complete for a base, the same process is run for the other base. The C++, Python, and Java implementations follow the same mathematical plan; the C++ version evaluates the two bases concurrently when they differ, the Java version performs the two passes directly, and the Python entry point delegates to the same C++ computation. After both tables are available, the implementation sums all \(k\) with matching step counts. One of the implementations also checks the smaller benchmark
$$g(100,10,3)=3302$$
before producing the final answer.
Let \(d_b(k)\) be the number of base-\(b\) digits of \(k\). Without pruning, a number with \(d\) digits has \(2^{d-1}\) contiguous partitions, so the raw dynamic program would cost
$$O\!\left(\sum_{k=b}^{n} 2^{d_b(k)-1}\right).$$
Since \(d_b(k)\le \lfloor \log_b n \rfloor+1\), a coarse worst-case bound is
$$O\!\left(n^{\,1+\log_b 2}\right)$$
for one base, before pruning. The implemented method adds two linear-size arrays for step counts and digit sums, so the memory usage is \(O(n)\) per base computation, plus \(O(\log_b n)\) recursion depth and a small suffix-summary structure.
What makes the program practical is not a better worst-case formula, but the pruning. The initial candidate \(1+f_b(s_b(k))\) is often already close to optimal, and the lower-bound test removes most of the partition tree. For the required input \(n=10^7\), that practical reduction is strong enough to make the full computation feasible.
Für eine Basis \(b\) schreibt man \(k\) in Basis \(b\) und zerlegt die Ziffernfolge in zusammenhängende Blöcke. Jeder Block wird als Basis-\(b\)-Zahl interpretiert, dann werden die Blockwerte addiert. Sei \(f_b(k)\) die minimale Anzahl solcher Schritte, bis der Wert \(< b\) ist.
Gesucht ist
$$g(n,b_1,b_2)=\sum_{k=1}^{n}[f_{b_1}(k)=f_{b_2}(k)]\,k,$$
und konkret soll \(g(10^7,10,3)\) berechnet werden. Die Schwierigkeit besteht darin, dass jede Zahl viele verschiedene zusammenhängende Partitionen zulässt; eine naive Suche über alle Reduktionsfolgen wäre daher viel zu groß.
Die Lösung berechnet \(f_b(k)\) für alle \(k\le n\) und für jede benötigte Basis getrennt. Die entscheidende Beobachtung ist, dass jeder nützliche Schritt eine echt kleinere Zahl erzeugt. Dadurch wird das Problem zu einer dynamischen Programmierung in aufsteigender Reihenfolge von \(k\).
Sei die Basis-\(b\)-Darstellung von \(k\) eine Ziffernfolge. Eine Zerlegung dieser Folge in zusammenhängende Blöcke \(P_1,\dots,P_r\) erzeugt den nächsten Wert
$$T_b(k;P_1,\dots,P_r)=\sum_{j=1}^{r} V_b(P_j),$$
wobei \(V_b(P_j)\) den gewöhnlichen ganzzahligen Wert des Blocks \(P_j\) in Basis \(b\) bezeichnet. Dann gilt
$$f_b(k)=0\qquad (0\le k < b),$$
und für \(k\ge b\)
$$f_b(k)=1+\min_{P_1|\cdots|P_r} f_b\!\left(T_b(k;P_1,\dots,P_r)\right).$$
Die Zerlegung in genau einen Block lässt die Zahl unverändert und verbessert das Optimum daher nie; alle nützlichen Zerlegungen führen zu einer echten Reduktion.
Sei \(s_b(k)\) die Summe der Basis-\(b\)-Ziffern von \(k\). Jeder Blockwert ist mindestens so groß wie die Summe seiner Ziffern, also gilt für jede Partition
$$s_b(k)\le T_b(k;P_1,\dots,P_r)\le k.$$
Die linke Gleichheit tritt ein, wenn jede Ziffer einen eigenen Block bildet. Die rechte Gleichheit tritt nur dann ein, wenn die gesamte Ziffernfolge als ein einziger Block stehen bleibt. Damit erfüllt jeder nützliche Übergang
$$s_b(k)\le T_b(k;P_1,\dots,P_r)<k.$$
Das liefert sofort einen gültigen ersten Kandidaten:
$$f_b(k)\le 1+f_b(s_b(k)).$$
Weil alle nützlichen Zielwerte kleiner als \(k\) sind, können die Werte \(f_b(0),f_b(1),\dots,f_b(k-1)\) vollständig feststehen, bevor \(f_b(k)\) berechnet wird.
Sobald die Reihenfolge der dynamischen Programmierung feststeht, bleibt für ein gegebenes \(k\) die Aufgabe, alle möglichen Blocksummen zu erzeugen. Die Implementierung verarbeitet die Ziffern von der niederwertigsten zur höchstwertigen Stelle.
Bei jeder neuen Ziffer gibt es genau zwei strukturelle Möglichkeiten:
$$\text{einen neuen Block beginnen}\qquad \text{oder} \qquad \text{den aktuellen Block erweitern}.$$
Diese zwei Entscheidungen erzeugen den vollständigen binären Partitionierungsbaum. Hat die Basis-\(b\)-Darstellung von \(k\) genau \(d\) Ziffern, dann besitzt der rohe Suchbaum \(2^{d-1}\) Blätter, eines für jede mögliche Platzierung von Trennstellen zwischen benachbarten Ziffern. Keine Partition geht verloren und keine wird doppelt gezählt.
Während der Tiefensuche ist bereits ein Teil der Ziffernfolge verarbeitet. Nehmen wir an, ein Zustand speichere
$$A=\text{Summe der abgeschlossenen Blöcke},\qquad C=\text{Wert des aktuell offenen Blocks},\qquad R=\text{Summe der noch unverarbeiteten Ziffern}.$$
Dann erzeugt jede Fortsetzung dieses Zustands einen Gesamtwert \(T\) mit
$$T\ge A+C+R.$$
Warum? Die noch nicht verarbeiteten höheren Ziffern tragen mindestens ihre Ziffernsumme \(R\) bei, wenn man sie einzeln abspaltet, und jedes Zusammenfassen kann diesen Beitrag nur vergrößern. Ebenso liefert das sofortige Abschließen des aktuellen Blocks den Wert \(C\); eine Erweiterung dieses Blocks kann ihn nur erhöhen. Daher ist
$$L=A+C+R$$
eine optimistische Untergrenze für jeden Nachkommen des aktuellen DFS-Knotens.
Definiere
$$\Phi_k(L)=\min_{L\le x<k} f_b(x).$$
Weil alle nützlichen nächsten Werte kleiner als \(k\) sind, läuft dieses Minimum nur über bereits gelöste Zustände. Sei \(B\) die bisher beste Antwort für die aktuelle Zahl. Dann benötigt jede Fortsetzung des aktuellen DFS-Knotens mindestens
$$1+\Phi_k(L)$$
Schritte. Falls also
$$1+\Phi_k(L)\ge B,$$
kann der gesamte Teilbaum sicher abgeschnitten werden. Genau das ist die zentrale Beschleunigung: Die Suche muss eine Partition nicht vollständig ausführen, sobald die Untergrenze beweist, dass sie den aktuellen Bestwert nicht mehr schlagen kann.
In Basis \(10\) lautet die Ziffernfolge \(13\). Die zwei Partitionen sind
$$13\qquad\text{und}\qquad 1|3\mapsto 1+3=4.$$
Der nichttriviale Schritt sendet also \(13\) auf \(4<10\), damit gilt
$$f_{10}(13)=1.$$
In Basis \(3\) gilt \(13=(111)_3\). Die zusammenhängenden Partitionen liefern
$$111_3=13,\qquad 1|11_3=1+4=5,\qquad 11|1_3=4+1=5,\qquad 1|1|1_3=3.$$
Der beste erste Schritt ist also \(13\to 3\). Doch \(3=(10)_3\) liegt noch nicht unter \(3\), und erst ein weiterer Schritt \(10_3\to 1\) beendet die Reduktion. Daher
$$f_{3}(13)=2.$$
Somit trägt \(13\) nicht zu \(g(n,10,3)\) bei, weil die optimalen Schrittzahlen in den beiden Basen verschieden sind.
Die Implementierung baut die Tabelle der Schrittzahlen jeweils für eine Basis auf. Zuerst wird die Basis-\(b\)-Ziffernsumme aller Zahlen bis \(n\) mit der Rekurrenz
$$s_b(k)=s_b\!\left(\left\lfloor\frac{k}{b}\right\rfloor\right)+(k\bmod b)$$
vorberechnet. Alle Werte unterhalb von \(b\) erhalten die Schrittzahl \(0\), größere Werte beginnen mit einer großen vorläufigen Schranke. Für jedes \(k\ge b\) ist der erste Kandidat die Zerlegung in Einzelziffern, also \(1+f_b(s_b(k))\).
Anschließend durchläuft eine Tiefensuche die Ziffern von rechts nach links und erzeugt alle zusammenhängenden Partitionen, indem sie fortlaufend zwischen zwei Möglichkeiten wählt: den aktuellen Block abschließen und einen neuen beginnen, oder den aktuellen Block mit der nächsten Ziffer erweitern. In jedem Knoten wird die Untergrenze \(L=A+C+R\) ausgewertet, der beste Wert mit dem bereits bekannten Wert an Position \(L\) verbessert und dann das Minimum der bereits gelösten Schrittzahlen auf dem Suffix \([L,k)\) abgefragt. Kann selbst dieses optimistische Suffixminimum den aktuellen Bestwert nicht mehr schlagen, wird der Ast verworfen.
Eine kompakte Suffix-Minimum-Zusammenfassung unterstützt diese Anfragen effizient: Für jede bereits erreichte Schrittzahl merkt sie sich, wie weit rechts dieser Wert unter den gelösten Zahlen schon vorkam. Damit lässt sich \(\Phi_k(L)\) schnell bestimmen, ohne das ganze Intervall abzulaufen.
Sobald die Tabelle für eine Basis fertig ist, wird derselbe Vorgang für die andere Basis wiederholt. Die C++, Python- und Java-Implementierungen folgen demselben mathematischen Plan; die C++-Version berechnet die beiden Basen parallel, falls sie verschieden sind, die Java-Version führt beide Durchläufe direkt aus, und der Python-Einstieg delegiert an dieselbe C++-Berechnung. Danach summiert die Implementierung alle \(k\), deren Schrittzahlen übereinstimmen. Eine der Implementierungen prüft vor der endgültigen Ausgabe außerdem den kleineren Kontrollwert
$$g(100,10,3)=3302.$$
Sei \(d_b(k)\) die Anzahl der Basis-\(b\)-Ziffern von \(k\). Ohne Pruning besitzt eine Zahl mit \(d\) Ziffern genau \(2^{d-1}\) zusammenhängende Partitionen. Damit hätte das rohe dynamische Programm Aufwand
$$O\!\left(\sum_{k=b}^{n} 2^{d_b(k)-1}\right).$$
Da \(d_b(k)\le \lfloor \log_b n \rfloor+1\) gilt, erhält man eine grobe Worst-Case-Schranke
$$O\!\left(n^{\,1+\log_b 2}\right)$$
für eine Basis, noch ohne Pruning. Die implementierte Methode benötigt zwei linear große Arrays für Schrittzahlen und Ziffernsummen, also \(O(n)\) Speicher pro Basisberechnung, dazu \(O(\log_b n)\) Rekursionstiefe und eine kleine Suffix-Zusammenfassung.
Praktisch schnell wird das Programm jedoch erst durch das Abschneiden von Teilbäumen. Der Anfangskandidat \(1+f_b(s_b(k))\) liegt oft schon nahe am Optimum, und der Untergrenzentest entfernt den größten Teil des Partitionierungsbaums. Für die geforderte Eingabe \(n=10^7\) ist diese praktische Reduktion stark genug, um die vollständige Berechnung möglich zu machen.
Taban \(b\) için \(k\) sayısını taban \(b\) basamaklarıyla yazıp bu basamak dizisini bitişik bloklara ayırıyoruz. Her blok taban-\(b\) sayısı olarak yorumlanıyor ve sonra tüm blok değerleri toplanıyor. \(f_b(k)\), bu işlemi uygulayarak değeri \(< b\) yapmanın gereken en az adım sayısıdır.
İstenen büyüklük
$$g(n,b_1,b_2)=\sum_{k=1}^{n}[f_{b_1}(k)=f_{b_2}(k)]\,k,$$
ve hedef çıktı \(g(10^7,10,3)\) değeridir. Zorluk şuradadır: her sayı için bitişik bloklara ayırmanın çok sayıda yolu vardır; bu yüzden tüm indirgeme dizilerini kaba kuvvetle aramak patlayıcı biçimde büyür.
Çözüm, her istenen taban için \(f_b(k)\) değerlerini \(k\le n\) aralığında tek tek hesaplar. Temel gözlem şudur: işe yarayan her hamle sayıyı gerçekten küçültür. Böylece problem, artan \(k\) sırasıyla çalışan bir dinamik programa dönüşür.
\(k\)'nın taban-\(b\) gösterimini bir basamak dizisi olarak düşünelim. Bu diziyi bitişik bloklara \(P_1,\dots,P_r\) şeklinde ayırdığımızda oluşan yeni değer
$$T_b(k;P_1,\dots,P_r)=\sum_{j=1}^{r} V_b(P_j)$$
olur; burada \(V_b(P_j)\), \(P_j\) bloğunun taban \(b\)'deki normal tamsayı değeridir. O halde
$$f_b(k)=0\qquad (0\le k < b),$$
ve \(k\ge b\) için
$$f_b(k)=1+\min_{P_1|\cdots|P_r} f_b\!\left(T_b(k;P_1,\dots,P_r)\right).$$
Tek bloklu ayırım sayıyı değiştirmez; dolayısıyla optimumu iyileştirmez. Gerçekten işe yarayan tüm ayırımlar sayıyı daha küçük bir değere indirir.
\(s_b(k)\), \(k\)'nın taban-\(b\) basamak toplamı olsun. Her blok değeri, içindeki basamakların toplamından en az o kadar büyüktür. Bu yüzden her ayırım için
$$s_b(k)\le T_b(k;P_1,\dots,P_r)\le k$$
eşitsizliği geçerlidir. Sol taraftaki eşitlik, her basamak tek başına blok yapıldığında oluşur. Sağ taraftaki eşitlik ise yalnızca tüm sayı tek bir blok bırakıldığında oluşur. Dolayısıyla her faydalı geçiş
$$s_b(k)\le T_b(k;P_1,\dots,P_r)<k$$
şartını sağlar. Bu da hemen geçerli bir ilk aday verir:
$$f_b(k)\le 1+f_b(s_b(k)).$$
Faydalı tüm hedefler \(k\)'dan küçük olduğu için \(f_b(0),f_b(1),\dots,f_b(k-1)\) değerleri tamamlandıktan sonra \(f_b(k)\) güvenle hesaplanabilir.
Dinamik programlama sırası belirlendikten sonra, sabit bir \(k\) için geriye kalan iş tüm olası blok toplamlarını üretmektir. Uygulama basamakları en düşük anlamlı basamaktan en yüksek anlamlı basamağa doğru işler.
Her yeni basamak geldiğinde tam olarak iki yapısal seçenek vardır:
$$\text{yeni bir blok başlat}\qquad \text{veya} \qquad \text{mevcut bloğu genişlet}.$$
Bu iki karar, tüm ikili ayrım ağacını üretir. Eğer \(k\)'nın taban-\(b\) gösterimi \(d\) basamaklıysa, ham arama ağacı komşu basamaklar arasına ayraç koymanın tüm yollarına karşılık gelen \(2^{d-1}\) yaprak içerir. Hiçbir ayırım atlanmaz, hiçbir ayırım iki kez sayılmaz.
Derinlik öncelikli arama sırasında basamak dizisinin bir kısmı işlenmiş olur. Bir durumun şu üç bilgiyi tuttuğunu düşünelim:
$$A=\text{tamamlanmış blokların toplamı},\qquad C=\text{şu anda açık olan bloğun değeri},\qquad R=\text{henüz işlenmemiş basamakların toplamı}.$$
Bu durumdan türeyen her tamamlamanın toplamı \(T\) için
$$T\ge A+C+R$$
olur. Çünkü yukarıda kalan işlenmemiş basamaklar tek tek blok yapılırsa en az \(R\) katkı verir; bunları birleştirmek katkıyı ancak artırır. Benzer biçimde açık blok hemen kapatılırsa \(C\) katkısı gelir; bu bloğu genişletmek ise değeri küçültmez. O halde
$$L=A+C+R$$
ifadesi mevcut DFS düğümünün tüm alt dalları için iyimser bir alt sınırdır.
Şimdi
$$\Phi_k(L)=\min_{L\le x<k} f_b(x)$$
tanımını yapalım. Faydalı sonraki değerlerin hepsi \(k\)'dan küçük olduğundan bu minimum yalnızca daha önce çözülmüş durumlar üzerinde alınır. Mevcut sayı için şimdiye kadarki en iyi cevap \(B\) ise, mevcut DFS düğümünden gelen her tamamlamanın en az
$$1+\Phi_k(L)$$
adım gerektireceği kesindir. Dolayısıyla
$$1+\Phi_k(L)\ge B$$
olduğu anda tüm alt ağaç güvenle budanabilir. Hız kazandıran asıl fikir budur: alt sınır artık mevcut en iyi değeri geçemeyeceğini gösterdiğinde o dalı sonuna kadar açmaya gerek kalmaz.
Taban \(10\)'da basamak dizisi \(13\) olur. İki ayırım şunlardır:
$$13\qquad\text{ve}\qquad 1|3\mapsto 1+3=4.$$
Önemsiz olmayan hamle \(13\)'ü \(4<10\) değerine indirir; dolayısıyla
$$f_{10}(13)=1.$$
Taban \(3\)'te ise \(13=(111)_3\) yazılır. Bitişik ayırımlar
$$111_3=13,\qquad 1|11_3=1+4=5,\qquad 11|1_3=4+1=5,\qquad 1|1|1_3=3$$
sonuçlarını verir. En iyi ilk hamle \(13\to 3\) olur. Fakat \(3=(10)_3\) hâlâ \(3\)'ten küçük değildir; bir adım daha, yani \(10_3\to 1\), gerekir. Bu yüzden
$$f_{3}(13)=2.$$
Sonuç olarak \(13\), \(g(n,10,3)\) toplamına katkı yapmaz; çünkü iki tabandaki en iyi adım sayıları farklıdır.
Uygulama, adım sayılarını her taban için ayrı ayrı tablo halinde üretir. Önce
$$s_b(k)=s_b\!\left(\left\lfloor\frac{k}{b}\right\rfloor\right)+(k\bmod b)$$
bağıntısıyla \(n\)'ye kadar tüm sayıların taban-\(b\) basamak toplamı önceden hesaplanır. \(b\)'den küçük değerler için adım sayısı \(0\) olarak atanır; daha büyük değerler geniş bir geçici üst sınırla başlatılır. Her \(k\ge b\) için ilk aday, tüm basamakları tekli bloklara ayıran durumdan gelen \(1+f_b(s_b(k))\) değeridir.
Daha sonra derinlik öncelikli arama basamakları sağdan sola tarar ve her aşamada iki karar arasında seçim yaparak tüm bitişik ayırımları üretir: mevcut bloğu kapatıp yeni blok başlatmak veya mevcut bloğu bir sonraki basamakla genişletmek. Her düğümde \(L=A+C+R\) alt sınırı değerlendirilir, \(L\) için zaten bilinen değerle en iyi aday güncellenir ve ardından \([L,k)\) aralığındaki çözülmüş adım sayılarının minimumu sorgulanır. Bu iyimser minimum bile mevcut en iyi cevabı iyileştiremiyorsa dal kesilir.
Kompakt bir suffix-minimum özeti bu sorguları verimli hale getirir: elde edilmiş her adım sayısı için o değerin çözülmüş sayılar arasında en sağda hangi indekste görüldüğü tutulur. Böylece tüm aralığı baştan sona taramadan \(\Phi_k(L)\) hızlıca bulunur.
Bir taban için tablo tamamlanınca aynı süreç diğer taban için tekrarlanır. C++, Python ve Java uygulamaları aynı matematiksel planı izler; C++ sürümü tabanlar farklıysa iki hesabı eşzamanlı yürütür, Java sürümü iki geçişi doğrudan yapar, Python giriş noktası ise aynı C++ hesabını çağırır. Her iki tablo hazır olduğunda, adım sayıları eşit olan tüm \(k\) değerleri toplanır. Uygulamalardan biri ayrıca tam cevap üretilmeden önce
$$g(100,10,3)=3302$$
kontrolünü de yapar.
\(d_b(k)\), \(k\)'nın taban-\(b\) basamak sayısı olsun. Budama yapılmazsa, \(d\) basamaklı bir sayının \(2^{d-1}\) adet bitişik ayırımı vardır. Bu durumda ham dinamik programın maliyeti
$$O\!\left(\sum_{k=b}^{n} 2^{d_b(k)-1}\right)$$
olur. \(d_b(k)\le \lfloor \log_b n \rfloor+1\) olduğundan tek bir taban için kaba bir en kötü durum üst sınırı
$$O\!\left(n^{\,1+\log_b 2}\right)$$
şeklindedir. Uygulanan yöntemde adım sayıları ve basamak toplamları için iki lineer boyutlu dizi kullanılır; dolayısıyla her taban hesabı için bellek maliyeti \(O(n)\), ek olarak \(O(\log_b n)\) çağrı derinliği ve küçük bir suffix özeti vardır.
Programı pratikte hızlı yapan şey daha iyi bir en kötü durum formülü değil, budamanın kendisidir. Başlangıç adayı \(1+f_b(s_b(k))\) çoğu zaman zaten optimale yakındır ve alt sınır testi ayrım ağacının büyük bölümünü ortadan kaldırır. Gerekli \(n=10^7\) girdisi için bu pratik küçülme, tam hesabı uygulanabilir hale getirir.
Para una base \(b\), escribimos \(k\) en base \(b\) y dividimos su cadena de dígitos en bloques contiguos. Cada bloque se interpreta como un entero en base \(b\), y luego se reemplaza \(k\) por la suma de los valores de esos bloques. Sea \(f_b(k)\) el número mínimo de pasos necesarios para que el valor quede \(< b\).
La cantidad pedida es
$$g(n,b_1,b_2)=\sum_{k=1}^{n}[f_{b_1}(k)=f_{b_2}(k)]\,k,$$
y en este problema hay que calcular \(g(10^7,10,3)\). La dificultad es que cada número admite muchas particiones contiguas distintas, así que una búsqueda ingenua sobre todas las secuencias de reducción sería inmanejable.
La solución calcula \(f_b(k)\) para todo \(k\le n\) y para cada base necesaria por separado. La observación central es que todo movimiento útil produce un número estrictamente menor, de modo que el problema se convierte en una programación dinámica en orden creciente de \(k\).
Sea la expansión de \(k\) en base \(b\) una cadena de dígitos. Una partición de esa cadena en bloques contiguos \(P_1,\dots,P_r\) produce el siguiente valor
$$T_b(k;P_1,\dots,P_r)=\sum_{j=1}^{r} V_b(P_j),$$
donde \(V_b(P_j)\) es el valor entero usual del bloque \(P_j\) en base \(b\). Entonces
$$f_b(k)=0\qquad (0\le k < b),$$
y para \(k\ge b\),
$$f_b(k)=1+\min_{P_1|\cdots|P_r} f_b\!\left(T_b(k;P_1,\dots,P_r)\right).$$
La partición en un solo bloque deja el número intacto, así que nunca mejora el óptimo; todas las particiones útiles crean una reducción estricta.
Sea \(s_b(k)\) la suma de los dígitos de \(k\) en base \(b\). El valor de cualquier bloque es al menos la suma de sus dígitos, por lo que toda partición satisface
$$s_b(k)\le T_b(k;P_1,\dots,P_r)\le k.$$
La igualdad de la izquierda ocurre cuando cada dígito forma su propio bloque. La igualdad de la derecha ocurre solo cuando toda la cadena se deja como un bloque único. Por tanto, toda transición útil cumple
$$s_b(k)\le T_b(k;P_1,\dots,P_r)<k.$$
Esto da inmediatamente un primer candidato válido:
$$f_b(k)\le 1+f_b(s_b(k)).$$
Como todos los destinos útiles son menores que \(k\), los valores \(f_b(0),f_b(1),\dots,f_b(k-1)\) pueden quedar fijados antes de calcular \(f_b(k)\).
Una vez fijado el orden de la programación dinámica, la tarea restante para un \(k\) dado es enumerar todas las sumas de bloques posibles. La implementación recorre los dígitos desde el menos significativo hasta el más significativo.
En cada nuevo dígito hay exactamente dos decisiones estructurales:
$$\text{empezar un bloque nuevo}\qquad \text{o} \qquad \text{extender el bloque actual}.$$
Esas dos decisiones generan el árbol binario completo de particiones. Si la expansión de \(k\) en base \(b\) tiene \(d\) dígitos, el árbol bruto tiene \(2^{d-1}\) hojas, una por cada forma de colocar separadores entre dígitos adyacentes. Ninguna partición se pierde y ninguna se cuenta dos veces.
Durante la búsqueda en profundidad, una parte de la cadena de dígitos ya ha sido procesada. Supongamos que un estado guarda
$$A=\text{suma de los bloques cerrados},\qquad C=\text{valor del bloque abierto actual},\qquad R=\text{suma de los dígitos aún no procesados}.$$
Entonces cualquier continuación de ese estado produce un total \(T\) que satisface
$$T\ge A+C+R.$$
La razón es que los dígitos superiores aún no procesados aportan como mínimo su suma \(R\) si se separan individualmente, y cualquier agrupación solo puede aumentar esa contribución. Del mismo modo, cerrar el bloque actual tal como está da \(C\), mientras que extenderlo solo puede hacerlo mayor. Por tanto,
$$L=A+C+R$$
es una cota inferior optimista para cualquier descendiente del nodo DFS actual.
Definimos
$$\Phi_k(L)=\min_{L\le x<k} f_b(x).$$
Como todos los valores siguientes útiles son menores que \(k\), este mínimo recorre solo estados ya resueltos. Si la mejor respuesta encontrada hasta el momento para el número actual es \(B\), entonces cualquier continuación del nodo DFS actual necesita al menos
$$1+\Phi_k(L)$$
pasos. En consecuencia, si
$$1+\Phi_k(L)\ge B,$$
todo el subárbol puede podarse con seguridad. Esa es la aceleración principal: no hace falta terminar una partición si la cota inferior ya demuestra que no puede mejorar la mejor respuesta conocida.
En base \(10\), la cadena de dígitos es \(13\). Las dos particiones son
$$13\qquad\text{y}\qquad 1|3\mapsto 1+3=4.$$
El movimiento no trivial lleva \(13\) a \(4<10\), así que
$$f_{10}(13)=1.$$
En base \(3\), tenemos \(13=(111)_3\). Las particiones contiguas producen
$$111_3=13,\qquad 1|11_3=1+4=5,\qquad 11|1_3=4+1=5,\qquad 1|1|1_3=3.$$
La mejor primera jugada es entonces \(13\to 3\). Pero \(3=(10)_3\) todavía no está por debajo de \(3\), y hace falta un paso más, \(10_3\to 1\), para terminar. Por lo tanto,
$$f_{3}(13)=2.$$
Así, \(13\) no contribuye a \(g(n,10,3)\), porque sus números óptimos de pasos en las dos bases son distintos.
La implementación construye la tabla de números de pasos para una base a la vez. Primero precalcula la suma de dígitos en base \(b\) de todos los números hasta \(n\) mediante la recurrencia
$$s_b(k)=s_b\!\left(\left\lfloor\frac{k}{b}\right\rfloor\right)+(k\bmod b).$$
Todos los valores menores que \(b\) se inicializan con paso \(0\), mientras que los valores mayores arrancan con una cota provisional grande. Para cada \(k\ge b\), el primer candidato es la partición en dígitos sueltos, es decir, \(1+f_b(s_b(k))\).
Después, una búsqueda en profundidad recorre los dígitos de derecha a izquierda y enumera todas las particiones contiguas eligiendo repetidamente entre cerrar el bloque actual y abrir otro nuevo, o extender el bloque actual con el siguiente dígito. En cada nodo evalúa la cota inferior \(L=A+C+R\), mejora la mejor respuesta usando el valor ya conocido en \(L\) y luego consulta el mínimo número de pasos resuelto en el sufijo \([L,k)\). Si ni siquiera ese mínimo optimista puede mejorar la mejor respuesta actual, la rama se descarta.
Un resumen compacto de mínimos de sufijo hace eficientes esas consultas: para cada número de pasos ya alcanzado, recuerda hasta qué posición hacia la derecha apareció ese valor entre los números ya resueltos. Eso basta para recuperar rápidamente \(\Phi_k(L)\) sin recorrer todo el intervalo.
Cuando la tabla está completa para una base, el mismo proceso se repite para la otra. Las implementaciones en C++, Python y Java siguen el mismo plan matemático; la versión en C++ evalúa las dos bases en paralelo cuando son distintas, la versión en Java realiza ambos recorridos directamente y la entrada en Python delega en el mismo cálculo en C++. Después, la implementación suma todos los \(k\) cuyos números de pasos coinciden. Una de las implementaciones también comprueba el valor pequeño
$$g(100,10,3)=3302$$
antes de emitir la respuesta final.
Sea \(d_b(k)\) el número de dígitos de \(k\) en base \(b\). Sin poda, un número con \(d\) dígitos tiene \(2^{d-1}\) particiones contiguas, de modo que la programación dinámica bruta costaría
$$O\!\left(\sum_{k=b}^{n} 2^{d_b(k)-1}\right).$$
Como \(d_b(k)\le \lfloor \log_b n \rfloor+1\), una cota grosera de peor caso es
$$O\!\left(n^{\,1+\log_b 2}\right)$$
para una base, antes de la poda. El método implementado usa dos arreglos lineales para los números de pasos y las sumas de dígitos, así que el consumo de memoria es \(O(n)\) por cálculo de una base, más una profundidad de recursión \(O(\log_b n)\) y una estructura pequeña para el resumen de sufijos.
Lo que vuelve práctico al programa no es una mejor fórmula asintótica de peor caso, sino la poda. El candidato inicial \(1+f_b(s_b(k))\) a menudo ya está cerca del óptimo, y la prueba de cota inferior elimina gran parte del árbol de particiones. Para la entrada requerida \(n=10^7\), esa reducción práctica es suficiente para que el cálculo completo sea viable.
对一个进制 \(b\)，把整数 \(k\) 写成 \(b\) 进制数字串，然后把这串数字切成若干个连续块。每个块都按 \(b\) 进制整数解释，再把这些块的数值相加，用这个和替换原来的 \(k\)。定义 \(f_b(k)\) 为把数值降到 \(< b\) 所需的最少步数。
题目要求计算
$$g(n,b_1,b_2)=\sum_{k=1}^{n}[f_{b_1}(k)=f_{b_2}(k)]\,k,$$
这里真正需要的是 \(g(10^7,10,3)\)。难点在于，每个整数都对应很多种连续分块方式；如果暴力搜索所有可能的分块序列和后续递归路径，规模会迅速失控。
解法对每个需要的进制分别计算所有 \(k\le n\) 的 \(f_b(k)\)。核心观察是：任何真正有用的一步都会把数变成一个更小的数，因此整个问题可以按 \(k\) 从小到大做动态规划。
把 \(k\) 的 \(b\) 进制表示看成一串数字。若把它切成连续块 \(P_1,\dots,P_r\)，下一步得到的值就是
$$T_b(k;P_1,\dots,P_r)=\sum_{j=1}^{r} V_b(P_j),$$
其中 \(V_b(P_j)\) 表示块 \(P_j\) 按 \(b\) 进制解释后的普通整数值。于是有
$$f_b(k)=0\qquad (0\le k < b),$$
而当 \(k\ge b\) 时，
$$f_b(k)=1+\min_{P_1|\cdots|P_r} f_b\!\left(T_b(k;P_1,\dots,P_r)\right).$$
如果整串数字完全不切分，只保留一个块，那么下一步仍然是原数 \(k\)，这显然不会改善最优解。所以真正有意义的转移一定是严格下降的转移。
记 \(s_b(k)\) 为 \(k\) 的 \(b\) 进制数位和。对任意一个块来说，它的数值至少不小于其中各位数字之和，因此任意分块都满足
$$s_b(k)\le T_b(k;P_1,\dots,P_r)\le k.$$
左边取等号时，意味着每一位数字都单独成块；右边取等号时，意味着整串数字保持为一个整体块。因此，对所有真正有用的转移，都有
$$s_b(k)\le T_b(k;P_1,\dots,P_r)<k.$$
这立刻给出一个天然的初始候选值：
$$f_b(k)\le 1+f_b(s_b(k)).$$
因为所有有效下一状态都严格小于 \(k\)，所以在计算 \(f_b(k)\) 之前，\(f_b(0),f_b(1),\dots,f_b(k-1)\) 都已经是最终值了。
确定了动态规划顺序之后，对固定的 \(k\) 来说，剩下的工作就是枚举所有可能的分块和。实现采用从低位到高位的扫描方式。
每读入一个新数字，结构上只有两个选择：开始一个新块，或者把该数字并入当前块。
这两个选择恰好生成完整的二叉分块树。如果 \(k\) 的 \(b\) 进制表示有 \(d\) 位，那么原始搜索树会有 \(2^{d-1}\) 个叶子，对应于相邻数字之间所有可能的切分方式。这样做不会漏掉任何一种连续分块，也不会重复计数。
在深度优先搜索过程中，一部分数字已经处理完，另一部分还没有。设某个状态记录了三个量：\(A\) 表示已经闭合的块之和，\(C\) 表示当前尚未闭合块的数值，\(R\) 表示还没处理的数字之和。
那么从这个状态出发的任何完整分块，其总和 \(T\) 都满足
$$T\ge A+C+R.$$
原因很直接：尚未处理的高位数字如果全部拆成单个数字块，最少也会贡献它们的数位和 \(R\)；把这些位进一步合并，只会让贡献更大。当前打开的块如果现在就关闭，会贡献 \(C\)；继续向左扩展这个块，也只会让它的数值不减。因此
$$L=A+C+R$$
就是当前 DFS 节点所有后代的一个乐观下界。
定义
$$\Phi_k(L)=\min_{L\le x<k} f_b(x).$$
由于所有有用的下一状态都严格小于 \(k\)，这个最小值只在已经求解过的状态中取。若当前数字 \(k\) 已经找到的最好答案是 \(B\)，那么当前 DFS 节点的任意后代都至少需要
$$1+\Phi_k(L)$$
步。如果已经有
$$1+\Phi_k(L)\ge B,$$
就说明这个子树无论怎么继续都不可能改进当前最优值，因此可以直接剪掉。真正让程序变快的关键正是这一点：不是把每一种分块都做到底，而是在下界已经足够说明“无望更优”时立刻停止。
在 \(10\) 进制里，数字串就是 \(13\)。它只有两种连续分块：
$$13\qquad\text{以及}\qquad 1|3\mapsto 1+3=4.$$
非平凡的一步把 \(13\) 直接变成 \(4<10\)，所以
$$f_{10}(13)=1.$$
在 \(3\) 进制里，\(13=(111)_3\)。所有连续分块对应的结果为
$$111_3=13,\qquad 1|11_3=1+4=5,\qquad 11|1_3=4+1=5,\qquad 1|1|1_3=3.$$
因此第一步最优只能做到 \(13\to 3\)。但 \(3=(10)_3\) 仍然没有降到 \(3\) 以下，还要再做一步 \(10_3\to 1\)。所以
$$f_{3}(13)=2.$$
这说明 \(13\) 不会计入 \(g(n,10,3)\)，因为它在两个进制下的最优步数不同。
实现先针对单个进制建立整张步数表。第一步是用递推式
$$s_b(k)=s_b\!\left(\left\lfloor\frac{k}{b}\right\rfloor\right)+(k\bmod b)$$
预处理所有不超过 \(n\) 的数位和。所有小于 \(b\) 的值都直接记为 \(0\) 步；更大的数先赋一个很宽松的上界。对于每个 \(k\ge b\)，最先得到的候选答案就是“把每一位都单独切开”所产生的 \(1+f_b(s_b(k))\)。
随后，深度优先搜索从低位向高位扫描数字，并通过不断在“关闭当前块、开始新块”和“把下一位并入当前块”之间二选一来枚举所有连续分块。在每个搜索节点上，程序都会计算下界 \(L=A+C+R\)，先用位置 \(L\) 处已经求出的值尝试更新当前最优答案，再查询区间 \([L,k)\) 内已知步数的最小值。如果连这个最乐观的后缀最小值都不可能击败当前最优值，那么这一整支搜索都会被剪掉。
为了高效回答这类查询，程序维护了一个紧凑的后缀最小值摘要：对每一种已经出现过的步数，只记录这种步数在已解决整数中最靠右出现到哪里。借助这份摘要，就能快速恢复 \(\Phi_k(L)\)，而不必线性扫描整个区间。
当一个进制的步数表建完之后，对另一个进制重复同样的过程。C++、Python 和 Java 的实现遵循相同的数学流程；C++ 版本在两个进制不同的时候会并行计算两张表，Java 版本直接顺序完成两遍，Python 入口则委托给同一套 C++ 计算。两张表都准备好以后，实现会把所有满足步数相同的 \(k\) 累加起来。其中一个实现还会在最终输出前检查较小的基准值
$$g(100,10,3)=3302.$$
记 \(d_b(k)\) 为 \(k\) 的 \(b\) 进制位数。如果完全不做剪枝，一个 \(d\) 位数有 \(2^{d-1}\) 种连续分块，因此原始动态规划的代价是
$$O\!\left(\sum_{k=b}^{n} 2^{d_b(k)-1}\right).$$
由于 \(d_b(k)\le \lfloor \log_b n \rfloor+1\)，可以得到一个粗略的单进制最坏情况上界
$$O\!\left(n^{\,1+\log_b 2}\right).$$
实现中还需要两个线性大小的数组来保存步数和数位和，所以单个进制的空间复杂度是 \(O(n)\)，外加 \(O(\log_b n)\) 的递归深度以及一个很小的后缀摘要结构。
真正让程序在实践中可行的并不是更漂亮的最坏情况公式，而是剪枝本身。初始候选值 \(1+f_b(s_b(k))\) 往往已经非常接近最优，而下界判定会砍掉绝大多数分块树分支。对于题目要求的 \(n=10^7\)，这种实际上的削减已经足以让完整计算落在可接受范围内。
Для основания \(b\) запишем число \(k\) в системе счисления по основанию \(b\) и разобьем его строку цифр на смежные блоки. Каждый блок интерпретируется как число в той же системе, после чего \(k\) заменяется суммой значений всех блоков. Обозначим через \(f_b(k)\) минимальное число таких шагов, после которых значение станет \(< b\).
Нужно вычислить
$$g(n,b_1,b_2)=\sum_{k=1}^{n}[f_{b_1}(k)=f_{b_2}(k)]\,k,$$
и в частности получить \(g(10^7,10,3)\). Сложность в том, что у каждого числа очень много возможных смежных разбиений, поэтому прямой перебор всех цепочек преобразований быстро становится неподъемным.
Решение вычисляет \(f_b(k)\) для всех \(k\le n\) отдельно для каждого нужного основания. Главная идея состоит в том, что любой полезный ход всегда уменьшает число строго. Значит, задачу можно решать динамически, перебирая \(k\) по возрастанию.
Пусть запись числа \(k\) в основании \(b\) рассматривается как строка цифр. Разбиение этой строки на смежные блоки \(P_1,\dots,P_r\) задает следующее значение
$$T_b(k;P_1,\dots,P_r)=\sum_{j=1}^{r} V_b(P_j),$$
где \(V_b(P_j)\) означает обычное целочисленное значение блока \(P_j\) в основании \(b\). Тогда
$$f_b(k)=0\qquad (0\le k < b),$$
а для \(k\ge b\)
$$f_b(k)=1+\min_{P_1|\cdots|P_r} f_b\!\left(T_b(k;P_1,\dots,P_r)\right).$$
Разбиение на один-единственный блок оставляет число неизменным, поэтому оптимум оно улучшить не может; все полезные разбиения дают строго меньший результат.
Обозначим через \(s_b(k)\) сумму цифр числа \(k\) в основании \(b\). Значение любого блока не меньше суммы его цифр, поэтому для любого разбиения выполняется
$$s_b(k)\le T_b(k;P_1,\dots,P_r)\le k.$$
Левая граница достигается, когда каждая цифра образует отдельный блок. Правая граница достигается только тогда, когда вся строка цифр оставлена одним блоком. Следовательно, любой полезный переход удовлетворяет
$$s_b(k)\le T_b(k;P_1,\dots,P_r)<k.$$
Отсюда сразу получается первый корректный кандидат:
$$f_b(k)\le 1+f_b(s_b(k)).$$
Поскольку все полезные целевые значения меньше \(k\), числа \(f_b(0),f_b(1),\dots,f_b(k-1)\) уже окончательно известны к моменту вычисления \(f_b(k)\).
После выбора порядка динамики остается для каждого фиксированного \(k\) перебрать все возможные суммы блоков. Реализация сканирует цифры от младшей к старшей.
При появлении очередной цифры есть ровно два структурных варианта:
$$\text{начать новый блок}\qquad \text{или} \qquad \text{продолжить текущий блок}.$$
Эти два выбора порождают полный двоичный дерево разбиений. Если запись \(k\) в основании \(b\) содержит \(d\) цифр, то необрезанное дерево имеет \(2^{d-1}\) листьев, по одному для каждого способа поставить разделители между соседними цифрами. Ни одно разбиение не пропускается и ни одно не учитывается дважды.
Во время поиска в глубину часть цифр уже обработана, а часть еще нет. Пусть состояние хранит
$$A=\text{сумму уже закрытых блоков},\qquad C=\text{значение текущего открытого блока},\qquad R=\text{сумму еще не обработанных цифр}.$$
Тогда любая полная достройка этого состояния дает итоговый результат \(T\), для которого верно
$$T\ge A+C+R.$$
Причина такова: неразобранные старшие цифры в минимальном случае дают свой цифровой суммарный вклад \(R\), если отделить их по одной, а любое объединение может этот вклад только увеличить. Аналогично, если закрыть текущий блок немедленно, он дает \(C\); дальнейшее расширение блока уменьшить его не может. Значит,
$$L=A+C+R$$
является оптимистичной нижней границей для любого потомка текущего узла DFS.
Введем обозначение
$$\Phi_k(L)=\min_{L\le x<k} f_b(x).$$
Так как все полезные следующие значения строго меньше \(k\), этот минимум берется только по уже решенным состояниям. Если лучшая найденная к данному моменту оценка для текущего числа равна \(B\), то любой потомок текущего узла DFS потребует как минимум
$$1+\Phi_k(L)$$
шагов. Поэтому при условии
$$1+\Phi_k(L)\ge B$$
весь поддерево можно безопасно отсечь. Именно это и дает основное ускорение: не нужно доводить разбиение до конца, если нижняя оценка уже показывает, что улучшить текущий лучший ответ невозможно.
В основании \(10\) строка цифр равна \(13\). Возможны два разбиения:
$$13\qquad\text{и}\qquad 1|3\mapsto 1+3=4.$$
Нетривиальный ход переводит \(13\) в \(4<10\), следовательно,
$$f_{10}(13)=1.$$
В основании \(3\) имеем \(13=(111)_3\). Смежные разбиения дают
$$111_3=13,\qquad 1|11_3=1+4=5,\qquad 11|1_3=4+1=5,\qquad 1|1|1_3=3.$$
Значит, лучший первый ход — это \(13\to 3\). Но \(3=(10)_3\) все еще не меньше \(3\), поэтому нужен еще один шаг \(10_3\to 1\). Итак,
$$f_{3}(13)=2.$$
Следовательно, число \(13\) не входит в сумму \(g(n,10,3)\), поскольку оптимальные числа шагов в двух основаниях различаются.
Реализация строит таблицу числа шагов отдельно для каждого основания. Сначала для всех чисел до \(n\) предварительно вычисляется сумма цифр в основании \(b\) по рекуррентной формуле
$$s_b(k)=s_b\!\left(\left\lfloor\frac{k}{b}\right\rfloor\right)+(k\bmod b).$$
Все значения меньше \(b\) сразу получают шаг \(0\), а большие числа стартуют с большой временной верхней оценкой. Для каждого \(k\ge b\) первым кандидатом служит разбиение на одиночные цифры, то есть \(1+f_b(s_b(k))\).
После этого поиск в глубину просматривает цифры справа налево и перечисляет все смежные разбиения, каждый раз выбирая одно из двух действий: закрыть текущий блок и начать новый или расширить текущий блок следующей цифрой. В каждом узле вычисляется нижняя граница \(L=A+C+R\), улучшается текущий лучший ответ с помощью уже известного значения в точке \(L\), а затем запрашивается минимум уже решенных шагов на суффиксе \([L,k)\). Если даже этот оптимистичный минимум не может улучшить текущий лучший ответ, ветвь отбрасывается.
Для эффективной поддержки таких запросов используется компактная сводка суффикс-минимумов: для каждого достигнутого числа шагов запоминается, насколько далеко вправо это значение уже встречалось среди решенных чисел. Этого достаточно, чтобы быстро восстановить \(\Phi_k(L)\), не просматривая весь интервал.
Когда таблица для одного основания завершена, тот же процесс повторяется для другого. Реализации на C++, Python и Java следуют одному и тому же математическому плану; версия на C++ вычисляет два основания параллельно, если они различаются, версия на Java выполняет оба прохода напрямую, а входная точка Python делегирует той же C++-реализации. После этого суммируются все \(k\), у которых числа шагов совпадают. Одна из реализаций также проверяет малый контрольный пример
$$g(100,10,3)=3302$$
перед выводом окончательного ответа.
Пусть \(d_b(k)\) — число цифр в записи \(k\) по основанию \(b\). Без отсечений число с \(d\) цифрами имеет \(2^{d-1}\) смежных разбиений, поэтому грубая динамика стоила бы
$$O\!\left(\sum_{k=b}^{n} 2^{d_b(k)-1}\right).$$
Так как \(d_b(k)\le \lfloor \log_b n \rfloor+1\), получаем грубую верхнюю оценку худшего случая
$$O\!\left(n^{\,1+\log_b 2}\right)$$
для одного основания еще до учета отсечений. Реализованный метод использует два линейных массива для чисел шагов и сумм цифр, так что память составляет \(O(n)\) на одно основание, плюс глубина рекурсии \(O(\log_b n)\) и небольшая структура сводки суффиксов.
Практическую эффективность обеспечивает не лучшая асимптотика худшего случая, а именно отсечение ветвей. Начальный кандидат \(1+f_b(s_b(k))\) часто уже близок к оптимальному, а проверка нижней границы удаляет большую часть дерева разбиений. Для требуемого входа \(n=10^7\) этого практического сокращения достаточно, чтобы полный расчет оказался выполнимым.
بالنسبة لأساس \(b\)، نكتب العدد \(k\) بهذا الأساس ثم نقسم سلسلة أرقامه إلى كتل متجاورة. تُفسَّر كل كتلة على أنها عدد في الأساس \(b\)، ثم يُستبدل \(k\) بمجموع قيم هذه الكتل. نرمز بـ \(f_b(k)\) إلى أقل عدد من الخطوات اللازمة لجعل القيمة \(< b\).
الكمية المطلوبة هي
$$g(n,b_1,b_2)=\sum_{k=1}^{n}[f_{b_1}(k)=f_{b_2}(k)]\,k,$$
والمطلوب فعليًا هو حساب \(g(10^7,10,3)\). تكمن الصعوبة في أن كل عدد يملك عددًا كبيرًا من طرق التقسيم المتجاور، ولذلك فإن البحث الساذج في جميع سلاسل الاختزال الممكنة يصبح ضخمًا جدًا.
يحسب الحل قيم \(f_b(k)\) لكل \(k\le n\) ولكل أساس مطلوب على حدة. والفكرة الحاسمة هي أن كل خطوة مفيدة تعطي عددًا أصغر بشكل صارم، وهذا يحول المسألة إلى برمجة ديناميكية تسير مع \(k\) تصاعديًا.
لننظر إلى تمثيل \(k\) في الأساس \(b\) بوصفه سلسلة أرقام. إذا قسّمنا هذه السلسلة إلى كتل متجاورة \(P_1,\dots,P_r\)، فإن القيمة التالية تكون
$$T_b(k;P_1,\dots,P_r)=\sum_{j=1}^{r} V_b(P_j),$$
حيث تمثل \(V_b(P_j)\) القيمة الصحيحة المعتادة للكتلة \(P_j\) في الأساس \(b\). عندئذٍ
$$f_b(k)=0\qquad (0\le k < b),$$
ولكل \(k\ge b\) نحصل على
$$f_b(k)=1+\min_{P_1|\cdots|P_r} f_b\!\left(T_b(k;P_1,\dots,P_r)\right).$$
أما التقسيم إلى كتلة واحدة فقط فيعيد العدد نفسه، ولذلك لا يمكن أن يحسن الجواب الأمثل؛ وكل تقسيم مفيد حقًا يعطي اختزالًا صارمًا.
لنعرف \(s_b(k)\) بأنه مجموع أرقام \(k\) في الأساس \(b\). فقيمة أي كتلة لا تقل عن مجموع أرقامها، ولذلك يحقق أي تقسيم
$$s_b(k)\le T_b(k;P_1,\dots,P_r)\le k.$$
وتتحقق المساواة اليسرى عندما يكون كل رقم كتلة مستقلة، بينما تتحقق المساواة اليمنى فقط عندما تبقى السلسلة كلها كتلة واحدة. ومن ثم فإن كل انتقال مفيد يحقق
$$s_b(k)\le T_b(k;P_1,\dots,P_r)<k.$$
وهذا يعطي مباشرة مرشحًا أوليًا صالحًا:
$$f_b(k)\le 1+f_b(s_b(k)).$$
وبما أن جميع القيم التالية المفيدة أصغر من \(k\)، فإن القيم \(f_b(0),f_b(1),\dots,f_b(k-1)\) تكون محسومة بالكامل قبل حساب \(f_b(k)\).
بعد تثبيت ترتيب البرمجة الديناميكية، تبقى المهمة هي تعداد جميع مجاميع الكتل الممكنة لعدد ثابت \(k\). تنفذ الخوارزمية ذلك بمسح الأرقام من الأقل أهمية إلى الأعلى أهمية.
عند كل رقم جديد توجد حالتان بنيويتان فقط: بدء كتلة جديدة، أو توسيع الكتلة الحالية.
هاتان الحالتان تولدان شجرة التقسيم الثنائية كاملة. فإذا كان تمثيل \(k\) في الأساس \(b\) يتكون من \(d\) أرقام، فإن شجرة البحث الخام تحوي \(2^{d-1}\) أوراقًا، واحدة لكل طريقة ممكنة لوضع الفواصل بين الأرقام المتجاورة. وبهذا لا يضيع أي تقسيم ولا يُعد أي تقسيم مرتين.
أثناء البحث بالعمق يكون جزء من سلسلة الأرقام قد عولج بالفعل. لنفترض أن حالة ما تخزن ثلاثة مقادير: \(A\) هو مجموع الكتل المغلقة، و\(C\) هو قيمة الكتلة المفتوحة الحالية، و\(R\) هو مجموع الأرقام التي لم تُعالج بعد.
فعندئذٍ فإن أي إكمال لتلك الحالة ينتج قيمة كلية \(T\) تحقق
$$T\ge A+C+R.$$
والسبب هو أن الأرقام العليا غير المعالجة تسهم على الأقل بمجموعها \(R\) إذا فُصلت كل واحدة منها في كتلة مستقلة، وأي دمج بينها لا يزيد إلا القيمة. وبالمثل، فإن إغلاق الكتلة الحالية كما هي يعطي \(C\)، وتمديدها لا يمكن أن ينقصها. لذلك فإن
$$L=A+C+R$$
يمثل حدًا سفليًا متفائلًا لجميع الفروع المنحدرة من عقدة DFS الحالية.
لنعرف
$$\Phi_k(L)=\min_{L\le x<k} f_b(x).$$
وبما أن جميع القيم التالية المفيدة أصغر من \(k\)، فإن هذا الحد الأدنى يؤخذ فقط على حالات سبق حلها. إذا كان أفضل جواب عُثر عليه حتى الآن للعدد الحالي هو \(B\)، فإن أي إكمال للعقدة الحالية يحتاج على الأقل إلى
$$1+\Phi_k(L)$$
خطوات. لذلك إذا تحقق
$$1+\Phi_k(L)\ge B,$$
فإن الشجرة الفرعية كلها يمكن تقليمها بأمان. هذا هو مصدر التسريع الحقيقي: لا حاجة إلى متابعة تقسيم ما حتى النهاية إذا كان الحد السفلي قد أثبت سلفًا أنه لن يتفوق على أفضل قيمة معروفة.
في الأساس \(10\)، سلسلة الأرقام هي \(13\). والتقسيمان الممكنان هما
$$13,\qquad 1|3\mapsto 1+3=4.$$
الخطوة غير التافهة ترسل \(13\) إلى \(4<10\)، ومن ثم
$$f_{10}(13)=1.$$
أما في الأساس \(3\) فلدينا \(13=(111)_3\). وتعطي التقسيمات المتجاورة
$$111_3=13,\qquad 1|11_3=1+4=5,\qquad 11|1_3=4+1=5,\qquad 1|1|1_3=3.$$
إذن أفضل خطوة أولى هي \(13\to 3\). لكن \(3=(10)_3\) ما زال ليس أصغر من \(3\)، ولذلك نحتاج خطوة أخرى هي \(10_3\to 1\). وبالتالي
$$f_{3}(13)=2.$$
وعليه فإن \(13\) لا يساهم في \(g(n,10,3)\)، لأن عدد الخطوات الأمثل يختلف بين الأساسين.
تبني الشيفرة جدول أعداد الخطوات لأساس واحد في كل مرة. أولًا تُحسب مجاميع الأرقام في الأساس \(b\) لكل الأعداد حتى \(n\) بالعلاقة
$$s_b(k)=s_b\!\left(\left\lfloor\frac{k}{b}\right\rfloor\right)+(k\bmod b).$$
كل القيم الأصغر من \(b\) تبدأ بعدد خطوات يساوي \(0\)، بينما تبدأ القيم الأكبر بحد علوي مؤقت كبير. ولكل \(k\ge b\)، يكون المرشح الأول هو تقسيم كل رقم في كتلة مستقلة، أي \(1+f_b(s_b(k))\).
بعد ذلك ينفذ بحث بالعمق يمسح الأرقام من اليمين إلى اليسار ويعدّد جميع التقسيمات المتجاورة عبر الاختيار المتكرر بين إغلاق الكتلة الحالية وفتح كتلة جديدة، أو توسيع الكتلة الحالية بالرقم التالي. عند كل عقدة يحسب الحد السفلي \(L=A+C+R\)، ثم يحسّن أفضل جواب باستخدام القيمة المعروفة مسبقًا عند \(L\)، وبعدها يستعلم عن أصغر عدد خطوات محلول على المقطع \([L,k)\). فإذا كان حتى هذا الحد الأدنى المتفائل لا يستطيع تحسين أفضل جواب حالي، تُهمل تلك الشعبة مباشرة.
ولجعل هذه الاستعلامات سريعة، تُحفظ بنية مضغوطة لحدود النهايات الدنيا على المقاطع اللاحقة: لكل عدد خطوات تحقق سابقًا، تتذكر البنية أبعد موضع إلى اليمين ظهر فيه ذلك العدد بين القيم المحسومة. وهذا يكفي لاستعادة \(\Phi_k(L)\) بسرعة من غير مسح كامل المجال.
بعد اكتمال الجدول لأساس واحد، تتكرر العملية نفسها للأساس الآخر. تتبع تطبيقات C++ وPython وJava الخطة الرياضية نفسها؛ فنسخة C++ تحسب الأساسين بالتوازي عندما يكونان مختلفين، ونسخة Java تنفذ المرورين مباشرة، أما مدخل Python فيفوّض الحساب إلى تنفيذ C++ نفسه. وبعد توفر الجدولين، تجمع الشيفرة كل القيم \(k\) التي تتساوى فيها أعداد الخطوات. كما أن أحد التطبيقات يفحص أيضًا القيمة الصغيرة
$$g(100,10,3)=3302$$
قبل إخراج الجواب النهائي.
لنرمز بعدد الأرقام في تمثيل \(k\) بالأساس \(b\) إلى \(d_b(k)\). من دون أي تقليم، يملك العدد ذو \(d\) أرقام عددًا مقداره \(2^{d-1}\) من التقسيمات المتجاورة، ولذلك تكون كلفة البرمجة الديناميكية الخام
$$O\!\left(\sum_{k=b}^{n} 2^{d_b(k)-1}\right).$$
وبما أن \(d_b(k)\le \lfloor \log_b n \rfloor+1\)، نحصل على حد علوي تقريبي لأسوأ حالة لأساس واحد هو
$$O\!\left(n^{\,1+\log_b 2}\right).$$
أما الطريقة المنفذة فتستخدم مصفوفتين بحجم خطي لحفظ أعداد الخطوات ومجاميع الأرقام، ولذلك تكون الذاكرة \(O(n)\) لكل حساب أساس، بالإضافة إلى عمق استدعاء \(O(\log_b n)\) وبنية صغيرة لتلخيص المقاطع اللاحقة.
ما يجعل البرنامج عمليًا ليس مجرد صيغة أفضل لأسوأ حالة، بل التقليم نفسه. فالمرشح الابتدائي \(1+f_b(s_b(k))\) يكون غالبًا قريبًا جدًا من الحل الأمثل، كما أن اختبار الحد السفلي يحذف معظم فروع شجرة التقسيم. وبالنسبة إلى الإدخال المطلوب \(n=10^7\)، فإن هذا الانكماش العملي يكفي لجعل الحساب الكامل ممكنًا.