Loading...
Loading...
Loading...
A message is forwarded so that the number of copies is multiplied by a every hour. After b hours there are a^b copies, a huge number, so print only its remainder when divided by m.
b can be as large as 10^18, so multiplying b times is far too slow. Write a recursive method static long powerMod(long a, long b, long m) that halves b on every call. Take a^0 as 1, even for a = 0.
Example 1
Input
2 10 1000
Output
24
2^10 = 1024, and 1024 mod 1000 = 24.
Example 2
Input
3 0 7
Output
1
Anything to the power 0 is 1.
Try the problem first. Open one hint at a time.
a^b = (a^(b/2))² when b is even, and a × (a^(b/2))² when b is odd (integer division).
Compute half = powerMod(a, b / 2, m) once and square it; calling it twice brings back the slow version.
Take % m after every multiplication. Every value stays below m ≤ 10^9, so a product stays below 10^18 and fits in a long.
Base case: b = 0 returns 1 % m (so m = 1 gives 0).
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor