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

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

AtCoder ABC 165 D - Floor Function (2Q, 茶色, 400 点)

AtCoder AtCoder400点 ABC-D 数学(整数問題) 気付き系 周期性に着目する 単調性に着目する 実験 茶色diff NoviSteps2Q

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

問題へのリンク

問題概要

正の整数 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;
}