Problem link : contest practice
Difficulty : Easy-Medium
Pre-requisites : Modular Arithmetic
Problem : Find the maximal K that M^{k} 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(N^{2}) 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 X^{N} N times gives us N!.
Now our problem transforms to the following one: find the largest possible K that M^{K} divides (M^{R}-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 M^{R}-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 M^{2}, 2M^{2}, 3M^{2}, and so on.
- …
- F(i) >= R-2 for i equal to M^{R-2}, 2M^{R-2}, …, (M^{2}-1)M^{R-2}. M^{2}M^{R-2} is not suitable here because it’s greater that M^{R}-1. So, there are only M^{2}-1 such numbers.
- F(i) >= R-1 for i equal to M^{R-1}, 2M^{R-1}, …, (M-1)M^{R-1}. So, there are only M-1 such numbers.
Using the results above, we can reduce the problem to the following: calculate M + M^{2} + … + M^{R-1} - R and this will be the answer to the problem. M + M^{2} + … + M^{R-1} is a sum of a geometric progression and it equals to M^{R} 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.