弊社はエンジニアを熱烈募集しています． 以下から気軽にカジュアル面談申し込んでください． 就職・転職を考えている知人にも積極的に宣伝してください．
Spir | Smart scheduling calendar
この勉強会の宣伝もお願いします． 参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会 で実況や感想，質問を呟くなども．
以下の値を高速に求めるアルゴリズム。 $(a,b\geq 0, m,w> 0)$ （atcoder とは記号を変えてる）
$$ F(a,b,m,w)\coloneqq\sum_{x=0}^{w-1} \left\lfloor \dfrac{ax+b}{m} \right\rfloor $$
一次関数 $f(x)= \dfrac{ax+b}{m}$ について、 $0≤x < w$ の範囲で $f(x)$ の下にある格子点の数を数える問題と見ることが出来る。（式で書くと $|\{(x,y)\in\mathbb{Z}^2 \mid 0≤x<w, 1≤y≤f(x)\}|$ ）
点の個数を数える問題
ac-library に入っているので atcoder としては典型判定をしている？ 600 点前後の問題でそこそこ見る印象。
式通り計算すると $\Theta(w)$ 時間かかるが、工夫すると $O(\log \min\{a,m\})$ 時間で求められる。
数式を少しずつ変形する。
まず $a,b$ が $m$ 以上のときは $m$ で割った余りについて求めれば良いことを示す。
実際、$a = m\alpha + a', b = m\beta + b'$ とすると
$$ \begin{align*} F(a,b,m,w) &= \sum_{x=0}^{w-1} \left\lfloor \dfrac{(m\alpha + a')x+m\beta + b'}{m} \right\rfloor\\ &= \sum_{x=0}^{w-1}\left( \alpha x + \beta + \left\lfloor \dfrac{a'x+ b'}{m} \right\rfloor\right)\\ &= \left(\alpha \dfrac{w(w-1)}{2} + \beta w + \sum_{x=0}^{w-1}\left\lfloor \dfrac{a'x+ b'}{m} \right\rfloor\right)\\ &= \alpha \dfrac{w(w-1)}{2} + \beta w + F(a',b',m,w)\\ \end{align*} $$
したがって $a,b$ について $m$ で割った余りの問題に帰着されることがわかる。 以下では $0\leq a,b < m$ の場合のみ扱う。