結果

問題 No.3022 一元一次式 mod 1000000000
コンテスト
ユーザー atcoder8
提出日時 2025-02-14 23:30:38
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 1,804 bytes
コンパイル時間 12,995 ms
コンパイル使用メモリ 394,320 KB
実行使用メモリ 8,832 KB
最終ジャッジ日時 2025-02-17 12:58:05
合計ジャッジ時間 14,356 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{fastout, input};

const MODULUS: i128 = 10_i128.pow(9);

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

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

fn solve(n: i128, m: i128) -> Option<i128> {
    let a = n;
    let b = MODULUS;
    let c = -m;
    let (x0, _, d) = ext_gcd(a, b);

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

    let scale = c / d;
    let scaled_x = x0 * scale;
    let divided_b = b / d;

    let mut best_x = (scaled_x % divided_b + divided_b) % divided_b;
    if best_x == 0 {
        best_x = divided_b;
    }

    Some(best_x)
}

pub fn modinv(mut a: i128, m: i128) -> i128 {
    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: i128, mut b: i128) -> (i128, i128, i128) {
    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