#703378 (Rust) No.186 中華風 (Easy)

• 問題: No.186 中華風 (Easy)
• ユーザー: o_loAol_o
• 提出日時: 2021-09-28 04:36:41
• 言語: Rust (1.83.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 5,624 bytes
• コンパイル時間: 14,474 ms
• コンパイル使用メモリ: 391,252 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-07-07 02:55:15
• 合計ジャッジ時間: 13,758 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
other	AC * 21 WA * 2

ソースコード

// No.186 (https://yukicoder.me/problems/447)
#![allow(unreachable_code)]
#![allow(dead_code)]

fn main() {
    let variables = input()
        .into_iter()
        .map(|(e0, e1)| (1, e0, e1))
        .collect::<Vec<_>>();
    let ans = number_library::solve_simultaneous_linear_congruent(&variables);
    if let Some((x, m)) = ans {
        println!("{}", x % m)
    } else {
        println!("-1")
    }
}

#[inline(always)]
fn input() -> Vec<(i64, i64)> {
    let mut v = Vec::with_capacity(3);
    for _ in 0..3 {
        let i = read_line::<i64>();
        v.push((i[0], i[1]))
    }
    v
}

#[inline(always)]
fn read_line<T>() -> Vec<T>
where
    T: std::str::FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim()
        .split_whitespace()
        .map(|c| T::from_str(c).unwrap())
        .collect()
}

pub mod number_library {
    /// O(lg n)
    #[inline]
    pub fn gcd<T>(a: T, b: T) -> T
    where
        T: std::ops::Rem<Output = T> + Zero + std::cmp::Eq + Copy + std::cmp::Ord,
    {
        let mut max = std::cmp::max(a, b);
        let mut min = std::cmp::min(a, b);
        while min != T::ZERO {
            let tmp = min;
            min = max % min;
            max = tmp;
        }
        max
    }

    /// O(lg n)
    #[inline]
    pub fn lcm<T>(a: T, b: T) -> T
    where
        T: Copy
            + std::ops::Rem<Output = T>
            + std::ops::Mul<Output = T>
            + std::ops::Div<Output = T>
            + std::cmp::Ord
            + Zero
            + std::cmp::Eq,
    {
        a / gcd(a, b) * b
    }

    /// return gcd(a, b), x, y s.t. ax + by = gcd(a, b)
    /// verified (https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5877610#1)
    /// O(lg n)
    #[inline]
    pub fn ext_gcd<T>(a: T, b: T) -> (T, T, T)
    where
        T: std::ops::Rem<Output = T>
            + std::ops::Div<Output = T>
            + std::ops::Mul<Output = T>
            + std::ops::Sub<Output = T>
            + Zero
            + One
            + std::cmp::Eq
            + Copy,
    {
        if b == T::ZERO {
            (a, T::ONE, T::ZERO)
        } else {
            let (d, y_b, x_b) = ext_gcd(b, a % b);
            (d, x_b, y_b - (a / b) * x_b)
        }
    }

    /// return inverse element a^-1 s.t. a * a^-1 ≡ 1 (mod m)
    /// verified (https://atcoder.jp/contests/abc024/submissions/26192341)
    /// O(lg n)
    #[inline]
    pub fn mod_inverse<T>(a: T, m: T) -> Option<T>
    where
        T: std::ops::Rem<Output = T>
            + std::ops::Add<Output = T>
            + std::ops::Div<Output = T>
            + std::ops::Mul<Output = T>
            + std::ops::Sub<Output = T>
            + Zero
            + One
            + std::cmp::Eq
            + Copy,
    {
        let (d, x, _) = ext_gcd(a, m);
        if d == T::ONE {
            Some((m + x % m) % m)
        } else {
            None
        }
    }

    /// solve simultaneous linear congruent
    /// give ai x ≡ bi (mod mi) (1 <= i <= n) as Vec<(ai, bi, mi)>,
    /// then return Option<(b, m)> s.t. x ≡ b (mod m)
    #[inline]
    pub fn solve_simultaneous_linear_congruent<T>(variables: &[(T, T, T)]) -> Option<(T, T)>
    where
        T: Zero
            + One
            + Copy
            + std::cmp::Eq
            + std::cmp::Ord
            + std::ops::Add<Output = T>
            + std::ops::Sub<Output = T>
            + std::ops::Mul<Output = T>
            + std::ops::MulAssign
            + std::ops::Div<Output = T>
            + std::ops::Rem<Output = T>,
    {
        // ∀x, x ≡ 0 (mod 1)
        let mut x = T::ZERO;
        let mut m1 = T::ONE;
        for &(a, b, m2) in variables {
            let am1 = a * m1;
            let b2_ab1 = {
                let tmp = (b - a * x) % m2;
                if tmp < T::ZERO {
                    tmp + m2
                } else {
                    tmp
                }
            };
            let d = gcd(am1, m2);
            if b2_ab1 % d != T::ZERO {
                // no answer exists.
                return None;
            }
            let t = b2_ab1 / d * mod_inverse(am1 / d, m2 / d).unwrap() % (m2 / d);
            x = x + m1 * t;
            m1 *= m2 / d;
        }
        Some((x % m1, m1))
    }

    pub trait Zero {
        const ZERO: Self;
    }

    macro_rules! impl_zero {
            ( $($e:ty),* ) => {
                $(
                    impl Zero for $e {
                        const ZERO: Self = 0;
                    }
                )*
            };
        }

    impl_zero!(isize, i8, i16, i32, i64, i128, usize, u8, u16, u32, u64, u128);

    pub trait One {
        const ONE: Self;
    }

    macro_rules! impl_one {
            ( $($e:ty),* ) => {
                $(
                    impl One for $e {
                        const ONE: Self = 1;
                    }
                )*
            };
        }

    impl_one!(isize, i8, i16, i32, i64, i128, usize, u8, u16, u32, u64, u128);

    #[cfg(test)]
    mod tests_number {
        use super::*;

        #[test]
        fn for_gcd() {
            assert_eq!(gcd(9, 12), 3);
        }

        #[test]
        fn for_lcm() {
            assert_eq!(lcm(9, 12), 36);
        }

        #[test]
        fn for_ext_gcd() {
            assert_eq!(ext_gcd(4, 12), (4, 1, 0));
            assert_eq!(ext_gcd(3, 8), (1, 3, -1));
        }

        #[test]
        fn for_mod_inverse() {
            assert_eq!(mod_inverse(4, 11), Some(3));
            assert_eq!(mod_inverse(7, 13), Some(2));
        }
    }
}