\(V = \max(A_i,S_i)\) とします。 \(\gcd(S_i,A_1,A_2, \cdots , A_j)\) となる最小の \(j\) を求めたいです。この値は \(\gcd(S_i , \gcd(A_1,A_2, \cdots , A_j) )\) と同じなので \(O(N \log V)\) の前準備で \(g[j] = \gcd(A_1,A_2, \cdots , A_j)\) を \(1 \leq j \leq N\) について求めることでクエリを二分探索によって \(O( \log N \log V)\) で解くことができます。
よってこの問題は \(O((N+Q \log N) \log V)\) で解けました。