まず、最後に残る数はすべて、\(A_1, A_2, A_3, \dots, A_N\) から \(1\) 個以上選んで最大公約数をとったものとして表せます。 (\(x, y\) がともにこのように表せるとき \(\min(x, y)\) も \(\gcd(x, y)\) もこのように表せるので)

また、\(\min(x, y)\) も \(\gcd(x, y)\) も \(\min(x, y)\) 以下なので最終的に残る数は \(\min{\{A\}}\) 以下という条件があります。

ではこの \(2\) 条件を満たすものは全て最後に残る可能性があるでしょうか ?
これは正しいです。以下に具体的な操作方法を書きます。

最後に残る数 \(r\) が \(A_{x_1}, A_{x_2}, A_{x_3}, \dots, A_{x_k}\) の最大公約数だとします。まず最初に \(A_{x_1}, A_{x_2}, A_{x_3}, \dots, A_{x_k}\) を全て \(\gcd\) でまとめます。
今黒板に書かれている数は \(r\) と、\(A\) の要素の一部です。\(r \le \min{\{A\}}\) だったので今ある数を全て \(\min\) でまとめれば \(r\) が残せます。

これを踏まえて、「\(A_1, A_2, A_3, \dots, A_N\) から \(1\) 個以上選んで最大公約数をとったものとして表せる」数を全て陽に求め、そのうち \(\min{\{A\}}\) 以下のものの数を数える方針を採ります。
ある \(x\) が 「\(A_1, A_2, A_3, \dots, A_N\) から \(1\) 個以上選んで最大公約数をとったものとして表せる」数であることと、「\(A\) の要素のうち \(x\) の倍数であるものが \(1\) 個以上存在し、それらの最大公約数が \(x\) に等しい」ことは同値です。
よって、以下のような手順で全て求めることができます。

• まず連想配列である \(t\) を用意する(最初 \(t\) は空である)
• すべての \(A_i\) について以下を行う
  • \(A_i\) の各約数 \(j\) について、\(t_j \leftarrow \gcd(t_j, A_i)\) とする。ただし、\(t_j\) が存在しないなら \(t_j \leftarrow A_i\) とする。
• \(t_j = j\) であるものが「\(A_1, A_2, A_3, \dots, A_N\) から \(1\) 個以上選んで最大公約数をとったものとして表せる」数である

計算量を考えます。
約数列挙は合計で \(O(N \sqrt{\max{\{A\}}})\) でできます。
\(n\) 以下の正整数の約数の個数の最大を \(d(n)\) とし、各操作が \(O(1)\) のハッシュマップ等を連想配列に使えば、連想配列の操作は\(O(N d(\max{\{A\}}))\)、\(\gcd\) の計算も \(O(N d(\max{\{A\}}) \log(\max{\{A\}}))\) です。

\(d(10^9) = 1344\) であることを考慮すれば間に合います。