Calculating large power of a number
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;
}
In this function when I pass a=2, b>31, it always returns 0.for b=31 i got 147483634.can you tell where the problem is?
or can you tell another method for calculating large powers of a number.
La solution
In (a*a)%M
, a*a probably overflows before computing the remainder. And starting with 2, the overflow producing 0 doesn't surprise me. You need to work with a type able to represent (M-1)*(M-1), i.e. 1000000012000000036 while int
is commonly limited to 2147483647. long long
(standard in C since 99 and C++ since 11, common extension elsewhere) is guaranteed to work.
Autres conseils
Under <cmath>
there's pow(x,y)
in which x is the base and y is the exponent. x^y.
When a
is an int
, a*a
uses int
-sized arithmetic. Try a*(long long)a
instead, to use wider arithmetic that won't overflow.