How to write a program in c++ to find the power of x ^ y, where y = 2 ^ k? To avoid overflow for large numbers (10^18 and larger) the program should give modulo 10^9+7 in return. I will be grateful for your help.
#include <iostream>
usingnamespace std;
unsignedlonglong pow2k( unsignedlonglong x, unsigned k, unsigned M )
{
unsignedlonglong ans = x % M;
for ( int i = 1; i <= k; i++ ) ans = ( ans * ans ) % M;
return ans;
}
int main()
{
constunsigned M = 1000000007;
unsigned x = 3, k = 4; // check case where modulo is irrelevant
cout << x << "^(2^" << k << ") (mod " << M << ") = " << pow2k( x, k, M ) << '\n';
x = 10; // check case where modulo is important
cout << x << "^(2^" << k << ") (mod " << M << ") = " << pow2k( x, k, M ) << '\n';
cout << 10000000000000000ull % M;
}
If the numbers are huge, you'll need to use a mathematical C++ library or a different language that supports large numbers, like Python.
You can also program your own way to handle large numbers. This can be done by having an array of 1 byte numbers holding the number, or even just a regular string holding the values. Then you code a way to do operations on them.