整数境界と同値区間を正確に分ける

概要

整数境界・同値区間分割

floor値・整数根・表記桁数・圧縮block内の式が変わる整数境界を正確に分け、区間ごとに処理する。

商q=floor(N/l)が一定の最大区間は[l,floor(N/q)]である。右端の次へ進めば、i≤√Nの部分と商≤√Nの部分を合わせてO(√N)個のblockだけを処理できる。三角数・整数根・桁数の境界も、式が変わる位置を整数演算で求める。

一次式の床和を格子点領域の転置で計算するfloor_sumは別の原理である。商一定区間の列挙と混ぜず、「格子点転置によるfloor_sum」の節で引数の減少と重み付き和への拡張を学ぶ。

考え方

floor(N/i)はiが増えると非増加で、同じ商qを持つ最後の位置はfloor(N/q)になる。値が一定のblockをまとめて数えると、巨大な整数範囲を直接列挙せず集計できる。

一次・二次のblockと交点を整数へ戻す

整数域[L,R]でax+b≥0を判定すると、a>0ならx≥ceil(−b/a)、a<0ならx≤floor(−b/a)。a=0は全成立か全不成立である。この切替位置とその次を境界へ入れ、全条件の境界をsort・uniqueすれば各半開区間内の真偽は一定となる。平方根・三角数の境界は候補kに対するk²≤Nやk(k+1)/2≤Nを整数で再確認して求める。

圧縮block内の値がf(x)=ax²+bx+cなら、最大・最小の候補は両端と頂点−b/(2a)のfloor・ceilを域内へ絞った点である。順位を探すなら頂点で単調な二区間へ分け、各区間の成立数を二分探索する。a=0は一次式として扱い、二次式が区間全体で単調とは仮定しない。

一次関数群のmin/max包絡では二本の差も一次式で、優劣は高々一回しか変わらない。各交点のfloor・ceilと前後の整数を候補境界へ含める。同傾きは常に優る切片だけを残す。境界間では選ばれる直線が一定なので、inclusiveな[L,R]の和は a·(L+R)(R−L+1)/2+b·(R−L+1)。素朴な全対交点ならO(直線数²)候補を使い、直線包絡の専用構造がある場合はその有効blockだけを使う。商のO(√N)評価を別の式へ流用しない。

成立条件と計算量

正のNでは相異なる商はO(√N)個。lからq=N/l、r=N/qを求めr+1へ進む。0除算、N=0、block長と元座標の重みを確認する。別の床式にはその式に合う境界を導く必要がある。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。床関数や整数根が変わる境界を厳密に求め、同じ値の区間をまとめる。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-integer-boundary-blocks

習得する技能

  • 圧縮block内の一次・二次式や操作列の累積境界を閉形式にし、極値・順位・個数を求められる。
  • 成立判定が変わり得る整数境界を全て列挙し、隣り合う境界の間で判定が一定であることを示して、代表点判定と区間長で整数解の個数を求められる。
  • floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。
  • 整数区間上の一次関数包絡を交点の前後で分け、各affine blockの値を等差数列和で合計できる。

前提と範囲

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

直接の前提単元: なし。

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

floorや整数根の値が変わる境界を正確に求め、同値な整数範囲をまとめて処理する。

このUnitでは扱わないもの

  • 素因数指数による整数条件の分解。

根拠