GCD of Contiguous Subsequence

$2$整数におけるGCDは，結合律を満たします．また，多くの言語でGCDの単位元は $0$ とされており，整数集合におけるGCDはモノイドであると言えます．従って，セグメント木を用いて，指定区間のGCDは，$\mathrm{O}(\log (N) \log (A))$ で高速に計算可能です．

また，$G(l, r) = \gcd(A_l, A_{l+1}, A_{l+2}, \dots A_{r})$ とすると，$l$ を固定したとき，$G(l, r)$ は $r$ について明らかに広義単調減少です．
従って，数列$A$の区間における左端 $l$ を固定したとき，$G(l, r) \geq M$ を満たす最大の $r$ を $r_1$，$G(l, r) \gt M$ を満たす最大の $r$ を $r_2$ として，$r_1-r_2$ 個が $G(l, r) = M$ を満たします．
よって，$1$ 以上 $N$ 以下の $l$ について上の値を二分探索とセグメント木を用いて $\mathrm{O}(\log^2 (N) \times \log (A))$ で求めることができるため，全体の計算量は $\mathrm{O}(N \times \log^2 (N) \log (A))$ となりますが，セグメント木上で直接二分探索を行うことで，さらに計算量を $\mathrm{O}(N \times \log (N) \log (A))$ に落とすことができます．

コード例（C++）