Contest Duration: - (local time) (100 minutes) Back to Home

## B - MAX-=min Editorial by evima

It takes too much time to simulate the procedure naively.

An important fact is that $$\mathrm{gcd}(x,y) = \mathrm{gcd}(x,y-x)$$ holds for $$x$$ and $$y$$ such that $$0 \leq x \leq y$$.

From this, we can show that $$\mathrm{gcd}(a)$$ does not change during the procedure. Thus, we just need to find $$\mathrm{gcd}(a)$$, which can be done fast enough in $$O(N + \log(\max A_i))$$ time using Euclidian Algorithm.

posted:
last update: