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 separately multiply one A. What about base case, i.e. if B==0 ? It should return 1%M.
(see code for further clarity.)
The only difference a modulus make here is every time you multiply you need to take modulus of multiplicands and the final product so that it does not go out of range of long long int.
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 separately multiply one A. What about base case, i.e. if B==0 ? It should return 1%M.
(see code for further clarity.)
The only difference a modulus make here is every time you multiply you need to take modulus of multiplicands and the final product so that it does not go out of range of long long int.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include<bits/stdc++.h> using namespace std; #define ll long long int ll mod_exponentiation(ll base, ll n, ll m){ if(base ==0 ) return 0; if( n==0) return 1%m; ll half = mod_exponentiation(base, n/2, m); if(n%2==0) return (half%m*half%m)%m; else return ((half%m*half%m)%m*(base%m))%m; } int main(){ ll b,p,m; while(cin>>b>>p>>m){ cout<<mod_exponentiation(b,p,m)<<endl; } } |
So I conclude here and recommend you to explore more about modular arithmetic.
See you next time.
By: hulk_baba
Comments
Post a Comment