Berechnung (a^b)% MOD

Question

Ich möchte für die Berechnung des Wertes von pow (a, b)% MOD codieren. Ich benutze C++, um zu programmieren.

Aber das Problem ist der Wert von b kann sehr groß sein. Ich kenne die log (b) Zeitkomplexitätsmethode. Aber der Wert von b passt möglicherweise nicht in den Datentyp "long long" von C++. Zum Beispiel kann b 1000000000 Fibonacci-Nummer sein. Die genaue Berechnung einer so großen Zahl ist selbst nicht möglich (zeitlich befristet).

P.S. :

• pow (a, b) bedeutet a * a * a * a * ... b mal.
• X% MOD bedeutet den Rest, der beim Teilen von X durch MOD erhalten wird.

Answer 1

Das ist eine typische Aufgabe. Bitte (oder wirklich, bitte!) Lesen Sie über die Euler's totient function.

Und dann die Euler's theorem.

Die Sache ist, Sie können drastisch reduzieren a^b zu a^(b% Phi (MOD)). Ja, Sie werden eine Art von ganzzahliger Faktorisierungsmethode benötigen, aber immer noch keine verrückten Ideen, die benötigte Leistung tatsächlich zu berechnen.

Wir haben solche Proben in meiner Jugend von Hand gemacht :) Auch wenn die Zahlen weit über 32/64 Bit reichen.

EDIT: Nun, du lebst und lernst. Im Jahr 2008 wird das Ergebnis erhalten:

"Die totient der diskreten Fourier-Transformation des GCD ist: (Schramm (2008))"

So zu berechnen phi (b) man nicht seine Faktoren zu wissen braucht.

EDIT (2):

Und die Carmichael's function ist, was Sie die richtige Antwort für jedes a zu erhalten, b und MOD berechnen müssen.

Answer 2

Erstens: ^ in C/C++ sind nicht die Betreiber für Kräfte. In der Tat gibt es dafür keinen Operator. ^ steht für eine bitweise XOR. Sie müssen pow(base, exp) verwenden, die in der Kopfzeile math.h oder cmath gefunden werden kann.

Für so große Zahlen, mit double oder long double (genaue Längen und und daraus resultierende Datentypen können je nach Plattform variieren), aber irgendwann stolpern Sie über Präzisionsprobleme, abhängig von Ihrem Anwendungsfall, Größe der Werte Am besten verwenden Sie einen benutzerdefinierten Datentyp (bearbeiten Sie ihn zB aus einer der Bibliotheken in einer der verknüpften Fragen).

Answer 3

Ich schlage vor, eine spezielle Mathematikbibliothek zu verwenden. Auch das sieht wie Krypto aus, also schlage ich vor, eine Krypto-Bibliothek zu verwenden. GNU muss einen haben, den Sie verwenden können. Dies liegt daran, dass der Exponent in krypto in vielen Fällen ausgewählt werden kann, um eine effiziente Berechnung unter Verwendung von Verknüpfungen zu ermöglichen, die normale mathematische Bibliotheken nicht annehmen können.

Answer 4

Für den Umgang mit sehr großen Zahlen, werfen Sie einen Blick auf boost's Multiprecision Bibliothek. Es hat eine powm() -Funktion, die für diesen Zweck gut funktioniert.

Von Generic Integer Operations:

template <class Integer> 
Integer powm(const Integer& b, const Integer& p, const Integer& m); 

Returns b ^p% m.

Beispiel:

#include <boost/multiprecision/cpp_int.hpp> 

boost::multiprecision::cpp_int pow("8912627233012800753578052027888001981"); 
boost::multiprecision::cpp_int mod("0x86f71688cdd2612c117d1f54bdae029"); 
boost::multiprecision::cpp_int base(12345); 

boost::multiprecision::cpp_int result = powm(base, pow, mod); 

std::cout << "result is: " << result << std::endl; 

druckt:

result is: 5758534182572671080415167723795472693 

Answer 5

ich diese Funktion verwenden, dieses Problem

UVA 374 zu lösen - Big Mod

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=310

// a^b % T 

// with Exponentiation by squaring (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method) 

// if a very large use 
// R=(unsigned long long)(R*a)%T; 

int restOfPot(long long a,int b,int T) 
{ 
    a%=T; 
    long long R=1; 

    while(b) 
    { 
     if(b&1) R=(R*a)%T; 
     a=(a*a)%T; 
     b>>=1; 
    } 

    return int(R); 
} 

Answer 6

Aber könnte der Wert von b nicht in dem Datentyp passen "long long" von C++. Zum Beispiel kann b 1000000000 Fibonacci-Nummer sein.

Für Dinge wie diese, gibt es eine einfache Lösung: erinnern

a^(b + c) == a^b * a^c mod d

können Sie Berechnen Sie das Produkt, nach dem Sie gefragt haben, mit der gleichen Rekursion, mit der Sie Fibonacci-Zahlen berechnen - Sie brauchen keine großen Zahlen oder modulare Potenzierung!

Eine andere Version, die sich manchmal kommt, ist

a^(b * c) = (a^b)^c mod d

Answer 7

#include <iostream> 
#include <math.h> 
#include <stdint.h> 

using namespace std; 

int main(){ 
int64_t a, b, k, d; 
cin >> a >> b >> k; 

int64_t poew = pow(a, b); 
d = poew % k; 

cout << d; 
} 

weil int64_t größere Reichweite als int hat