ABC 300 G — P-smooth number

考察

N≤10^16を整数ごとに調べることはできない。P≤100なので使える素数は25個以下だが、全smooth数を一つの列へ生成しても最大入力で約23億個になる。素数集合を二群へ分け、各側でN以下の素数冪積だけを列挙するmeet-in-the-middleを使う。

両リストは1から始める。素数を昇順に見て、現在のリスト長が小さい側へ追加する(同長なら第二側)。旧リストを固定し、その各値uについてu p,u p²,…≤Nを追加する。新しい素数なので全要素は重複しない。最大入力での実際の生成長は正当性節に示す通り、全smooth数より大幅に小さい。

両側をsortし、一方を昇順に走査する。他方の末尾を、v≤N/uになるまで下げ、その位置までの要素数を答えへ加える。配列を均衡化する目的はpair全探索ではなく、生成・sortの最大サイズを抑えることである。

典型の発動条件

meet-in-the-middle

発動条件: 独立な素因数選択の全積は大きいが二群なら列挙可能。

素数集合を分割して半側smooth数を生成する。

積制約pair counting

発動条件: sort済み正数列からuv≤Nを数える。

overflowを避けN/uで上限pointerを動かす。

問題固有の要素

分割品質を素数数でなく実際の生成listサイズでonline均衡化するのが最大ケースを抑える。

別の問題へ持ち帰る視点: MITMの群分けは状態数推定を重みにする。

正当性

二群の素数集合は重ならないため、素因数分解の一意性により、各P-smooth数は一方の素数の積uと他方の積vの組へ一意に分解される。各群内でも素数を追加する際、旧リストだけを各正の冪で増やすので重複生成しない。uv≤Nなら各因子もN以下なので、各リストをNで打ち切っても必要な組は残る。sort後、uが増えるとvの許容上限N/uは減るので、二ポインタで全組を一度数える。

小さい側へ次の素数を入れる方針は実用的な分割の工夫であり、それ自体は最悪リストサイズの証明ではない。実行時間は生成したリスト長U,Vに依存する。最大入力N=10^16,P=100で、素数を昇順に追加し、同長なら第二リストへ入れる規約を実際に計算するとU=4,141,074,V=2,903,751、総生成7,044,825個である。答えの2,345,134,674個を全生成する必要はなく、約56.4MBの64bit値配列とsortで扱える。

実装上の注意

  • 倍乗の前にu≤N/pで判定する。pair比較もu*vではなくv≤N/uにする。
  • 素数を追加する際は旧リストの長さを固定し、新しく追加した値から再び生成しない。
  • 約704万個は最終要素数であり、vectorを拡張するときの容量・一時コピーも空間に含める。片側の旧要素数だけを記録してin-placeで追加すれば別の全リストコピーは不要。

復習の核

  • 小Nのfactor全探索と比較し、P=2、N=1、P以下最大素数の冪境界を確認する。

計算量と制約

時間

O(U log U+V log V+P(U+V))、P以下primeを列挙し生成list最大長U,V、最後のpair走査O(U+V)。

空間

O(U+V+P)。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: N is an integer such that 1 \le N \le 10^{16}.; P is a prime such that 2 \le P \le 100.

出典

分類・前提・執筆情報

掲載状態: 収録済み

P-smooth number の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: meet-in-the-middle・半分全列挙

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

    主タグ: meet-in-the-middle・半分全列挙

    補助タグ: 尺取り法・sliding window

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

    学習の位置

    体系上の位置: meet-in-the-middle・半分全列挙

    • 探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題