ABC238 G - Cubic? - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の数列 ${A}$ が与えられる．以下の ${Q}$ 個のクエリを処理せよ．

${L_i,R_i}$ が与えられる． ${A_{L_i}×A_{L_i+1}×...×A_{R_i}}$ は立方数か答えよ．

${1\leq N,Q\leq 2×10^5\\ 1\leq A_i\leq 10^6\\ 1\leq L_i\leq R_i\leq N}$

解説

この問題はMo's algorithmを用いて解くことができます．

${A_{L_i}×A_{L_i+1}×...×A_{R_i}}$ が立方数であるということは， ${A_{L_i}×A_{L_i+1}×...×A_{R_i}}$ を素因数分解したときのすべての指数が ${3}$ の倍数であるということです．
各素数が何回かけられたか、という情報を管理しながらMo's Algorithmを行います． ${A_i}$ を掛ける場合， ${A_i}$ を素因数分解し，各素因数の個数を足します．各数の素因数分解はエラトステネスの篩などを用いて前計算すれば， ${O(\log{A_i})}$ で求められます．ただし，更新には素因数の種類分の時間しかかからないので， ${10^6}$ 以下の数に関しては高々 ${7}$ 個であるため十分高速に動きます．計算量は ${O(N\sqrt{Q}\log{A})}$ です．(※極端なケースだとTLEするかもしれません)