#1197555 (Rust) No.2558 中国剰余定理

• 問題: No.2558 中国剰余定理
• ユーザー: matajupi
• 提出日時: 2026-11-07 08:02:25
• 言語: Rust (1.99.1 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 15,602 bytes
• コンパイル時間: 5,030 ms
• コンパイル使用メモリ: 215,344 KB
• 実行使用メモリ: 9,888 KB
• 最終ジャッジ日時: 2026-11-07 08:02:33
• 合計ジャッジ時間: 5,114 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	AC * 3
other	AC * 29

ソースコード

// Reference: https://github.com/matajupi/matajupilib_snippets

// 　∧＿∧
// （｡･ﻌ･｡)つ━☆・*。
// ⊂　　 ノ 　　　✧・゜+.
// 　しーＪ　　　°。+ *´¨)
// 　　　　　　　　　.· ´¸.·´¨) ¸.·¨)
// 　　　　　　　　　　(¸.·´ ✧(¸.·’*✧

#![allow(dead_code, unused_imports, unused_macros, unexpected_cfgs)]

#[macro_use]
mod matajupilib {
    use crate::*;

    // =============================================================================
    // Macros
    // =============================================================================
    macro_rules! chmin {
        ($a:expr, $b:expr) => {
            if $b < $a {
                $a = $b;
                true
            } else {
                false
            }
        };
    }

    macro_rules! chmax {
        ($a:expr, $b:expr) => {
            if $b > $a {
                $a = $b;
                true
            } else {
                false
            }
        };
    }

    macro_rules! r {
        ($num:expr, $den:expr) => {
            Rational64::new($num, $den)
        };
    }

    /// Debug print macro (Only works in Debug builds; ignored in Release builds)
    macro_rules! d {
        ($($a:expr),* $(,)?) => {
            #[cfg(debug_assertions)]
            eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
        };
    }

    // =============================================================================
    // Constants & Type Aliases
    // =============================================================================
    pub const IINF: i64 = 4_000_000_000_000_000_000;
    pub const UINF: usize = 1_000_000_000;

    pub const DX4: [i64; 4] = [1, 0, -1, 0];
    pub const DY4: [i64; 4] = [0, 1, 0, -1];
    pub const DX8: [i64; 8] = [1, 1, 0, -1, -1, -1, 0, 1];
    pub const DY8: [i64; 8] = [0, 1, 1, 1, 0, -1, -1, -1];

    pub type MinHeap<T> = BinaryHeap<R<T>>;
    pub type MaxHeap<T> = BinaryHeap<T>;

    // =============================================================================
    // Type Cast Traits
    // =============================================================================
    macro_rules! define_cast_trait {
        ($trait_name:ident, $fn_name:ident, $target_type:ty, $($source_type:ty),*) => {
            pub trait $trait_name {
                fn $fn_name(self) -> $target_type;
            }
            $(
                impl $trait_name for $source_type {
                    #[inline]
                    fn $fn_name(self) -> $target_type { self as $target_type }
                }
            )*
        };
    }

    define_cast_trait!(
        AsUsize, u, usize, i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, char,
        f32, f64
    );
    define_cast_trait!(
        AsI64, i, i64, i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, char, f32,
        f64
    );
    define_cast_trait!(
        AsF64, f, f64, i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, f32, f64
    );
    define_cast_trait!(
        AsI128, l, i128, i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, char, f32,
        f64
    );

    pub trait AsMint {
        fn m(self) -> Mint;
    }

    impl<T> AsMint for T
    where
        T: Into<Mint>,
    {
        #[inline]
        fn m(self) -> Mint {
            self.into()
        }
    }

    // =============================================================================
    // Helper Traits
    // =============================================================================
    pub trait Unwrapper<T> {
        fn uw(self) -> T;
        fn uwor(self, default: T) -> T;
        fn uworelse<F>(self, f: F) -> T
        where
            F: FnOnce() -> T;
    }

    impl<T> Unwrapper<T> for Option<T> {
        #[inline]
        fn uw(self) -> T {
            self.expect("None value")
        }
        #[inline]
        fn uwor(self, default: T) -> T {
            self.unwrap_or(default)
        }
        #[inline]
        fn uworelse<F>(self, f: F) -> T
        where
            F: FnOnce() -> T,
        {
            self.unwrap_or_else(f)
        }
    }

    impl<T, E: std::fmt::Debug> Unwrapper<T> for Result<T, E> {
        #[inline]
        fn uw(self) -> T {
            self.expect("Err value")
        }
        #[inline]
        fn uwor(self, default: T) -> T {
            self.unwrap_or(default)
        }
        #[inline]
        fn uworelse<F>(self, f: F) -> T
        where
            F: FnOnce() -> T,
        {
            self.unwrap_or_else(|_| f())
        }
    }

    pub trait ShortNumOps: Sized {
        fn sadd(self, rhs: Self) -> Self;
        fn ssub(self, rhs: Self) -> Self;
        fn smul(self, rhs: Self) -> Self;
        fn oadd(self, rhs: Self) -> (Self, bool);
        fn osub(self, rhs: Self) -> (Self, bool);
        fn omul(self, rhs: Self) -> (Self, bool);
    }

    macro_rules! impl_short_num_ops {
        ($($t:ty),*) => { $(
            impl ShortNumOps for $t {
                #[inline] fn sadd(self, rhs: Self) -> Self { self.saturating_add(rhs) }
                #[inline] fn ssub(self, rhs: Self) -> Self { self.saturating_sub(rhs) }
                #[inline] fn smul(self, rhs: Self) -> Self { self.saturating_mul(rhs) }
                #[inline] fn oadd(self, rhs: Self) -> (Self, bool) { self.overflowing_add(rhs) }
                #[inline] fn osub(self, rhs: Self) -> (Self, bool) { self.overflowing_sub(rhs) }
                #[inline] fn omul(self, rhs: Self) -> (Self, bool) { self.overflowing_mul(rhs) }
            }
        )* };
    }
    impl_short_num_ops!(
        i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize
    );

    pub trait MapExt<K, V> {
        fn orins(&mut self, key: K, default: V) -> &mut V;
        fn ordef(&mut self, key: K) -> &mut V
        where
            V: Default;
        fn orwith<F: FnOnce() -> V>(&mut self, key: K, f: F) -> &mut V;
    }

    impl<K: Eq + Hash, V, S: BuildHasher> MapExt<K, V> for HashMap<K, V, S> {
        #[inline]
        fn orins(&mut self, key: K, default: V) -> &mut V {
            self.entry(key).or_insert(default)
        }
        #[inline]
        fn ordef(&mut self, key: K) -> &mut V
        where
            V: Default,
        {
            self.entry(key).or_default()
        }
        #[inline]
        fn orwith<F: FnOnce() -> V>(&mut self, key: K, f: F) -> &mut V {
            self.entry(key).or_insert_with(f)
        }
    }

    impl<K: Ord, V> MapExt<K, V> for BTreeMap<K, V> {
        #[inline]
        fn orins(&mut self, key: K, default: V) -> &mut V {
            self.entry(key).or_insert(default)
        }
        #[inline]
        fn ordef(&mut self, key: K) -> &mut V
        where
            V: Default,
        {
            self.entry(key).or_default()
        }
        #[inline]
        fn orwith<F: FnOnce() -> V>(&mut self, key: K, f: F) -> &mut V {
            self.entry(key).or_insert_with(f)
        }
    }

    pub trait StrExt {
        fn cv(&self) -> Vec<char>;
    }

    impl StrExt for str {
        #[inline]
        fn cv(&self) -> Vec<char> {
            self.chars().collect()
        }
    }

    // =============================================================================
    // Iterator Extensions
    // =============================================================================
    pub trait IntoIterExt: IntoIterator + Sized {
        #[inline]
        fn iit(self) -> Self::IntoIter {
            self.into_iter()
        }
        #[inline]
        fn col<B: FromIterator<Self::Item>>(self) -> B {
            self.into_iter().collect()
        }
        #[inline]
        fn colv(self) -> Vec<Self::Item> {
            self.into_iter().collect()
        }
    }
    impl<T: IntoIterator> IntoIterExt for T {}

    pub trait IterExt {
        #[inline]
        fn it(&self) -> <&Self as IntoIterator>::IntoIter
        where
            for<'a> &'a Self: IntoIterator,
        {
            self.into_iter()
        }
        #[inline]
        fn itm(&mut self) -> <&mut Self as IntoIterator>::IntoIter
        where
            for<'a> &'a mut Self: IntoIterator,
        {
            self.into_iter()
        }
    }
    impl<T: ?Sized> IterExt for T {}

    // =============================================================================
    // Scanner
    // =============================================================================
    use std::io::Read;

    pub struct Scanner {
        iter: std::vec::IntoIter<String>,
    }

    impl Scanner {
        pub fn new() -> Self {
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            Self {
                iter: s.split_whitespace().map(|s| s.to_string())
                    .collect::<Vec<_>>().into_iter(),
            }
        }
        pub fn n<T: std::str::FromStr>(&mut self) -> T {
            self.iter.next().unwrap().parse().ok().unwrap()
        }
        pub fn ns<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.n()).collect()
        }
    }
}

