Power Function

[GEqLhbRD]

I want to calculate power of large number using modulus(10^9+7). Now when i am using python inbuit functions pow(a,b,m). Is it running for all the test cases but when writing the following code in cpp. Its is not passing some of the case.

  long long int power( long long int a,long long  int b)
{
    a=a%MOD;
	long long int p = 1;
	while(b>0)
	{
        if(b&1)
		{p = (p*a)%MOD;}
		a = (a*a)%MOD;
        b >>= 1;
	}
	return(p%MOD);
}

Can anyone tell me what is wrong with my code? Thanks in advance.

[jonnin]

bitwise logic may not work on signed values (some compilers may tolerate it).
you may need to say
if(b%2 == 1)
and the shift may act weird as well.
maybe b should just be unsigned?

scratch that, mine is just pow() yours is something else, missed that.

the only differences I see is the above + you did not do the overflow checks, so that seems like a reasonable thing to look at too, as Ganado said.

[Ganado]

Can't test any code right now, but I believe the method I learned in school for doing fast modular exponentiation was this: https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

Maybe the pseudo-code there will help. Although it looks like that's the algorithm you're already using.
___________________

northremembers, it would be helpful if you told us exactly which test case is failing. It could be possible that your a*a is overflowing. Can you tell us what test a, b, m value combination is failing?