ABC 238 G — Cubic?

考察

区間積が立方数であることは、区間内の各素数 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

出典

分類・前提・執筆情報

掲載状態: 収録済み

Cubic? の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 乱択代数fingerprint

主題
  • 乱択代数fingerprint: multiset・素因数指数vector・巨大整数式をランダムな体元やXOR和へ写し、非同値対象が衝突する確率を評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 乱択代数fingerprint

    補助タグ: 素因数・約数分解

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 乱択代数fingerprint

    • multiset・素因数指数vector・巨大整数式をランダムな体元やXOR和へ写し、非同値対象が衝突する確率を評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題