// =============================================================================
// Imports & Main
// =============================================================================
// AtCoder
// use amplify::*;
// use omniswap::swap;
// use ordered_float::OrderedFloat as OF;
// use rand::Rng;
// use superslice::Ext;

// yukicoder
use ::num::{integer::*, rational::*, *};
use itertools::Itertools;
use ac_library::*;
use proconio::{marker::*, *};

// Other
use std::cmp::{Reverse as R, *};
use std::collections::{HashMap as Map, HashSet as Set, *};
use std::f64::consts::*;
use std::hash::{BuildHasher, Hash};
use std::mem::*;
use std::ops::{Range, RangeBounds};

// AtCoder, yukicoder
use ac_library::ModInt998244353 as Mint;
// Other
// type Mint = i64;

use matajupilib::*;

mod primes {
    use crate::*;

    pub fn factorize(mut n: i64, pfs: &mut HashMap<i64, usize>) {
        for p in 2.. {
            if p * p > n {
                break;
            }

            let mut e = 0;
            while n % p == 0 {
                n /= p;
                e += 1;
            }

            if e > 0 {
                *pfs.entry(p).or_insert(0) += e;
            }
        }

        if n != 1 {
            *pfs.entry(n).or_insert(0) += 1;
        }
    }

    // 素因数分解する最大値をMとしてsqrt(M)までのprimesを求めておく
    // Mが小さい時はOsa-k法も検討する
    pub fn factorize_with_primes(
        mut n: i64,
        primes: &[usize],
        pfs: &mut HashMap<i64, usize>
    ) {
        for &p in primes {
            let p = p.i();
            if p * p > n {
                break;
            }

            let mut e = 0;
            while n % p == 0 {
                n /= p;
                e += 1;
            }

            if e > 0 {
                *pfs.entry(p).or_insert(0) += e;
            }
        }

        if n != 1 {
            *pfs.entry(n).or_insert(0) += 1;
        }
    }

