Range Prod GCD

$A$の制約が $1 \leq A_i \leq 10^2$（$1 \leq i \leq N$） と小さいことに注目します．$10^2$以下の素数は$25$個であるため，$A_i$を素因数分解した結果には，高々$25$個の素数しか現れないことがわかります．
従って，それらを掛け合わせた値 $\displaystyle \prod_{w_i \leq k \leq x_i}A_k$ と $\displaystyle \prod_{y_i \leq k \leq z_i}A_k$ も当然高々$25$個の素数のみを使った掛け算で表せます．
$2$つの自然数のGCDは，それぞれに含まれる素因数について，指数の最小値乗を掛け合わせたものであるため，それら$25$個の素数が $\displaystyle \prod_{w_i \leq k \leq x_i}A_k$ と $\displaystyle \prod_{y_i \leq k \leq z_i}A_k$ にそれぞれ何回掛けられているかが分かれば最大公約数を求めることができます．

これは，数列$A$について，$25$個の素数それぞれの指数における累積和を持って置くことで高速に計算することが可能です．

実装にもよりますが，高速な素因数分解法を用いることで計算量は$\mathrm{O}((Q+N) \times \log(A))$となります．

コード例（Python）