---
tags: AtCoder
---
# ABC165 D - Floor Function

## 問題
$x$ を $1$ から $N$ まで動かすとき、
$$\left\lfloor\frac{x}{B}\times A\right\rfloor - \left\lfloor\frac{x}{B}\right\rfloor\times A \tag{1}$$ の最大値を求めよ。

## 式変形

$\{x\}$ で $x$ の小数部分を表す。

$$\left\lfloor\frac{x}{B}\times A\right\rfloor = \frac{x}{B}\times A - \left\{\frac{x}{B}\times A\right\}$$
$$\left\lfloor\frac{x}{B}\right\rfloor\times A = \frac{x}{B}\times A - \left\{\frac{x}{B}\right\}\times A$$

より、 $(1)$ は、

$$\left\{\frac{x}{B}\right\}\times A - \left\{\frac{x}{B}\times A\right\}$$

分母が邪魔なので $B$ を掛ける

$$(x \bmod B)\times A - (x \times A \bmod B)$$

ここみえないがち 右側をぐっとにらむ

$$(x \bmod B)\times A - ((x \bmod B) \times A \bmod B)$$

$X = (x \bmod B)$ とおく

$$X\times A - (X \times A \bmod B)$$

これな〜んだ？　商だね

$$\left\lfloor\frac{X\times A}{B}\right\rfloor\times B$$

最後に $B$ を掛けた分を戻す

$$\left\lfloor\frac{X\times A}{B}\right\rfloor$$

## 完成

よって、 $A$, $B$ が定数であることに注意すると、 $X$ はなるべく大きくしたほうがいいことがわかった。

つまり、 $x = min(N, B - 1)$ とすればよい。