解説

$A_1$ $, \ldots ,$ $A_N$ の最大公約数を $X$ とすると、 $X$ の約数の個数が答えになります。

$X$ の約数であれば、$X$ を割り切ることができるため、 $A$ の要素を全て割り切ることができます。
逆に、$X$ の約数でなければ、$A$ の要素に割り切れないものが含まれます。
($X$ の約数でない数が $A$ の要素を全て割り切るとすると、 $X$ が最大公約数であることに矛盾します。)

よって、$A$ の要素を全て割り切ることと、$X$ の約数であることは同値です。

計算量は、 $A_1$ $, \ldots ,$ $A_N$ の最大公約数 $X$ を求める部分で $O(N+\log A_{\max})$、$X$ の約数を数える部分で $O(\sqrt A_{\max})$
よって全体で $O(N+\sqrt A_{\max})$ です。