Search code examples
cmodulusexponentiation

Modular Exponentiation of 2

I have written this code to calculate 2^n mod 10^9+7. But sadly this function works only till 2^31 and afterwards all the answers are zero. Can somebody shed some light why?

typedef unsigned long long LL;
const int MOD = 1000000007;
LL powmod(int a,int n)
{
    LL p=1;
    for(;n;)
    {
        if(n%2) p=(p*a)%MOD;
        if(n/=2) a=(a*a)%MOD;
    }
    return p;
}
Solution

  • Just change LL powmod(int a,int n) to LL powmod(LL a,int n).

    As squeamish ossifrage hinted at, with int a, the subexpression a*a is computed in int range and overflows "when a * a exceeds MAX_INT" (M.M), while with LL a, it is computed in unsigned long long range.