Zenn
📑

ABC 165 | D - Floor Function

2020/11/04に公開
#
競プロ
tech

問題

https://atcoder.jp/contests/abc165/tasks/abc165_d

考えたこと

入力例1のとき以下のグラフになる。

上記よりBの赤い線と青い線の差分が一番大きくなるxはB-1のときである。xがB以上のときはインターバルで同じ繰り返しなので無視できる。
条件としてxはN以下なのでx=min(N, B-1)が答えである。

コード

実装時のTips

  • 整数の割り算なのでldを使う
#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll a, b, n;
  cin >> a >> b >> n;
  ll x = min(b - 1, n);
  ll r = floor((ld)a * x / b) - a * floor((ld)x / b);
  cout << r << endl;
}

参考

Discussion