結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー manta1130
提出日時 2020-09-10 21:29:14
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 5,105 bytes
コンパイル時間 13,918 ms
コンパイル使用メモリ 377,880 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-24 02:36:12
合計ジャッジ時間 15,197 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `n`
   --> src/main.rs:153:9
    |
153 |     let n = r.len();
    |         ^ help: if this is intentional, prefix it with an underscore: `_n`
    |
    = note: `#[warn(unused_variables)]` on by default

ソースコード

diff # 

//https://github.com/manta1130/Competitive_Programming_Template_Rust

#[macro_use]
mod input {

    use std;
    use std::io;

    const SPLIT_DELIMITER: char = ' ';

    #[macro_export]
    #[allow(unused_macros)]
    macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

    #[allow(dead_code)]
    pub fn input_line_str() -> String {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        s.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn p<T>(t: T)
    where
        T: std::fmt::Display,
    {
        println!("{}", t);
    }

    #[allow(dead_code)]
    pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<Vec<T>> = Vec::new();

        for _ in 0..line {
            let vec_line = input_vector();
            v.push(vec_line);
        }
        v
    }

    #[allow(dead_code)]
    pub fn input_vector<T>() -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<T> = Vec::new();

        let s = input_line_str();
        let split_result = s.split(SPLIT_DELIMITER);
        for z in split_result {
            let buf = match z.parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error"),
            };
            v.push(buf);
        }
        v
    }

    #[allow(dead_code)]
    pub fn input_vector_row<T>(n: usize) -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v = Vec::with_capacity(n);
        for _ in 0..n {
            let buf = match input_line_str().parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error"),
            };
            v.push(buf);
        }
        v
    }

    pub trait ToCharVec {
        fn to_charvec(&self) -> Vec<char>;
    }

    impl ToCharVec for String {
        fn to_charvec(&self) -> Vec<char> {
            self.to_string().chars().collect::<Vec<_>>()
        }
    }
}

//https://github.com/rust-lang-ja/ac-library-rs

use input::*;
use std::mem::swap;

fn inv_gcd(a: i64, b: i64) -> (i64, i64) {
    let a = safe_mod(a, b);
    if a == 0 {
        return (b, 0);
    }

    // Contracts:
    // [1] s - m0 * a = 0 (mod b)
    // [2] t - m1 * a = 0 (mod b)
    // [3] s * |m1| + t * |m0| <= b
    let mut s = b;
    let mut t = a;
    let mut m0 = 0;
    let mut m1 = 1;

    while t != 0 {
        let u = s / t;
        s -= t * u;
        m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b

        // [3]:
        // (s - t * u) * |m1| + t * |m0 - m1 * u|
        // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        // = s * |m1| + t * |m0| <= b

        swap(&mut s, &mut t);
        swap(&mut m0, &mut m1);
    }
    // by [3]: |m0| <= b/g
    // by g != b: |m0| < b/g
    if m0 < 0 {
        m0 += b / s;
    }
    (s, m0)
}

fn safe_mod(mut x: i64, m: i64) -> i64 {
    x %= m;
    if x < 0 {
        x += m;
    }
    x
}

fn crt(r: &Vec<i64>, m: &Vec<i64>) -> (i64, i64) {
    assert!(r.len() == m.len());
    let n = r.len();
    // Contracts: 0 <= r0 < m0
    let (mut r0, mut m0) = (0, 1);
    for (ri, mi) in r.iter().zip(m.iter()) {
        assert!(1 < *mi);
        let mut r1 = safe_mod(*ri, *mi);
        let mut m1 = *mi;
        if m0 < m1 {
            swap(&mut r0, &mut r1);
            swap(&mut m0, &mut m1);
        }
        if m0 % m1 == 0 {
            if r0 % m1 != r1 {
                return (0, 0);
            }
            continue;
        }
        // assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)

        // (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
        // r2 % m0 = r0
        // r2 % m1 = r1
        // -> (r0 + x*m0) % m1 = r1
        // -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)
        // -> x = (r1 - r0) / g * inv(u0) (mod u1)

        // im = inv(u0) (mod u1) (0 <= im < u1)
        let (g, im) = inv_gcd(m0, m1);
        let u1 = m1 / g;
        // |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
        if (r1 - r0) % g != 0 {
            return (0, 0);
        }
        // u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
        let x = (r1 - r0) / g % u1 * im % u1;

        // |r0| + |m0 * x|
        // < m0 + m0 * (u1 - 1)
        // = m0 + m0 * m1 / g - m0
        // = lcm(m0, m1)
        r0 += x * m0;
        m0 *= u1; // -> lcm(m0, m1)
        if r0 < 0 {
            r0 += m0
        };
    }

    (r0, m0)
}

fn main() {
    let n: usize;
    input!(n);
    let mut x = vec![];
    let mut y = vec![];
    for _ in 0..n {
        let (q, w): (i64, i64);
        input!(q, w);
        x.push(q);
        y.push(w);
    }
    let ans = crt(&x, &y);
    if ans.0 == 0 && ans.1 == 0 {
        println!("-1");
    } else {
        println!("{}", ans.0 % 1_000_000_007);
    }
}
0