長方形領域における GCD を求める問題． 2次元の計算を 1次元に落とす． 気持ちとしては，和や差によって GCD が変わらないことを利用して， 左上を基準のマスとして，残りは差分で計算したい． 行と列の差分を別々に計算することで，計算量を減らす．
\(d = GCD\) とおく． \begin{align} d(a+b_{0}, a+b_{1}, a+b_{2}) &=& d(a+b_{0}, b_{1}-b_{0}, b_{2}-b_{1}) \\ \end{align} であることから， \begin{align} d_{i \in H,\,j \in W}(a_{i}+b_{j}) % &= d(a_{i}+b_{0}, b_{1}-b_{0}, b_{2}-b_{1}, \cdots , b_{W-1}-b_{W-2}) \\ &= d_{i \in H,\, j \in W-1} (a_{i}+b_{0}, b_{j+1}-b_{j}) \\ &= d_{i \in H-1,\, j \in W-1} (a_{0}+b_{0}, a_{i+1}-a_{i}, b_{j+1}-b_{j}) \\ \end{align} となる． つまり，左上のマスを基準として， 差分は行と列で独立して計算できる．
行と列について，区間 GCD は segtree で求めればよい．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,q;
cin >> n >> q;
vll a(n); rep(i,n) { cin >> a[i]; }
vll b(n); rep(i,n) { cin >> b[i]; }
rep(i,n-1){
sta.set(i, a[i+1]-a[i]);
}
rep(qi,q){
vll h(2), w(2);
cinv(h);
cinv(w);
h[0]--;
w[0]--;
ll d = 0;
d = GCD(d, a[h[0]] + b[w[0]]);
d = GCD(d, sta.prod(h[0], h[1]-1));
cout << d << endl;
}
return 0;
}
