情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

yukicoder contest 218 D - 公平なりんご分配

D問題の解説です。

問題

No.854 公平なりんご分配 - yukicoder

問題文(要約)

問題文

Q個のクエリが与えられるので、各クエリについて\prod_{j=L_i}^{R_i} A_jP_iで割り切れるか判定してください。

制約

  • 1 \leq N, Q \leq 10^5
  • 0 \leq A_i \leq 2 \times 10^3
  • 1 \leq L_i \leq R_i \leq N
  • 1 \leq P_i \leq 10^9


この手の連続部分列のクエリ系問題は、累積和で高速にするのが有効ですよね!
ただ、このままだと逆元が無いので良い感じにクエリの判定ができないし、値をそのまま計算すると大きくなりすぎてしまいます……。
そこでP_i素因数分解すると、各素因数については単にその個数だけ素因数を含むか判定する問題になります。
これならば累積和上で個数は管理できるので、無事に解けました。

感想

まぁ典型よりですかね、これは普通に解かれる問題と思っていました。
実際に解かれている模様なので、こんなものかなと。