三浦ノート

自分の経験したことを検索可能にしていくブログ.誰かの役に立ってくれれば嬉しいです.

剰余の変域

問題

L ≦ x ≦ R な自然数 x に対して, 自然数 m を法とする剰余の値 y = x%m の変域は

if (R - L ≥ m) 0 ≦ y ≦ m - 1

else if ($\lfloor$L/m$\rfloor$ = $\lfloor$R/m$\rfloor$) L%m ≦ y ≦ R%m

else if ($\lfloor$L/m$\rfloor$ + 1 = $\lfloor$R/m$\rfloor$) 0 ≦ y ≦ R%m , L%m ≦ y ≦ m - 1

である.$\lfloor\cdot\rfloor$ は床関数(小数切り捨て操作)を表す.

説明

自然数 m を法とした剰余関数 y = x%m, (x : 自然数) のグラフを見れば自明.

参照

C - Remainder Minimization 2019