We consider all natural numbers \(a,b\) with \(1 \le a,b < 100\) and ask for the largest possible decimal digit sum of \(a^b\). If we write the digit-sum function as \(s(n)\), the goal is to maximize \(s(a^b)\) over the \(99 \times 99 = 9801\) candidate pairs.
The search space in \((a,b)\) is small, but the values themselves are not. The largest candidate, \(99^{99}\), already has almost 200 decimal digits, so fixed-width arithmetic is not enough. The right approach is therefore not deeper number theory, but exact decimal arithmetic with reuse from one exponent to the next.
The implementations all exploit the same idea: for a fixed base \(a\), compute the powers \(a^1,a^2,\dots,a^{99}\) incrementally. Instead of rebuilding each power from scratch, store the current power in base 10 and multiply that representation by \(a\) once per step.
For any \(a > 1\), the number of decimal digits of \(a^b\) is
$$d(a,b)=\lfloor b\log_{10} a \rfloor+1.$$
This gives an immediate size bound for the whole problem. Since
$$d(99,99)=\lfloor 99\log_{10}99 \rfloor+1=198,$$
every candidate fits into a decimal array of length at most 198. That is far too large for ordinary machine integers, but tiny for a manual big-integer representation.
For a fixed base \(a\), write the current power \(a^b\) as
$$a^b=\sum_{i=0}^{m_b-1} d_i^{(b)}10^i,\qquad 0 \le d_i^{(b)} \le 9.$$
The digits are stored from least significant to most significant, so the coefficient list is exactly the decimal expansion in little-endian order. With this notation, the quantity we want to maximize is simply
$$s(a^b)=\sum_{i=0}^{m_b-1} d_i^{(b)}.$$
Once the decimal digits are available, the digit sum is just a linear scan of the vector.
Suppose the digits of \(a^b\) are already known. To obtain \(a^{b+1}=a \cdot a^b\), multiply the digit vector by the small integer \(a\) exactly as in schoolbook arithmetic. Start with carry \(c_0=0\), and for each position \(i\) define
$$t_i=a\,d_i^{(b)}+c_i,$$
$$d_i^{(b+1)}=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
After the old digits are exhausted, any remaining carry is split into decimal digits and appended to the vector. This recurrence is the core mathematical object behind all three implementations.
After processing positions \(0,1,\dots,i-1\), the multiplication step maintains the identity
$$a\sum_{j=0}^{i-1} d_j^{(b)}10^j=\sum_{j=0}^{i-1} d_j^{(b+1)}10^j+c_i10^i.$$
So the lower \(i\) digits of the new power are already correct, and every unprocessed contribution has been compressed into the single carry term \(c_i10^i\). When the scan ends and the final carry is flushed, the whole product \(a^{b+1}\) has been reconstructed exactly.
Start with \(99^1=99\), stored as digits \([9,9]\).
At the units digit,
$$9 \cdot 99 + 0 = 891,$$
so we write \(1\) and carry \(89\).
At the tens digit,
$$9 \cdot 99 + 89 = 980,$$
so we write \(0\) and carry \(98\).
Now the original digit vector is finished, and the remaining carry \(98\) contributes the last two digits \(8\) and \(9\). The new vector is \([1,0,8,9]\), which means
$$99^2=9801,\qquad s(99^2)=9+8+0+1=18.$$
One more application of the same recurrence gives \(99^3=970299\), again without restarting from scratch.
Once decimal multiplication is available, the remaining search is tiny. There are only 9801 pairs \((a,b)\), and for each fixed base \(a\) the sequence of powers is generated in order by repeated multiplication. No pruning is required, and no candidate is missed: after the \(b\)-th multiplication, the maintained vector is exactly \(a^b\).
The cases \(a=1\) or \(b=1\) are harmless and can stay in the sweep. They never produce the optimum, but including them keeps the code uniform and the mathematics cleaner.
The C++, Python, and Java implementations all follow the same structure. For each base \(a\), they reset the current decimal vector to \([1]\), representing \(a^0=1\). Then they iterate the exponent from \(1\) up to the chosen limit, multiply the vector by \(a\), compute the digit sum of the updated vector, and compare it with the best value seen so far.
The multiplication step is performed directly on the stored decimal digits. Each digit is replaced by its new value modulo 10, while the quotient becomes the carry for the next position. If a carry remains after the last stored digit, new digits are appended until the carry vanishes. Because the digits are stored least-significant first, the carry naturally moves forward through the list.
The implementations therefore never need floating-point arithmetic, never recompute an already known power, and never store more than one current power per base. They also include a small checkpoint on the reduced range \(a,b \le 10\), where the correct maximum digit sum is \(45\), to confirm that the digit machinery is behaving correctly.
Let \(A=99\), \(B=99\), and let
$$D=\max_{1 \le a,b \le 99} d(a,b)=198.$$
For one state \((a,b)\), the multiplication-by-\(a\) step touches each stored digit once, and the digit-sum pass also touches each stored digit once. So each state costs \(O(D)\) time, giving an overall running time of
$$O(ABD).$$
In this problem that means only a few million digit operations, which is why the full exhaustive search is easily practical. The memory usage is \(O(D)\), because the implementation stores only the current power's decimal digits plus a few scalar counters.
Wir betrachten alle natürlichen Zahlen \(a,b\) mit \(1 \le a,b < 100\) und suchen die größtmögliche Dezimalziffernsumme von \(a^b\). Bezeichnet \(s(n)\) die Ziffernsumme von \(n\), so soll also \(s(a^b)\) über alle \(99 \times 99 = 9801\) Kandidaten maximiert werden.
Der Suchraum in den Parametern ist klein, die entstehenden Zahlen selbst aber nicht. Schon \(99^{99}\) hat fast 200 Dezimalstellen. Gewöhnliche Maschinenzahlen reichen daher nicht aus. Der richtige Zugang ist exakte Dezimalarithmetik, bei der man die bereits berechnete Potenz für den nächsten Exponenten wiederverwendet.
Alle drei Implementierungen benutzen dieselbe Grundidee: Für eine feste Basis \(a\) werden die Potenzen \(a^1,a^2,\dots,a^{99}\) schrittweise aufgebaut. Anstatt jede Potenz neu zu berechnen, speichert man die aktuelle Potenz in Dezimaldarstellung und multipliziert diese Darstellung in jedem Schritt genau einmal mit \(a\).
Für \(a > 1\) besitzt \(a^b\) genau
$$d(a,b)=\lfloor b\log_{10} a \rfloor+1$$
Dezimalstellen. Damit erhält man sofort eine globale Schranke. Wegen
$$d(99,99)=\lfloor 99\log_{10}99 \rfloor+1=198$$
passt jeder Kandidat in ein Dezimalarray der Länge höchstens 198. Für Standard-Integer ist das viel zu groß, für eine selbst verwaltete Zifferndarstellung aber sehr klein.
Für eine feste Basis \(a\) schreiben wir
$$a^b=\sum_{i=0}^{m_b-1} d_i^{(b)}10^i,\qquad 0 \le d_i^{(b)} \le 9.$$
Die Ziffern werden von der niederwertigsten zur höchstwertigen gespeichert. Der Vektor ist also einfach die Dezimalentwicklung in Little-Endian-Reihenfolge. Mit dieser Notation lautet die zu maximierende Größe
$$s(a^b)=\sum_{i=0}^{m_b-1} d_i^{(b)}.$$
Sobald die Dezimalziffern bekannt sind, erhält man die Ziffernsumme durch einen linearen Durchlauf über den Vektor.
Seien die Ziffern von \(a^b\) bekannt. Dann wird \(a^{b+1}=a \cdot a^b\) durch eine Schulbuchmultiplikation mit der kleinen Zahl \(a\) erzeugt. Man startet mit Übertrag \(c_0=0\) und definiert für jede Position \(i\)
$$t_i=a\,d_i^{(b)}+c_i,$$
$$d_i^{(b+1)}=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
Sind alle alten Ziffern verarbeitet, wird ein verbleibender Übertrag selbst wieder in Dezimalziffern zerlegt und angehängt. Genau diese Rekurrenz ist das zentrale mathematische Objekt der Implementierungen.
Nach der Verarbeitung der Positionen \(0,1,\dots,i-1\) gilt stets
$$a\sum_{j=0}^{i-1} d_j^{(b)}10^j=\sum_{j=0}^{i-1} d_j^{(b+1)}10^j+c_i10^i.$$
Die unteren \(i\) Ziffern der neuen Potenz sind also bereits korrekt, und alle noch nicht verarbeiteten Beiträge stecken vollständig im einzelnen Übertragsterm \(c_i10^i\). Wenn der Durchlauf endet und der letzte Übertrag ausgeschrieben wird, ist das gesamte Produkt exakt rekonstruiert.
Wir beginnen mit \(99^1=99\), gespeichert als \([9,9]\).
An der Einerstelle gilt
$$9 \cdot 99 + 0 = 891,$$
also schreiben wir \(1\) und tragen \(89\) weiter.
An der Zehnerstelle gilt
$$9 \cdot 99 + 89 = 980,$$
also schreiben wir \(0\) und tragen \(98\) weiter.
Danach sind die ursprünglichen Ziffern aufgebraucht; der Übertrag \(98\) liefert noch die Ziffern \(8\) und \(9\). Der neue Vektor ist \([1,0,8,9]\), also
$$99^2=9801,\qquad s(99^2)=9+8+0+1=18.$$
Mit derselben Rekurrenz erhält man im nächsten Schritt \(99^3=970299\), ohne wieder von vorne beginnen zu müssen.
Sobald die Dezimalmultiplikation verfügbar ist, bleibt nur noch eine sehr kleine Suche. Es gibt lediglich 9801 Paare \((a,b)\), und für jede feste Basis \(a\) werden die Potenzen der Reihe nach durch wiederholte Multiplikation erzeugt. Weder Abschneiden noch tiefergehende Zahlentheorie ist nötig: Nach dem \(b\)-ten Multiplikationsschritt stellt der Vektor genau \(a^b\) dar.
Auch die Fälle \(a=1\) oder \(b=1\) dürfen einfach mitlaufen. Sie liefern nie das Optimum, aber ihre Einbeziehung hält sowohl den Code als auch die mathematische Beschreibung einheitlich.
Die C++-, Python- und Java-Implementierungen folgen alle demselben Ablauf. Für jede Basis \(a\) wird der aktuelle Dezimalvektor auf \([1]\) zurückgesetzt, also auf die Darstellung von \(a^0=1\). Danach läuft der Exponent von \(1\) bis zur Obergrenze. In jedem Schritt wird der Vektor mit \(a\) multipliziert, die Ziffernsumme des aktualisierten Vektors berechnet und mit dem bisher besten Wert verglichen.
Die Multiplikation geschieht direkt auf den gespeicherten Dezimalziffern. Jede Ziffer wird durch ihren neuen Wert modulo 10 ersetzt, und der Quotient wird als Übertrag an die nächste Position weitergereicht. Bleibt nach der letzten gespeicherten Ziffer noch ein Übertrag übrig, werden neue Ziffern angehängt, bis der Übertrag verschwunden ist. Weil die Ziffern niederwertig zuerst gespeichert sind, wandert der Übertrag ganz natürlich nach vorne durch die Liste.
Die Implementierungen benötigen deshalb weder Gleitkommazahlen noch eine Neuberechnung bereits bekannter Potenzen, und pro Basis wird nie mehr als eine aktuelle Potenz gespeichert. Zusätzlich gibt es einen kleinen Selbsttest für den eingeschränkten Bereich \(a,b \le 10\), in dem die korrekte maximale Ziffernsumme \(45\) ist.
Seien \(A=99\), \(B=99\) und
$$D=\max_{1 \le a,b \le 99} d(a,b)=198.$$
Für einen einzelnen Zustand \((a,b)\) berührt die Multiplikation mit \(a\) jede gespeicherte Ziffer genau einmal, und auch die Berechnung der Ziffernsumme durchläuft jede gespeicherte Ziffer einmal. Damit kostet jeder Zustand \(O(D)\) Zeit, insgesamt also
$$O(ABD).$$
Für dieses Problem sind das nur wenige Millionen Ziffernoperationen, weshalb die vollständige Enumeration problemlos praktikabel ist. Der Speicherbedarf beträgt \(O(D)\), da nur die Dezimalziffern der aktuellen Potenz sowie einige wenige Skalare gehalten werden.
\(1 \le a,b < 100\) koşulunu sağlayan tüm doğal sayılar için \(a^b\)'nin onluk basamaktaki rakam toplamının alabileceği en büyük değeri arıyoruz. Rakam toplamını \(s(n)\) ile gösterirsek amaç, toplam \(99 \times 99 = 9801\) aday çift üzerinde \(s(a^b)\)'yi maksimize etmektir.
Parametre uzayı küçük olsa da oluşan sayılar küçük değildir. En büyük aday olan \(99^{99}\) neredeyse 200 basamaklıdır. Bu yüzden sabit genişlikli tamsayılar yeterli olmaz. Doğru yöntem, bir kuvvetten sonrakine geçerken mevcut sonucu yeniden kullanan tam onluk aritmetiktir.
Üç uygulamanın da kullandığı temel fikir aynıdır: sabit bir \(a\) tabanı için \(a^1,a^2,\dots,a^{99}\) kuvvetlerini art arda üretmek. Her kuvveti baştan hesaplamak yerine mevcut kuvvetin onluk gösterimini saklar ve her adımda bu gösterimi bir kez daha \(a\) ile çarparız.
\(a > 1\) için \(a^b\)'nin basamak sayısı
$$d(a,b)=\lfloor b\log_{10} a \rfloor+1$$
formülüyle verilir. Böylece küresel büyüklük sınırı hemen çıkar. Çünkü
$$d(99,99)=\lfloor 99\log_{10}99 \rfloor+1=198,$$
her aday en fazla 198 uzunluklu bir onluk diziye sığar. Bu, sıradan makine tamsayıları için fazla büyüktür ama elde yönetilen bir basamak vektörü için çok küçüktür.
Sabit bir \(a\) için mevcut kuvveti
$$a^b=\sum_{i=0}^{m_b-1} d_i^{(b)}10^i,\qquad 0 \le d_i^{(b)} \le 9$$
şeklinde yazalım. Basamaklar en düşük anlamlı basamaktan en yüksek anlamlı basamağa doğru saklanır. Yani liste, sayının little-endian sıralı onluk açılımıdır. Bu gösterimde maksimize etmek istediğimiz nicelik doğrudan
$$s(a^b)=\sum_{i=0}^{m_b-1} d_i^{(b)}$$
olur. Basamaklar eldeyse rakam toplamı yalnızca bu vektör üzerinde doğrusal bir toplamdır.
\(a^b\)'nin basamakları biliniyorsa \(a^{b+1}=a \cdot a^b\) sayısı, küçük bir tam sayıyla yapılan klasik çarpma ile elde edilir. Başlangıç taşıması \(c_0=0\) olsun. Her konum \(i\) için
$$t_i=a\,d_i^{(b)}+c_i,$$
$$d_i^{(b+1)}=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor$$
tanımlarını yaparız. Eski basamaklar bittikten sonra elde kalan taşıma da onluk basamaklarına ayrılıp sona eklenir. Üç çözümün ortak çekirdeği tam olarak bu bağıntıdır.
\(0,1,\dots,i-1\) konumları işlendikten sonra şu özdeşlik korunur:
$$a\sum_{j=0}^{i-1} d_j^{(b)}10^j=\sum_{j=0}^{i-1} d_j^{(b+1)}10^j+c_i10^i.$$
Buna göre yeni kuvvetin alt \(i\) basamağı artık kesin olarak doğrudur; henüz işlenmeyen her şey tek bir \(c_i10^i\) taşıma teriminde toplanmıştır. Tarama bittiğinde ve son taşıma yazıldığında tüm çarpım eksiksiz biçimde elde edilir.
\(99^1=99\) sayısını \([9,9]\) olarak saklayarak başlayalım.
Birler basamağında
$$9 \cdot 99 + 0 = 891$$
olduğu için yeni basamak \(1\), taşıma \(89\) olur.
Onlar basamağında
$$9 \cdot 99 + 89 = 980$$
olduğu için yeni basamak \(0\), taşıma \(98\) olur.
Artık eski basamaklar bitmiştir; geriye kalan \(98\) taşıması da \(8\) ve \(9\) basamaklarını verir. Böylece yeni vektör \([1,0,8,9]\) olur; yani
$$99^2=9801,\qquad s(99^2)=9+8+0+1=18.$$
Aynı bağıntıyı bir kez daha uygulamak \(99^3=970299\) sonucunu verir. Yani önceki kuvveti çöpe atmadan bir sonrakine geçebiliriz.
Onluk çarpma hazır olduktan sonra geriye çok küçük bir arama kalır. Yalnızca 9801 adet \((a,b)\) çifti vardır ve sabit bir \(a\) için tüm kuvvetler sırayla üretilir. Ne budama gerekir ne de ileri seviye sayı teorisi: \(b\). çarpma adımı bittiğinde eldeki vektör tam olarak \(a^b\)'dir.
\(a=1\) veya \(b=1\) durumları da rahatlıkla taramada bırakılabilir. Bunlar optimumu vermez, fakat dahil edilmeleri hem kodu hem de açıklamayı tek biçimli tutar.
C++, Python ve Java uygulamaları aynı iskeleti kullanır. Her taban \(a\) için mevcut onluk vektör \([1]\) değerine sıfırlanır; bu, \(a^0=1\) gösterimidir. Sonra üs \(1\)'den üst sınıra kadar ilerletilir. Her adımda vektör \(a\) ile çarpılır, güncellenmiş vektörün rakam toplamı alınır ve bulunan en iyi değerle karşılaştırılır.
Çarpma işlemi doğrudan saklanan onluk basamakların üzerinde yapılır. Her basamak yeni değerinin 10'a göre kalanı ile değiştirilir, bölüm kısmı ise bir sonraki basamağa aktarılacak taşıma olur. Son saklanan basamaktan sonra hâlâ taşıma kalmışsa taşıma sıfırlanana kadar yeni basamaklar sona eklenir. Basamaklar en düşük anlamlıdan başladığı için taşıma listede doğal olarak ileri doğru yürür.
Bu yüzden uygulamalar kayan noktalı aritmetiğe ihtiyaç duymaz, daha önce üretilmiş bir kuvveti yeniden hesaplamaz ve her taban için aynı anda yalnızca tek bir güncel kuvvet tutar. Ayrıca \(a,b \le 10\) alt problemi üzerinde doğru maksimumun \(45\) olduğunu kontrol eden küçük bir sağlamlık testi de vardır.
\(A=99\), \(B=99\) ve
$$D=\max_{1 \le a,b \le 99} d(a,b)=198$$
olsun. Tek bir \((a,b)\) durumu için \(a\) ile çarpma adımı her saklanan basamağa bir kez dokunur; rakam toplamı hesabı da aynı basamakları bir kez daha dolaşır. Bu nedenle her durumun maliyeti \(O(D)\), toplam çalışma süresi ise
$$O(ABD)$$
olur. Bu problemde bu, yalnızca birkaç milyon basamak işlemi demektir; dolayısıyla tam tarama rahatlıkla uygulanabilir. Bellek kullanımı \(O(D)\)'dir, çünkü yalnızca mevcut kuvvetin onluk basamakları ve birkaç skaler değer saklanır.
Consideramos todos los números naturales \(a,b\) con \(1 \le a,b < 100\) y buscamos la mayor suma posible de las cifras decimales de \(a^b\). Si denotamos por \(s(n)\) la suma de cifras de \(n\), el objetivo es maximizar \(s(a^b)\) entre los \(99 \times 99 = 9801\) pares candidatos.
El espacio de búsqueda en \((a,b)\) es pequeño, pero los valores que aparecen no lo son. El mayor candidato, \(99^{99}\), ya tiene casi 200 cifras decimales, de modo que la aritmética entera de tamaño fijo no basta. La idea correcta no es una teoría profunda, sino aritmética decimal exacta reutilizando una potencia para construir la siguiente.
Las tres implementaciones explotan la misma observación: para una base fija \(a\), las potencias \(a^1,a^2,\dots,a^{99}\) se generan de forma incremental. En lugar de recalcular cada potencia desde cero, se guarda la potencia actual en base 10 y en cada paso se multiplica esa representación una sola vez por \(a\).
Para \(a > 1\), el número de cifras decimales de \(a^b\) es
$$d(a,b)=\lfloor b\log_{10} a \rfloor+1.$$
Eso da de inmediato una cota global para el problema. Como
$$d(99,99)=\lfloor 99\log_{10}99 \rfloor+1=198,$$
cada candidato cabe en un arreglo decimal de longitud a lo sumo 198. Es demasiado grande para enteros ordinarios, pero muy pequeño para una representación manual por cifras.
Para una base fija \(a\), escribimos
$$a^b=\sum_{i=0}^{m_b-1} d_i^{(b)}10^i,\qquad 0 \le d_i^{(b)} \le 9.$$
Las cifras se almacenan de la menos significativa a la más significativa. Así, la lista coincide exactamente con la expansión decimal en orden little-endian. Con esta notación, la cantidad que queremos maximizar es simplemente
$$s(a^b)=\sum_{i=0}^{m_b-1} d_i^{(b)}.$$
Una vez conocidas las cifras decimales, la suma de cifras es solo un recorrido lineal del vector.
Supongamos que ya conocemos las cifras de \(a^b\). Para obtener \(a^{b+1}=a \cdot a^b\), multiplicamos el vector decimal por el entero pequeño \(a\) exactamente como en la multiplicación escolar. Empezamos con acarreo \(c_0=0\) y para cada posición \(i\) definimos
$$t_i=a\,d_i^{(b)}+c_i,$$
$$d_i^{(b+1)}=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
Cuando se agotan las cifras antiguas, cualquier acarreo restante se descompone también en cifras decimales y se añade al final. Esta recurrencia es el objeto matemático central de las tres soluciones.
Después de procesar las posiciones \(0,1,\dots,i-1\), se mantiene la identidad
$$a\sum_{j=0}^{i-1} d_j^{(b)}10^j=\sum_{j=0}^{i-1} d_j^{(b+1)}10^j+c_i10^i.$$
Eso significa que las \(i\) cifras inferiores de la nueva potencia ya son correctas, y toda la información pendiente está condensada en el término de acarreo \(c_i10^i\). Cuando termina el barrido y se vacía el último acarreo, el producto completo queda reconstruido exactamente.
Comenzamos con \(99^1=99\), almacenado como \([9,9]\).
En la cifra de unidades,
$$9 \cdot 99 + 0 = 891,$$
así que escribimos \(1\) y arrastramos \(89\).
En la cifra de decenas,
$$9 \cdot 99 + 89 = 980,$$
así que escribimos \(0\) y arrastramos \(98\).
Ya no quedan cifras antiguas, y el acarreo \(98\) aporta las dos cifras finales \(8\) y \(9\). El nuevo vector es \([1,0,8,9]\), es decir,
$$99^2=9801,\qquad s(99^2)=9+8+0+1=18.$$
Una aplicación más de la misma recurrencia produce \(99^3=970299\), sin volver a empezar desde cero.
Una vez disponible la multiplicación decimal, la búsqueda restante es diminuta. Solo hay 9801 pares \((a,b)\), y para cada base fija \(a\) las potencias se generan en orden mediante multiplicaciones repetidas. No hace falta poda ni teoría de números adicional: después del paso \(b\), el vector mantenido es exactamente \(a^b\).
Los casos \(a=1\) o \(b=1\) pueden quedarse en el recorrido sin problema. Nunca dan el máximo, pero incluirlos mantiene uniforme tanto el algoritmo como la explicación.
Las implementaciones en C++, Python y Java usan exactamente el mismo esquema. Para cada base \(a\), reinician el vector decimal actual a \([1]\), que representa \(a^0=1\). Luego hacen avanzar el exponente desde \(1\) hasta el límite elegido. En cada paso multiplican el vector por \(a\), calculan la suma de cifras del vector actualizado y comparan ese valor con el mejor máximo observado.
La multiplicación se hace directamente sobre las cifras decimales almacenadas. Cada cifra se reemplaza por su nuevo valor módulo 10, y el cociente se convierte en el acarreo de la posición siguiente. Si aún queda acarreo después de la última cifra almacenada, se añaden nuevas cifras hasta que el acarreo desaparezca. Como las cifras están guardadas desde la menos significativa, el acarreo avanza naturalmente hacia delante por la lista.
Por eso la implementación nunca necesita aritmética en coma flotante, nunca recalcula una potencia ya conocida y nunca almacena más de una potencia actual por base. Además, incluye una pequeña comprobación en el subproblema \(a,b \le 10\), donde la suma máxima correcta es \(45\), para verificar que el manejo de cifras está funcionando bien.
Sea \(A=99\), \(B=99\), y
$$D=\max_{1 \le a,b \le 99} d(a,b)=198.$$
Para un estado \((a,b)\), la multiplicación por \(a\) toca cada cifra almacenada una vez, y el cálculo de la suma de cifras vuelve a recorrer esas mismas cifras una vez más. Así, cada estado cuesta \(O(D)\) tiempo, y el tiempo total es
$$O(ABD).$$
En este problema eso significa solo unos pocos millones de operaciones sobre cifras, de modo que la enumeración completa es perfectamente viable. El uso de memoria es \(O(D)\), porque solo se almacenan las cifras decimales de la potencia actual y unos pocos contadores escalares.
我们要在所有满足 \(1 \le a,b < 100\) 的自然数对中，找出 \(a^b\) 的十进制数位和所能达到的最大值。记数位和函数为 \(s(n)\)，那么目标就是在总共 \(99 \times 99 = 9801\) 个候选对里最大化 \(s(a^b)\)。
参数范围本身并不大，但数值大小一点也不小。最大的候选 \(99^{99}\) 已经接近 200 位十进制数，因此普通固定宽度整数根本不够。这个问题真正需要的不是复杂的高阶数论，而是能够复用前一幂结果的精确十进制大整数运算。
三个实现都建立在同一个核心思路上：对固定底数 \(a\)，按顺序生成 \(a^1,a^2,\dots,a^{99}\)。与其每次从头计算 \(a^b\)，不如把当前幂保存成十进制数字向量，然后每一步再乘一次 \(a\)。
当 \(a > 1\) 时，\(a^b\) 的十进制位数满足
$$d(a,b)=\lfloor b\log_{10} a \rfloor+1.$$
这马上给出了整个问题的规模上界。因为
$$d(99,99)=\lfloor 99\log_{10}99 \rfloor+1=198,$$
所以任何候选值都可以装进一个长度不超过 198 的十进制数组中。对于机器整数来说这已经太大，但对于手工维护的按位表示来说，这个长度其实很小。
对固定底数 \(a\)，把当前幂写成
$$a^b=\sum_{i=0}^{m_b-1} d_i^{(b)}10^i,\qquad 0 \le d_i^{(b)} \le 9.$$
这里的数字从最低位到最高位存放，所以这个向量就是 little-endian 顺序的十进制展开。在这种表示下，题目要优化的量就是
$$s(a^b)=\sum_{i=0}^{m_b-1} d_i^{(b)}.$$
也就是说，只要当前幂的十进制数字已经在数组里，数位和就只是一次线性求和。
假设 \(a^b\) 的各位数字已经知道。要得到 \(a^{b+1}=a \cdot a^b\)，只需把这个十进制向量乘以小整数 \(a\)，过程与竖式乘法完全一样。设初始进位 \(c_0=0\)，对每个位置 \(i\) 定义
$$t_i=a\,d_i^{(b)}+c_i,$$
$$d_i^{(b+1)}=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
当旧向量的数字处理完之后，如果还剩进位，就继续把进位拆成十进制数字附加到末尾。这个递推关系正是三个实现共享的数学核心。
在处理完位置 \(0,1,\dots,i-1\) 之后，算法始终保持
$$a\sum_{j=0}^{i-1} d_j^{(b)}10^j=\sum_{j=0}^{i-1} d_j^{(b+1)}10^j+c_i10^i.$$
这意味着新幂的低 \(i\) 位已经完全正确，尚未处理的全部影响都被压缩进单个进位项 \(c_i10^i\) 里。等扫描结束并把最后的进位全部写出，整个乘积 \(a^{b+1}\) 就被精确重建了。
从 \(99^1=99\) 开始，它的数字向量是 \([9,9]\)。
个位上有
$$9 \cdot 99 + 0 = 891,$$
所以写下新个位 \(1\)，并把进位设为 \(89\)。
十位上有
$$9 \cdot 99 + 89 = 980,$$
所以写下新十位 \(0\)，并把进位设为 \(98\)。
原来的数字已经处理完，剩余进位 \(98\) 再提供两个数字 \(8\) 和 \(9\)。于是新向量变成 \([1,0,8,9]\)，也就是
$$99^2=9801,\qquad s(99^2)=9+8+0+1=18.$$
再做一次同样的更新，就能得到 \(99^3=970299\)，完全不需要从头重新算幂。
一旦十进制乘法实现好了，剩下的搜索规模其实非常小。总共只有 9801 个 \((a,b)\) 组合，而对每个固定底数 \(a\)，所有幂都是按顺序通过重复乘法生成的。既不需要剪枝，也不需要额外的高深性质：做完第 \(b\) 次更新之后，向量保存的就恰好是 \(a^b\)。
\(a=1\) 或 \(b=1\) 这样的平凡情况也可以直接保留在循环里。它们不会给出最终最大值，但保留它们可以让算法和证明都保持统一。
C++、Python 和 Java 三个实现的结构完全一致。对每个底数 \(a\)，先把当前十进制向量重置为 \([1]\)，也就是 \(a^0=1\) 的表示。然后让指数从 \(1\) 递增到上界。每一步都把这个向量乘以 \(a\)，计算更新后数字向量的数位和，再用它更新当前全局最大值。
乘法直接在保存的十进制数字上进行。每一位被替换为新值对 10 取模后的结果，而整除 10 的部分作为进位传给下一位。如果在最后一个已存数字之后仍然还有进位，就继续追加新数字，直到进位为零。由于数字按从低位到高位的顺序存放，进位也就自然地沿着数组向前传播。
因此，这些实现既不需要浮点数，也不会重复计算已经得到的幂，而且对每个底数始终只保留一个“当前幂”。它们还包含了一个小型检查：在缩小范围 \(a,b \le 10\) 时，正确的最大数位和应当是 \(45\)，这可以用来验证按位运算逻辑是否正确。
设 \(A=99\)、\(B=99\)，并且
$$D=\max_{1 \le a,b \le 99} d(a,b)=198.$$
对于单个状态 \((a,b)\)，乘以 \(a\) 的更新会逐个访问当前保存的每一位数字，而计算数位和也会再线性扫描一次这些数字。因此每个状态的时间代价是 \(O(D)\)，总时间复杂度为
$$O(ABD).$$
在本题里，这只相当于几百万次数字级别的基本操作，所以完整穷举完全可行。空间复杂度是 \(O(D)\)，因为实现只保存当前幂的十进制数字以及少量标量变量。
Нужно рассмотреть все натуральные числа \(a,b\) при \(1 \le a,b < 100\) и найти максимально возможную сумму десятичных цифр числа \(a^b\). Если обозначить сумму цифр через \(s(n)\), то задача состоит в максимизации \(s(a^b)\) по всем \(99 \times 99 = 9801\) парам.
Само пространство параметров невелико, но возникающие числа вовсе не малы. Уже \(99^{99}\) имеет почти 200 десятичных цифр, поэтому обычных целых фиксированной длины недостаточно. Здесь нужен не хитрый теоретический трюк, а точная десятичная арифметика с переиспользованием предыдущей степени при переходе к следующей.
Во всех трех реализациях используется одна и та же идея: для фиксированного основания \(a\) степени \(a^1,a^2,\dots,a^{99}\) строятся последовательно. Вместо того чтобы заново вычислять каждую степень, текущую степень хранят в десятичном виде и на каждом шаге один раз умножают эту запись на \(a\).
Для \(a > 1\) число десятичных цифр в \(a^b\) равно
$$d(a,b)=\lfloor b\log_{10} a \rfloor+1.$$
Это сразу дает глобальную оценку размера. Поскольку
$$d(99,99)=\lfloor 99\log_{10}99 \rfloor+1=198,$$
любой кандидат помещается в десятичный массив длины не более 198. Для стандартных машинных целых это слишком много, а для собственного массива цифр это совсем немного.
Для фиксированного основания \(a\) запишем текущую степень в виде
$$a^b=\sum_{i=0}^{m_b-1} d_i^{(b)}10^i,\qquad 0 \le d_i^{(b)} \le 9.$$
Цифры хранятся от младшей к старшей, то есть список совпадает с десятичной записью в little-endian порядке. В этих обозначениях величина, которую нужно максимизировать, имеет вид
$$s(a^b)=\sum_{i=0}^{m_b-1} d_i^{(b)}.$$
Когда десятичные цифры уже известны, сумма цифр получается простым линейным проходом по вектору.
Пусть цифры числа \(a^b\) уже известны. Тогда \(a^{b+1}=a \cdot a^b\) строится умножением десятичного вектора на малое число \(a\), точно как в школьном алгоритме. Берем начальный перенос \(c_0=0\) и для каждой позиции \(i\) определяем
$$t_i=a\,d_i^{(b)}+c_i,$$
$$d_i^{(b+1)}=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
После обработки старых цифр оставшийся перенос раскладывается в десятичные цифры и добавляется в конец. Именно эта рекуррентная схема и является центральным математическим объектом решения.
После обработки позиций \(0,1,\dots,i-1\) сохраняется тождество
$$a\sum_{j=0}^{i-1} d_j^{(b)}10^j=\sum_{j=0}^{i-1} d_j^{(b+1)}10^j+c_i10^i.$$
Это означает, что младшие \(i\) цифр новой степени уже вычислены правильно, а вся еще не обработанная информация собрана в единственном переносе \(c_i10^i\). Когда проход заканчивается и последний перенос полностью выгружается, все произведение восстановлено точно.
Начинаем с \(99^1=99\), то есть с вектора \([9,9]\).
На разряде единиц имеем
$$9 \cdot 99 + 0 = 891,$$
поэтому записываем \(1\) и переносим \(89\).
На разряде десятков имеем
$$9 \cdot 99 + 89 = 980,$$
поэтому записываем \(0\) и переносим \(98\).
Исходные цифры закончились, и остаточный перенос \(98\) дает еще две цифры \(8\) и \(9\). Новый вектор равен \([1,0,8,9]\), то есть
$$99^2=9801,\qquad s(99^2)=9+8+0+1=18.$$
Следующее применение той же схемы дает \(99^3=970299\), причем ничего не нужно вычислять заново с нуля.
Как только реализовано десятичное умножение, оставшийся перебор становится очень маленьким. Есть всего 9801 пара \((a,b)\), и для каждого фиксированного основания \(a\) все степени строятся по порядку повторным умножением. Никакая отсечка не нужна и никакое дополнительное число теоретическое свойство не требуется: после \(b\)-го шага обновления вектор хранит ровно \(a^b\).
Случаи \(a=1\) и \(b=1\) тоже можно спокойно оставить в общем цикле. Они не дают оптимум, но делают и код, и математическое описание полностью единообразными.
Реализации на C++, Python и Java устроены одинаково. Для каждого основания \(a\) текущий десятичный вектор сбрасывается в \([1]\), что соответствует \(a^0=1\). Затем показатель степени последовательно пробегает значения от \(1\) до заданной границы. На каждом шаге вектор умножается на \(a\), вычисляется сумма цифр обновленного вектора, и это значение сравнивается с текущим максимумом.
Умножение выполняется прямо над сохраненными десятичными цифрами. Каждая цифра заменяется новым значением по модулю 10, а целая часть деления становится переносом для следующей позиции. Если после последней сохраненной цифры перенос еще не равен нулю, вектор расширяется новыми цифрами, пока перенос не исчезнет. Поскольку цифры лежат от младшей к старшей, перенос естественно движется вперед по списку.
Поэтому реализации не используют числа с плавающей точкой, не пересчитывают уже известные степени и для каждого основания хранят только одну текущую степень. Дополнительно в них есть небольшой контрольный тест на диапазоне \(a,b \le 10\), где правильная максимальная сумма цифр равна \(45\).
Пусть \(A=99\), \(B=99\), и
$$D=\max_{1 \le a,b \le 99} d(a,b)=198.$$
Для одного состояния \((a,b)\) шаг умножения на \(a\) проходит по каждой сохраненной цифре один раз, и вычисление суммы цифр делает еще один линейный проход по тем же цифрам. Следовательно, стоимость одного состояния равна \(O(D)\), а общая временная сложность составляет
$$O(ABD).$$
В рамках этой задачи это всего лишь несколько миллионов операций над цифрами, так что полный перебор абсолютно практичен. Память имеет порядок \(O(D)\), потому что нужно хранить только десятичные цифры текущей степени и несколько скалярных величин.
ننظر إلى جميع الأزواج من الأعداد الطبيعية \(a,b\) التي تحقق \(1 \le a,b < 100\)، ونريد أكبر قيمة ممكنة لمجموع الأرقام العشرية للعدد \(a^b\). إذا رمزنا إلى مجموع الأرقام بالرمز \(s(n)\)، فالمطلوب هو تعظيم \(s(a^b)\) على جميع الأزواج وعددها \(99 \times 99 = 9801\).
حيز البحث في القيمتين \(a\) و\(b\) صغير، لكن الأعداد الناتجة نفسها ليست صغيرة. فالعدد \(99^{99}\) يملك ما يقارب 200 رقم عشري، ولذلك لا تكفي أنواع الأعداد الصحيحة ذات الحجم الثابت. الفكرة الصحيحة هنا ليست حيلة نظرية عميقة، بل حساب عشري دقيق يعيد استعمال القدرة الحالية لبناء القدرة التالية.
تعتمد التطبيقات الثلاثة على الفكرة نفسها: عند تثبيت الأساس \(a\)، تُبنى القوى \(a^1,a^2,\dots,a^{99}\) تدريجيًا. بدلاً من إعادة حساب كل قوة من الصفر، نحتفظ بالقوة الحالية على صورة متجه أرقام عشرية، ثم نضرب هذا التمثيل مرة واحدة أخرى في \(a\) في كل خطوة.
إذا كان \(a > 1\)، فإن عدد الأرقام العشرية في \(a^b\) يساوي
$$d(a,b)=\lfloor b\log_{10} a \rfloor+1.$$
وهذا يعطي مباشرة حدًا أعلى لحجم جميع القيم في المسألة. وبما أن
$$d(99,99)=\lfloor 99\log_{10}99 \rfloor+1=198,$$
فإن كل قيمة مرشحة يمكن تمثيلها داخل مصفوفة عشرية طولها الأقصى 198. هذا كبير جدًا على الأعداد الصحيحة المعتادة، لكنه صغير جدًا إذا استخدمنا تمثيلًا يدويًا قائمًا على الأرقام.
لأساس ثابت \(a\)، نكتب القدرة الحالية على الصورة
$$a^b=\sum_{i=0}^{m_b-1} d_i^{(b)}10^i,\qquad 0 \le d_i^{(b)} \le 9.$$
تُخزَّن الأرقام من الأقل أهمية إلى الأعلى أهمية، ولذلك فالقائمة هي نفسها التوسع العشري بترتيب little-endian. وبهذا الترميز تصبح الكمية التي نريد تعظيمها هي ببساطة
$$s(a^b)=\sum_{i=0}^{m_b-1} d_i^{(b)}.$$
فمتى كانت الأرقام العشرية معروفة، صار حساب مجموع الأرقام مجرد مرور خطي على المتجه.
إذا كانت أرقام \(a^b\) معروفة بالفعل، فإن \(a^{b+1}=a \cdot a^b\) يُحسب بضرب متجه الأرقام في العدد الصغير \(a\) كما في الضرب المدرسي. نبدأ بحمل \(c_0=0\)، ولكل موضع \(i\) نعرّف
$$t_i=a\,d_i^{(b)}+c_i,$$
$$d_i^{(b+1)}=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
وبعد الانتهاء من الأرقام القديمة، إذا بقي حمل غير صفري، نجزئه هو أيضًا إلى أرقام عشرية ونضيفها في نهاية المتجه. هذه العلاقة هي البنية الرياضية الأساسية المشتركة بين التطبيقات الثلاثة.
بعد معالجة المواضع \(0,1,\dots,i-1\)، يحافظ التحديث على الهوية
$$a\sum_{j=0}^{i-1} d_j^{(b)}10^j=\sum_{j=0}^{i-1} d_j^{(b+1)}10^j+c_i10^i.$$
ومعنى ذلك أن الأرقام الدنيا \(i\) في القدرة الجديدة أصبحت صحيحة بالفعل، وأن كل ما لم يُعالج بعد قد اختُزل في حد الحمل الواحد \(c_i10^i\). وعندما ينتهي المسح ويُفرَّغ الحمل الأخير بالكامل، نكون قد أعدنا بناء الناتج كله بدقة تامة.
نبدأ من \(99^1=99\)، أي من المتجه \([9,9]\).
في خانة الآحاد نحصل على
$$9 \cdot 99 + 0 = 891,$$
فنكتب \(1\) ويصبح الحمل \(89\).
وفي خانة العشرات نحصل على
$$9 \cdot 99 + 89 = 980,$$
فنكتب \(0\) ويصبح الحمل \(98\).
بعد ذلك تنتهي الأرقام الأصلية، ويعطي الحمل المتبقي \(98\) الرقمين الأخيرين \(8\) و\(9\). وهكذا يصبح المتجه الجديد \([1,0,8,9]\)، أي
$$99^2=9801,\qquad s(99^2)=9+8+0+1=18.$$
وبتطبيق العلاقة نفسها مرة أخرى نحصل على \(99^3=970299\) من دون أي إعادة حساب من الصفر.
حالما تصبح عملية الضرب العشري متاحة، يبقى لدينا بحث صغير جدًا فقط. هناك 9801 زوجًا لا غير، ولكل أساس ثابت \(a\) تُولد جميع القوى بالترتيب بواسطة تكرار الضرب. لا حاجة إلى تقليم ولا إلى نظرية أعداد إضافية: بعد خطوة التحديث رقم \(b\)، يكون المتجه المخزَّن هو \(a^b\) بالضبط.
أما الحالتان \(a=1\) و\(b=1\) فيمكن تركهما داخل الدوران العام بلا مشكلة. فهما لا تعطيان القيمة العظمى، لكن إبقاءهما يجعل كلًا من الشرح والخوارزمية أكثر انتظامًا.
تتبع تطبيقات C++ وPython وJava الهيكل نفسه. فلكل أساس \(a\)، يُعاد ضبط المتجه العشري الحالي إلى \([1]\)، وهو تمثيل \(a^0=1\). بعد ذلك يتحرك الأس من \(1\) حتى الحد الأعلى. في كل خطوة يُضرب المتجه في \(a\)، ثم يُحسب مجموع أرقام المتجه بعد تحديثه، ثم يُقارَن هذا المجموع بأفضل قيمة وُجدت حتى تلك اللحظة.
تتم عملية الضرب مباشرة على الأرقام العشرية المخزنة. كل رقم يُستبدل بباقي قيمته الجديدة modulo 10، أما خارج القسمة فينتقل حملًا إلى الموضع التالي. وإذا بقي حمل بعد آخر رقم مخزن، تُضاف أرقام جديدة حتى يختفي الحمل تمامًا. وبما أن الأرقام محفوظة من الأقل أهمية إلى الأعلى، فإن الحمل يتحرك طبيعيًا إلى الأمام داخل القائمة.
ولهذا لا تحتاج التطبيقات إلى حساب عشري عائم، ولا تعيد حساب قوة سبق الحصول عليها، ولا تخزن أكثر من قوة حالية واحدة لكل أساس. كما تتضمن فحصًا صغيرًا على المجال المصغر \(a,b \le 10\)، حيث يجب أن تكون أكبر قيمة صحيحة لمجموع الأرقام هي \(45\)، وذلك للتأكد من سلامة منطق التعامل مع الأرقام.
لنضع \(A=99\)، و\(B=99\)، و
$$D=\max_{1 \le a,b \le 99} d(a,b)=198.$$
بالنسبة إلى حالة واحدة \((a,b)\)، فإن خطوة الضرب في \(a\) تمر على كل رقم مخزَّن مرة واحدة، كما أن حساب مجموع الأرقام يمر على الأرقام نفسها مرة أخرى. لذلك فتكلفة كل حالة هي \(O(D)\)، ويصبح الزمن الكلي
$$O(ABD).$$
وفي هذه المسألة يعني ذلك بضعة ملايين فقط من العمليات على الأرقام، ولذلك يكون الفحص الشامل الكامل عمليًا جدًا. أما الذاكرة فهي \(O(D)\)، لأن التنفيذ لا يحتفظ إلا بأرقام القوة الحالية وبعض القيم العددية البسيطة.