Work out large powers quickly, with an optional modulus.
What to build
A recursive function with a default argument.
Requirements
- Write
long long power(long long base, int exp, long long mod = 0). - With a
modof 0, it returns the plain power. Otherwise it returns the result modulomod. - Use the halving method, not a simple loop.
Input
The first line has q. Each of the next q lines has b e, or b e m.
Output
One number per line.
Constraints
b is from 0 to 1000 and e from 0 to 1000000. Without a modulus, the result fits in a long long. m is from 1 to 1000000.
Example
Input:
2
2 10
3 0
Output:
1024
1
Why it works
Halving the exponent means that even an exponent of a million needs only about twenty steps, and taking the modulus at each step keeps the numbers small.
Examples
Example 1 · Input
2 2 10 3 0
Expected output
1024 1
Example 2 · Input
1 2 1000000 1000
Expected output
376
Hints
Hint 1
If exp is even, power(b, exp) is power(b, exp / 2) squared.
Hint 2
If it is odd, multiply by one more b.
Hint 3
Apply the modulus at each step when it is not 0.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
long long power(long long base, int exp, long long mod = 0) {
if (exp == 0) {
return mod ? 1 % mod : 1;
}
long long half = power(base, exp / 2, mod);
long long result = half * half;
if (mod) result %= mod;
if (exp % 2 == 1) {
result *= base;
if (mod) result %= mod;
}
return result;
}
int main() {
int q;
cin >> q;
cin.ignore();
for (int i = 0; i < q; i++) {
string line;
getline(cin, line);
istringstream in(line);
long long b, m;
int e;
in >> b >> e;
if (in >> m) cout << power(b, e, m) << endl;
else cout << power(b, e) << endl;
}
return 0;
}