Berechnen von (a^b)%MOD mit großen Exponenten

Bei dieser Codierungsherausforderung besteht die Aufgabe darin, den Wert von pow( zu berechnen a, b)%MOD, wobei der Exponent b extrem groß sein kann. Während die herkömmliche log(b)-Zeitkomplexitätsmethode für kleinere Werte geeignet ist, wird sie unpraktisch, wenn b die Kapazität von Long-Long-Datentypen in C überschreitet.

Ein effizienterer Ansatz beinhaltet jedoch die Nutzung der Totient-Funktion von Euler. φ(MOD). Der Satz von Euler besagt, dass a^φ(MOD)≡1(mod MOD). Dies bedeutet, dass die Potenz von a erheblich auf a^(b % φ(MOD)) reduziert werden kann.

Die Berechnung von φ(MOD) ist an sich keine triviale Aufgabe, kann aber mithilfe ganzzahliger Faktorisierungsmethoden erreicht werden . Nach der Berechnung kann der Exponent b durch b % φ(MOD) ersetzt werden, um die Rechenzeit drastisch zu reduzieren.

Weitere Verfeinerungen

Im Jahr 2008 demonstrierte Schramm, dass φ (b) kann aus der diskreten Fourier-Transformation von gcd(b, i) erhalten werden, wobei i im Bereich von 1 bis b liegt. Dadurch entfällt die Notwendigkeit einer expliziten Faktorisierung.

Zusätzlich kann die Carmichael-Funktion λ(MOD) verwendet werden, um die richtige Antwort zu erhalten, insbesondere wenn a und MOD gemeinsame Faktoren haben.

Code-Implementierung

Der folgende Codeausschnitt dient als Beispiel in C :

#include 
#include 

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }

ll pmod(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    if (b % 2 == 1) {
        return (a * pmod(a, b - 1, mod)) % mod;
    } else {
        ll tmp = pmod(a, b / 2, mod);
        return (tmp * tmp) % mod;
    }
}

int main() {
    ll a, b, mod;
    cin >> a >> b >> mod;
    cout