概要

$\displaystyle \sum_{i=0}^{n-1}\left\lfloor \frac{ai + b}{m}\right\rfloor$を求めてください。

制約

• $0 \leq n$
• $1 \leq m$
• $0 \leq a,b \leq m$

ユークリッドの互除法のノリで計算できる。ACL に入っている。

計算量は $O(\log m)$？

使い方

• 直線 $y = (ax + b)/m$ より下にある格子点の数

  https://x.com/Kiwamu_Watanabe/status/1812304183409950782

解説

• AtCoder Library Practice Contest C - Floor Sum 解説
  • 寄与と床関数・天井関数を使う
    • 寄与: $\displaystyle \sum_{i=0}^{N-1} A_i = \sum_{k=1}^{\max A} \#\{i \mid A_i \geq k\}$
      • 参考: 寄与・主客転倒
    • 床関数・天井関数
      • $-\lceil x\rceil= \lfloor -x \rfloor$
      • $\lfloor \cdot \rfloor$ や $\lceil \cdot \rceil$ は単調
      • 参考: 床関数と天井関数
    • その他
      • $i \geq k$ となる $i \in [n]$ の数は $n - k$ 個