WIP：約数の個数の話

従ってクエリ3で与えられる $x$ の最大値を $M$，$M$ 以下の素数の個数を $C$ とすると，$C$ 個の素数それぞれの指数についての区間変更/区間加算/区間和取得ができればよく，これは遅延セグメント木を用いれば実装できます．

クエリ1,2では $x$ を素因数分解して $C$ 回区間変更/区間加算を行えばよく，計算量は $O(\log x+C\log N)$ です．

クエリ3では各素因数ごとの指数の和から答えが計算でき，計算量は $O(C\log N)$ です．

本問題の制約下では $C\leq 25$ なので，以上を実装すればこの問題は解けます．

メモ

• サンプル案
• 24/4/1：3/20 24 12/5/3 1 3 3/2 1 2 2/3 1 1 4/1 2 3 49/3 2 2 5
• 20240401：ランダムに回せば作れる？→できた，$61\times 137\times 213\times 243\times 577$ とか
• $Q\leq 3\times10^4$ くらいでないと遅い言語が通らなさそう？かわりに $A_i\leq 10^{18}$ にする
• ↑ TL 4s, PyPy3 でランダムケースは通ったので OK，$O(C\sqrt{N})$ とかでも通るけど仕方ない