考察
区間積が立方数であることは、区間内の各素数 p の指数合計が全て 3 の倍数であることと同値である。
素数ごとの指数 mod 3 ベクトルを全 prefix に保存すると次元とメモリが大きいが、ゼロベクトルかどうかだけなら乱択 fingerprint に圧縮できる。
棄却する候補: 各素数について指数の累積和を持ち、クエリごとに全素数の指数差が 3 の倍数か調べる。
10 の 6 乗以下の素数と N 個の prefix の積を保存・走査できず、Q=20 万にも対応できない。
採用する候補: 各素数 p に独立な 64 bit 値 a_p,b_p を与え、p の出現へ a_p,b_p,a_p XOR b_p を周期的に割り当て、要素ごとの XOR 累積 hash を作る。
各素数pの出現回数を配列全体で管理すると、三個分のXORは0となり、prefix内の指数の剰余0,1,2はそれぞれ0,a_p,a_p XOR b_pに符号化される。指数mod 3をそのままXORするのではなく、各prefixの状態を乱数で表すのがポイントである。
区間積が立方数かは、両端prefixの全素数の位相が一致するかで決まる。区間hash=prefixHash[R] XOR prefixHash[L−1]が0かを調べれば、各queryをO(1)で判定できる。
典型の発動条件
素因数指数 mod k の乱択 fingerprint
発動条件: 積が完全 k 乗かを多数区間で判定したいが、全素数の指数ベクトルを明示できないとき。
同じ素数の k 個分が打ち消し合う乱数表現を与え、全素数の状態を固定長 hash へ圧縮する。
XOR 累積 hash
発動条件: 要素ごとの可換な XOR fingerprint があり、静的区間の fingerprint を高速に取得したいとき。
prefix XOR を構築し、左右 prefix の XOR 差で区間値を得る。
問題固有の要素
素因数 p の出現番号は配列全体で左から数え、三周期の割当を継続することで、任意の切り出し区間でも三個分の XOR が相殺する。
別の問題へ持ち帰る視点: 区間で個数 mod k を判定する周期 hash は、各要素内ではなく全 prefix を通じた出現位相を管理する。
正当性
立方数の区間では全素数の両端位相が同じなので、指紋は必ず一致する。非立方数なら、ある素数pのa_p,b_pの少なくとも一方が両端の差に奇数回現れる。他の乱数を固定しても独立一様な64 bit値が一つ残るので、誤一致の確率は2^(-64)である。乱数と独立に与えられるQ個のquery全体では、いずれかを誤判定する確率はQ/2^64以下となる。誤りは非立方数を立方数と判定する方向だけに起こる。
実装上の注意
- 最小素因数表などで A_i を分解し、同じ素数の重複指数も一回ずつ出現として hash に反映する。
- 符号なし 64 bit 整数で XOR を行い、素数ごとの a_p,b_p を独立性の高い乱数生成器から用意する。
復習の核
- 完全 k 乗判定は積そのものを扱わず、各素因数の指数を mod k でゼロ判定する問題へ移す。
- 高次元状態を hash へ圧縮する解法では、真のケースが必ず通ることと偽陽性の確率上界を分けて確認する。
計算量と制約
時間
O(V log log V+N log V+Q)、Vは値上限、SPF factorizationとprefix hash。
空間
O(V+N)。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: All values in input are integers.; 1 \le N,Q \le 2 \times 10^5; 1 \le A_i \le 10^6; 1 \le L_i \le R_i \le N
出典