The constraints are small enough so I recommend pure brute force. Here is one thing to consider. If a number X=M*K+R (we are considering the divisibility on M and R is the remainder). So, if we multiply X with another X we will have X=M*M*K*K +2*R*m*K + R*R all the elements are divisible by M except for the last one which means that taking the remainder after calculating the power or in the process of calculating the power will not change the final answer. This is important because the numbers might too big to fit into integer type so you need to take a remainder after every step.
No comments:
Post a Comment