格子点転置によるfloor_sum
一次式の床和を格子点数とみなし、整数部分の取り出しと領域の転置でEuclid互除法型に再帰する。商一定区間の列挙とは異なり、傾きと法の交換が計算量を決める。
この典型を扱う単元: 格子点転置によるfloor_sum
検索別名: Euclid型床和、floor_sum、格子点転置
未知問からこの典型を見つける手掛かり
- 扱う対象
- affine floor sum
- 格子点領域
- 使う手掛かり
- 一次式の床の総和
- 巨大な整数区間
- 保つ不変量
- Euclid型の引数減少
- 格子点数保存
- 求めるもの
- 対数時間の床和
- 重み付き床和
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 数論構造への変換
関連する典型
- 整数境界・同値区間分割: 商が一定の区間を列挙するO(√N)の分割と、床和の格子点領域を転置して法を減らすO(log m)の再帰を区別する。
学習成果と学習単位
Σ floor((ai+b)/m)を整数部分の取り出しと格子点領域の転置で再帰し、Euclid型の引数減少からO(log m)を示せる。
格子点転置によるfloor_sumで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC283 Ex「Popcount Sum」 公式問題主題: 格子点転置によるfloor_sum / 主タグ
- ABC313 G「Redistribution of Piles」 公式問題主題: 同値な状態を正規化する / 補助タグ
- ABC372 G「Ax + By < C」 公式問題主題: Convex Hull Trick・直線包絡 / 補助タグ
- ABC402 G「Sum of Prod of Mod of Linear」 公式問題主題: 格子点転置によるfloor_sum / 主タグ
- ABC443 G「Another Mod of Linear Problem」 公式問題主題: 格子点転置によるfloor_sum / 主タグ