概要

floor sum は以下の値を求めるアルゴリズムである。

$$ \displaystyle f(N, M, A, B) = \sum_{k=0}^{N-1}\left\lfloor \frac{Ak + B}{M}\right\rfloor $$

制約

• $N$ は $0$ 以上の整数
• $M$ は正の整数
• $A, B$ は整数

ACL に入ってる。計算量は $O(\log M)$ である。

導出

• 導出を文字起こししたもの

主客転倒の部分を図にすると以下のようになる。

導出に使う考え方

ベースとなる考え方はあまりを取って主客転倒する。

すると、ユークリッドの互除法のノリで $A$ と $M$ の値がどんどん考える値が小さくなる。

あまりを取って主客転倒して辻褄が合うように導出しようとしたら自動的に導出される。なんかいい感じにピースがハマる感じ

細かいテクニックは以下の通り

• 寄与・主客転倒 double counting
  • 自然数 $a$ に対して $a = \#[0, a) = \sum_{i=0}^{A-1} \mathbb{1}[i < a]$ と変形して、主客転倒の準備をする
    • $a = \sum_{i=0}^{A=1} i \cdot 1[i=a]$ とする方法もあるが、$a$ が床関数の場合は不等号の方が扱いやすい。