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.