けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 165 D - Floor Function (400 点)

気づけば一発系。ただし、数式の見た目がエグく見えてしまうかもしれない...

問題へのリンク

問題概要

正の整数  A, B, N が与えられる。 0 以上  N 以下の整数  x に対する

  •  \lfloor \frac{Ax}{B} \rfloor -  A \times \lfloor \frac{x}{B} \rfloor

の値の最大値を求めよ。

制約

  •  1 \le A \le 10^{6}
  •  1 \le B, N \le 10^{12}

考えたこと

全探索すれば  O(N) だけど、それでは間に合わない。さて、式の見た目がエグくてエグくてやばい。ちょっと思うことは

  • もし「小数点以下切り捨て」とかなくて実数演算だったら、 \frac{Ax}{B} -  \frac{Ax}{B} = 0 で常に 0 になるなぁ...

というくらいだろうか。よって、なんとなく、この値が大きくなるためには、後半の  \lfloor \frac{x}{B} \rfloor のところが、でかい小数点を抱え落ちすると良さそうという気持ちになる。たとえば  \lfloor \frac{19}{10} \rfloor = \lfloor 1.9 \rfloor = 1 という具合だ。

手を動かす

しかし、依然としてよくわからないので、こういうのはいくつかの具体例的に手を動かして、試してみると良さそう。

試しにサンプル 1 に従って、 A = 5 B = 7 について考えてみる。そして  x = 0, 1, 2, \dots に対して値がどのように変わるのかを眺めるのだ。

 x  \lfloor \frac{Ax}{B} \rfloor  A \times \lfloor \frac{x}{B} \rfloor
0 0 0 0
1 0 0 0
2 1 0 1
3 2 0 2
4 2 0 2
5 3 0 3
6 4 0 4
7 5 5 0
8 5 5 0
9 6 5 1
10 7 5 2
11 7 5 2
12 8 5 3
13 9 5 4

とりあえず気づくことは、

  •  A \times \lfloor \frac{x}{B} \rfloor は、周期  B (= 7) で、 A (= 5) だけ増える

ということだ。そしてよくみるとそれは  \lfloor \frac{Ax}{B} \rfloor の方も一緒だ。つまり、

 f(x) = \lfloor \frac{Ax}{B} \rfloor - A \times \lfloor \frac{x}{B} \rfloor

の値は、 B ごとに周期的になっているということだ!!!よって、 x の値としては

  •  x = 0, 1, 2, \dots, B-1

を試せば十分ということがわかる。それだけではない。


 x = 0, 1, \dots, B-1 の範囲で

  •  \lfloor \frac{Ax}{B} \rfloor は単調増加だが
  •  \lfloor \frac{x}{B} \rfloor の値は不変
  • したがって、 \lfloor \frac{Ax}{B} \rfloor - A \times \lfloor \frac{x}{B} \rfloor は単調増加

ということもいえる。よって、

  •  x = 0, 1, \dots, B-1
  •  x \le N

を満たす最大の  x が最適になる。つまり  x = \min(N, B-1) に対する値を求めれば良い。計算量は  O(1)

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

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