解説


の最大公約数を とすると、 の約数の個数が答えになります。

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

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

計算量は、 の最大公約数 を求める部分で の約数を数える部分で
よって全体で です。