# yukicoder No.2882 Comeback

$O(\sqrt{B})$ 解法．

## 問題

https://yukicoder.me/problems/no/2882

> 正整数 $A,B\ (A<B)$ が与えられる．$A\bmod m\geq B\bmod m$ となる正整数 $m$ の個数を求めよ．

## 解答

剰余を $\%$ で表す．

$-(m-1)\leq A\%m-B\%m\leq m-1$ より
$$-1<\frac{A\%m-B\%m}{m}<1$$

なので以下が成り立つ．
$$\begin{array}{c}
\left\lfloor\frac{A\%m-B\%m}{m}\right\rfloor\in\{-1,0\},\\
\left\lfloor\frac{A\%m-B\%m}{m}\right\rfloor=0\iff
A\%m\geq B\%m.
\end{array}$$

よって求める値は次に一致する．
$$B+\sum_{1\leq m\leq B}\left\lfloor\frac{A\%m-B\%m}{m}\right\rfloor$$

ここで $A\%m=A-\lfloor A/m\rfloor m$ と $m$ が正整数であることを用いれば
$$\begin{align*}
\left\lfloor\frac{A\%m-B\%m}{m}\right\rfloor
&=\left\lfloor\frac{A-B}{m}\right\rfloor-\left\lfloor\frac{A}{m}\right\rfloor+\left\lfloor\frac{B}{m}\right\rfloor\\
&=-\left(1+\left\lfloor\frac{B-A-1}{m}\right\rfloor\right)-\left\lfloor\frac{A}{m}\right\rfloor+\left\lfloor\frac{B}{m}\right\rfloor
\end{align*}$$

であるので次の問題に帰着される．

- 正整数 $N$ に対し $\sum_{k=1}^{N}\lfloor N/k\rfloor$ を求めよ．

$\lfloor N/k\rfloor$ の取り得る値の種類数が $O(\sqrt{N})$ であることを用いればこれは $O(\sqrt{N})$ で計算できる．

よって元の問題は $O(\sqrt{B})$ で解ける．