Min_25・Lucy DP型の総和篩

概要

素数和を定数個のLucy DPで求められる乗法的関数について、floor(N/i)の商集合上で素数冪を逆順に追加する簡略版Min_25でprefix sumを求める。素数冪の評価がO(1)なら、O(N^(3/4)/log N)時間・O(√N)空間。

考え方

乗法的関数fは、互いに素なa,bについてf(ab)=f(a)f(b)を満たす。f(1)=1とし、素数冪f(p^e)を計算できる場合に Σ_{m≤N}f(m) を求める。まず商の表で素数上の和を求め、次に最小素因数で合成数を一意に分類する。

素数計数からLucy DPを作る

状態集合を V={floor(N/i):1≤i≤N} とする。相異なる値はO(√N)個で、√N以下の全整数も含まれる。floor(v/p) もVに含まれるので更新先を共有できる。値の索引は、小さいvならv、大きいvならfloor(N/v)で二配列に分けられる。

最初は S(v)=v-1 とし、1を除いた2,…,vを数える。素数pを昇順に処理する直前のSは「処理済みの素数そのものと、まだその素数を因子に持たない整数」の個数とする。pで新たに除くのはp自身ではなく、最小素因数pの合成数である。

p²≤vの状態だけ、S(v)←S(v)-S(floor(v/p))+S(p-1) と更新する。除く数はp·mで、m≥pかつmにp未満の素因数がない。S(v/p)から既存の小さい素数S(p-1)を引けば、そのmだけが残る。v<p²では対象の合成数が存在しない。

vは降順に更新する。v/p<vなので右辺のS(v/p)は同じpを処理する前の値であり、不変量が保たれる。pは通常の篩で√Nまで求めてもよく、S(p)>S(p-1) を素数の判定にしてもよい。最後のS(v)はπ(v)となる。

f(p)の形に合わせて素数和を作る

f(p^e)を評価できるだけでは、この段を高速化できるとは限らない。例えば f(p)=Σ_{r=0}^d α_r p^r(定数d)なら、各rについて S_r(v)=Σ_{m=2}^v m^r から始め、S_r(v)←S_r(v)-p^r(S_r(floor(v/p))-S_r(p-1)) と同じ順で篩う。m^rが完全乗法的なので、除く重み(p·m)^rがp^r m^rと分離できる。初期の冪和をO(1)で求められれば、最後に P(v)=Σ_r α_r S_r(v)=Σ_{p≤v}f(p) を得る。

定数個の剰余類などでf(p)が分かれる場合は、その分類を状態に追加し、掛け算で分類がどう移るかを更新へ反映する。任意の素数値を与えるブラックボックスに、同じ篩の上界を適用してはいけない。

素数冪と残りを再帰する

素数をp_1<p_2<…とし、F(v,j) を「2≤m≤vかつ最小素因数がp_j以上であるmのf(m)の和」とする。素数だけの寄与は P(v)-Σ_{i<j}f(p_i)。直前までの素数prefix和をB_jとし、v<p_jならF(v,j)=0とする。実装で√Nまでの素数しか持たない場合も、合成数項に使うp_iだけを列挙し、v≤p_{j-1} なら0、それ以外なら素数単独の寄与を P(v)-B_j とする(p_0=1)。√Nより大きい素数を明示的に列挙する必要はない。

合成数は最小素因数p_i(i≥j)とその指数eを固定し、m=p_i^e·r、r=1または最小素因数r>p_iへ一意に分ける。よって

F(v,j)=P(v)-Σ_{i<j}f(p_i)+Σ_{i≥j, p_i²≤v} Σ_{e≥1, p_i^e≤v} f(p_i^e)(F(floor(v/p_i^e),i+1)+[e≥2])。

角括弧は条件が真なら1。r≥2の寄与はFで、r=1の純粋な素数冪はe≥2のときだけ追加する。e=1,r=1の素数は先頭のPで既に数えている。この分類で素数冪の重複と合成数の欠落を防ぐ。v<p_j²なら合成数項はなく、素数和だけを返せる。答えは 1+F(N,1)。小さいNや合成数を作れる素数がない範囲では直接素数和だけで終了する。

再帰を商の表へ共有して簡略版Min_25を実行する

上の再帰を各呼出しで展開する代わりに、素数を降順に戻す表として計算する。最初は全v∈Vについて T(v)=P(v)。素数pを処理する直前のTは「全素数と、最小素因数がpより大きい合成数」のfの和を持つ。

各v≥p²を降順に走査し、p^{e+1}≤vとなるe=1,2,…について

T(v) += f(p^e)(T(floor(v/p^e))-P(p)) + f(p^{e+1})

とする。第一項は、ちょうどp^eを含み、残りrがpより大きい素因数だけを持つr>1の数を追加する。第二項は純粋な素数冪p^{e+1}を追加する。rの範囲にp以下の全素数が含まれるので、固定した素数prefix P(p)を引ける。p^{e+1}>vとなったら停止する。

vの降順により右辺の小さい状態はpを戻す前の値で、pを二重に因子として使わない。pも降順に処理するので、残りrの許す最小素因数という条件が保たれる。全素数を戻した後の 1+T(N) が求める総和である。Tだけを商ごとに共有し、Pは変更せず保存する。

成立条件と計算量

Lucy DPの更新回数を数える。p≤N^{1/4}では一素数につきO(√N)状態、素数はO(N^{1/4}/log N)個なのでO(N^{3/4}/log N)。p>N^{1/4}ではv≥p²の商はO(N/p²)個で、素数上の和 Σ_p N/p² もO(N^{3/4}/log N)となる。定数dなら素数和の時間はこの上界、空間O(√N)である。

逆向きの表ではe=1の更新回数がLucy DPと同じ。e≥2では、p≤N^{1/6}の部分をO(√N·log N·π(N^{1/6}))=O(N^{2/3})で抑えられる。p>N^{1/6}では、対応する商の個数はO(N/p^{e+1})で、eを合計してO(N/p³)、pも合計してO(N^{2/3})になる。したがってf(p^e)をO(1)で評価できる場合、逆向きの表もO(N^{3/4}/log N)時間・O(√N)空間。二段階全体にこの上界を付けられる。

素数冪の再帰式は分類の正しさを理解するための形で、上記の時間・空間の保証は商の表を降順更新して共有する簡略版に対するもの。Min_25本来のN^{2/3}級の評価には追加の篩・再帰の整理が必要で、この更新式へその上界を付けない。二段階の具体的な利用はABC370 G公式解説でも確認できる。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 赤色(2800以上)。商の異なる値を状態とする篩を構築し、乗法的関数の総和を高速に計算する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 数論。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-min25-sieve

Min_25・Lucy DP型の総和篩

習得する技能

  • 素数和を定数個のLucy DPで求められる乗法的関数について、floor(N/i)の商集合上で素数冪を逆順に追加する簡略版Min_25でprefix sumを求める。素数冪の評価がO(1)なら、O(N^(3/4)/log N)時間・O(√N)空間。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 素因数分解と約数構造。

このUnitを直接前提とする単元: なし。

素因数・約数分解で得た考え方と実装を再利用し、Min_25・Lucy DP型の総和篩の発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • Min_25・Lucy DP型の総和篩の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