結果

問題 No.3022 一元一次式 mod 1000000000
コンテスト
ユーザー atcoder8
提出日時 2025-02-14 23:02:53
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,673 bytes
コンパイル時間 14,385 ms
コンパイル使用メモリ 405,272 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2025-02-14 23:03:19
合計ジャッジ時間 15,776 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{fastout, input};

const MODULUS: i64 = 10_i64.pow(9);

#[fastout]
fn main() {
    input! {
        t: usize,
        nm: [(i64, i64); t],
    }

    for &(n, m) in &nm {
        match solve(n, m) {
            Some(ans) => println!("{}", ans),
            None => println!("-1"),
        }
    }
}

fn solve(n: i64, m: i64) -> Option<i64> {
    let neg_m = MODULUS - m % MODULUS;

    let (x, _y, d) = ext_gcd(n, MODULUS);

    if neg_m % d != 0 {
        return None;
    }

    let mul = neg_m / d;
    let sub_mod = MODULUS / d;
    Some((x * mul * d % sub_mod + sub_mod) % sub_mod)
}

pub fn modinv(mut a: i64, m: i64) -> i64 {
    assert!(m >= 2);

    let (mut b, mut s, mut t) = (m, 1, 0);
    while b != 0 {
        let q = a / b;
        a -= q * b;
        std::mem::swap(&mut a, &mut b);
        s -= q * t;
        std::mem::swap(&mut s, &mut t);
    }

    assert_eq!(
        a.abs(),
        1,
        "The inverse does not exist. gcd(a, m) = {}",
        a.abs()
    );

    s %= m;
    if s < 0 {
        s += m;
    }

    s
}

/// Returns a tuple of `(x, y)` and `gcd(a, b)` that satisfy `ax + by = gcd(a, b)` in that order.
///
/// The returned `x`, `y` and `gcd(a, b)` satisfy the following:
///   * Both `|x|` and `|y|` are less than or equal to `max(|a|, |b|)`.
///   * `gcd(a, b)` is non-negative.
pub fn ext_gcd(mut a: i64, mut b: i64) -> (i64, i64, i64) {
    if a == 0 && b == 0 {
        return (0, 0, 0);
    }

    let (mut s, mut t, mut u, mut v) = (1, 0, 0, 1);
    while b != 0 {
        (a, b, s, t, u, v) = (b, a % b, t, s - a / b * t, v, u - a / b * v);
    }

    let sgn = a.signum();
    (sgn * s, sgn * u, sgn * a)
}
0