doubt regarding a^b^c mod p

general
, ,
1

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
2

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

1 Like
3

You are 100% correct, extend the case

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

1 Like
4

I am solving this problem http://www.spoj.com/problems/POWERUP/
and after using the above condition I got AC. http://www.spoj.com/status/POWERUP,shivam217/

1 Like
5

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
6

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
7

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

8

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

9

(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
10

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