結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー taka8
提出日時 2024-05-08 15:22:17
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 3,372 bytes
コンパイル時間 12,658 ms
コンパイル使用メモリ 388,116 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-14 20:17:03
合計ジャッジ時間 14,006 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Write;

fn main() {
    let mut output = std::io::BufWriter::new(std::io::stdout());
    input!{
        n: usize,
        a: [(i64, i64); n]
    }
    let (mut r, mut m) = (Vec::with_capacity(n), Vec::with_capacity(n));
    for (ri, mi) in a {
        r.push(ri);
        m.push(mi);
    }

    let ans = crt(&r, &m).0;
    writeln!(output, "{}", if ans == 0 {-1} else {ans}).unwrap();
}

pub fn crt(r: &[i64], m: &[i64]) -> (i64, i64) {
    assert_eq!(r.len(), m.len());
    let (mut r0, mut m0) = (0, 1);
    for (&(mut ri), &(mut mi)) in r.iter().zip(m.iter()) {
        assert!(1 <= mi);
        ri = ri % mi;
        if ri < 0 {ri += mi;}
        if m0 < mi {
            std::mem::swap(&mut r0, &mut ri);
            std::mem::swap(&mut m0, &mut mi);
        }
        if m0 % mi == 0 {
            if r0 % mi != ri {
                return (0, 0);
            }
            continue;
        }

        let (g, im) = mod_inv(m0, mi);
        let u1 = mi / g;
        if (ri - r0) % g != 0 {
            return (0, 0);
        }
        let x = (ri - r0) / g % u1 * im % u1;

        r0 += x * m0;
        m0 *= u1;
        if r0 < 0 {
            r0 += m0
        };
    }

    (r0, m0)
}


#[inline]
pub fn exgcd(a: i64, b: i64, x: &mut i64, y: &mut i64) -> i64 {
    let mut d = a;
    if b != 0 {
        d = exgcd(b, a%b, y, x);
        *y -= a / b * *x;
    }
    else {
        *x = 1;
        *y = 0;
    }
    d
}

// ax ≡ g (mod m)
// (g, x)
#[inline]
pub fn mod_inv(a: i64, m: i64) -> (i64, i64) {
    let mut x = 1;
    let mut y = 0;
    (exgcd(a, m, &mut x, &mut y), (m + x % m) % m)
    
}


#[allow(dead_code)]
mod procon_io {
    #[macro_export]
    macro_rules! input {
        (iter = $iter:expr, $($r:tt)*) => {
            input_inner!{$iter, $($r)*}
        };
        (buf = $s:expr, $($r:tt)*) => {
            let mut iter = $s.split_whitespace();
            input_inner!{iter, $($r)*}
        };
        ($($r:tt)*) => {
            let s = {
                use std::io::Read;
                let mut s = String::new();
                std::io::stdin().read_to_string(&mut s).unwrap();
                s
            };
            let mut iter = s.split_whitespace();
            input_inner!{iter, $($r)*}
        };
    }

    #[macro_export]
    macro_rules! input_inner {
        ($iter:expr) => {};
        ($iter:expr, ) => {};
        ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
            let $var = read!($iter, $t);
            input_inner!{$iter $($r)*}
        };
        ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
            let mut $var = read!($iter, $t);
            input_inner!{$iter $($r)*}
        };
    }

    #[macro_export]
    macro_rules! read {
        ($iter:expr, ( $($t:tt),* )) => {
            ( $(read!($iter, $t)),* )
        };
        ($iter:expr, [ $t:tt ; $len:expr ]) => {
            (0..$len).map(|_| read!($iter, $t)).collect::<Vec<_>>()
        };
        ($iter:expr, chars) => {
            read!($iter, String).chars().collect::<Vec<char>>()
        };
        ($iter:expr, bytes) => {
            read!($iter, String).bytes().collect::<Vec<u8>>()
        };
        ($iter:expr, usize1) => {
            read!($iter, usize) - 1
        };
        ($iter:expr, $t:ty) => {
            $iter.next().unwrap().parse::<$t>().expect("Parse error")
        };
    }
}
0