問題文中の手続きを愚直にシミュレーションすると、非常に時間がかかってしまいます。

重要な事実として整数 \(0 \leq x \leq y\) なる \(x,y\) について \(\mathrm{gcd}(x,y) = \mathrm{gcd}(x,y-x)\) が成り立ちます。

ここから手続きの過程で \(\mathrm{gcd}(a)\) が変化しないことが示せます。よって、\(\mathrm{gcd}(a)\) を求めればよく、これはユークリッドの互除法により \(O(N + \log(\max A_i))\) で十分高速に求めることができます。