ABC 368 F — Dividing Game

考察

A_iをproper divisorへ置き換える操作は、素因数分解に含まれる素因数を重複込みで一個以上取り除く操作と同値である。Ω(A_i)を素因数の総個数とすると、その山から任意の0..Ω−1へ移れるためGrundy数はΩ(A_i)になる。複数要素のgameはdisjoint sumである。指数和xの素因数multisetから任意のy<x個を残す約数を選べるので、遷移Grundy集合は{0,1,...,x−1}となりmexはxである。一手では一つのA_iだけを変更するため、独立heapのGrundy XORという通常Nimの合成条件を満たす。

採用する候補: 各A_iの重複込み素因数個数Ω(A_i)を求め、そのXORが非零かで勝者を判定する。

各数の約数gameが任意個数の石を取るNim heapと同型になり、Sprague-Grundy和を直接使える。

棄却する候補: 全約数を列挙して各値のGrundy数をmex DPする。

値ごとに遷移先約数を展開する必要はなく、操作が素因数個数だけで完全に特徴付けられる。

最大Aまでsmallest prime factorまたはΩ値をsieveで前計算し、各A_iを割りながら重複込み素因数数x_iを得る。全x_iのbitwise XORを取り、0ならBob、非0ならAnnaを出力する。

典型の発動条件

数論gameのNim同型化

発動条件: 整数を約数へ減らす操作が素因数multisetの削除として表せるとき。

素因数の総数をheap sizeとみなしGrundy数を決定する。

smallest-prime-factor sieve

発動条件: 多数の上限が小さい整数を重複込みで素因数分解するとき。

最小素因数表で割るたびΩを一つ増やす。

問題固有の要素

素因数の種類ではなく指数和だけが重要なのは、任意のproper divisorを選べて残す因子multisetを自由に決められるためである。

別の問題へ持ち帰る視点: divisor move gameでは指数vector全体のどの統計量へ任意に減らせるか調べる。

正当性

重複込み素因数数が x の整数からは任意の0..x−1個へ移れる。元の素因数多重集合から好きな個数を残す約数を選べるためである。帰納法でその Grundy 数は mex{0,..,x−1}=x。操作は一山にしか作用しないので全体 Grundy は各 x の xor。normal play では xor0が負け、非0が勝ちとなる。

実装上の注意

  • Ωはdistinct prime数でなく重複込み指数和とする。勝者名とnormal playでXOR=0が後手勝ちである対応を確認する。

復習の核

  • 12=2²·3をheap size3として、到達できるΩが0,1,2すべてあるか確認する。square-free因子数と混同しない。

計算量と制約

時間

N 山、最大値 V。最小素因数 sieve を O(V log log V) で作り、分解は O(N log V)。

空間

最小素因数表で O(V)、山入力を持つなら追加 O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^5; 2 \leq A_i \leq 10^5; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Dividing Game の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: ゲーム状態の勝敗とGrundy数

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: game状態・Grundy DP

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

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

    学習の位置

    体系上の位置: ゲーム状態の勝敗とGrundy数

    • 後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。

    先に読む単元:

    この解説で扱わないこと:

    • 有限DAGの得点差minimax、循環ゲームの距離評価、独立な数ゲームの加算。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題