結果

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

ソースコード

diff #
raw source code 

fn mwf(
    l: &BigInt,
    r: &BigInt,
    mut m: BigInt,
    mut a: BigInt,
    mut b: BigInt,
    mut c: BigInt,
    mut d: BigInt,
) -> BigInt {
    assert!(l < r && m.is_positive());
    let qd0: BigInt;
    (qd0, d) = (l * &c + d).div_rem_euclid(&m);
    let mut sum_acc = l * &a + qd0 * &b;
    let mut max_acc = sum_acc.clone();
    let mut n = r - l;
    loop {
        let (qc, qd): (BigInt, BigInt);
        (qc, c) = (&c).div_rem_euclid(&m);
        a += &b * qc;
        (qd, d) = (&d).div_rem_euclid(&m);
        sum_acc += &b * qd;
        n -= 1;
        let y_max = (&c * &n + &d) / &m;
        max_acc = max_acc.max(&sum_acc + (&a * &n + &b * &y_max).max(BigInt::zero()));
        if y_max.is_zero() {
            return max_acc;
        }
        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);
    let negm = -&m;
    if r.is_zero() && d * k + &g >= *a {
        return BigInt::from(-1i32);
    }
    let (mut lo, mut hi): (BigInt, 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;
    }
    while (&lo + 1) < hi {
        let mid: BigInt = (&lo + &hi) / 2;
        if mwf(&lo, &mid, a.clone(), b.clone(), negm.clone(), d.clone(), BigInt::zero()) <= bk.clone() {
            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