結果

問題 No.3398 Accuracy of Integer Division Approximate Function 2
コンテスト
ユーザー NyaanNyaan
提出日時 2025-12-05 07:51:15
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,916 ms / 2,000 ms
コード長 3,148 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,314 ms
コンパイル使用メモリ 435,492 KB
実行使用メモリ 18,048 KB
最終ジャッジ日時 2025-12-05 09:10:55
合計ジャッジ時間 20,421 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 翻訳元：https://yukicoder.me/submissions/1138660
// translated by ChatGPT 5.1

#include <bits/stdc++.h>

#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;
using Int = cpp_int;

// sum_{i=0}^{n-1} floor((a*i + b) / m)
Int floor_sum(Int n, Int m, Int a, Int b) {
  Int ans = 0;

  if (a < 0) {
    Int a2 = a % m + ((a % m) < 0 ? m : 0);
    Int cnt = n * (n - 1) / 2;
    ans -= cnt * ((a2 - a) / m);
    a = a2;
  }
  if (b < 0) {
    Int b2 = b % m + ((b % m) < 0 ? m : 0);
    ans -= n * ((b2 - b) / m);
    b = b2;
  }
  if (a >= m) {
    Int cnt = (n - 1) * n / 2;
    ans += cnt * (a / m);
    a %= m;
  }
  if (b >= m) {
    ans += n * (b / m);
    b %= m;
  }

  Int y_max = (a * n + b) / m;
  Int x_max = y_max * m - b;
  if (y_max == 0) return ans;

  ans += (n - (x_max + a - 1) / a) * y_max;
  ans += floor_sum(y_max, a, m, (a - x_max % a) % a);
  return ans;
}

// sum_{i=nL}^{nR-1} floor((a*i + b) / m)
Int fs(Int nL, Int nR, Int m, Int a, Int b) {
  if(nL == nR) return Int{0};
  static map<tuple<Int, Int, Int, Int>, Int> mp;
  auto get = [&](Int N, Int M, Int A, Int B) -> Int {
    if (N == 0) return 0;
    if (mp.count({N, M, A, B})) return mp[{N, M, A, B}];
    return mp[{N, M, A, B}] = floor_sum(N, M, A, B);
  };
  return get(nR, m, a, b) - get(nL, m, a, b);
}

Int between(Int N, Int a1, Int b1, Int m1, Int a2, Int b2, Int m2) {
  auto on = [&](const Int& x) -> bool {
    // (a1*x + b1)/m1 > (a2*x + b2)/m2
    return (a1 * x + b1) * m2 > (a2 * x + b2) * m1;
  };

  Int nL = 0, nR = N;

  // 左側: on(x) が最初に true になる点
  if (!on(nL)) {
    Int ng = nL, ok = nR;
    while (ng + 1 < ok) {
      Int x = (ng + ok) / 2;
      if (on(x))
        ok = x;
      else
        ng = x;
    }
    nL = ok;
  }

  // 右側: on(x) が最後に true になる点
  if (!on(nR)) {
    Int ok = nL, ng = nR;
    while (ok + 1 < ng) {
      Int x = (ok + ng) / 2;
      if (on(x))
        ok = x;
      else
        ng = x;
    }
    nR = ng;
  }

  return fs(nL, nR, m1, a1, b1) - fs(nL, nR, m2, a2, b2);
}

Int calc(Int D, Int A, Int B, Int K) {
  K += 1;
  Int C = A * B / D;
  if (C == 0) return K * D;

  struct Line {
    Int a, b, m;
  };

  Line L1{D, 0, A};
  Line L2{D, -A, A};
  Line L3{B, B * (-K + 1) - 1, C};
  Line L4{B, -B * K - 1, C};

  // INF = 10^50
  Int INF = 1;
  for (int i = 0; i < 38; i++) INF *= 10;

  Int ng = 0, ok = INF;
  while (ng + 1 < ok) {
    Int N = (ng + ok) / 2;

    Int n1 = between(N + 1, L1.a, L1.b, L1.m, L4.a, L4.b, L4.m);
    Int n2 = between(N + 1, L1.a, L1.b, L1.m, L3.a, L3.b, L3.m);
    Int n3 = between(N + 1, L2.a, L2.b, L2.m, L4.a, L4.b, L4.m);
    Int n4 = between(N + 1, L2.a, L2.b, L2.m, L3.a, L3.b, L3.m);

    Int num = n1 - n2 - n3 + n4;
    if (num > 0)
      ok = N;
    else
      ng = N;
  }

  if (ok == INF) return Int(-1);
  return ok * D;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t = 1;
  if (!(cin >> t)) return 0;
  while (t--) {
    Int D, A, B, K;
    cin >> D >> A >> B >> K;
    Int ans = calc(D, A, B, K);
    cout << ans << '\n';
  }
  return 0;
}
0