Was benötigt die Anweisung von (num + mod)% mod?

Question

Was ist die Notwendigkeit der Aussage ans = (ans + mod) % mod in diesem Programm?

Angenommen, mod = 10^9+7. Diese Funktion wird die Berechnung a auf die Kraft der b unter mod Betrieb in O (log (n)) Komplexität:

long long power(long long a, long long b) 
{ 
    if (b == 0) 
     return 1ll; 
    long long ans = power(a, b/2); 
    ans = (ans * ans) % mod; 
    ans = (ans + mod) % mod; 
    if(b % 2 == 1) 
     ans = (ans * a) % mod; 
    ans = (ans + mod) % mod; 
    return ans; 
} 

Answer 1

Die häufigste Verwendung eines solchen Konstrukts, dass das Ergebnis nicht negativ zu machen. Der Standard operator% verhält sich für positive und negative Argumente unterschiedlich: zum Beispiel 4%3==1, aber (-2)%3==-2, während Sie erwarten könnten (-2)%3==1 und (-2)/3==-1, die mathematisch korrekter ist.

Dieses Verhalten kann oft Probleme verursachen, wenn modulare Arithmetik verwendet wird, und dieser Trick des Hinzufügens mod wird oft verwendet, um das mathematisch korrektere nicht negative Ergebnis zu erhalten. Anstatt einfach a%b zu schreiben, wenn a negativ sein kann, schreibt man (a%b+b)%b.

Allerdings ist seine Verwendung im Code in Ihrer Frage seltsam. In diesem Fall ist es einfacher anzunehmen, dass a positiv ist vor Aufruf der power Funktion aus dem Hauptcode (zum Beispiel, indem Sie den Hauptanruf wie power((a%mod+mod)%mod, b)). Wahrscheinlich wollte der Autor nur zusätzliche Sicherheit für die Korrektheit bekommen, obwohl es nicht nötig war.