BEN2のブログ

たまに書いています。

ABC 165 D - Floor Function

競技プログラミング

ABC 165 D - Floor Function についてのメモを残します。

周期 B の関数

\begin{aligned} f(x) = \left\lfloor \frac{Ax}{B} \right\rfloor - A \left\lfloor \frac{x}{B} \right\rfloor \end{aligned}

とする。 x が B の倍数のとき f(x) = 0 なので、 x = mB + n \, (0 \leq n \leq B-1) とすると、

\begin{aligned} f(mB+n) &= \left\lfloor \frac{A(mB+n)}{B} \right\rfloor - A \left\lfloor \frac{mB+n}{B} \right\rfloor \\ &= \left\lfloor Am + \frac{An}{B} \right\rfloor - A \left\lfloor m + \frac{n}{B} \right\rfloor \\ &= Am + \left\lfloor \frac{An}{B} \right\rfloor - Am \\ &= \left\lfloor \frac{An}{B} \right\rfloor \\ &= f(n) \end{aligned}

よって、 0 \leq x \leq B-1 についてのみ考えればよくて、
N \geq B-1 のとき、 f(x) の最大値は f(B-1)
N \lt B-1 のとき、 f(x) の最大値は f(N)

#include <bits/stdc++.h>
using namespace std;

int main() {
  long long A, B, N; cin >> A >> B >> N;
  if (N >= B-1) cout << A * (B-1) / B << endl;
  else cout << A * N / B << endl;
}