Modular Exponentiation | Last testcase did not pass

#1


My code.
I unlocked test cases, and found out output is 4 which is same as output of my code. Then why did test case not pass?

Why is it not passing all test cases
#2

Hey @manisini.chakraborty

while (b > 0)
{
if (b & 1)
answer = (1ll*answer * a) % c; //added 1ll
b = b >> 1;
a = (1ll*a * a) % c; //added 1ll
}

These are the required changes otherwise if a is 10^5-1 and c is 10^5 then those statements will overflow

Sometimes testcases are jumbled:)

#3

Hello, thank you for your help. Also is there any other way of doing this other than typecasting to long long int may be?

while (b > 0)
{
	if (b & 1)
		answer = ((answer % c)*(a % c)) % c;

	b = b >> 1;
	a = ((a % c)  * (a % c)) % c;
	
}

I mean something like this? I tried doing this but test case did not pass. I tried applying the formula (ab % p ) = ( (a % p ) * (b % p) ) % p as mentioned in the editorial.

#4

Hey,No there is no other way
U have to make it long long either by taking them as long long (done in editorial) or by multiplying by long long

#5

Thank you for your help. My doubt has been resolved.

1 Like