結果

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

ソースコード

diff #
raw source code 

fn mwf(
    mut n: BigInt,
    mut m: BigInt,
    mut a: BigInt,
    mut b: BigInt,
    mut c: BigInt,
    mut d: BigInt,
) -> BigInt {
    assert!(n.is_positive() && m.is_positive());
    let (mut r, mut s) = (BigInt::zero(), BigInt::zero());
    loop {
        n -= 1;
        let y_max = (&c * &n + &d) / &m;
        r = r.max(s.clone()).max(&s + &a * &n + &b * &y_max);
        if y_max.is_zero() {
            break;
        }
        d = &m - d - 1;
        let (qm, rm) = (&m).div_rem_euclid(&c);
        let (qd, rd) = (&d).div_rem_euclid(&c);
        s += (&a + &b) * BigInt::from(a.is_negative()) + qd * &a;
        (m, a, b, c, d) = (c, &b + qm * &a, a, rm, rd);
    }
    r
}

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(mid.clone(), a.clone(), b.clone(), negm.clone(), d.clone(), BigInt::zero()) <= bk {
            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