# doubt regarding a^b^c mod p

We want to calculate a^b^c mod p where p is a prime number and suppose 0 <= a,b,c <= (int range) and a^b represents a raise to power b . My doubt is regarding to the following condition .

``````if (a != 0 && (a % p == 0))
print 0
``````

But if suppose a is multiple of p , b = 0 and c > 0 , then b^c is 0 and a^0 is 1. Please explain this case.
Any comments or suggestions are appreciated. Thank you.

EDIT 1 :

``````if(a%p == 0 && a>0)
{
if(b==0 && c>0)
{
print 1    //// this gets also accepted
print 0    //// this gets also accepted

}
else
{
print 0
}

}
``````

Both above mentioned conditions are getting accepted. So which one is correct ??

3 Likes

You are 100% correct, extend the case

if (a != 0 && (a % p == 0) && b!=0)

1 Like

if(a%p == 0 && a>0)
{
if(b==0 && c>0)
{
print 1 //// this gets also accepted
print 0 //// this gets also accepted

``````            }
else
{
print 0
}

}
``````

Both above mentioned conditions are getting accepted. So which one is correct ??

2 Likes

This means that the corner cases are not checked…@betlista you are correct

yeah… this means that the corner cases have not been checked in the test files
you can comment on the problem page itself. It’s quite a new problem, so if you mention there that the judge is accepting solutions giving different answers for the above cases, there is a good chance that the psetter may update the test cases and rejudge the solutions

(a^(b^c)) % p == modpow(a, modpow(b, c, p), p)

with this method, you don’t need to check for corner cases.

``````modpow(b, e, m):
r = 1
while e:
if  e & 1:
r = (r * b) % m
b = (b * b) % m
e >>= 1
return r``````

I do no know what you are referring to… Where that condition came from. It seems valid to me what you wrote…

1 Like

I am solving this problem SPOJ.com - Problem POWERUP
and after using the above condition I got AC. Sphere Online Judge (SPOJ) - Status

1 Like

Getting accepted means that there is probably no such corner case in test cases. You are correct. You can try to write to spoj team to add your test case, but I have bad experience with CodeChef on this, they never did that (I tried just few times).

1 Like

Thanks for your answer. But with your equation, I am getting wrong answer. I think, your equation is not in accordance with Fermat’s little theorem. If a and p are coprime, then we will calculate modpow(b,c,p-1). But,one thing to notice is that a,b,c can also be zero. So, we have to take care of cases when anyone of a,b,c is zero.

2 Likes