わずかに工夫して計算量のオーダーの \(\log\) を \(1\) 個にします。

\(Z\) を \(A _ i\) の最大値制約 ( \(=10^6\) ) とします。

\(K = \sum _ {i=1} ^ Q K _ i\) （クエリで消える要素の個数の総和）とします。

\(Z\) 以下の整数について最小の素因数を求めておくことで、 \(A _ i\) の素因数分解は計算量 \(O( \log Z )\) でできます。

素数 \(p\) と正整数 \(e\) の組について、 \(p^e\) を約数にもつ要素の個数 \(f(p,e)\) を管理します。要素 \(1\) つの追加および削除について、素因数分解を用いて計算量 \(O( \log Z)\) で更新できます。

答えは \(f(p,e) \geq 1\) となる \((p,e)\) について \(p\) を掛け合わせたものです。 \(p\) の \(\bmod \ 998244353\) の逆元を前計算しておくことで、全体で計算量 \(O(Z \log \log Z+(N+K)\log Z)\) が達成されます。

解答例

線形篩を用いると、全体の計算量は \(O(Z+(N+K)\log Z)\) になります。