Modulo für große Zahlen, die quadriert werden

Question

Ich habe eine große Zahl, die ich den Rest nehmen möchte. Zum Beispiel 300^31. Wenn ich versuche, % Operator zu verwenden, sagt es, dass ich es nicht im Doppel verwenden kann, da es nur für Ganzzahlen funktioniert. Gibt es eine Funktion für diese Berechnung?

Ich versuchte a=pow(b,x)%d;

Answer 1

Ich denke, es ist besser zu nehmen Rest zu verwenden, während Sie zu potenzieren versuchen. Sie können Big Modulo Algorithm verwenden. Es wird Ihnen helfen, große Zahlen zu vermeiden. Und danach können Sie einfach lange statt doppelt verwenden.

Ich versuche, diesen Code in Codeblöcken 16,01 (codeblocks-16.01mingw-setup.exe) zu schreiben und es funktioniert ziemlich gut (mein Code etwas anders als der Link-Code, aber es das gleiche Konzept hat):

#include<iostream> 
using namespace std; 

int bmod = 33; 

int bigmod(long long int x,long long int b){ // x^b 
    int ans=1; 
    while(b){ 
     if(b%2)ans=((long long)ans*x)%bmod; 
     b=b>>1; 
     x=((long long)x*x)%bmod; 
    } 
    return ans;} 

int main(){ 
    cout<<bigmod(300,31); 
} 

Answer 2

Wenn b, x und d passen in ganzen Zahlen, können Sie

int expoModulo(int b, int x, int d) { 
    int a = 1; 
    for(int i=0; i<x; i++) { 
     a = (a*b)%d; 
    } 
    return a; 
}