    // Eratosthenes sieve
    pub fn sieve(n: usize) -> Vec<usize> {
        let mut is_prime = vec![true; n + 1];
        is_prime[0] = false;
        is_prime[1] = false;

        for i in 2.. {
            if i*i > n {
                break;
            }

            if is_prime[i] {
                for j in (i*i..=n).step_by(i) {
                    is_prime[j] = false;
                }
            }
        }

        (2..=n).filter(|&i| is_prime[i]).collect()
    }
}
use primes::*;

mod crt {
    use crate::*;
    #[derive(Clone, Debug)]
    pub struct Crt {
        // prime -> (maximum prime power, corresponding residue)
        pp: BTreeMap<i64, (i64, i64)>,
        // Whether all added constraints are consistent.
        ok: bool,
    }

    impl Crt {
        pub fn new() -> Self {
            Self {
                pp: BTreeMap::new(),
                ok: true,
            }
        }

        // Add constraint A ≡ x (mod y)
        pub fn add(&mut self, x: i64, y: i64) -> bool {
            if !self.ok {
                return false;
            }

            let mut pfs = HashMap::new();
            factorize(y, &mut pfs);

            for (p, e) in pfs {
                let q = pow(p, e);
                let r = x.rem_euclid(q);

                if !self.add_prime_power(p, q, r) {
                    self.ok = false;
                    return false;
                }
            }

            true
        }

