CSES Solutions – Exponentiation II
Your task is to efficiently calculate values a^(b^c) modulo 109+7.
Note that in this task we assume that 00 = 1.
Examples:
Input: N = 2, queries[][] = {{3, 7, 1}, {2, 3, 2}}
Output:
2187
512
Explanation:
- 3 ^ (7 ^ 1) mod 109+7 = 3 ^ 7 = 2187
- 2 ^ (3 ^ 2) mod 109+7 = 2 ^ 9 = 512
Input: N = 3, queries[][] = {{3, 7, 1}, {15, 2, 2}, {3, 4, 5}}
Output:
2187
50625
763327764
Approach: To solve the problem, follow the below idea:
We can efficiently calculates a^b % mod using the binary exponentiation by squaring technique.
For any positive integer b, a^b can be calculated more efficiently by dividing b by 2 and squaring the result.
- If b is even, a^b = (a^(b/2)) 2.
- If b is odd, a^b = a * (a^(b/2)) 2.
- handling base cases where b is 0 or 1.
Modular Inverse Calculation: We’ll use Fermat’s Little Theorem, it states that if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p). The modular inverse of a is a^(p-2) mod p.
Euler’s theorem: Since Euler theorem states that aN ≡ aNmodΦ(m) (mod M) so to calculate (a^(b^c)) modulo 109+7 we will calculate ((b ^ c) modulo 109 + 6). To get the final answer, we calculate (a ^ ((b ^ c) % 109+6)) % 109+7
Step-by-step algorithm:
- Calculate Modular Exponentiation:
- If the exponent is 0, it returns 1. If the exponent is 1, it returns the base modulo the given value.
- Recursively computes the result by dividing the exponent by 2 and squaring the result until the exponent is reduced to 0 or 1.
- If the exponent is even, it squares the result. If the exponent is odd, it multiplies the result by the base after squaring.
- Calculate (b ^ c) % (109+6) using modular exponentiation and store it in a variable, say power_bc.
- Calculate (a ^ power_bc) % (109+7) using modular exponentiation and return it as the final answer.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD = 1000000007;
// Function to calculate power with modulo
ll powerWithModulo(ll base, ll exponent, int mod)
{
if (exponent == 0)
return 1;
if (exponent == 1)
return base % mod;
// Recursive approach for exponentiation by squaring
ll temp = powerWithModulo(base, exponent / 2, mod);
if (exponent % 2 == 0)
// If exponent is even, square the result
return (temp * temp) % mod;
else
// If exponent is odd, multiply by base after
// squaring
return (((temp * temp) % mod) * base) % mod;
}
// Function to calculate modular inverse using Fermat's
// Little Theorem
ll calculateInverse(ll base, int mod)
{
// Using Fermat's Little Theorem: a^(p-2) mod p
return powerWithModulo(base, mod - 2, mod);
}
int main()
{
ll N = 3;
vector<vector<ll> > queries
= { { 3, 7, 1 }, { 15, 2, 2 }, { 3, 4, 5 } };
for (int i = 0; i < N; i++) {
ll a = queries[i][0], b = queries[i][1],
c = queries[i][2];
// Calculate b^c modulo MOD-1
ll power_bc = powerWithModulo(b, c, MOD - 1);
// Calculate a^(b^c) modulo MOD
ll result = powerWithModulo(a, power_bc, MOD);
// Print the result for the current calculation
cout << result << "\n";
}
return 0;
}
import java.util.*;
public class Main {
static final int MOD = 1000000007;
// Function to calculate power with the modulo
static long GFG(long base, long exponent, int mod) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base % mod;
// Recursive approach for the exponentiation by squaring
long temp = GFG(base, exponent / 2, mod);
if (exponent % 2 == 0)
// If exponent is even
// square the result
return (temp * temp) % mod;
else
// If exponent is odd
// multiply by base after squaring
return (((temp * temp) % mod) * base) % mod;
}
// Function to calculate modular inverse using the Fermat's Little Theorem
static long calculateInverse(long base, int mod) {
return GFG(base, mod - 2, mod);
}
public static void main(String[] args) {
int N = 3;
List<List<Long>> queries = Arrays.asList(
Arrays.asList(3L, 7L, 1L),
Arrays.asList(15L, 2L, 2L),
Arrays.asList(3L, 4L, 5L)
);
for (int i = 0; i < N; i++) {
long a = queries.get(i).get(0);
long b = queries.get(i).get(1);
long c = queries.get(i).get(2);
// Calculate b^c modulo MOD-1
long power_bc = GFG(b, c, MOD - 1);
// Calculate a^(b^c) modulo MOD
long result = GFG(a, power_bc, MOD);
// Print the result for current calculation
System.out.println(result);
}
}
}
MOD = 10**9 + 7
# Function to calculate power with modulo
def powerWithModulo(base, exponent, mod):
if exponent == 0:
return 1
if exponent == 1:
return base % mod
# Recursive approach for exponentiation by squaring
temp = powerWithModulo(base, exponent // 2, mod)
if exponent % 2 == 0:
# If exponent is even, square the result
return (temp * temp) % mod
else:
# If exponent is odd, multiply by base after squaring
return (((temp * temp) % mod) * base) % mod
# Function to calculate modular inverse using Fermat's Little Theorem
def calculateInverse(base, mod):
# Using Fermat's Little Theorem: a^(p-2) mod p
return powerWithModulo(base, mod - 2, mod)
if __name__ == "__main__":
N = 3
queries = [[3, 7, 1], [15, 2, 2], [3, 4, 5]]
for query in queries:
a, b, c = query
# Calculate b^c modulo MOD-1
power_bc = powerWithModulo(b, c, MOD - 1)
# Calculate a^(b^c) modulo MOD
result = powerWithModulo(a, power_bc, MOD)
# Print the result for the current calculation
print(result)
const MOD = BigInt(10**9 + 7);
// Function to calculate power with modulo
function powerWithModulo(base, exponent, mod) {
if (exponent === 0n) {
return 1n;
}
if (exponent === 1n) {
return base % mod;
}
// Recursive approach for exponentiation by squaring
let temp = powerWithModulo(base, exponent / 2n, mod);
if (exponent % 2n === 0n) {
// If exponent is even, square the result
return (temp * temp) % mod;
} else {
// If exponent is odd, multiply by base after squaring
return (((temp * temp) % mod) * base) % mod;
}
}
// Function to calculate modular inverse using Fermat's Little Theorem
function calculateInverse(base, mod) {
// Using Fermat's Little Theorem: a^(p-2) mod p
return powerWithModulo(base, mod - 2n, mod);
}
// Main function
function main() {
const N = 3;
const queries = [[3, 7, 1], [15, 2, 2], [3, 4, 5]];
for (let query of queries) {
let [a, b, c] = query;
// Calculate b^c modulo MOD-1
let power_bc = powerWithModulo(BigInt(b), BigInt(c), MOD - 1n);
// Calculate a^(b^c) modulo MOD
let result = powerWithModulo(BigInt(a), power_bc, MOD);
// Print the result for the current calculation
console.log(result.toString());
}
}
// Run the main function
main();
Output
2187 50625 763327764
Time complexity: O(N * log(exponent)), where N is the number of queries.
Auxiliary Space: O(N * log(exponent))
Contact Us