Raising a number to a huge power one multiplication at a time is too slow. Halve the exponent at each step instead.
What to build
A program that computes B to the power E modulo M with recursion, and counts the calls.
Requirements
- Write a recursive
static long power(long b, long e, long m)as described in the hints, working modulo m at every step. - For each line print
B^E mod M = R (C calls), where C is the number of calls to power for that line.
Input
Line 1: n. Then n lines B E M.
Output
n lines.
Constraints
1 ≤ n ≤ 50; 0 ≤ B ≤ 10^9; 0 ≤ E ≤ 10^18; 1 ≤ M ≤ 10^9.
Example
Input:
2
2 10 1000
3 0 7
Output:
2^10 mod 1000 = 24 (5 calls)
3^0 mod 7 = 1 (1 calls)
Why it works
Each call halves the exponent, so 10^18 needs only about 61 calls instead of 10^18 multiplications, and taking the remainder after every product keeps each value below 10^18, inside a long.
Examples
Example 1 · Input
2 2 10 1000 3 0 7
Expected output
2^10 mod 1000 = 24 (5 calls) 3^0 mod 7 = 1 (1 calls)
Example 2 · Input
1 5 3 13
Expected output
5^3 mod 13 = 8 (3 calls)
Hints
Hint 1
power(b, e, m): if e is 0 return 1 % m; otherwise compute half = power(b, e / 2, m), square it, and multiply by b once more when e is odd.
Hint 2
Count calls in a static field that the method adds 1 to each time it starts.
Solution
Show one correct solution (try it yourself first)
import java.util.Scanner;
public class Main {
static int calls = 0;
static long power(long b, long e, long m) {
calls++;
if (e == 0) return 1 % m;
long half = power(b, e / 2, m);
long result = half * half % m;
if (e % 2 == 1) result = result * (b % m) % m;
return result;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int i = 0; i < n; i++) {
long b = in.nextLong(), e = in.nextLong(), m = in.nextLong();
calls = 0;
long r = power(b, e, m);
System.out.println(b + "^" + e + " mod " + m + " = " + r + " (" + calls + " calls)");
}
}
}