#1197209 (Rust) No.187 中華風 (Hard)

• 問題: No.187 中華風 (Hard)
• ユーザー: matajupi
• 提出日時: 2026-11-06 06:16:09
• 言語: Rust (1.99.1 + proconio + num + itertools + ACL)
• 結果: WA
• 実行時間: -
• コード長: 12,087 bytes
• コンパイル時間: 5,552 ms
• コンパイル使用メモリ: 212,708 KB
• 実行使用メモリ: 9,920 KB
• 最終ジャッジ日時: 2026-11-06 06:16:18
• 合計ジャッジ時間: 4,944 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
other	AC * 24 WA * 1

ソースコード

// 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::*;

fn crt(a: &[i128], m: &[i128]) -> Vec<i128> {
    assert!(a.len() == m.len());

    let n = a.len();
    let mut c = vec![0; n];
    for i in 0..n {
        let mut xi = 0;
        let mut m_prod = 1;
        for j in 0..i {
            xi = (xi + c[j] * m_prod) % m[i];
            m_prod = (m_prod * m[j]) % m[i];
        }
        let mut b = i128::extended_gcd(&m_prod, &-m[i]).x;
        b = (b + m[i]) % m[i];
        c[i] = ((a[i] - xi + m[i]) % m[i]) * b % m[i];
    }

    c
}

fn calc_x(c: &[i128], m: &[i128], modi: i128) -> i128 {
    let n = c.len();
    let mut x = 0;
    for i in (0..n).rev() {
        x = ((x * m[i]) % modi + c[i]) % modi;
    }
    x
}

fn factorize(mut n: i64, pfs: &mut HashMap<i64, usize>) {
    let mut p = 2;
    while p*p <= n {
        let mut e = 0;
        while n % p == 0 {
            n /= p;
            e += 1;
        }
        if e > 0 {
            *pfs.entry(p).or_insert(0) += e;
        }
        p += 1;
    }
    if n != 1 {
        *pfs.entry(n).or_insert(0) += 1;
    }
}

const MOD: i128 = 1000000007;

fn solve() {
    // x = a (mod m^e1), x = b (mod m^e2) (e1 < e2)
    // x = b (mod m^e2) -> x = b (mod m^e1)
    input! {
        n: usize,
        xy: [(i64, i64); n],
    };

    let mut map = HashMap::new();
    for i in 0..n {
        let (x, y) = xy[i];
        let mut pfs = HashMap::new();
        factorize(y, &mut pfs);
        for (p, e) in pfs {
            let q = pow(p, e);
            let x = x % q;
            map.orwith(p, || vec![]).push((q, x));
        }
    }

    let mut a = vec![];
    let mut m = vec![];
    for (_, mut v) in map.iit() {
        v.sort();
        v.reverse();
        let (q, y) = v[0];
        for (q, x) in v {
            if y % q != x {
                println!("-1");
                return;
            }
        }
        a.push(y.l());
        m.push(q.l());
    }

    let c = crt(&a, &m);
    let mut d = calc_x(&c, &m, MOD);
    if d == 0 {
        d = 1;
        for mi in m {
            d = (d * mi) % MOD;
        }
    }

    println!("{}", d);
}

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