Loading...
Loading...
Loading...
A security tool needs a raised to the power b, but only the remainder when divided by m, with b as large as 10^18. Write the repeated-squaring loop yourself.
Example 1
Input
2 10 1000
Output
24
1024 mod 1000 = 24.
Example 2
Input
3 0 7
Output
1
Try the problem first. Open one hint at a time.
Read b in binary: for each 1 bit multiply the answer by the current power.
Square the base and halve b each time, taking the remainder after every multiplication.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor