Loading...
Loading...
Loading...
Aditya's cryptography club makes a secret key from three numbers a, b and m. The key is a multiplied by itself b times, and then the remainder when divided by m.
b can be as large as 10^18, so multiplying one step at a time is far too slow. Print a^b mod m. By the usual rule, a^0 = 1 for every a, including 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
Any number to the power 0 is 1.
Try the problem first. Open one hint at a time.
If you know x = a^(b/2), then a^b is x × x when b is even.
When b is odd, a^b is x × x × a, because b/2 rounds down.
Take the remainder mod m after every multiplication, so no product grows past about 10^18.
The base case is b = 0, where the answer is 1 mod m (not just 1, because m can be 1).
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor