The number in the problem is
$$N=28433\cdot 2^{7830457}+1.$$
Writing out \(N\) in full would be pointless, because the question asks only for the last ten digits. That means we do not need \(N\) itself; we need only its residue modulo
$$m=10^{10}.$$
So the whole task is to evaluate \(N \bmod m\). Once that modular computation is done, the final ten-digit residue is \(8739992577\).
The C++, Python, and Java implementations all use the same mathematical reduction: keep every intermediate value modulo \(10^{10}\), compute the huge power with binary exponentiation, and then apply the outer multiplication by \(28433\) and the final \(+1\).
Because congruences respect multiplication and addition, we may reduce the power first:
$$N \equiv 28433\cdot \left(2^{7830457}\bmod m\right)+1 \pmod m.$$
If we set
$$P\equiv 2^{7830457}\pmod m,$$
then the answer is simply
$$\boxed{(28433\cdot P+1)\bmod 10^{10}.}$$
So the real work is concentrated in one object: the residue of \(2^{7830457}\) modulo \(10^{10}\).
The exponent \(7830457\) is large, but it has only 23 binary digits. Binary exponentiation processes that exponent by repeated halving. Start with
$$r_0=1,\qquad b_0=2\bmod m,\qquad e_0=7830457.$$
At each step, if the current exponent is odd, multiply the accumulated result by the current base; then square the base and halve the exponent:
$$ \text{if } e_t \text{ is odd, then } r_{t+1}\equiv r_t b_t \pmod m,\quad \text{otherwise } r_{t+1}=r_t, $$
$$ b_{t+1}\equiv b_t^2\pmod m,\qquad e_{t+1}=\left\lfloor \frac{e_t}{2}\right\rfloor. $$
After about \(\lfloor \log_2 7830457 \rfloor+1=23\) iterations, the exponent becomes zero, so the algorithm finishes very quickly.
The key invariant is
$$r_t\cdot b_t^{e_t}\equiv 2^{7830457}\pmod m.$$
Initially this is true because \(r_0=1\), \(b_0=2\), and \(e_0=7830457\). If \(e_t\) is odd, we move one factor of \(b_t\) from \(b_t^{e_t}\) into \(r_t\); if \(e_t\) is even, we do not need that extra multiplication. In both cases we then replace \(b_t\) by \(b_t^2\) and replace \(e_t\) by \(\lfloor e_t/2\rfloor\), which preserves the same total power of 2 modulo \(m\).
When the loop terminates, \(e_t=0\). The invariant becomes
$$r_t\equiv 2^{7830457}\pmod m,$$
so the accumulated value is exactly the residue we need.
A smaller version of the same computation appears naturally as a checkpoint. Replace \(7830457\) by \(20\). Then
$$2^{20}=1048576,$$
so
$$28433\cdot 2^{20}+1=28433\cdot 1048576+1=29814161409.$$
Taking the last ten digits gives
$$29814161409\bmod 10^{10}=9814161409.$$
This is mathematically identical to the full problem. The only difference is that the real exponent is much larger, so repeated squaring is essential.
The modulus is
$$10^{10}=2^{10}\cdot 5^{10}.$$
Since the base is 2, we have \(\gcd(2,10^{10})=2\neq 1\). That means the usual form of Euler's theorem does not directly reduce the exponent modulo \(\varphi(10^{10})\) for the full modulus. The implementations therefore use the robust approach that always works: repeated squaring with modular reduction at every multiplication.
All three implementations follow the same mathematical pipeline. First they set the modulus to \(10^{10}\). Next they compute the residue of \(2^{7830457}\) modulo that modulus. Then they multiply by \(28433\), add 1, reduce once more modulo \(10^{10}\), and print the resulting ten-digit tail.
The mathematical formula is identical in C++, Python, and Java, but the arithmetic tools are different. The C++ implementation performs modular multiplication through a wider intermediate integer type, because the product of two residues below \(10^{10}\) can be as large as roughly \(10^{20}\), which does not fit safely in ordinary 64-bit multiplication. The Python implementation relies on built-in arbitrary-precision integers and built-in modular exponentiation. The Java implementation uses arbitrary-precision integer arithmetic together with the library operation for modular powers.
The C++ version also verifies the core arithmetic on two smaller cases before printing the final answer. One checkpoint confirms
$$2^{10}\equiv 24\pmod{1000},$$
and another confirms the reduced full-expression example
$$28433\cdot 2^{20}+1\equiv 9814161409\pmod{10^{10}}.$$
Those checks reflect the same recurrence and the same final formula used for the actual exponent \(7830457\).
Binary exponentiation uses \(O(\log e)\) modular multiplications, where \(e=7830457\). Since \(e\) has only 23 binary digits, the main loop runs only about 23 iterations, with at most one extra modular multiplication in each iteration when the current bit is 1.
The memory usage is \(O(1)\) in the mathematical sense: the algorithm stores only a fixed number of integers such as the current result, the current base, the current exponent, and the modulus. Even in the arbitrary-precision implementations, every value is immediately reduced modulo \(10^{10}\), so the integers remain tiny compared with the full size of \(N\).
Die Zahl der Aufgabe ist
$$N=28433\cdot 2^{7830457}+1.$$
Man soll diese Zahl nicht vollständig ausrechnen, sondern nur ihre letzten zehn Ziffern bestimmen. Genau das bedeutet: Gesucht ist der Rest von \(N\) modulo
$$m=10^{10}.$$
Damit schrumpft die Aufgabe von einer riesigen Ganzzahl auf eine einzige Kongruenzrechnung. Führt man sie korrekt aus, erhält man als letzten Zehn-Ziffern-Block \(8739992577\).
Die C++-, Python- und Java-Implementierungen benutzen dieselbe mathematische Idee: Alle Zwischenergebnisse werden sofort modulo \(10^{10}\) reduziert, die Potenz wird per binärer Exponentiation berechnet, und erst danach wird mit \(28433\) multipliziert und 1 addiert.
Wegen der Verträglichkeit von Kongruenzen mit Addition und Multiplikation gilt
$$N \equiv 28433\cdot \left(2^{7830457}\bmod m\right)+1 \pmod m.$$
Setzt man
$$P\equiv 2^{7830457}\pmod m,$$
dann ist die gesuchte Zahl einfach
$$\boxed{(28433\cdot P+1)\bmod 10^{10}.}$$
Der schwierige Teil ist also allein die effiziente Bestimmung des Restes von \(2^{7830457}\) modulo \(10^{10}\).
Der Exponent \(7830457\) ist groß, hat aber nur 23 Binärstellen. Genau das macht wiederholtes Quadrieren so effizient. Wir beginnen mit
$$r_0=1,\qquad b_0=2\bmod m,\qquad e_0=7830457.$$
In jedem Schleifendurchlauf gilt: Ist der aktuelle Exponent ungerade, wird der laufende Wert mit der aktuellen Basis multipliziert; anschließend wird die Basis quadriert und der Exponent halbiert:
$$ \text{falls } e_t \text{ ungerade ist, dann } r_{t+1}\equiv r_t b_t \pmod m,\quad \text{sonst } r_{t+1}=r_t, $$
$$ b_{t+1}\equiv b_t^2\pmod m,\qquad e_{t+1}=\left\lfloor \frac{e_t}{2}\right\rfloor. $$
Nach ungefähr \(\lfloor \log_2 7830457 \rfloor+1=23\) Schritten ist der Exponent null, und die Rechnung ist abgeschlossen.
Der Kern der Methode ist die Schleifeninvariante
$$r_t\cdot b_t^{e_t}\equiv 2^{7830457}\pmod m.$$
Am Anfang ist sie offensichtlich richtig. Ist \(e_t\) ungerade, wird ein Faktor \(b_t\) aus \(b_t^{e_t}\) in den Akkumulator \(r_t\) verschoben; ist \(e_t\) gerade, entfällt genau dieser Schritt. Danach ersetzt man \(b_t\) durch \(b_t^2\) und \(e_t\) durch \(\lfloor e_t/2\rfloor\). So bleibt dieselbe Gesamtpotenz von 2 modulo \(m\) erhalten.
Wenn die Schleife endet, gilt \(e_t=0\). Dann vereinfacht sich die Invariante zu
$$r_t\equiv 2^{7830457}\pmod m,$$
und genau dieser Rest wird in die Endformel eingesetzt.
Ein verkleinertes Beispiel zeigt dieselbe Struktur. Ersetze \(7830457\) durch \(20\). Dann ist
$$2^{20}=1048576,$$
und daher
$$28433\cdot 2^{20}+1=28433\cdot 1048576+1=29814161409.$$
Die letzten zehn Ziffern sind also
$$29814161409\bmod 10^{10}=9814161409.$$
Genau dieselbe Rechnung wird in der echten Aufgabe durchgeführt, nur mit einem sehr viel größeren Exponenten und deshalb mit wiederholtem Quadrieren statt mit direkter Potenzbildung.
Der Modul ist
$$10^{10}=2^{10}\cdot 5^{10}.$$
Da die Basis 2 ist, gilt \(\gcd(2,10^{10})=2\neq 1\). Deshalb ist die übliche Form von Eulers Satz auf dem Gesamtmodul hier nicht der passende Abkürzungsweg. Die Implementierungen wählen stattdessen die robuste Methode, die immer funktioniert: modulares wiederholtes Quadrieren mit Reduktion nach jeder Multiplikation.
Alle drei Implementierungen folgen derselben Pipeline. Zuerst wird der Modul \(10^{10}\) festgelegt. Danach wird der Rest von \(2^{7830457}\) modulo diesem Modul bestimmt. Anschließend wird mit \(28433\) multipliziert, 1 addiert, erneut modulo \(10^{10}\) reduziert und der resultierende Zehn-Ziffern-Block ausgegeben.
Die Mathematik ist in C++, Python und Java identisch, aber die Zahlentypen sind es nicht. Die C++-Version benutzt für modulare Multiplikationen einen breiteren Zwischentyp, weil das Produkt zweier Reste unterhalb von \(10^{10}\) ungefähr \(10^{20}\) erreichen kann und damit für gewöhnliche 64-Bit-Multiplikation zu groß wäre. Die Python-Version verlässt sich auf eingebaute Ganzzahlen beliebiger Präzision und eingebaute modulare Exponentiation. Die Java-Version verwendet Ganzzahlen beliebiger Präzision und die Bibliotheksoperation für modulare Potenzen.
Die C++-Implementierung überprüft den Arithmetikkern außerdem an zwei kleinen Testfällen. Ein Kontrollpunkt bestätigt
$$2^{10}\equiv 24\pmod{1000},$$
und ein weiterer bestätigt das verkleinerte Gesamtbeispiel
$$28433\cdot 2^{20}+1\equiv 9814161409\pmod{10^{10}}.$$
Diese Tests benutzen genau dieselbe Rekursion und dieselbe Abschlussformel wie die eigentliche Lösung.
Binäre Exponentiation benötigt \(O(\log e)\) modulare Multiplikationen mit \(e=7830457\). Da \(e\) nur 23 Binärstellen hat, läuft die Hauptschleife nur ungefähr 23 Mal; pro Schritt kommt höchstens eine zusätzliche Multiplikation hinzu, wenn das aktuelle Bit gleich 1 ist.
Der Speicherbedarf ist mathematisch \(O(1)\), denn gehalten werden nur wenige Ganzzahlen wie aktuelles Ergebnis, aktuelle Basis, aktueller Exponent und Modul. Selbst in den Implementierungen mit beliebiger Präzision bleiben die Werte klein, weil nach jedem Schritt sofort modulo \(10^{10}\) reduziert wird.
Problemin merkezindeki sayı
$$N=28433\cdot 2^{7830457}+1$$
şeklindedir. Bu sayının tamamını yazmak ya da doğrudan üretmek gereksizdir; çünkü istenen şey yalnızca son 10 basamaktır. Bu da tam olarak şu anlama gelir: \(N\)'nin
$$m=10^{10}$$
modundaki kalanı bulunacaktır. Bu modüler hesap doğru yapıldığında son on basamak \(8739992577\) olur.
C++, Python ve Java uygulamalarının ortak fikri çok nettir: tüm ara değerleri sürekli \(10^{10}\) modunda tut, dev üs hesabını ikili üs alma ile yap, sonra dıştaki \(28433\) ile çarpma ve \(+1\) adımını uygula.
Eşleniklikler toplama ve çarpma altında korunduğu için önce kuvvet kısmını mod içinde hesaplayabiliriz:
$$N \equiv 28433\cdot \left(2^{7830457}\bmod m\right)+1 \pmod m.$$
Eğer
$$P\equiv 2^{7830457}\pmod m$$
olarak tanımlarsak, cevap
$$\boxed{(28433\cdot P+1)\bmod 10^{10}}$$
olur. Dolayısıyla asıl hesaplanması gereken nesne, \(2^{7830457}\)'nin \(10^{10}\) modundaki kalıntısıdır.
\(7830457\) büyük bir üstür, fakat ikili gösterimde yalnızca 23 bitten oluşur. Bu yüzden tekrar tekrar ikiye bölme fikri çok etkilidir. Başlangıç durumunu
$$r_0=1,\qquad b_0=2\bmod m,\qquad e_0=7830457$$
olarak alalım. Her adımda, eğer mevcut üs tekse birikmiş sonuca mevcut tabanı çarparız; sonra tabanı karesini alarak günceller ve üssü ikiye böleriz:
$$ \text{eğer } e_t \text{ tekse } r_{t+1}\equiv r_t b_t \pmod m,\quad \text{değilse } r_{t+1}=r_t, $$
$$ b_{t+1}\equiv b_t^2\pmod m,\qquad e_{t+1}=\left\lfloor \frac{e_t}{2}\right\rfloor. $$
Böylece yaklaşık \(\lfloor \log_2 7830457 \rfloor+1=23\) turdan sonra üs sıfıra iner.
Döngünün temel değişmezi şudur:
$$r_t\cdot b_t^{e_t}\equiv 2^{7830457}\pmod m.$$
Başlangıçta bu eşitlik açıktır. Eğer \(e_t\) tekse, \(b_t^{e_t}\) içindeki bir \(b_t\) çarpanı birikmiş sonuç tarafına aktarılır; çiftse buna gerek yoktur. Ardından \(b_t\) yerine \(b_t^2\) ve \(e_t\) yerine \(\lfloor e_t/2\rfloor\) yazıldığında aynı toplam üs korunur. Bu yüzden değişmez her turda geçerli kalır.
Döngü bittiğinde \(e_t=0\) olur ve değişmez
$$r_t\equiv 2^{7830457}\pmod m$$
şeklinde sadeleşir. Yani döngüden çıkan değer tam olarak istediğimiz kuvvet kalıntısıdır.
Aynı matematik daha küçük bir üstle de görülebilir. \(7830457\) yerine \(20\) yazalım. O zaman
$$2^{20}=1048576$$
ve dolayısıyla
$$28433\cdot 2^{20}+1=28433\cdot 1048576+1=29814161409.$$
Son on basamak
$$29814161409\bmod 10^{10}=9814161409$$
olur. Bu, gerçek soruda yapılan işlemin aynısıdır; sadece gerçek üs çok daha büyük olduğundan hızlı üs alma zorunlu hale gelir.
Modül
$$10^{10}=2^{10}\cdot 5^{10}$$
olduğu için taban ile modül aralarında asaldır diyemeyiz; gerçekten de \(\gcd(2,10^{10})=2\) olur. Bu nedenle bütün modül üzerinde Euler teoremini doğrudan uygulayıp üssü küçültmek bu çözümün dayandığı fikir değildir. Uygulamalar bunun yerine her durumda güvenli olan yöntemi seçer: her çarpım sonrası mod alarak tekrarlı kareleme.
Üç uygulama da aynı sırayı izler. Önce modül \(10^{10}\) olarak alınır. Sonra \(2^{7830457}\)'nin bu modüldeki kalanı hesaplanır. Daha sonra sonuç \(28433\) ile çarpılır, 1 eklenir, tekrar \(10^{10}\) moduna indirilir ve son on basamak ekrana yazdırılır.
Matematik aynı olsa da sayı aritmetiği dilden dile değişir. C++ uygulaması, iki kalıntının çarpımı yaklaşık \(10^{20}\) seviyesine çıkabildiği için modüler çarpımı daha geniş bir ara tamsayı türü üzerinden yapar. Python uygulaması yerleşik büyük tamsayıları ve yerleşik modüler üs alma yeteneğini kullanır. Java uygulaması ise keyfi hassasiyetli tamsayı aritmetiği ve kütüphanedeki modüler kuvvet alma işlemiyle aynı hesabı yapar.
C++ sürümünde son cevaptan önce iki küçük kontrol de vardır. Biri
$$2^{10}\equiv 24\pmod{1000}$$
eşitliğini, diğeri de küçültülmüş tam ifade örneği olan
$$28433\cdot 2^{20}+1\equiv 9814161409\pmod{10^{10}}$$
sonucunu doğrular. Bu testler, gerçek çözümde kullanılan yineleme ve son formülün aynısını sınar.
İkili üs alma \(e=7830457\) için \(O(\log e)\) adet modüler çarpım gerektirir. \(e\) yalnızca 23 bit uzunluğunda olduğu için ana döngü yaklaşık 23 tur sürer; her turda bit 1 ise en fazla bir ek modüler çarpım yapılır.
Bellek kullanımı matematiksel olarak \(O(1)\)'dir; çünkü yalnızca mevcut sonuç, mevcut taban, mevcut üs ve modül gibi sabit sayıda tamsayı tutulur. Python ve Java tarafında büyük tamsayı aritmetiği kullanılsa bile tüm değerler her adımda \(10^{10}\) moduna indirildiğinden sayıların boyutu çok küçük kalır.
La cantidad central del problema es
$$N=28433\cdot 2^{7830457}+1.$$
No hace falta escribir \(N\) completo, porque la pregunta solo pide sus últimos diez dígitos. Eso equivale exactamente a calcular el residuo de \(N\) módulo
$$m=10^{10}.$$
Así, el problema entero se reduce a una sola operación modular. Si se realiza correctamente, el bloque final de diez dígitos es \(8739992577\).
Las implementaciones en C++, Python y Java siguen la misma idea matemática: reducir todos los valores intermedios módulo \(10^{10}\), obtener la potencia enorme mediante exponenciación binaria y, al final, aplicar la multiplicación exterior por \(28433\) y la suma de 1.
Como las congruencias son compatibles con la suma y la multiplicación, podemos aislar primero la potencia:
$$N \equiv 28433\cdot \left(2^{7830457}\bmod m\right)+1 \pmod m.$$
Si definimos
$$P\equiv 2^{7830457}\pmod m,$$
entonces la respuesta queda como
$$\boxed{(28433\cdot P+1)\bmod 10^{10}.}$$
Por tanto, todo gira alrededor de calcular eficientemente el residuo de \(2^{7830457}\) módulo \(10^{10}\).
El exponente \(7830457\) es enorme, pero en binario ocupa solo 23 bits. Eso permite usar el esquema clásico de cuadrados sucesivos. Se parte de
$$r_0=1,\qquad b_0=2\bmod m,\qquad e_0=7830457.$$
En cada iteración, si el exponente actual es impar, se multiplica el acumulador por la base actual; después se reemplaza la base por su cuadrado y se divide el exponente entre 2:
$$ \text{si } e_t \text{ es impar, } r_{t+1}\equiv r_t b_t \pmod m,\quad \text{si no, } r_{t+1}=r_t, $$
$$ b_{t+1}\equiv b_t^2\pmod m,\qquad e_{t+1}=\left\lfloor \frac{e_t}{2}\right\rfloor. $$
Después de unas \(\lfloor \log_2 7830457 \rfloor+1=23\) vueltas, el exponente se vuelve cero.
El razonamiento se apoya en el invariante
$$r_t\cdot b_t^{e_t}\equiv 2^{7830457}\pmod m.$$
Al comienzo es inmediato. Si \(e_t\) es impar, se extrae un factor \(b_t\) de \(b_t^{e_t}\) y se incorpora al acumulador \(r_t\); si es par, ese paso extra no hace falta. Luego se sustituye \(b_t\) por \(b_t^2\) y \(e_t\) por \(\lfloor e_t/2\rfloor\), lo que conserva exactamente la misma potencia total de 2 en aritmética modular.
Cuando termina el proceso, \(e_t=0\). Entonces el invariante se convierte en
$$r_t\equiv 2^{7830457}\pmod m,$$
y ese es precisamente el residuo que se necesitaba.
Un ejemplo más pequeño muestra el mismo mecanismo. Sustituyamos \(7830457\) por \(20\). En ese caso
$$2^{20}=1048576,$$
y por tanto
$$28433\cdot 2^{20}+1=28433\cdot 1048576+1=29814161409.$$
Sus últimos diez dígitos son
$$29814161409\bmod 10^{10}=9814161409.$$
La estructura matemática es idéntica a la del problema real; lo único que cambia es que el exponente grande obliga a usar exponenciación rápida.
El módulo es
$$10^{10}=2^{10}\cdot 5^{10}.$$
Como la base es 2, se tiene \(\gcd(2,10^{10})=2\neq 1\). Por eso la forma habitual del teorema de Euler no es el atajo natural sobre el módulo completo. Las implementaciones prefieren el método que funciona sin condiciones adicionales: cuadrados sucesivos con reducción modular tras cada multiplicación.
Las tres implementaciones siguen la misma secuencia. Primero fijan el módulo \(10^{10}\). Después calculan el residuo de \(2^{7830457}\) módulo ese valor. Luego multiplican por \(28433\), suman 1, vuelven a reducir módulo \(10^{10}\) y muestran el bloque final de diez cifras.
La matemática es la misma en C++, Python y Java, pero las herramientas numéricas no lo son. La versión en C++ realiza la multiplicación modular con un tipo intermedio más ancho, porque el producto de dos residuos menores que \(10^{10}\) puede acercarse a \(10^{20}\), demasiado grande para una multiplicación ordinaria de 64 bits. La versión en Python aprovecha enteros de precisión arbitraria y exponenciación modular incorporada. La versión en Java usa enteros de precisión arbitraria y la operación de biblioteca para potencias modulares.
La versión en C++ también verifica la aritmética con dos casos reducidos. Uno comprueba
$$2^{10}\equiv 24\pmod{1000},$$
y el otro comprueba el ejemplo reducido de la expresión completa:
$$28433\cdot 2^{20}+1\equiv 9814161409\pmod{10^{10}}.$$
Ambas comprobaciones ejercitan exactamente la misma recurrencia y la misma fórmula final que se usan para \(7830457\).
La exponenciación binaria requiere \(O(\log e)\) multiplicaciones modulares, con \(e=7830457\). Como el exponente tiene solo 23 bits, el bucle principal se ejecuta unas 23 veces, con a lo sumo una multiplicación adicional en cada iteración cuando el bit actual vale 1.
El uso de memoria es \(O(1)\) en sentido matemático: solo se almacenan unas pocas cantidades, como el acumulador, la base actual, el exponente restante y el módulo. Incluso en las versiones con enteros de precisión arbitraria, todos los valores permanecen pequeños porque se reducen inmediatamente módulo \(10^{10}\).
题目中的数是
$$N=28433\cdot 2^{7830457}+1.$$
这不是一道“把整个整数算出来”的题，而是一道“只保留最后十位”的题。只要求末十位，就等价于只要求 \(N\) 在
$$m=10^{10}$$
下的余数。因此，真正的目标不是构造一个两百多万位的整数，而是完成一次精确的模运算。做完这一步以后，最终得到的十位尾数就是 \(8739992577\)。
本题的三个实现虽然语言不同，但数学骨架完全一致：所有中间结果始终保留在模 \(10^{10}\) 的范围内，超大的幂 \(2^{7830457}\) 用二进制快速幂求余，最后再乘上 \(28433\)、加上 1，并再次取模。
因为同余运算与加法、乘法兼容，我们可以先只处理幂的部分：
$$N \equiv 28433\cdot \left(2^{7830457}\bmod m\right)+1 \pmod m.$$
如果记
$$P\equiv 2^{7830457}\pmod m,$$
那么答案就可以写成
$$\boxed{(28433\cdot P+1)\bmod 10^{10}.}$$
这样一来，整个问题就被浓缩成了一个核心对象：\(2^{7830457}\) 在 \(10^{10}\) 模下的剩余类。
指数 \(7830457\) 虽然很大，但它的二进制长度只有 23 位。快速幂正是利用这一点，把“高次幂”变成“不断平方并折半指数”的过程。初始化为
$$r_0=1,\qquad b_0=2\bmod m,\qquad e_0=7830457.$$
之后反复执行以下更新：如果当前指数是奇数，就把当前底数乘进累积结果；无论奇偶，都要把底数平方并把指数除以 2：
$$ \text{若 } e_t \text{ 为奇数，则 } r_{t+1}\equiv r_t b_t \pmod m,\quad \text{否则 } r_{t+1}=r_t, $$
$$ b_{t+1}\equiv b_t^2\pmod m,\qquad e_{t+1}=\left\lfloor \frac{e_t}{2}\right\rfloor. $$
由于 \(7830457\) 只有 23 个二进制位，所以整个循环只需要大约 \(\lfloor \log_2 7830457 \rfloor+1=23\) 轮。
快速幂的关键不变量是
$$r_t\cdot b_t^{e_t}\equiv 2^{7830457}\pmod m.$$
初始时这显然成立，因为 \(r_0=1\)、\(b_0=2\)、\(e_0=7830457\)。如果 \(e_t\) 是奇数，就先从 \(b_t^{e_t}\) 里拿出一个 \(b_t\) 乘到 \(r_t\) 上；如果 \(e_t\) 是偶数，就不用做这一步。随后把 \(b_t\) 换成 \(b_t^2\)，把 \(e_t\) 换成 \(\lfloor e_t/2\rfloor\)。这样做并没有改变“总共还代表多少个 2 的幂”，所以不变量被完整保留下来。
当循环结束时，\(e_t=0\)。这时不变量退化为
$$r_t\equiv 2^{7830457}\pmod m,$$
也就是说，累积器中保存的正是我们需要代回最终公式的那个余数。
为了看清公式如何落地，可以把指数先缩小到 20。此时
$$2^{20}=1048576,$$
所以
$$28433\cdot 2^{20}+1=28433\cdot 1048576+1=29814161409.$$
它的末十位就是
$$29814161409\bmod 10^{10}=9814161409.$$
这个例子与正式题目的数学结构完全相同，差别只在于正式题目中的指数太大，必须用快速幂而不能直接展开。
模数可以分解为
$$10^{10}=2^{10}\cdot 5^{10}.$$
由于底数本身就是 2，所以 \(\gcd(2,10^{10})=2\neq 1\)。这说明在整个模 \(10^{10}\) 上，常见的欧拉定理形式并不是这里的自然捷径。代码采用的是更稳健、也更直接的路线：每做一次乘法就立即取模，通过重复平方逐步得到最终余数。
C++、Python 和 Java 三个实现都遵循同一条流水线。先把模数设为 \(10^{10}\)，再求出 \(2^{7830457}\) 在该模数下的余数，随后乘上 \(28433\)、加上 1、再取一次模，最后输出得到的十位尾数。
数学完全一致，但具体的数值运算方式略有区别。C++ 实现会在模乘时使用更宽的中间整数类型，因为两个小于 \(10^{10}\) 的余数相乘，数量级可能接近 \(10^{20}\)，普通 64 位乘法并不安全。Python 实现依赖语言自带的大整数和内建的模幂能力。Java 实现则使用任意精度整数，并借助标准库里的模幂运算来完成同样的计算。
C++ 版本在输出正式答案前还做了两个小检验。第一个检验确认
$$2^{10}\equiv 24\pmod{1000},$$
第二个检验确认缩小版完整表达式
$$28433\cdot 2^{20}+1\equiv 9814161409\pmod{10^{10}}.$$
这两个检查并不是额外的数学分支，而是对同一套递推更新和同一条最终公式的直接验证。
快速幂的时间复杂度是 \(O(\log e)\)，这里 \(e=7830457\)。由于指数只有 23 个二进制位，主循环大约执行 23 次；每轮至多再做一次“若当前位为 1 则乘入累积器”的模乘。
空间复杂度在数学意义上是 \(O(1)\)。程序始终只维护少量状态：当前累积结果、当前底数、剩余指数和模数。即使在 Python 和 Java 中使用任意精度整数，因为每一步都会立刻对 \(10^{10}\) 取模，所以数值规模始终远小于原始的两百多万位整数。
Число из задачи имеет вид
$$N=28433\cdot 2^{7830457}+1.$$
Полностью вычислять и записывать это число не нужно, потому что требуется только его последние десять цифр. А это в точности означает: нужно найти остаток от \(N\) по модулю
$$m=10^{10}.$$
Тем самым задача сводится не к работе с огромным простым числом, а к одной модульной формуле. Результирующий десятизначный хвост равен \(8739992577\).
Во всех трех реализациях используется одна и та же математика: каждое промежуточное значение сразу сокращается по модулю \(10^{10}\), гигантская степень \(2^{7830457}\) вычисляется двоичным возведением в степень, а затем применяется внешняя операция умножения на \(28433\) и прибавления единицы.
Поскольку сравнения по модулю согласованы с умножением и сложением, можно сначала изолировать степенной член:
$$N \equiv 28433\cdot \left(2^{7830457}\bmod m\right)+1 \pmod m.$$
Если обозначить
$$P\equiv 2^{7830457}\pmod m,$$
то ответ принимает вид
$$\boxed{(28433\cdot P+1)\bmod 10^{10}.}$$
Следовательно, главное вычислительное ядро задачи состоит в нахождении остатка \(2^{7830457}\) по модулю \(10^{10}\).
Показатель \(7830457\) огромен, но в двоичной записи занимает всего 23 бита. Поэтому подходит схема повторного возведения в квадрат. Вводятся значения
$$r_0=1,\qquad b_0=2\bmod m,\qquad e_0=7830457.$$
Далее на каждом шаге, если текущий показатель нечетный, накопленный результат умножается на текущую базу; затем база заменяется на квадрат, а показатель делится на 2:
$$ \text{если } e_t \text{ нечетно, то } r_{t+1}\equiv r_t b_t \pmod m,\quad \text{иначе } r_{t+1}=r_t, $$
$$ b_{t+1}\equiv b_t^2\pmod m,\qquad e_{t+1}=\left\lfloor \frac{e_t}{2}\right\rfloor. $$
Через примерно \(\lfloor \log_2 7830457 \rfloor+1=23\) итерации показатель становится равным нулю.
Ключевой инвариант цикла имеет вид
$$r_t\cdot b_t^{e_t}\equiv 2^{7830457}\pmod m.$$
В начальный момент он очевиден. Если \(e_t\) нечетно, один множитель \(b_t\) переносится из \(b_t^{e_t}\) в аккумулятор \(r_t\); если \(e_t\) четно, такого переноса не требуется. После этого \(b_t\) заменяется на \(b_t^2\), а \(e_t\) на \(\lfloor e_t/2\rfloor\), и полная степень двойки, представляемая произведением, сохраняется.
В конце цикла \(e_t=0\), поэтому инвариант упрощается до
$$r_t\equiv 2^{7830457}\pmod m,$$
то есть аккумулятор действительно содержит нужный модульный остаток.
Полезно посмотреть на ту же формулу при показателе \(20\) вместо \(7830457\). Тогда
$$2^{20}=1048576,$$
и потому
$$28433\cdot 2^{20}+1=28433\cdot 1048576+1=29814161409.$$
Последние десять цифр равны
$$29814161409\bmod 10^{10}=9814161409.$$
Это ровно та же математика, что и в исходной задаче; отличие только в том, что для настоящего показателя необходимо быстрое возведение в степень.
Модуль раскладывается как
$$10^{10}=2^{10}\cdot 5^{10}.$$
Поскольку база равна 2, имеем \(\gcd(2,10^{10})=2\neq 1\). Поэтому привычное применение теоремы Эйлера к полному модулю здесь не служит основным инструментом. Реализации выбирают универсальный путь: повторное возведение в квадрат с модульным сокращением после каждой операции умножения.
Во всех трех версиях сначала фиксируется модуль \(10^{10}\). Затем находится остаток \(2^{7830457}\) по этому модулю. После этого результат умножается на \(28433\), к нему прибавляется 1, выполняется еще одно сокращение по модулю \(10^{10}\), и на экран выводится искомый десятизначный хвост.
Математическая формула в C++, Python и Java одинакова, но механика числа отличается. В C++ модульное умножение выполняется через более широкий промежуточный целочисленный тип, потому что произведение двух остатков меньше \(10^{10}\) может быть порядка \(10^{20}\), что небезопасно для обычного 64-битного умножения. В Python используются встроенные целые произвольной точности и встроенное модульное возведение в степень. В Java та же схема реализуется с помощью целых произвольной точности и библиотечной операции модульной степени.
В C++-версии перед выводом окончательного ответа проверяются два уменьшенных случая. Первый подтверждает
$$2^{10}\equiv 24\pmod{1000},$$
а второй подтверждает сокращенный вариант полной формулы:
$$28433\cdot 2^{20}+1\equiv 9814161409\pmod{10^{10}}.$$
Обе проверки используют ту же рекуррентную схему и ту же итоговую формулу, что и основное вычисление.
Двоичное возведение в степень требует \(O(\log e)\) модульных умножений при \(e=7830457\). Поскольку показатель имеет только 23 двоичных разряда, основной цикл выполняется примерно 23 раза; в каждой итерации может потребоваться еще одно умножение, если текущий бит равен 1.
Память имеет порядок \(O(1)\) в математическом смысле: хранятся только аккумулятор, текущая база, оставшийся показатель и модуль. Даже в вариантах с целыми произвольной точности все значения остаются маленькими, потому что после каждого шага они немедленно сокращаются по модулю \(10^{10}\).
العدد المحوري في المسألة هو
$$N=28433\cdot 2^{7830457}+1.$$
ليس المطلوب أن نحسب هذا العدد كاملًا، لأن السؤال يطلب آخر 10 أرقام فقط. وهذا يعادل تمامًا أن نحسب باقي \(N\) بترديد
$$m=10^{10}.$$
إذًا المسألة كلها تتحول إلى حساب معياري واحد بدل التعامل مع عدد هائل جدًا. وعند إتمام هذا الحساب نحصل على الذيل العشري \(8739992577\).
الفكرة الرياضية في تطبيقات C++ وPython وJava واحدة: نُبقي كل القيم الوسيطة مختزلة بترديد \(10^{10}\)، ونحسب القوة الضخمة \(2^{7830457}\) بطريقة الرفع السريع الثنائي، ثم نطبق الضرب الخارجي في \(28433\) وأخيرًا نضيف 1.
بما أن التطابقات تنسجم مع الجمع والضرب، يمكننا عزل جزء القوة أولًا:
$$N \equiv 28433\cdot \left(2^{7830457}\bmod m\right)+1 \pmod m.$$
إذا رمزنا إلى
$$P\equiv 2^{7830457}\pmod m,$$
فإن الجواب يصبح
$$\boxed{(28433\cdot P+1)\bmod 10^{10}.}$$
وهكذا ينحصر العمل الحقيقي في إيجاد باقي \(2^{7830457}\) بترديد \(10^{10}\).
الأس \(7830457\) كبير جدًا، لكنه لا يحتاج إلا إلى 23 خانة ثنائية. لهذا يكون الرفع بالتربيع المتكرر مناسبًا جدًا. نبدأ بالقيم
$$r_0=1,\qquad b_0=2\bmod m,\qquad e_0=7830457.$$
وفي كل خطوة، إذا كان الأس الحالي فرديًا فإن الناتج التراكمي يتغير وفق
$$r_{t+1}\equiv r_t b_t \pmod m,$$
أما إذا كان زوجيًا فيبقى الناتج التراكمي كما هو:
$$r_{t+1}=r_t.$$
وفي الحالتين معًا نحدّث القاعدة والأس بالعلاقتين
$$b_{t+1}\equiv b_t^2\pmod m,\qquad e_{t+1}=\left\lfloor \frac{e_t}{2}\right\rfloor.$$
وبعد نحو \(\lfloor \log_2 7830457 \rfloor+1=23\) دورة فقط يصبح الأس صفرًا.
الثابت الأساسي داخل الحلقة هو
$$r_t\cdot b_t^{e_t}\equiv 2^{7830457}\pmod m.$$
هذا واضح في البداية. وإذا كان \(e_t\) فرديًا فإننا ننقل عاملًا واحدًا من \(b_t\) من الحد \(b_t^{e_t}\) إلى المجمع \(r_t\). وإذا كان زوجيًا فلا حاجة إلى هذا النقل. بعد ذلك نستبدل \(b_t\) بـ \(b_t^2\) و\(e_t\) بـ \(\lfloor e_t/2\rfloor\)، فتظل القوة الكلية نفسها محفوظة بترديد \(m\).
عندما تنتهي الحلقة يكون \(e_t=0\)، فيتحول الثابت إلى
$$r_t\equiv 2^{7830457}\pmod m,$$
وهذا يعني أن القيمة المتراكمة هي بالضبط الباقي الذي نحتاج إليه في الصيغة النهائية.
يمكن رؤية الفكرة نفسها بوضوح إذا استبدلنا \(7830457\) بالأس \(20\). عندئذ
$$2^{20}=1048576,$$
ومن ثم
$$28433\cdot 2^{20}+1=28433\cdot 1048576+1=29814161409.$$
وآخر عشرة أرقام تساوي
$$29814161409\bmod 10^{10}=9814161409.$$
البنية الرياضية هنا مطابقة تمامًا للمسألة الأصلية، لكن الأس الحقيقي أكبر بكثير، ولذلك تصبح طريقة التربيع المتكرر ضرورية.
يمكن تحليل الموديل إلى
$$10^{10}=2^{10}\cdot 5^{10}.$$
وبما أن الأساس هو 2، فإن \(\gcd(2,10^{10})=2\neq 1\). لهذا لا تكون الصيغة المعتادة من مبرهنة أويلر هي الأداة المباشرة على الموديل الكامل هنا. ولهذا اختارت التطبيقات المسار الأكثر صلابة: تربيع متكرر مع اختزال معياري بعد كل عملية ضرب.
التنفيذات الثلاثة تتبع الخطوات نفسها. أولًا يُثبَّت الموديل \(10^{10}\). بعد ذلك يُحسب باقي \(2^{7830457}\) بالنسبة إلى هذا الموديل. ثم تُضرَب النتيجة في \(28433\)، ويُضاف 1، ثم يُؤخذ الباقي مرة أخرى بترديد \(10^{10}\)، وأخيرًا يُطبع الذيل العشري المطلوب.
المعادلة الرياضية واحدة في C++ وPython وJava، لكن وسيلة تنفيذ الحساب تختلف. في C++ تُنفَّذ الضربات المعيارية باستعمال نوع وسيط أوسع، لأن حاصل ضرب عددين أصغر من \(10^{10}\) قد يقترب من \(10^{20}\)، وهو أكبر من الضرب المعتاد على 64 بت. في Python يعتمد التنفيذ على الأعداد الصحيحة ذات الدقة المفتوحة وعلى الرفع المعياري المدمج في اللغة. أما في Java فيُستخدم حساب الأعداد الصحيحة كبيرة الحجم مع عملية مكتبية مخصصة للقوى المعيارية.
نسخة C++ تتحقق كذلك من الحساب على حالتين أصغر قبل إخراج الجواب النهائي. الأولى تؤكد أن
$$2^{10}\equiv 24\pmod{1000},$$
والثانية تؤكد المثال المصغر للتعبير الكامل:
$$28433\cdot 2^{20}+1\equiv 9814161409\pmod{10^{10}}.$$
هاتان المراجعتان تستعملان العلاقة التكرارية نفسها والصيغة الختامية نفسها المستعملة في المسألة الأصلية.
الرفع الثنائي يحتاج إلى \(O(\log e)\) من الضربات المعيارية عندما يكون \(e=7830457\). وبما أن هذا الأس لا يملك إلا 23 بتًا، فالحلقة الرئيسية لا تدور إلا نحو 23 مرة، مع إمكانية ضربة معيارية إضافية واحدة عندما يكون البت الحالي مساويًا لـ 1.
أما الذاكرة فتعقيدها \(O(1)\) بالمعنى الرياضي، لأن الخوارزمية تحتفظ بعدد ثابت من القيم فقط: الناتج التراكمي، والأساس الحالي، والأس المتبقي، والموديل. وحتى في اللغتين اللتين تستخدمان أعدادًا كبيرة، تبقى القيم صغيرة جدًا لأن كل خطوة تختزل مباشرة بترديد \(10^{10}\).