Cake Walk

Can you guys help me in calculating this -

(x^y)%c

where 1<=x,y<=1000000000

1<=c<=1000000000

I think it is just cakewalk for u guys :stuck_out_tongue:

Hello @theshubhamgoel,

Nothing is too cakewalk if we can actually do something about it :slight_smile:

“Nothing is too small or too trivial if you can actually do something about it.” - Richard P. Feynman

The problem you are asking us about is what is usually known as [Exponentiation by squaring][1].

The main idea to efficiently solve this problem is to figure a way of reducing the number of multiplications and that can be done by the above method.

Usually, the value of c, tends to be a prime number, you can learn why, [here][2].

On the case where c has the particular value of 10^9 + 7 (as it had on a previous problem), here is the code:

long long int fast_exp(int base, int exp)
{
    if(exp==1)
    return base;
    else
    {
        if(exp%2 == 0)
        {
            long long int base1 = pow(fast_exp(base, exp/2),2);
            if(base1 >= 1000000007)
            return base1%1000000007;
            else
            return base1;
        }
        else
        {
            long long int ans = (base*  pow(fast_exp(base,(exp-1)/2),2));
            if(ans >= 1000000007)
            return ans%1000000007;
            else
            return ans;
        }
    }
}

All the best,

Bruno
[1]: http://en.wikipedia.org/wiki/Exponentiation_by_squaring
[2]: http://discuss.codechef.com/questions/3510/whats-significant-about-the-number-choice-1000000007
[3]: http://en.wikipedia.org/wiki/Chinese_remainder_theorem

3 Likes

@junior94 You are right. fast exponentiation will work for all values of c.
@kuruma You will need c to be prime only when you are doing a division operation like x/y % c. Here is a simple proof this works for non-prime c.

Let me first prove that MOD operation can be split in multiplication for any general c. Say we want to multiply 2 numbers x and y and calculate MOD with c.
x can be written as q1 *c + r1. y can be written as q2 * c + r2. Where q1,r1,q2,r2 >= 0.

 (x * y) % c = (( q1 *c + r1 ) * (q2 * c + r2)) % c

           = ((q1 * c * q2) + (q1 * c * r2 ) + (r1 * q2) + (r1 * r2)) % c

           = (r1 * r2) % c.  // Since all terms with c will become 0 after taking MOD with c.

Assume we can apply the mod on each individual variable. i.e.

  x * y % c =  ((x % c) * (y % c)) % c

            = ((q1 * c + r1 ) % c * (q2 * c + r2) % c) % c

            = (r1 * r2) % c //Same in both cases.

Hence we can see that mod operation in multiplication can be first applied to the individual operands in the multiplication and then we can multiply them and take their MOD. Also in the proof above, nowhere is it necessary that c be a prime number.

Since exponentiation by squaring is just a case of applying the MOD operation on individual terms calculated in the recursion before multiplying, it is not necessary for c to be prime.

Life is so much easier in Python. just 1 line : pow(x,y,c) !!

1 Like

@theshubhamgoel read this, it should help you understand.

Can someone really explain that code ?

Thanks

Hello @theshubhamgoel,

As I have already told you, you can read here for a more detailed explanation…

If you still don’t understand it fully, ask us more specific questions and we will be glad to help you out :slight_smile:

All the best,

Bruno

use repeated squaring with mod

time complexity : O(logN)

method is working like how u convert decimal number to binary

Q N=3 pow=5

ANS : ans=1

    • 5%2==1
      ans=1 * 3; pow =5-1=4
    • N=3 * 3 pow =4/2=2
  • 2%2==0
  • N = 9 * 9
    pow =2/2=1
    • 1%2==1
      ans = ans*81
    • N= 81*81
      pow =1/2=0

final ans = 243



  long long int cal(long long int N,long long int pow,long long int MOD){


      if(N==0 || N===1) return N%MOD;

      if(pow==0) return 1;

       if(mod==1) return 0;

      long long int ans=1;

        while(pow){

            if(pow%2){

               ans=(ans*N)%MOD;
            }

            N=(N*N)%MOD;
            pow/=2;
        }
    return ans;
  }


HAPPY CODING

Since (a * b) % m = ((a % m) * (b % m)) % m

So x^y = x * x * x * x …y times

ans=x;
for(int i=1;i<=y-1;i++) {
	ans = ((ans % M) * (x % M)) % M;
}

It has O(y) complexity. Hope you underdtand! :slight_smile:

Happy Coding.

I think this method works even if c is not prime, the real problem arises when we are calculating modulo inverse. Perhaps I misunderstood what you were trying to say or my thinking is wrong but so far I can’t understand why we can’t do the same thing when c is not prime.

4 Likes

Yes, but, as I’ve discussed with @junior94, the link which motivated me to add the last edition to my comment was this:

more especifically the third bullet point :slight_smile:

The 3rd bullet just helps in simplifying the multiplications invloved in the problem when we are calculating by hand. However as we are using computer to do our multiplication , we dont bother with the reductions as it will make the program more complex. we will need to add code to find gcd and then reduce it to the form shown there. Just not worth the extra trouble.

Thanks for the reply Mr. @kuruma

How exactly this code is working . I did not get it. Please explain your code for more explanation .Please

Hello again and I’m sorry for the added confusion with prime modulus and whatsnot…

Please read this link, of an older tutorial I had written precisely about this:

http://discuss.codechef.com/questions/20451/a-tutorial-on-fast-modulo-multiplication-exponential-squaring

1 Like

@kuruma could you edit the answer above and remove the prime number and gcd part? it might cause confusion.

Sure, will do it right now :slight_smile: