A - Max Mod Min Editorial by evima
[1] Naive simulation
One can solve this problem by simulating the process as follows.
- Search for an integer $i$ such that $A_i=\min(\{A_1,A_2,\dots,A_k\})$ in $\mathrm{O}(N)$ time.
- Search for an integer $j$ such that $A_j=\max(\{A_1,A_2,\dots,A_k\}),i \neq j$ in $\mathrm{O}(N)$ time.
- Set $A_j$ to $(A_j \bmod A_i)$. If $A_j$ becomes $0$, delete it.
Instead of actually deleting an element, one can replace it with a special value such as \(-1\), which takes \(\mathrm{O}(1)\) time.
This solution takes \(\mathrm{O}(NX)\) time, where \(X\) is the answer. Since each operation decreases the length of \(A\) by at most \(1\), we have \(X \ge N\), so it will run out of time.
[2] Analyzing $X$
To analyze the value \(X\), consider the number of times a certain element gets chosen as \(A_j\) in the simulation above. When \(A_j\) is chosen, \(A_j\) becomes less than half since \(\frac{A_j}{2} \ge (A_j \bmod A_i)\).
Proof
Assume that $\frac{X}{2} < X \bmod Y$ holds for positive integers $X$ and $Y$ $(X \ge Y)$. Let $Z = X \bmod Y$. From $\frac{X}{2} < Z$, we have $X < 2Z$. However, from $X \ge Y$, we have $Z < (X-Z)$ because otherwise one could further subtract a multiple of $Y$ from $Z$. Thus, we have $X < 2Z$ and $2Z < X$, a contradiction.Therefore, each element in \(A\) gets chosen as \(A_j\) at most \(\mathrm{O}(\log \max A)\) times, so \(X\) is \(\mathrm{O}(N \log \max A)\).
[3] Optimizing the simulation
First, let us sort \(A\) so that \(A_1 \le A_2 \le \dots \le A_N\). Then, let us repeat the following.
- Take out $A_k$ from $A$, where $k$ is the current length of $A$.
- If $(A_k \bmod A_1) > 0$, insert $(A_k \bmod A_i)$ at the beginning of $A$.
- Otherwise, do nothing.
One can see that \(A_1 \le A_2 \le \dots \le A_k\) always holds during the process of this simulation.
One can perform all operations above in \(\mathrm{O}(1)\) time by using a double-ended queue.
Therefore, the problem can be solved in \(\mathrm{O}(X+N\log N)\) time.
posted:
last update: