Skip to main content

Posts

Showing posts with the label UVA 374

Modular Exponentiation

Just wanted to introduce you to very basic concept of Modular Exponentiation through a problem,  Big Mod . We need to calculate A^B % M for large inputs. For a second let's forget about A^B  % M and think about A^B only and say A^B lies within the range of long long int and B is less than 10^7. A basic brute force approach to calculate A^B will be to loop through 1 to B and multiply A every time. The time complexity of this approach is O(n). This is perfect on current constraints but what happens if I change the constraint on B and raise it to 10^12 or so. Now  this approach will give a TLE. An efficient approach is needed. O(n) is not sufficient. We will use a recursive approach for this. Suppose I want to calculate A^B but if B is even, I can calculate A^(B/2) and multiply it to itself, and the way to calculate A^(B/2) is to calculate A^(B/4) and so on you get the idea. But what if B is not even, no problem,  B-1 will be even do the same except replace B with B-1 and separ