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 
Hello @theshubhamgoel,
Nothing is too cakewalk if we can actually do something about it 
ā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]: Exponentiation by squaring - Wikipedia
[2]: What's significant about the number choice 1000000007? - general - CodeChef Discuss
[3]: Chinese remainder theorem - Wikipedia
4 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
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
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! 
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
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:
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