[CSA] Round #2 Online Gcd
問題
https://csacademy.com/contest/beta-round-2/task/online_gcd/方針
ず初めに \( N \) 個の整数の配列を \( a \) とし、この配列の最大公約数を \( g \) とします。そのあとの \( M \) 回の操作は、整数 \( i, k \) が与えられ、配列の要素を
\[ a_i = \dfrac{a_i}{k} \]
として更新します。この時の配列 \( a \) の最大公約数を解答として出力します。
更新後の配列の最大公約数は、
\[ g = gcd(g, a_i)\]
となります。最大公約数の性質を利用して、更新後の配列の最大公約数を求めなくても、更新後の値とその前の最大公約数の二つの値を用いて最大公約数を計算するだけで済むというものですね。