前処理として、\(A\) の全ての要素を素因数分解します。そして、全ての素数 \(p\) に対し、「\(A_i\) が \(p\) を素因数に持つ \(i\) に対する \(\lbrace A_i\) の \(p\) で割り切れる回数\(,i \rbrace\) を降順にソートした配列」を持ちます。

\(K_i = X\) の時に、クエリを \(\mathrm{O}(X\log A)\) で解くことができれば十分です。

与えられた index に対する \(A_i\) の素因数としてあり得るものを列挙します。そして、列挙した素数 \(p\) に対して用意した配列を上から見ていき、与えられた index 以外の index が出てきたら見るのをやめます。このようにすることで \(N-X\) 個の最小公倍数の \(p\) で割り切れる回数を求めることができます。

上記のステップの計算量は、与えられた index に対する \(A_i\) の素因数の個数で抑えられます。

上記より、本問題を \(\mathrm{O}((N\log \max A+\max A+Q)\log \max A )\) で解くことができます。