        pub fn is_consistent(&self) -> bool {
            self.ok
        }

        pub fn crt(&self) -> Option<(i64, i64, Vec<i64>)> {
            if !self.ok {
                return None;
            }

            let mut c = vec![0; self.pp.len()];
            let mut m_prod = 1;
            let mut x = 0_i64;

            for (i, &(m, a)) in self.pp.values().enumerate() {
                let b = i64::extended_gcd(&m_prod, &m).x
                    .rem_euclid(m);
                let delta = (a.rem_euclid(m) - x.rem_euclid(m))
                    .rem_euclid(m);
                c[i] = ((delta.l() * b.l()) % m.l()).i();
                x += c[i] * m_prod;
                m_prod *= m;
            }

            Some((x, m_prod, c))
        }

        pub fn mix_radix_large(&self) -> Option<Vec<i64>> {
            if !self.ok {
                return None;
            }

            let m = self.pp.values().map(|&(m, _)| m.l()).colv();
            let a = self.pp.values().map(|&(_, a)| a.l()).colv();
            let n = self.pp.len();

            let mut c = vec![0; n];

            for i in 0..n {
                let mut x = 0_i128;
                let mut m_prod = 0_i128;

                for j in 0..i {
                    x = (x + c[j].l() * m_prod) % m[i];
                    m_prod = (m_prod * m[j]) % m[i];
                }

                let b = i128::extended_gcd(&m_prod, &m[i]).x
                    .rem_euclid(m[i]);
                let delta = (a[i] - x).rem_euclid(m[i]);
                c[i] = (delta * b % m[i]).i();
            }

            Some(c)
        }

        pub fn crt_large(&self, modulus: i64) -> Option<(i64, i64, Vec<i64>)> {
            let modulus = modulus.l();

            let c = self.mix_radix_large()?;

            let mut m_prod = 1_i128;
            let mut x = 0_i128;

            for (&(_, m), &c) in self.pp.values().zip(c.it()).rev() {
                x = (x * m.l() + c.l()) % modulus;
                m_prod = (m_prod * m.l()) % modulus;
            }

            Some((x.i(), m_prod.i(), c))
        }

        // Add A ≡ r (mod q), where q is a power of p.
        fn add_prime_power(&mut self, p: i64, q: i64, r: i64) -> bool {
            if let Some((old_q, old_r)) = self.pp.get_mut(&p) {
                if q > *old_q {
                    if r % *old_q != *old_r {
                        return false;
                    }

                    *old_q = q;
                    *old_r = r;
                } else {
                    if *old_r % q != r {
                        return false;
                    }
                }
            } else {
                self.pp.insert(p, (q, r));
            }

            true
        }
    }
}
use crt::Crt;

fn solve() {
    input! {
        m1: i64, m2: i64, a: i64, b: i64,
    };

    let mut crt = Crt::new();
    crt.add(a, m1);
    crt.add(b, m2);
    let (d, _, _) = crt.crt().uw();
    println!("{}", d);
}

fn main() {
    let t = 1;
    for _ in 0..t {
        solve();
    }
}