Problem 29 asks for the number of distinct terms among \(a^b\) with \(2 \le a \le 100\) and \(2 \le b \le 100\). More generally, if we write
$$P(A,B)=\{a^b \mid 2 \le a \le A,\ 2 \le b \le B\},$$
the task is to determine the cardinality \(|P(A,B)|\).
The difficulty is duplication. Different pairs \((a,b)\) can represent the same integer, such as \(2^4=4^2\) and \(2^6=4^3=8^2\). A correct solution therefore needs an exact way to recognize when two powers are equal.
The mathematics has two complementary parts. Unique factorization explains exactly why collisions occur, and the small search range explains why the implementation can simply generate every power exactly and let a set remove duplicates automatically.
Write the prime factorization of a base \(a\) as
$$a=\prod_{i=1}^r p_i^{e_i}.$$
If
$$g=\gcd(e_1,e_2,\dots,e_r),$$
then we can factor out the common exponent:
$$a=\left(\prod_{i=1}^r p_i^{e_i/g}\right)^g=c^g.$$
The number \(c\) is not a perfect power, because the exponents in its own prime factorization now have gcd \(1\). This gives a unique representation \(a=c^g\) with a minimal base \(c\) and an exponent \(g \ge 1\).
Examples are \(4=2^2\), \(8=2^3\), \(16=2^4\), \(27=3^3\), while \(6\) is already in minimal form and must be written as \(6^1\).
Suppose two bases are written in minimal form:
$$a_1=c_1^{k_1},\qquad a_2=c_2^{k_2}.$$
Then
$$a_1^{b_1}=c_1^{k_1b_1},\qquad a_2^{b_2}=c_2^{k_2b_2}.$$
By the fundamental theorem of arithmetic, these two values are equal if and only if the primitive bases agree and the total exponents agree:
$$a_1^{b_1}=a_2^{b_2}\iff c_1=c_2,\ k_1b_1=k_2b_2.$$
So collisions never mix different minimal bases. They occur only inside the same perfect-power family. The family generated by minimal base \(2\), for instance, contains \(2,4,8,16,32,64\), and every one of those bases contributes values of the form \(2^m\).
For \(2 \le a,b \le 5\), there are initially \(4 \cdot 4 = 16\) candidate pairs. Among the bases, \(2\) and \(4=2^2\) share minimal base \(2\), while \(3\) and \(5\) are already minimal.
The values coming from the minimal base \(2\) are
$$2^2,2^3,2^4,2^5,\qquad 4^2=2^4,\ 4^3=2^6,\ 4^4=2^8,\ 4^5=2^{10}.$$
The distinct exponents here are \(\{2,3,4,5,6,8,10\}\), so this family contributes \(7\) distinct values. The minimal base \(3\) contributes \(3^2,3^3,3^4,3^5\), and the minimal base \(5\) contributes \(5^2,5^3,5^4,5^5\). Those two families are disjoint from everything else, so
$$|P(5,5)|=7+4+4=15.$$
At the pair-count level, the only duplication is the collision \(2^4=4^2\).
One could count these families analytically, but the given bounds are small. The full Project Euler instance has only
$$99 \cdot 99 = 9801$$
candidate powers. The largest of them is
$$100^{100}=10^{200},$$
which is large but still routine for arbitrary-precision integer types. Because integer equality is exact, storing every computed power in a set gives the correct cardinality without any special duplicate-removal formula.
For each base \(a\), the implementation starts from \(1\) and repeatedly multiplies by \(a\). After one multiplication the current value is \(a\), after two it is \(a^2\), and if we denote the stored value after \(b\) multiplications by \(v_b\), the loop invariant is
$$v_b=a^b.$$
This avoids recomputing powers from scratch. Once \(b \ge 2\), the current value belongs to \(P(A,B)\), so it is inserted into the deduplication container.
The C++, Python, and Java implementations all use exact integer arithmetic, so a collision such as \(4^5=2^{10}\) produces literally the same stored integer in every language. The container therefore keeps only one copy of each value, and after all pairs \((a,b)\) have been processed, its size is exactly \(|P(A,B)|\).
The three versions differ only in the concrete container type: the C++ implementation uses an ordered set of arbitrary-precision integers, while the Python and Java implementations use exact big integers inside hash-based sets. They also include small checkpoints that verify \(|P(5,5)|=15\) and \(|P(10,10)|=69\).
Let \(N=(A-1)(B-1)\) be the number of generated powers. The value \(a^b\) has \(\Theta(b\log a)\) bits, so the cost of multiplying and storing it grows with the exponent. A high-level digit-cost model gives
$$O\!\left(\sum_{a=2}^{A}\sum_{b=2}^{B} b\log a\right)=O(AB^2\log A)$$
for the arithmetic work needed to build all values incrementally.
On top of that, each insertion pays container overhead: an ordered-set lookup in the C++ version and expected constant-time hashing in the Python and Java versions, all applied to arbitrary-precision integers. Space usage is proportional to the number of distinct powers kept in the set. For the Euler bounds this remains modest: at most 9801 values are generated, and even the largest one has only 201 decimal digits.
Problem 29 fragt nach der Anzahl verschiedener Werte der Form \(a^b\) mit \(2 \le a \le 100\) und \(2 \le b \le 100\). Allgemeiner schreiben wir
$$P(A,B)=\{a^b \mid 2 \le a \le A,\ 2 \le b \le B\},$$
und gesucht ist die Mächtigkeit \(|P(A,B)|\).
Die Schwierigkeit liegt in den Kollisionen. Verschiedene Paare \((a,b)\) können dieselbe ganze Zahl erzeugen, zum Beispiel \(2^4=4^2\) oder \(2^6=4^3=8^2\). Eine korrekte Lösung muss also Gleichheit von Potenzen exakt erkennen.
Die Mathematik hat hier zwei Seiten. Die eindeutige Primfaktorzerlegung erklärt exakt, warum Duplikate entstehen, und die kleinen Schranken erklären, warum die Implementierung trotzdem einfach alle Potenzen berechnen und per Menge deduplizieren kann.
Schreibe die Primfaktorzerlegung einer Basis \(a\) als
$$a=\prod_{i=1}^r p_i^{e_i}.$$
Mit
$$g=\gcd(e_1,e_2,\dots,e_r)$$
kann man den gemeinsamen Exponenten ausklammern:
$$a=\left(\prod_{i=1}^r p_i^{e_i/g}\right)^g=c^g.$$
Die Zahl \(c\) ist keine perfekte Potenz mehr, weil die Exponenten in ihrer eigenen Primfaktorzerlegung nun ggT \(1\) haben. Dadurch erhält man eine eindeutige Darstellung \(a=c^g\) mit einer minimalen Basis \(c\) und einem Exponenten \(g \ge 1\).
Beispiele sind \(4=2^2\), \(8=2^3\), \(16=2^4\), \(27=3^3\), während \(6\) bereits minimal ist und nur als \(6^1\) geschrieben werden kann.
Schreibe zwei Basen in Minimalform:
$$a_1=c_1^{k_1},\qquad a_2=c_2^{k_2}.$$
Dann gilt
$$a_1^{b_1}=c_1^{k_1b_1},\qquad a_2^{b_2}=c_2^{k_2b_2}.$$
Nach dem Fundamentalsatz der Arithmetik sind diese beiden Werte genau dann gleich, wenn die primitiven Basen übereinstimmen und auch die Gesamt-Exponenten übereinstimmen:
$$a_1^{b_1}=a_2^{b_2}\iff c_1=c_2,\ k_1b_1=k_2b_2.$$
Kollisionen mischen also niemals verschiedene minimale Basen. Sie entstehen nur innerhalb derselben Familie perfekter Potenzen. Die Familie zur minimalen Basis \(2\) enthält zum Beispiel \(2,4,8,16,32,64\), und all diese Basen erzeugen letztlich Werte der Form \(2^m\).
Für \(2 \le a,b \le 5\) gibt es zunächst \(4 \cdot 4 = 16\) Kandidatenpaare. Unter den Basen teilen sich \(2\) und \(4=2^2\) die minimale Basis \(2\), während \(3\) und \(5\) bereits minimal sind.
Die Werte aus der Familie mit minimaler Basis \(2\) sind
$$2^2,2^3,2^4,2^5,\qquad 4^2=2^4,\ 4^3=2^6,\ 4^4=2^8,\ 4^5=2^{10}.$$
Die verschiedenen Exponenten sind also \(\{2,3,4,5,6,8,10\}\), daher liefert diese Familie \(7\) unterschiedliche Werte. Die minimale Basis \(3\) liefert \(3^2,3^3,3^4,3^5\), und die minimale Basis \(5\) liefert \(5^2,5^3,5^4,5^5\). Diese beiden Familien sind zu allem anderen disjunkt, also folgt
$$|P(5,5)|=7+4+4=15.$$
Auf Ebene der Paare sieht man genau eine Kollision: \(2^4=4^2\).
Man könnte die Familien auch analytisch zählen, aber die vorgegebenen Grenzen sind klein. Im vollständigen Euler-Fall gibt es nur
$$99 \cdot 99 = 9801$$
Kandidatenpotenzen. Der größte Wert ist
$$100^{100}=10^{200},$$
also groß, aber für Ganzzahlen mit beliebiger Präzision immer noch völlig unproblematisch. Weil Ganzzahlgleichheit exakt ist, liefert das Speichern aller berechneten Potenzen in einer Menge direkt die richtige Mächtigkeit.
Für jede Basis \(a\) startet die Implementierung bei \(1\) und multipliziert wiederholt mit \(a\). Nach einer Multiplikation steht \(a\) im Speicher, nach zwei \(a^2\), und wenn man den gespeicherten Wert nach \(b\) Multiplikationen mit \(v_b\) bezeichnet, lautet die Schleifeninvariante
$$v_b=a^b.$$
Dadurch müssen Potenzen nicht jedes Mal neu berechnet werden. Sobald \(b \ge 2\) gilt, gehört der aktuelle Wert zur Zielmenge und wird in den Container zur Deduplikation eingefügt.
Die C++-, Python- und Java-Implementierungen arbeiten alle mit exakter Ganzzahlarithmetik. Eine Kollision wie \(4^5=2^{10}\) erzeugt daher in jeder Sprache exakt dieselbe gespeicherte Zahl. Der Container behält nur ein Exemplar jedes Wertes, und nach der Verarbeitung aller Paare \((a,b)\) ist seine Größe genau \(|P(A,B)|\).
Unterschiede gibt es nur beim konkreten Container: In C++ wird eine geordnete Menge mit Ganzzahlen beliebiger Präzision verwendet, in Python und Java hashbasierte Mengen mit exakten großen Ganzzahlen. Zusätzlich prüfen die Implementierungen kleine Referenzfälle mit \(|P(5,5)|=15\) und \(|P(10,10)|=69\).
Sei \(N=(A-1)(B-1)\) die Anzahl der erzeugten Potenzen. Der Wert \(a^b\) hat \(\Theta(b\log a)\) Bits, daher wachsen Multiplikations- und Speicherkosten mit dem Exponenten. Ein grobes Modell auf Ziffernebene ergibt
$$O\!\left(\sum_{a=2}^{A}\sum_{b=2}^{B} b\log a\right)=O(AB^2\log A)$$
für den arithmetischen Aufwand beim inkrementellen Aufbau aller Werte.
Hinzu kommt der Container-Overhead: geordnete-Satz-Suchen in der C++-Version und erwartete konstante Hash-Zugriffe in Python und Java, jeweils auf Ganzzahlen beliebiger Präzision. Der Speicherbedarf ist proportional zur Zahl der unterschiedlichen Potenzen im Container. Für die Euler-Grenzen bleibt das klein: höchstens 9801 Werte werden erzeugt, und selbst der größte hat nur 201 Dezimalstellen.
Problem 29, \(2 \le a \le 100\) ve \(2 \le b \le 100\) için \(a^b\) biçimindeki farklı terimlerin sayısını ister. Daha genel olarak
$$P(A,B)=\{a^b \mid 2 \le a \le A,\ 2 \le b \le B\}$$
kümesini tanımlarsak, aranan şey \(|P(A,B)|\) değeridir.
Zorluk tekrar eden değerlerdir. Farklı \((a,b)\) çiftleri aynı tam sayıyı üretebilir; örneğin \(2^4=4^2\) ve \(2^6=4^3=8^2\). Bu yüzden doğru bir çözüm, iki kuvvetin eşitliğini tam olarak ayırt etmelidir.
Problemin matematiği iki parçadan oluşur. Bir yandan asal çarpanlara ayırma, çakışmaların neden ortaya çıktığını tam olarak açıklar. Öte yandan aralık çok küçük olduğu için uygulama bütün kuvvetleri doğrudan üretip bir kümede tekilleştirerek sonuca ulaşabilir.
Bir \(a\) tabanının asal çarpanlara ayrılmış hali
$$a=\prod_{i=1}^r p_i^{e_i}$$
olsun. Eğer
$$g=\gcd(e_1,e_2,\dots,e_r)$$
ise ortak üs dışarı alınabilir:
$$a=\left(\prod_{i=1}^r p_i^{e_i/g}\right)^g=c^g.$$
Buradaki \(c\), artık mükemmel kuvvet olmayan en küçük tabandır; çünkü kendi asal üslerinin ebobu \(1\) olmuştur. Böylece her \(a\) sayısı, benzersiz biçimde bir minimal taban \(c\) ve bir üs \(g \ge 1\) ile \(a=c^g\) şeklinde yazılır.
Örneğin \(4=2^2\), \(8=2^3\), \(16=2^4\), \(27=3^3\) iken \(6\) zaten minimaldir ve yalnızca \(6^1\) olarak yazılabilir.
İki tabanı minimal biçimde yazalım:
$$a_1=c_1^{k_1},\qquad a_2=c_2^{k_2}.$$
O zaman
$$a_1^{b_1}=c_1^{k_1b_1},\qquad a_2^{b_2}=c_2^{k_2b_2}.$$
Aritmetiğin temel teoremine göre bu iki değer ancak ve ancak ilkel tabanlar aynıysa ve toplam üsler eşitse aynıdır:
$$a_1^{b_1}=a_2^{b_2}\iff c_1=c_2,\ k_1b_1=k_2b_2.$$
Yani çakışmalar farklı minimal tabanlar arasında olmaz; yalnızca aynı mükemmel-kuvvet ailesi içinde görülür. Minimal tabanı \(2\) olan aile buna iyi bir örnektir: \(2,4,8,16,32,64\) tabanlarının hepsi sonunda \(2^m\) biçimindeki değerlere gider.
\(2 \le a,b \le 5\) için başlangıçta \(4 \cdot 4 = 16\) aday çift vardır. Bu tabanlar arasında \(2\) ile \(4=2^2\) aynı minimal tabanı paylaşır; \(3\) ve \(5\) ise zaten minimaldir.
Minimal tabanı \(2\) olan aileden gelen değerler şunlardır:
$$2^2,2^3,2^4,2^5,\qquad 4^2=2^4,\ 4^3=2^6,\ 4^4=2^8,\ 4^5=2^{10}.$$
Buradaki farklı üsler \(\{2,3,4,5,6,8,10\}\) olduğundan bu aile \(7\) farklı değer üretir. Minimal tabanı \(3\) olan aile \(3^2,3^3,3^4,3^5\), minimal tabanı \(5\) olan aile de \(5^2,5^3,5^4,5^5\) verir. Bu iki aile diğerlerinden ayrıdır; dolayısıyla
$$|P(5,5)|=7+4+4=15.$$
Çift sayımı açısından görülen tek tekrar \(2^4=4^2\) eşitliğidir.
Bu aileler analitik olarak da sayılabilir, fakat verilen sınırlar küçüktür. Tam Project Euler örneğinde yalnızca
$$99 \cdot 99 = 9801$$
adet aday kuvvet vardır. En büyük değer
$$100^{100}=10^{200}$$
olur. Bu sayı büyük olsa da keyfi duyarlıklı tam sayılar için tamamen yönetilebilir durumdadır. Tam sayı eşitliği kesin olduğu için, üretilen bütün kuvvetleri bir kümeye koymak doğru kardinaliteyi doğrudan verir.
Her \(a\) tabanı için uygulama \(1\) ile başlar ve sürekli \(a\) ile çarpar. Bir çarpmadan sonra eldeki değer \(a\), iki çarpmadan sonra \(a^2\) olur; \(b\) çarpımdan sonraki saklanan değeri \(v_b\) ile gösterirsek döngü değişmezi
$$v_b=a^b.$$
Böylece her üs için kuvveti baştan hesaplamak gerekmez. \(b \ge 2\) olduğunda eldeki değer hedef kümeye aittir ve tekilleştirme kabına eklenir.
C++, Python ve Java uygulamalarının üçü de tam sayıları kesin olarak temsil eder. Bu yüzden \(4^5=2^{10}\) gibi bir çakışma, her dilde gerçekten aynı saklanan tam sayıyı üretir. Küme yapısı her değerden yalnızca bir kopya tuttuğu için, tüm \((a,b)\) çiftleri işlendiğinde kümenin boyutu tam olarak \(|P(A,B)|\) olur.
Sürümler arasındaki fark yalnızca kullanılan kap tipidir: C++ tarafında keyfi duyarlıklı tam sayılardan oluşan sıralı bir küme vardır; Python ve Java tarafında ise tam büyük tamsayılarla çalışan hash tabanlı kümeler kullanılır. Ayrıca küçük doğrulama örnekleri olarak \(|P(5,5)|=15\) ve \(|P(10,10)|=69\) sonuçları kontrol edilir.
\(N=(A-1)(B-1)\) üretilen kuvvet sayısı olsun. \(a^b\) değeri \(\Theta(b\log a)\) bit içerir; dolayısıyla çarpma ve saklama maliyeti üs büyüdükçe artar. Basamak-temelli üst düzey bir model
$$O\!\left(\sum_{a=2}^{A}\sum_{b=2}^{B} b\log a\right)=O(AB^2\log A)$$
aritmetik iş yükü verir.
Buna ek olarak küme ekleme maliyeti vardır: C++ sürümünde sıralı küme araması, Python ve Java sürümlerinde ise beklenen sabit zamanlı hash erişimi yapılır; her durumda karşılaştırılan veya özetlenen nesneler keyfi duyarlıklı tam sayılardır. Bellek kullanımı, kümede saklanan farklı kuvvet sayısı ile orantılıdır. Euler sınırlarında bu maliyet küçüktür: en fazla 9801 değer üretilir ve en büyüğünün bile yalnızca 201 ondalık basamağı vardır.
El problema 29 pide contar cuántos términos distintos aparecen entre los valores \(a^b\) con \(2 \le a \le 100\) y \(2 \le b \le 100\). En forma general, si definimos
$$P(A,B)=\{a^b \mid 2 \le a \le A,\ 2 \le b \le B\},$$
lo que se busca es la cardinalidad \(|P(A,B)|\).
La dificultad está en los duplicados. Distintos pares \((a,b)\) pueden producir el mismo entero, por ejemplo \(2^4=4^2\) o \(2^6=4^3=8^2\). Por eso la solución debe distinguir con exactitud cuándo dos potencias son realmente iguales.
Aquí intervienen dos ideas complementarias. La factorización prima explica exactamente por qué aparecen las colisiones, y el tamaño reducido del rango explica por qué la implementación puede generar todos los valores de manera directa y dejar que un conjunto elimine los repetidos.
Escribamos la factorización prima de una base \(a\) como
$$a=\prod_{i=1}^r p_i^{e_i}.$$
Si
$$g=\gcd(e_1,e_2,\dots,e_r),$$
entonces se puede extraer el exponente común:
$$a=\left(\prod_{i=1}^r p_i^{e_i/g}\right)^g=c^g.$$
El número \(c\) ya no es una potencia perfecta, porque los exponentes de su propia factorización tienen gcd igual a \(1\). Así obtenemos una representación única \(a=c^g\) con una base mínima \(c\) y un exponente \(g \ge 1\).
Por ejemplo, \(4=2^2\), \(8=2^3\), \(16=2^4\), \(27=3^3\), mientras que \(6\) ya está en forma mínima y solo puede escribirse como \(6^1\).
Supongamos que dos bases están escritas en forma mínima:
$$a_1=c_1^{k_1},\qquad a_2=c_2^{k_2}.$$
Entonces
$$a_1^{b_1}=c_1^{k_1b_1},\qquad a_2^{b_2}=c_2^{k_2b_2}.$$
Por el teorema fundamental de la aritmética, estos dos valores son iguales si y solo si coinciden las bases primitivas y también los exponentes totales:
$$a_1^{b_1}=a_2^{b_2}\iff c_1=c_2,\ k_1b_1=k_2b_2.$$
Eso significa que las colisiones nunca mezclan bases mínimas distintas. Solo aparecen dentro de una misma familia de potencias perfectas. La familia asociada a la base mínima \(2\), por ejemplo, contiene \(2,4,8,16,32,64\), y todas esas bases terminan produciendo valores de la forma \(2^m\).
Para \(2 \le a,b \le 5\) hay inicialmente \(4 \cdot 4 = 16\) pares candidatos. Entre las bases, \(2\) y \(4=2^2\) comparten la base mínima \(2\), mientras que \(3\) y \(5\) ya son mínimas.
Los valores que salen de la familia con base mínima \(2\) son
$$2^2,2^3,2^4,2^5,\qquad 4^2=2^4,\ 4^3=2^6,\ 4^4=2^8,\ 4^5=2^{10}.$$
Los exponentes distintos son \(\{2,3,4,5,6,8,10\}\), así que esta familia aporta \(7\) valores. La base mínima \(3\) aporta \(3^2,3^3,3^4,3^5\), y la base mínima \(5\) aporta \(5^2,5^3,5^4,5^5\). Como esas familias no se solapan con las demás, obtenemos
$$|P(5,5)|=7+4+4=15.$$
Mirando solo los pares, la única repetición visible es \(2^4=4^2\).
Se podría contar cada familia de forma analítica, pero los límites dados son pequeños. En la instancia completa de Project Euler solo hay
$$99 \cdot 99 = 9801$$
potencias candidatas. La mayor es
$$100^{100}=10^{200},$$
un número grande, pero perfectamente manejable para enteros de precisión arbitraria. Como la igualdad entre enteros es exacta, guardar todas las potencias calculadas en un conjunto produce directamente la cardinalidad correcta.
Para cada base \(a\), la implementación empieza en \(1\) y va multiplicando repetidamente por \(a\). Tras una multiplicación el valor actual es \(a\), tras dos es \(a^2\), y si llamamos \(v_b\) al valor almacenado después de \(b\) multiplicaciones, la invariante del bucle es
$$v_b=a^b.$$
Eso evita recomputar cada potencia desde cero. En cuanto \(b \ge 2\), el valor actual pertenece a \(P(A,B)\) y se inserta en el contenedor que elimina duplicados.
Las implementaciones en C++, Python y Java usan aritmética exacta con enteros grandes. Por eso una colisión como \(4^5=2^{10}\) produce literalmente el mismo entero almacenado en los tres lenguajes. El contenedor conserva una sola copia de cada valor, y al terminar de procesar todos los pares \((a,b)\), su tamaño es exactamente \(|P(A,B)|\).
La única diferencia real entre versiones está en el contenedor concreto: C++ usa un conjunto ordenado de enteros de precisión arbitraria, mientras que Python y Java usan conjuntos hash con enteros exactos. Las tres versiones también comprueban dos casos pequeños: \(|P(5,5)|=15\) y \(|P(10,10)|=69\).
Sea \(N=(A-1)(B-1)\) el número de potencias generadas. El valor \(a^b\) tiene \(\Theta(b\log a)\) bits, así que el coste de multiplicarlo y almacenarlo crece con el exponente. Un modelo de coste a nivel de dígitos da
$$O\!\left(\sum_{a=2}^{A}\sum_{b=2}^{B} b\log a\right)=O(AB^2\log A)$$
para el trabajo aritmético necesario al construir todos los valores de manera incremental.
Además, cada inserción paga el coste del contenedor: búsquedas en árbol ordenado en C++ y hashing de tiempo esperado constante en Python y Java, siempre sobre enteros de precisión arbitraria. El espacio usado es proporcional al número de potencias distintas guardadas. Para los límites del problema esto sigue siendo pequeño: como máximo se generan 9801 valores y el mayor de ellos solo tiene 201 cifras decimales.
第 29 题要求统计所有 \(a^b\) 中不同结果的个数，其中 \(2 \le a \le 100\)，\(2 \le b \le 100\)。更一般地，定义
$$P(A,B)=\{a^b \mid 2 \le a \le A,\ 2 \le b \le B\},$$
题目要找的就是集合大小 \(|P(A,B)|\)。
真正的难点不是生成这些幂，而是识别重复项。不同的 \((a,b)\) 可能对应同一个整数，例如 \(2^4=4^2\)，又例如 \(2^6=4^3=8^2\)。因此，解法必须能够准确判断两个幂何时相等。
这道题有两层数学结构。第一层来自唯一分解定理，它精确说明了重复是如何产生的。第二层来自题目的规模：范围只有 \(99 \times 99\)，因此实现上完全可以把所有幂都精确算出来，再用集合自动去重。
把底数 \(a\) 的素因数分解写成
$$a=\prod_{i=1}^r p_i^{e_i}.$$
如果记
$$g=\gcd(e_1,e_2,\dots,e_r),$$
那么就可以把公共指数提出来：
$$a=\left(\prod_{i=1}^r p_i^{e_i/g}\right)^g=c^g.$$
这里的 \(c\) 已经不是完全幂，因为它自己的素因数指数的最大公因数已经变成了 \(1\)。这样，每个 \(a\) 都能唯一写成 \(a=c^g\) 的形式，其中 \(c\) 是最小底数，\(g \ge 1\)。
例如 \(4=2^2\)、\(8=2^3\)、\(16=2^4\)、\(27=3^3\)，而 \(6\) 本身就不是完全幂，所以它的规范形式只能是 \(6^1\)。
设两个底数都已经写成最小形式：
$$a_1=c_1^{k_1},\qquad a_2=c_2^{k_2}.$$
那么
$$a_1^{b_1}=c_1^{k_1b_1},\qquad a_2^{b_2}=c_2^{k_2b_2}.$$
根据算术基本定理，这两个值相等，当且仅当最小底数相同并且总指数相同：
$$a_1^{b_1}=a_2^{b_2}\iff c_1=c_2,\ k_1b_1=k_2b_2.$$
这说明重复永远只会发生在同一个完全幂家族内部，不会跨越不同的最小底数。例如最小底数为 \(2\) 的家族包含 \(2,4,8,16,32,64\)，这些底数最终都只会产生形如 \(2^m\) 的结果。
当 \(2 \le a,b \le 5\) 时，一共有 \(4 \cdot 4 = 16\) 个候选对。底数里，\(2\) 与 \(4=2^2\) 共享最小底数 \(2\)，而 \(3\) 和 \(5\) 已经是最小形式。
最小底数为 \(2\) 的家族产生的值是
$$2^2,2^3,2^4,2^5,\qquad 4^2=2^4,\ 4^3=2^6,\ 4^4=2^8,\ 4^5=2^{10}.$$
这里出现的不同指数为 \(\{2,3,4,5,6,8,10\}\)，所以这一家族贡献 \(7\) 个不同值。最小底数为 \(3\) 的家族贡献 \(3^2,3^3,3^4,3^5\)，最小底数为 \(5\) 的家族贡献 \(5^2,5^3,5^4,5^5\)。这两组与前面完全不重合，因此
$$|P(5,5)|=7+4+4=15.$$
如果只从原始的 \((a,b)\) 对来看，唯一的碰撞就是 \(2^4=4^2\)。
当然也可以按照这些家族做纯分析计数，但题目的范围并不大。完整的 Euler 实例只有
$$99 \cdot 99 = 9801$$
个候选幂。最大的一个是
$$100^{100}=10^{200},$$
虽然数值很大，但对任意精度整数来说仍然完全可处理。既然整数相等可以精确判断，那么把每个算出的幂放进集合里，最后取集合大小，就已经是严格正确的答案。
对于每个底数 \(a\)，实现都从 \(1\) 开始，然后不断乘以 \(a\)。乘一次得到 \(a\)，乘两次得到 \(a^2\)。如果把做完 \(b\) 次乘法后保存的值记作 \(v_b\)，那么循环不变量就是
$$v_b=a^b.$$
这样就不必为每个指数从头重新求幂。当 \(b \ge 2\) 时，当前值已经属于目标集合，于是把它插入去重容器。
C++、Python 和 Java 三个实现都使用精确的大整数表示，因此像 \(4^5=2^{10}\) 这样的碰撞，在三个语言里都会得到字面上完全相同的整数对象。集合只保留每个值的一份拷贝，所以当所有 \((a,b)\) 都处理完以后，集合大小恰好就是 \(|P(A,B)|\)。
三种语言的差别只在具体容器上：C++ 使用有序的任意精度整数集合，Python 和 Java 使用基于哈希的精确大整数集合。实现里还带有两个小型校验点，分别验证 \(|P(5,5)|=15\) 和 \(|P(10,10)|=69\)。
记 \(N=(A-1)(B-1)\) 为生成的幂的总数。数 \(a^b\) 的位数规模是 \(\Theta(b\log a)\)，所以乘法和存储成本都会随着指数增大而增长。若用高层次的“按位数计成本”模型，可以得到
$$O\!\left(\sum_{a=2}^{A}\sum_{b=2}^{B} b\log a\right)=O(AB^2\log A)$$
这一数量级的算术工作量。
除此之外，每次插入还要支付容器开销：C++ 版本是有序集合查找，Python 和 Java 版本是期望常数时间的哈希操作，而处理对象始终都是任意精度整数。空间复杂度与集合中保存的不同幂的个数成正比。对本题范围来说，这一成本很小：最多生成 9801 个值，而最大的那个也只有 201 位十进制数字。
В задаче 29 нужно посчитать число различных значений вида \(a^b\), где \(2 \le a \le 100\) и \(2 \le b \le 100\). В более общем виде можно ввести множество
$$P(A,B)=\{a^b \mid 2 \le a \le A,\ 2 \le b \le B\},$$
и требуется найти его мощность \(|P(A,B)|\).
Сложность возникает из-за совпадений. Разные пары \((a,b)\) могут давать одно и то же число, например \(2^4=4^2\) или \(2^6=4^3=8^2\). Поэтому решение должно точно определять, когда две степени действительно равны.
Здесь полезны две идеи. Уникальность разложения на простые множители точно описывает источник повторов, а малый размер диапазона объясняет, почему реализация может просто вычислить все степени и поручить удаление повторов множеству.
Запишем разложение основания \(a\) на простые множители в виде
$$a=\prod_{i=1}^r p_i^{e_i}.$$
Если обозначить
$$g=\gcd(e_1,e_2,\dots,e_r),$$
то общий показатель можно вынести:
$$a=\left(\prod_{i=1}^r p_i^{e_i/g}\right)^g=c^g.$$
Число \(c\) уже не является совершенной степенью, потому что показатели в его собственной факторизации имеют gcd, равный \(1\). Значит, каждое \(a\) единственным образом представляется как \(a=c^g\), где \(c\) — минимальное основание, а \(g \ge 1\).
Например, \(4=2^2\), \(8=2^3\), \(16=2^4\), \(27=3^3\), тогда как \(6\) уже находится в минимальной форме и записывается только как \(6^1\).
Пусть два основания записаны в минимальной форме:
$$a_1=c_1^{k_1},\qquad a_2=c_2^{k_2}.$$
Тогда
$$a_1^{b_1}=c_1^{k_1b_1},\qquad a_2^{b_2}=c_2^{k_2b_2}.$$
По основной теореме арифметики эти значения равны тогда и только тогда, когда совпадают минимальные основания и полные показатели:
$$a_1^{b_1}=a_2^{b_2}\iff c_1=c_2,\ k_1b_1=k_2b_2.$$
Следовательно, совпадения никогда не смешивают разные минимальные основания. Они возникают только внутри одного семейства совершенных степеней. Например, семейство с минимальным основанием \(2\) содержит \(2,4,8,16,32,64\), и все эти базы порождают значения вида \(2^m\).
При \(2 \le a,b \le 5\) есть \(4 \cdot 4 = 16\) исходных пар. Среди оснований числа \(2\) и \(4=2^2\) имеют одно и то же минимальное основание \(2\), а \(3\) и \(5\) уже минимальны.
Семейство с минимальным основанием \(2\) дает значения
$$2^2,2^3,2^4,2^5,\qquad 4^2=2^4,\ 4^3=2^6,\ 4^4=2^8,\ 4^5=2^{10}.$$
Различные показатели здесь равны \(\{2,3,4,5,6,8,10\}\), значит это семейство дает \(7\) различных значений. Минимальное основание \(3\) дает \(3^2,3^3,3^4,3^5\), а минимальное основание \(5\) дает \(5^2,5^3,5^4,5^5\). Эти семейства не пересекаются с остальными, поэтому
$$|P(5,5)|=7+4+4=15.$$
Если смотреть только на пары \((a,b)\), видимое совпадение здесь одно: \(2^4=4^2\).
Можно было бы считать такие семейства аналитически, но заданные границы малы. В полной постановке Project Euler имеется всего
$$99 \cdot 99 = 9801$$
кандидатных степеней. Наибольшее значение равно
$$100^{100}=10^{200},$$
что, хотя и велико, все же совершенно обычно для целых чисел произвольной точности. Поскольку равенство целых чисел проверяется точно, достаточно сохранить все вычисленные степени в множестве и взять его размер.
Для каждого основания \(a\) реализация начинает с \(1\) и затем многократно умножает текущее значение на \(a\). После одного умножения получается \(a\), после двух — \(a^2\). Если обозначить сохраненное значение после \(b\) умножений через \(v_b\), то инвариант цикла имеет вид
$$v_b=a^b.$$
Это избавляет от пересчета каждой степени с нуля. Как только \(b \ge 2\), текущее значение принадлежит целевому множеству и добавляется в контейнер для удаления повторов.
Реализации на C++, Python и Java используют точную арифметику больших целых. Поэтому совпадение вроде \(4^5=2^{10}\) в каждом языке создает буквально одно и то же целое число. Контейнер хранит только по одному экземпляру каждого значения, и после обработки всех пар \((a,b)\) его размер точно равен \(|P(A,B)|\).
Различие между версиями только в типе контейнера: в C++ используется упорядоченное множество целых произвольной точности, а в Python и Java — хеш-множества с точными большими целыми. Кроме того, реализации проверяют два контрольных случая: \(|P(5,5)|=15\) и \(|P(10,10)|=69\).
Пусть \(N=(A-1)(B-1)\) — число генерируемых степеней. Величина \(a^b\) содержит \(\Theta(b\log a)\) бит, поэтому стоимость умножения и хранения растет вместе с показателем. Высокоуровневая модель по разрядной длине дает
$$O\!\left(\sum_{a=2}^{A}\sum_{b=2}^{B} b\log a\right)=O(AB^2\log A)$$
арифметической работы для пошагового построения всех значений.
Сверх этого есть накладные расходы контейнера: поиск в упорядоченном множестве в C++ и ожидаемое постоянное время хеширования в Python и Java, причем везде обрабатываются целые числа произвольной точности. Память пропорциональна числу различных степеней, сохраненных в множестве. Для границ Euler это немного: генерируется не более 9801 значений, а самое большое из них имеет только 201 десятичную цифру.
تطلب المسألة 29 حساب عدد القيم المختلفة من الشكل \(a^b\) عندما يكون \(2 \le a \le 100\) و\(2 \le b \le 100\). وبصورة أعم، إذا عرفنا
$$P(A,B)=\{a^b \mid 2 \le a \le A,\ 2 \le b \le B\},$$
فإن المطلوب هو إيجاد عدد عناصر هذه المجموعة، أي \(|P(A,B)|\).
الصعوبة الحقيقية تأتي من التكرار. فقد يعطي زوجان مختلفان \((a,b)\) العدد نفسه، مثل \(2^4=4^2\)، أو \(2^6=4^3=8^2\). لذلك يجب أن تكون الطريقة قادرة على تحديد متى تكون قوتان متساويتين بدقة تامة.
تعتمد الفكرة الرياضية على جانبين متكاملين. الأول هو التحليل إلى عوامل أولية، وهو يشرح بدقة كيف تظهر التصادمات. والثاني هو أن نطاق المسألة صغير نسبيًا، ولذلك يمكن للتنفيذ أن يولد كل القيم مباشرة ويترك للمجموعة مهمة حذف المكرر.
لنكتب تحليل الأساس \(a\) إلى عوامله الأولية على الصورة
$$a=\prod_{i=1}^r p_i^{e_i}.$$
وإذا كان
$$g=\gcd(e_1,e_2,\dots,e_r),$$
فيمكن استخراج الأس المشترك:
$$a=\left(\prod_{i=1}^r p_i^{e_i/g}\right)^g=c^g.$$
العدد \(c\) هنا لم يعد قوة كاملة، لأن القاسم المشترك الأكبر لأسس عوامله الأولية أصبح \(1\). وبهذا نحصل على تمثيل وحيد من الشكل \(a=c^g\)، حيث \(c\) هو الأساس الأدنى و\(g \ge 1\).
على سبيل المثال \(4=2^2\)، و\(8=2^3\)، و\(16=2^4\)، و\(27=3^3\)، بينما \(6\) ليس قوة كاملة أصلًا، لذلك تبقى صورته الدنيا هي \(6^1\).
إذا كتبنا أساسين في صورتهما الدنيا،
$$a_1=c_1^{k_1},\qquad a_2=c_2^{k_2},$$
فإن
$$a_1^{b_1}=c_1^{k_1b_1},\qquad a_2^{b_2}=c_2^{k_2b_2}.$$
وبحسب النظرية الأساسية في الحساب، فإن هاتين القيمتين تتساويان إذا وفقط إذا تساوى الأساس الأدنى وتساوى أيضًا الأس الكلي:
$$a_1^{b_1}=a_2^{b_2}\iff c_1=c_2,\ k_1b_1=k_2b_2.$$
إذن لا تحدث التصادمات بين عائلات مختلفة من الأسس الدنيا، بل فقط داخل العائلة نفسها. فالعائلة ذات الأساس الأدنى \(2\) مثلًا تضم \(2,4,8,16,32,64\)، وكل هذه القواعد تنتج في النهاية قيمًا من الشكل \(2^m\).
عندما يكون \(2 \le a,b \le 5\)، يوجد أولًا \(4 \cdot 4 = 16\) زوجًا مرشحًا. ومن بين القواعد، يشترك \(2\) و\(4=2^2\) في الأساس الأدنى \(2\)، بينما \(3\) و\(5\) في صورتهما الدنيا أصلًا.
القيم الناتجة من عائلة الأساس الأدنى \(2\) هي
$$2^2,2^3,2^4,2^5,\qquad 4^2=2^4,\ 4^3=2^6,\ 4^4=2^8,\ 4^5=2^{10}.$$
الأسس المختلفة هنا هي \(\{2,3,4,5,6,8,10\}\)، ولذلك تسهم هذه العائلة في \(7\) قيم مختلفة. أما العائلة ذات الأساس الأدنى \(3\) فتعطي \(3^2,3^3,3^4,3^5\)، والعائلة ذات الأساس الأدنى \(5\) تعطي \(5^2,5^3,5^4,5^5\). وهاتان العائلتان منفصلتان عن غيرهما، ومن ثم
$$|P(5,5)|=7+4+4=15.$$
وعند النظر إلى الأزواج الأصلية فقط، يكون التكرار الظاهر الوحيد هو \(2^4=4^2\).
يمكن عد هذه العائلات تحليليًا، لكن حدود المسألة صغيرة. ففي نسخة Project Euler الكاملة يوجد فقط
$$99 \cdot 99 = 9801$$
قيمة مرشحة. وأكبرها هو
$$100^{100}=10^{200},$$
وهو عدد كبير، لكنه ما يزال سهل التعامل بالنسبة إلى الأعداد الصحيحة ذات الدقة غير المحدودة. وبما أن مساواة الأعداد الصحيحة مساواة دقيقة تمامًا، فإن وضع كل قوة محسوبة داخل مجموعة يكفي للحصول على العدد الصحيح للعناصر المختلفة.
لكل أساس \(a\)، يبدأ التنفيذ من القيمة \(1\)، ثم يضربها مرارًا في \(a\). بعد ضربة واحدة تصبح القيمة \(a\)، وبعد ضربتين تصبح \(a^2\). وإذا رمزنا إلى القيمة المخزنة بعد \(b\) ضربات بالرمز \(v_b\)، فإن ثابت الحلقة هو
$$v_b=a^b.$$
هذا يلغي الحاجة إلى إعادة حساب كل قوة من البداية. وما إن يصبح \(b \ge 2\)، حتى تنتمي القيمة الحالية إلى المجموعة الهدف وتُدرج في وعاء إزالة التكرارات.
تعتمد تطبيقات C++ وPython وJava كلها على تمثيل دقيق للأعداد الصحيحة الكبيرة، ولذلك فإن تصادمًا مثل \(4^5=2^{10}\) ينتج العدد نفسه حرفيًا في كل لغة. وتحفظ المجموعة نسخة واحدة فقط من كل قيمة، ولهذا يكون حجمها بعد معالجة جميع الأزواج \((a,b)\) مساويًا تمامًا لـ \(|P(A,B)|\).
الاختلاف بين النسخ الثلاث يقتصر على نوع الوعاء: فنسخة C++ تستخدم مجموعة مرتبة من أعداد صحيحة ذات دقة غير محدودة، بينما تستخدم نسختا Python وJava مجموعات مبنية على التجزئة مع أعداد صحيحة دقيقة. كما تتضمن التطبيقات حالتي تحقق صغيرتين تؤكدان أن \(|P(5,5)|=15\) و\(|P(10,10)|=69\).
لنرمز إلى عدد القوى المولدة بالرمز \(N=(A-1)(B-1)\). إن القيمة \(a^b\) تحتوي على \(\Theta(b\log a)\) بتات، ولذلك تزداد كلفة الضرب والتخزين مع ازدياد الأس. ويعطي نموذج تقريبي على مستوى طول الأعداد
$$O\!\left(\sum_{a=2}^{A}\sum_{b=2}^{B} b\log a\right)=O(AB^2\log A)$$
بوصفه مقدار العمل الحسابي اللازم لبناء جميع القيم تدريجيًا.
وفوق ذلك توجد كلفة خاصة بالوعاء: بحث في مجموعة مرتبة في نسخة C++، وتجزيء بزمن متوقع ثابت في نسختي Python وJava، وكل ذلك على أعداد صحيحة كبيرة. ويكون استهلاك الذاكرة متناسبًا مع عدد القوى المختلفة المحفوظة في المجموعة. وبالنسبة إلى حدود المسألة، يظل هذا صغيرًا: إذ لا يزيد عدد القيم المولدة على 9801، وحتى أكبر قيمة لا تتجاوز 201 رقمًا عشريًا.