計算一個數的大功率

Question

#include<iostream> 
#include<cstdio> 
#define M 1000000007 
using namespace std; 

long long int power(int a,int b) 
{ 
    if(b==0) 
     return 1; 
    else if(b==1) 
     return a; 
    else if(b%2==0) 
     return power((a*a)%M,b/2); 
    else 
     return (power((a*a)%M,b/2)*a)%M; 
} 

在這個函數中，當我傳遞a = 2，b> 31時，它總是返回0.for b = 31我得到了147483634，你告訴問題出在哪裏？

或者你能否告訴另一種計算大數的方法。

Answer 1

在(a*a)%M，一*計算剩餘之前可能溢出。從2開始，產生0的溢出並不讓我感到驚訝。您需要使用能夠表示（M-1）*（M-1）的類型，即1000000012000000036，而int通常限制爲2147483647. long long（自99以來的標準C以及11以後的C++，其他地方的常見擴展）上班。

Answer 2

在<cmath>有pow(x,y)其中x是基數，y是指數。 X ^年。

Reference here

Answer 3

當a是int時，a*a使用int大小的算術。請嘗試使用a*(long long)a，以使用不會溢出的更寬泛的算術。