結果

問題 No.3398 Accuracy of Integer Division Approximate Function 2
コンテスト
ユーザー hos.lyric
提出日時 2025-12-05 18:52:25
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 3,213 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,188 ms
コンパイル使用メモリ 170,304 KB
実行使用メモリ 11,172 KB
最終ジャッジ日時 2025-12-05 18:52:39
合計ジャッジ時間 8,807 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// same problem as yesterday...

import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }

string COLOR(string s = "") { return "\x1b[" ~ s ~ "m"; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


alias T = Tuple!(BigInt, "sum", BigInt, "mx");

enum ZERO = BigInt(0);
enum INF = BigInt(10)^^100;
enum T IDEN = T(ZERO, -INF);

T mul(T a, T b) {
  return T(a.sum + b.sum, max(a.mx, a.sum + b.mx));
}
T pow(T a, BigInt e) {
  return (e == 0) ? IDEN : T(e * a.sum, (a.sum > 0) ? ((e - 1) * a.sum + a.mx) : a.mx);
}

// y^f(0) x y^(f(1)-f(0)) x y^(f(2)-f(1)) x ... x y^(f(n)-f(n-1))
//   where f(i) = floor((a i + b) / m)
T pathUnder(BigInt m, BigInt a, BigInt b, BigInt n, T e, T x, T y) {
  assert(m >= 1); assert(a >= 0); assert(b >= 0); assert(n >= 0);
  BigInt c = (a * n + b) / m;
  T pre = e, suf = e;
  for (; ; ) {
    const p = a / m; a %= m; x = x.mul(y.pow(p));
    const q = b / m; b %= m; pre = pre.mul(y.pow(q));
    c -= (p * n + q);
    if (c == 0) return pre.mul(x.pow(n)).mul(suf);
    const d = (m * c - b - 1) / a + 1;
    suf = y.mul(x.pow(n - d)).mul(suf);
    b = m - b - 1 + a; swap(m, a); n = c - 1; c = d; swap(x, y);
  }
}

void main() {
  try {
    for (; ; ) {
      const numCases = readInt;
      foreach (caseId; 0 .. numCases) {
        const BigInt D = readToken;
        const BigInt A = readToken;
        const BigInt B = readToken;
        const BigInt K = readToken;
        
        /*
          [x/D] - (P/Q) [x/A] > K
          update when D | x
        */
        const P = A * B / D;
        const Q = B;
        
        // x/D \in [0, n)
        bool check(BigInt n) {
          const res = pathUnder(A, D, ZERO, n, IDEN, T(Q, ZERO), T(-P, -INF));
          return (res.mx > Q * K);
        }
        
        BigInt ans = -1;
        BigInt lo = 0, hi = A * D;
        if (A * B % D != 0) {
          for (; !check(hi); lo = hi, hi <<= 1) {}
        } else {
          if (!check(hi)) goto failed;
        }
        for (; lo + 1 < hi; ) {
          const mid = (lo + hi) / 2;
          (check(mid) ? hi : lo) = mid;
        }
        ans = lo;
        ans *= D;
       failed:
        writeln(ans);
      }
    }
  } catch (EOFException e) {
  }
}
0