モノグサプログラミングコンテスト2022 (ABC238) G - Cubic? (600)
コンテスト中の考察
3つで消し合うので全ての素因数について先頭からの個数を持とうとしたが明らかに入らない
解説の方法
ある素数に対して乱数$ a,bを用意する
その素数が登場する度に順に$ a,b,a \oplus bと見做す
各素数について登場した回数をカウントしておく
4つで消える問題なら連番の4つの数?
それぞれの$ A_iについて乱数で置換した$ B_iを考える
先頭からの累積XORを求めておく
クエリは指定した範囲のXORが0になっているかどうかが答え