CSES Solutions – Exponentiation
Your task is to efficiently calculate values a^b modulo 109+7. Note that in this task we assume that 00=1.
Examples:
Input: N = 3, queries[][] = {{3, 4}, {2, 8}, {123, 123}}
Output:
81
256
921450052
Explanation:
- The first query is (3 ^ 4) % (109 + 7) = (3 * 3 * 3 * 3) % (109 + 7) = 81
- The second query is (2 ^ 8) % (109 + 7) = (2 * 2 * 2 * 2 * 2 * 2 * 2 * 2) % (109 + 7) = 256
- The third query is (123 ^ 123) % (109 + 7) = 921450052
Input: N = 2, queries[][] = {{4, 3}, {5, 3}}
Output:
64
125
Explanation:
- The first query is (4 ^ 3) % (109 + 7) = (4 * 4 * 4) % (109 + 7) = 64
- The second query is (5 ^ 3) % (109 + 7) = (5 * 5 * 5) % (109 + 7) = 125
Approach: To solve the problem, follow the below idea:
The idea is to uses the concept of binary exponentiation to do this efficiently. If the exponent is even, it squares the result of the base raised to half the exponent. If the exponent is odd, it multiplies the base with the square of the result of the base raised to half the exponent. This is done recursively until t he base case is reached.
Step-by-step algorithm:
- Create a constant variable MOD with a value of 1000000007.
- Create a function calPow() function to calculate the power of a number with modulo.
- Use a recursive approach for efficient exponentiation.
- Handles base cases for exponent == 0 and exponent == 1.
- Calculates the power by dividing the exponent by 2 and squaring the result.
- If the exponent is odd, it adjusts the calculation accordingly by multiplying the base.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Define the modulo constant
const int MOD = 1000000007;
// Function to calculate the power of a number with modulo
ll calPow(ll base, ll exponent)
{
// Base case: any number to the power of 0 is 1
if (exponent == 0)
return 1;
// Base case: any number to the power of 1 is the number
// itself
if (exponent == 1)
return base % MOD;
ll temp = calPow(base, exponent / 2);
if (exponent % 2 == 0) {
// If the exponent is even, the power can be
// calculated by squaring the result of base to the
// power of half the exponent
return (temp * temp) % MOD;
}
else {
// If the exponent is odd, the power can be
// calculated by multiplying the base with the
// square of the result of base to the power of half
// the exponent
return (((temp * temp) % MOD) * base) % MOD;
}
}
int main()
{
ll N = 3;
vector<vector<ll> > queries
= { { 3, 4 }, { 2, 8 }, { 123, 123 } };
for (auto query : queries) {
// Calculate and print the result of base to the
// power of exponent modulo MOD
cout << calPow(query[0], query[1]) << "\n";
}
}
import java.util.ArrayList;
import java.util.List;
public class Main {
// Define the modulo constant
static final int MOD = 1000000007;
// Function to calculate the power of a number with modulo
static long calPow(long base, long exponent) {
// Base case: any number to the power of 0 is 1
if (exponent == 0) {
return 1;
}
// Base case: any number to the power of 1 is the number itself
if (exponent == 1) {
return base % MOD;
}
long temp = calPow(base, exponent / 2);
if (exponent % 2 == 0) {
// If the exponent is even, the power can be calculated by squaring the result
// of base to the power of half the exponent
return (temp * temp) % MOD;
} else {
// If the exponent is odd, the power can be calculated by multiplying the base
// with the square of the result of base to the power of half the exponent
return (((temp * temp) % MOD) * base) % MOD;
}
}
public static void main(String[] args) {
long N = 3;
List<List<Long>> queries = new ArrayList<>();
queries.add(List.of(3L, 4L));
queries.add(List.of(2L, 8L));
queries.add(List.of(123L, 123L));
for (List<Long> query : queries) {
// Calculate and print the result of base to the power of exponent modulo MOD
System.out.println(calPow(query.get(0), query.get(1)));
}
}
}
// This code is contributed by shivamgupta0987654321
# Define the modulo constant
MOD = 1000000007
# Function to calculate the power of a number with modulo
def cal_pow(base, exponent):
# Base case: any number to the power of 0 is 1
if exponent == 0:
return 1
# Base case: any number to the power of 1 is the number itself
if exponent == 1:
return base % MOD
# Recursively calculate the power
temp = cal_pow(base, exponent // 2)
if exponent % 2 == 0:
# If the exponent is even, the power can be calculated by squaring the result
# of base to the power of half the exponent
return (temp * temp) % MOD
else:
# If the exponent is odd, the power can be calculated by multiplying the base
# with the square of the result of base to the power of half the exponent
return (((temp * temp) % MOD) * base) % MOD
# Main function
def main():
N = 3
queries = [
[3, 4],
[2, 8],
[123, 123]
]
for query in queries:
# Calculate and print the result of base to the power of exponent modulo MOD
print(cal_pow(query[0], query[1]))
# Call the main function
if __name__ == "__main__":
main()
// Define the modulo constant
const MOD = 1000000007;
// Function to calculate the power of a number with modulo
function calPow(base, exponent) {
// Base case: any number to the power of 0 is 1
if (exponent === 0) {
return 1;
}
// Base case: any number to the power of 1 is the number itself
if (exponent === 1) {
return base % MOD;
}
// Calculate the result of base to the power of half the exponent
let temp = calPow(base, Math.floor(exponent / 2));
if (exponent % 2 === 0) {
// If the exponent is even, the power can be calculated by squaring the result
// of base to the power of half the exponent
return (temp * temp) % MOD;
} else {
// If the exponent is odd, the power can be calculated by multiplying the base
// with the square of the result of base to the power of half the exponent
return (((temp * temp) % MOD) * base) % MOD;
}
}
// Main function
function main() {
const N = 3;
const queries = [[3, 4], [2, 8], [123, 123]];
for (let query of queries) {
// Calculate and print the result of base to the power of exponent modulo MOD
console.log(calPow(query[0], query[1]));
}
}
// Call the main function
main();
// Note: JavaScript's fixed precision integers may encounter overflow issues with
//very large numbers.
Output
81 256 921450052
Time Complexity: O(N * log(M)), where N is the number of queries and M is the maximum value of exponent.
Auxiliary Space: O(1)
Contact Us