I'm new to Python, and I'm trying to solve a programming problem where I have to compute 5 to the nth power, and once I have that, I just have to output the last two digits of that number. This is the code I wrote below:
print(str(pow(5, int(input())))[-2:])
The code works fine, for the most part, but exceeds the 500 ms time limit when the input is a large number like 1000000000000000000
What is the most efficient way to process such large inputs like this as an exponent without exceeding the time limit?
CodePudding user response：
It can be shown by induction that 5^n mod 100 = 25, for all n >= 2. This is clear when n = 2. Suppose 5^n is of the form 100k 25. Then 5^(n 1) = 100(5k 1) 25, whence 5^(n 1) mod 100 = 25. Hence, the last two digits of 5^n is 25, for all n >= 2.
Some general tricks for computing a^n mod b efficiently include repeated squaring for computing a^n, and computing remainders in each step so that the numbers stay small.
CodePudding user response：
For these kinds of heavy calculations you can use Multi Processing to use CPU cores to break down the calculation to little calculation simultaneously. For example (dummy example) we know 5^4 equals to 625. So we can use 2 cores of CPU to calculate 5^2, then multiply the result. 5^2 * 5^2 = 625.