結果

問題 No.3022 一元一次式 mod 1000000000
コンテスト
ユーザー atcoder8
提出日時 2025-02-14 22:33:47
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,282 bytes
コンパイル時間 18,749 ms
コンパイル使用メモリ 401,916 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2025-02-14 22:34:33
合計ジャッジ時間 20,118 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 rem_n = n % MODULUS;
    let neg_m = MODULUS - m % MODULUS;

    if rem_n == 0 && neg_m == 0 {
        return Some(1);
    }

    if rem_n == 0 {
        return None;
    }

    if gcd(rem_n, MODULUS) != 1 {
        return None;
    }

    Some(neg_m * modinv(rem_n, MODULUS) % MODULUS)
}

fn gcd(a: i64, b: i64) -> i64 {
    let mut a = a.abs();
    let mut b = b.abs();

    while b != 0 {
        let r = a % b;
        a = b;
        b = r;
    }

    a
}

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
}
0