格子点転置によるfloor_sum

概要

一次式の床和を格子点数とみなし、整数部分の取り出しと領域の転置でEuclid互除法型に再帰する。商一定区間の列挙とは異なり、傾きと法の交換が計算量を決める。

標準の床和F(n,m,a,b)=Σ_{i=0}^{n−1}floor((ai+b)/m)を、格子点数を保つ引数変換から導く。ABC443 Gは標準式の利用、ABC283 Exはbitごとの指示値への分解、ABC402 Gは床和の一般化を練習する問題である。以下では同じFを再利用する式を比較する。

定義: n≥0,m>0。a=qm+a′,b=rm+b′(0≤a′,b′<m)と分け、F=q·n(n−1)/2+rn+F(n,m,a′,b′)。負の係数でもfloor除算で非負剰余を取れば同じ式。

転置: 正規化後a>0としてy=floor((an+b)/m),c=(an+b) mod m。Fは0≤i<nかつ1≤j、mj≤ai+bの格子点数。iをn−1−iに反転し、jをy−tと書くと各t=0,…,y−1で許されるiの数はfloor((mt+c)/a)。従ってF(n,m,a,b)=F(y,a,m,c)。

終了と計算量: a=0なら正規化後の和は0。y=0でも0。転置後の法はa<mとなり、次の係数正規化でm mod aが現れる。Euclid互除法と同じ引数減少なので反復はO(log m)。

ABC283 Exでは対象列v=b+Miのbit kの指示値がfloor((v+2^k)/2^{k+1})−floor(v/2^{k+1})。この二つのFを計算し、bitごとの寄与を足す。

考え方

Σ_{0≤i<n} floor((ai+b)/m)を、aとbの商の寄与と剰余へ分ける。残る格子点領域の軸を交換するとEuclid型に引数が小さくなり、全iを走査せず和を求められる。

再帰式を反復へ落とす

累積ans=0から始める。n=0ならansを返す。各段でa=qm+a′、b=rm+b′をfloor除算で作り、ansへq·n(n−1)/2+rnを足し、a,bをa′,b′へ置き換える。これで「元の床和=ans+現在のF」という不変量を保つ。

a=0なら残り0で終了する。それ以外はz=an+bを旧引数で一度計算し、y=floor(z/m)、c=z mod mを得る。y=0なら終了、そうでなければ(n,m,a,b)を同時に(y,a,m,c)へ置き換える。格子点転置の等式が残りのFを保存し、次段の正規化でEuclidの余りが現れる。逐次代入で旧mや旧aを失わない。負のa,bでも最初のfloor正規化以降の剰余は非負になる。

成立条件と計算量

m>0、非負の標準形ではO(log m)段。負のa,bはfloor除算で正規化して寄与を分離する。三角数やa·nのoverflowを扱う。定義の半開区間を変えると端の一項が変わる。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。床和を格子点数へ写し、傾きと法の交換からEuclid型の再帰を導く。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-euclidean-floor-sum

格子点転置によるfloor_sum

習得する技能

  • Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。

前提と範囲

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

直接の前提単元: なし。

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

一次式の床和を格子点数とみなし、整数部分の取り出しと領域の転置でEuclid互除法型に再帰する。商一定区間の列挙とは異なり、傾きと法の交換が計算量を決める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • 格子点転置によるfloor_sumの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