tests/math/quotient/arc150-b.test.cpp

• View this file on GitHub
• Last update: 2025-03-03 00:33:48+09:00
• Problem: https://atcoder.jp/contests/arc150/tasks/arc150_b

Depends on

• 商列挙 (library/math/quotient.hpp)

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#include "../../../cpp/library/math/quotient.hpp"
#define PROBLEM "https://atcoder.jp/contests/arc150/tasks/arc150_b"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    ll a, b;
    cin >> a >> b;
    auto res = asalib::math::floor_quotient(b - 1);
    ll ans = 1e18;
    if (b % a == 0) ans = 0;
    for (auto [bdivk, k, _] : res) {
      ll x = max(0LL, bdivk + 1 - a);
      ll y = k * x + k * a - b;
      if (x >= 0 && y >= 0) ans = min(ans, x + y);
    }
    cout << ans << '\n';
  }
  return 0;
}

#line 1 "tests/math/quotient/arc150-b.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#line 2 "library/math/quotient.hpp"

#include <concepts>
#line 6 "library/math/quotient.hpp"
using namespace std;

namespace asalib {
  namespace math {
    template<integral T>
    constexpr vector<tuple<T, T, T>> floor_quotient(T n) {
      vector<tuple<T, T, T>> res;
      for (T i = 1; i <= n; ++i) {
        T v = n / i;
        res.push_back({ v, i, n / v });
        i = n / v;
      }
      return res;
    }

    template<integral T>
    constexpr vector<tuple<T, T, T>> ceil_quotient(T n) {
      vector<tuple<T, T, T>> res;
      for (T i = 1; i <= n; ++i) {
        T v = (n + i - 1) / i;
        if (i == n) {
          assert(v == 1);
          res.push_back({ v, i, i });
        }
        else {
          assert(v > 1);
          T j = (n + v - 2) / (v - 1) - 1;
          res.push_back({ v, i, j });
          i = j;
        }
      }
      return res;
    }
  }  // namespace math
}  // namespace asalib
#line 8 "tests/math/quotient/arc150-b.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/arc150/tasks/arc150_b"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    ll a, b;
    cin >> a >> b;
    auto res = asalib::math::floor_quotient(b - 1);
    ll ans = 1e18;
    if (b % a == 0) ans = 0;
    for (auto [bdivk, k, _] : res) {
      ll x = max(0LL, bdivk + 1 - a);
      ll y = k * x + k * a - b;
      if (x >= 0 && y >= 0) ans = min(ans, x + y);
    }
    cout << ans << '\n';
  }
  return 0;
}

Back to top page