Große mathematische Operation C++

Question

Ich möchte große mathematische Operation in C++.

long long h= 4294967295; 
long long d=7910266469; 
long long n=10021211227; 
long long result; 

Ich bin brauchen berechnen dies:

h^d mod n

result=pow(h,d) % n; 

Ich weiß nicht, welche Art using.Please mir helfen, für Typ-Nummern wählen .. Dank

Answer 1

Blick auf this wikipedia article. Es ist ein ziemlich schönes Beispiel mit dem folgenden speichereffizienten Pseudo-Code:

function modular_pow(base, exponent, modulus) 
    if modulus = 1 then return 0 
    c := 1 
    for e_prime = 1 to exponent 
     c := (c * base) mod modulus 
    return c 

Es gibt sogar ein Beispiel für beeing speichereffizient und weniger Operationen. Ich denke, es sollte möglich sein, den C++ - Code zu bekommen.

Wenn Sie diese Methode verwenden, sollte long long für Ihre Lösung in Ordnung sein.

---

getestet Nicht aber eine einfache 1: 1 Übersetzung aus dem Pseudo-Code von oben ...

long long result = 1; 
int i; 
for(i=0; i<d;i++){ 
    result = (result * h) % n; 
}