Problem link : contest practice
Difficulty : Easy-Medium
Pre-requisites : Modular Arithmetic
Problem : Find the maximal K that Mk divides an integer, obtained by the rules described in the problem statement.
Explanation :
At first, we can note that if we need the N-th number of the resulting list after N steps, then we can just create an initial list with the size of 2N and imitate the whole process. The complexity of this solution is O(N2) and it will not give us any points. Still, it is recommended to do that, because it can give us a very useful observation. And this will be a good start.
After the simplest solution is written, we can get solutions for the first, say, 20, values of N - namely, 1, 2, 3, …, 20. Having them written out somewhere, it’s quite easy to see: the N-th number of the resulting list is simply N!, i.e 1 * 2 * 3 * … * N. We can justify this result by the fact that each list is actually a differentiation of the previous one. Differentiating XN N times gives us N!.
Now our problem transforms to the following one: find the largest possible K that MK divides (MR-1)!.
Since M is a prime, we can say that K = sum of F(i) over integer i from 1 to N i.e. to MR-1, where F(i) is a number of times that i can be disided by M without residue. After looking at the sequence F(i) we see the following:
- F(i) = 0 if i is less than M
- F(i) >= 1 for i equal to M, 2M, 3M, and so on.
- F(i) >= 2 for i equal to M2, 2M2, 3M2, and so on.
- …
- F(i) >= R-2 for i equal to MR-2, 2MR-2, …, (M2-1)MR-2. M2MR-2 is not suitable here because it’s greater that MR-1. So, there are only M2-1 such numbers.
- F(i) >= R-1 for i equal to MR-1, 2MR-1, …, (M-1)MR-1. So, there are only M-1 such numbers.
Using the results above, we can reduce the problem to the following: calculate M + M2 + … + MR-1 - R and this will be the answer to the problem. M + M2 + … + MR-1 is a sum of a geometric progression and it equals to MR divided by M-1. Here we can use modulo inverse in order to make a division in a residue field since M is a prime number.