Розбір
Problem Author: | Pavlo Tsitsei |
Editorial by: | Pavlo Tsitsei |
Firstly, let's assume, that we have only operation choose some , replace by (in fact, this operation is enough). Also, let's use it on each element as long, as it is at least . Then, each element will be in range from 0 to . After this operations, it is enough to look if all elements are equal. Here is proof:
Let's look at two elements ( and ) and their difference (). When we make some operation on elements ( or ), we change value of difference () by . So, if they could possibly be equal after some number of operation, then difference should be divisible by . In our array, where each element from 0 to , maximum difference is , so we can make two elements equal, only if they are already.