H - Range Multiplication Query [Divisors ver.]

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

概要

愚直な方法では正解できません.
求めるべきことを明らかにして考えてみましょう.

問題原案:kusirakusira

解説

操作後の AA の要素は非常に大きくなりうるため,実際に操作を再現して答えを求めることは難しいです.
別なアプローチを考えてみましょう.

PiP_iii 番目に小さい素数とします.

整数 X=P1k1P2k2P3k3X = P_1^{k_1} \cdot P_2^{k_2} \cdot P_3^{k_3} \cdots の約数の個数は (k1+1)(k2+1)(k3+1)(k_1 + 1) (k_2 + 1) (k_3 + 1) \cdots と表されます.
XX のもつ ii 番目の素因数を 00 個以上 kik_i 個以下選ぶ組み合わせの総数です.

Ai=P1k1P2k2P3k3A_i = P_1^{k_1} \cdot P_2^{k_2} \cdot P_3^{k_3} \cdots の値を,ベクトル Ki=(k1,k2,k3,)K_i = (k_1, k_2, k_3, \ldots) として持つことを考えます.

すると,QQ 回の操作は各々次のように言い換えることができます:

  • xP1c1P2c2P3c3x \eqqcolon P_1^{c_1} \cdot P_2^{c_2} \cdot P_3^{c_3} \cdots とする.
  • lirl \leq i \leq r を満たす任意の整数 ii について:
    • KiK_iKi+(c1,c2,c3,)K_i + (c_1, c_2, c_3, \ldots) で置換する.

以上の操作はimos法を用いるなどして簡単に実装できます.

求めるべきは,E=(1,1,1,)E = (1, 1, 1, \ldots) として,Di=E(Ki+E))D_i = E \cdot (K_i + E)) です.

なお実際には Ai,x100A_i, x \leq 100 より各ベクトルの要素数は高々 2525 で十分と分かります.これは 100100 以下の素数の個数です.

解説:uni_kakurenbo

実装例

C++