結果

問題 No.3398 Accuracy of Integer Division Approximate Function 2
コンテスト
ユーザー 👑 Mizar
提出日時 2026-02-06 20:57:02
言語 Rust
(1.93.0 + proconio + num + itertools)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 2,461 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 17,046 ms
コンパイル使用メモリ 215,932 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-02-06 20:57:38
合計ジャッジ時間 18,784 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

fn mwf_leq(
    t: &BigInt,
    l: &BigInt,
    r: &BigInt,
    mut m: BigInt,
    mut a: BigInt,
    mut b: BigInt,
    mut c: BigInt,
    mut d: BigInt,
) -> bool {
    assert!(l < r && m.is_positive());
    let qd0;
    (qd0, d) = (&c * l + &d).div_rem_euclid(&m);
    let mut n = r - l;
    let mut sum_acc = &a * l + &b * qd0 - t;
    if sum_acc.is_positive() {
        return false;
    }
    loop {
        let (qc, qd);
        (qc, c) = c.div_rem_euclid(&m);
        a += &b * qc;
        (qd, d) = d.div_rem_euclid(&m);
        sum_acc += &b * qd;
        if sum_acc.is_positive() {
            return false;
        }
        n -= 1;
        let y_max = (&c * &n + &d) / &m;
        if (&sum_acc + &a * &n + &b * &y_max).is_positive() {
            return false;
        }
        if y_max.is_zero()
            || (!a.is_negative() && !b.is_negative())
            || (!a.is_positive() && !b.is_positive())
        {
            return true;
        }
        if a.is_negative() {
            sum_acc += &a + &b;
        }
        d = &m - &d - 1;
        (n, m, a, b, c) = (y_max, c, b, a, m);
    }
}

fn compute_xmin(d: BigInt, a: BigInt, b: BigInt, k: BigInt) -> BigInt {
    let g = d.gcd(&a);
    let bk = &b * &k;
    let (m, r) = (&a * &b).div_rem(&d);
    if r.is_zero() && &d * &k + &g >= a {
        return BigInt::from(-1i64);
    }
    let mut lo: BigInt;
    let mut hi: BigInt;
    if r.is_zero() {
        lo = &k + 1;
        hi = &a / &g;
    } else {
        lo = (&a * &b * &k - (&a - &g) * &m) / &r + 1;
        lo = lo.max(&k + 1);
        hi = (&a * &b * &k) / &r + 2;
    }
    let negm = -&m;
    while &(&lo + 1) < &hi {
        let mid = (&lo + &hi) / 2;
        if mwf_leq(
            &bk,
            &lo,
            &mid,
            a.clone(),
            b.clone(),
            negm.clone(),
            d.clone(),
            BigInt::zero(),
        ) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    d * lo
}

fn solve() -> std::io::Result<()> {
    input! { t: usize }
    let mut bw = BufWriter::new(stdout().lock());
    for _ in 0..t {
        input! { d: BigInt, a: BigInt, b: BigInt, k: BigInt }
        let ans = compute_xmin(d, a, b, k);
        writeln!(&mut bw, "{}", ans)?;
    }
    bw.flush()?;
    Ok(())
}

fn main() {
    solve().unwrap();
}

use num::{BigInt, Integer, Signed, Zero, traits::Euclid};
use proconio::input;
use std::io::{BufWriter, Write, stdout};
0