Struct MInt

pub struct MInt<M>
where
    M: MIntBase,
{ /* private fields */ }

Implementations

impl<M> MInt<M>

where M: MIntConvert<u32>,

pub fn sqrt(self) -> Option<Self>

Examples found in repository

crates/competitive/src/math/formal_power_series/mod.rs (line 67)

    fn sqrt_coefficient(&self) -> Option<Self> {
        self.sqrt()
    }

crates/library_checker/src/math/sqrt_mod.rs (line 12)

pub fn sqrt_mod(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, q, yp: [(u32, u32)]);
    for (y, p) in yp.take(q) {
        DynMIntU32::set_mod(p);
        if let Some(x) = DynMIntU32::from(y).sqrt() {
            writeln!(writer, "{}", x).ok();
        } else {
            writeln!(writer, "-1").ok();
        }
    }
}

impl<M> MInt<M>

where M: MIntConvert,

pub fn new(x: M::Inner) -> Self

Examples found in repository

crates/library_checker/src/math/sum_of_totient_function.rs (line 19)

pub fn sum_of_totient_function(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n: u64);
    let mut s = 1;
    let mut pp = 0;
    let mut pc = 0;
    let inv2 = M::new(2).inv();
    let qa = QuotientArray::from_fn(n, |i| [M::from(i), M::from(i) * M::from(i + 1) * inv2])
        .map(|[x, y]| [x - M::one(), y - M::one()])
        .lucy_dp::<ArrayOperation<AdditiveOperation<_>, 2>>(|[x, y], p| [x, y * M::from(p)])
        .map(|[x, y]| y - x)
        .min_25_sieve::<AddMulOperation<_>>(|p, c| {
            if pp != p || pc > c {
                pp = p;
                pc = 1;
                s = p - 1;
            }
            while pc < c {
                pc += 1;
                s *= p;
            }
            M::from(s)
        });
    writeln!(writer, "{}", qa[n]).ok();
}

crates/competitive/src/math/number_theoretic_transform.rs (line 368)

    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        let t1 = MInt::<N2>::new(N1::get_mod()).inv();
        let m1 = MInt::<M>::from(N1::get_mod());
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * MInt::<M>::from(N2::get_mod());
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .map(|((c1, c2), c3)| {
                let d1 = c1.inner();
                let d2 = ((c2 - MInt::<N2>::from(d1)) * t1).inner();
                let x = MInt::<N3>::new(d1) + MInt::<N3>::new(d2) * m1_3;
                let d3 = ((c3 - x) * t2).inner();
                MInt::<M>::from(d1) + MInt::<M>::from(d2) * m1 + MInt::<M>::from(d3) * m2
            })
            .collect()
    }

impl<M> MInt<M>

where M: MIntBase,

pub const fn new_unchecked(x: M::Inner) -> Self

Examples found in repository

crates/competitive/src/num/mint/mint_base.rs (line 60)

    pub fn new(x: M::Inner) -> Self {
        Self::new_unchecked(<M as MIntConvert<M::Inner>>::from(x))
    }
}
impl<M> MInt<M>
where
    M: MIntBase,
{
    #[inline]
    pub const fn new_unchecked(x: M::Inner) -> Self {
        Self {
            x,
            _marker: PhantomData,
        }
    }
    #[inline]
    pub fn get_mod() -> M::Inner {
        M::get_mod()
    }
    #[inline]
    pub fn pow(self, y: usize) -> Self {
        Self::new_unchecked(M::mod_pow(self.x, y))
    }
    #[inline]
    pub fn inv(self) -> Self {
        Self::new_unchecked(M::mod_inv(self.x))
    }
    #[inline]
    pub fn inner(self) -> M::Inner {
        M::mod_inner(self.x)
    }
}

impl<M> Clone for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn clone(&self) -> Self {
        *self
    }
}
impl<M> Copy for MInt<M> where M: MIntBase {}
impl<M> Debug for MInt<M>
where
    M: MIntBase,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        Debug::fmt(&self.inner(), f)
    }
}
impl<M> Default for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn default() -> Self {
        <Self as Zero>::zero()
    }
}
impl<M> PartialEq for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        PartialEq::eq(&self.x, &other.x)
    }
}
impl<M> Eq for MInt<M> where M: MIntBase {}
impl<M> Hash for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.x, state)
    }
}
macro_rules! impl_mint_from {
    ($($t:ty),*) => {
        $(impl<M> From<$t> for MInt<M>
        where
            M: MIntConvert<$t>,
        {
            #[inline]
            fn from(x: $t) -> Self {
                Self::new_unchecked(<M as MIntConvert<$t>>::from(x))
            }
        }
        impl<M> From<MInt<M>> for $t
        where
            M: MIntConvert<$t>,
        {
            #[inline]
            fn from(x: MInt<M>) -> $t {
                <M as MIntConvert<$t>>::into(x.x)
            }
        })*
    };
}
impl_mint_from!(
    u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize
);
impl<M> Zero for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn zero() -> Self {
        Self::new_unchecked(M::mod_zero())
    }
}
impl<M> One for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn one() -> Self {
        Self::new_unchecked(M::mod_one())
    }
}

impl<M> Add for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn add(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_add(self.x, rhs.x))
    }
}
impl<M> Sub for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn sub(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_sub(self.x, rhs.x))
    }
}
impl<M> Mul for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn mul(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_mul(self.x, rhs.x))
    }
}
impl<M> Div for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn div(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_div(self.x, rhs.x))
    }
}
impl<M> Neg for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn neg(self) -> Self::Output {
        Self::new_unchecked(M::mod_neg(self.x))
    }

pub fn get_mod() -> M::Inner

pub fn pow(self, y: usize) -> Self

Examples found in repository

crates/competitive/src/algorithm/chromatic_number.rs (line 23)

    pub fn k_colorable(&self, k: usize) -> bool {
        !self
            .ind
            .iter()
            .map(|d| d.pow(k))
            .enumerate()
            .map(|(s, d)| if s.count_ones() % 2 == 0 { d } else { -d })
            .sum::<MInt<M>>()
            .is_zero()
    }

pub fn inv(self) -> Self

Examples found in repository

crates/competitive/src/math/number_theoretic_transform.rs (line 286)

    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
        intt(&mut f);
        f.truncate(len);
        let inv = MInt::from(len.max(2).next_power_of_two() as u32).inv();
        for f in f.iter_mut() {
            *f *= inv;
        }
        f
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.len(), g.len());
        for (f, g) in f.iter_mut().zip(g.iter()) {
            *f *= *g;
        }
    }
    fn convolve(mut a: Self::T, mut b: Self::T) -> Self::T {
        if Self::length(&a).min(Self::length(&b)) <= 60 {
            return convolve_naive(&a, &b);
        }
        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
        let size = len.max(2).next_power_of_two();
        if len <= size / 2 + 2 {
            let xa = a.pop().unwrap();
            let xb = b.pop().unwrap();
            let mut c = vec![MInt::<M>::zero(); len];
            *c.last_mut().unwrap() = xa * xb;
            for (a, c) in a.iter().zip(&mut c[b.len()..]) {
                *c += *a * xb;
            }
            for (b, c) in b.iter().zip(&mut c[a.len()..]) {
                *c += *b * xa;
            }
            let d = Self::convolve(a, b);
            for (d, c) in d.into_iter().zip(&mut c) {
                *c += d;
            }
            return c;
        }
        let same = a == b;
        let mut a = Self::transform(a, len);
        if same {
            for a in a.iter_mut() {
                *a *= *a;
            }
        } else {
            let b = Self::transform(b, len);
            Self::multiply(&mut a, &b);
        }
        Self::inverse_transform(a, len)
    }
}
type MVec<M> = Vec<MInt<M>>;
impl<M, N1, N2, N3> ConvolveSteps for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    type T = MVec<M>;
    type F = (MVec<N1>, MVec<N2>, MVec<N3>);
    fn length(t: &Self::T) -> usize {
        t.len()
    }
    fn transform(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(2).next_power_of_two();
        let mut f = (
            MVec::<N1>::with_capacity(npot),
            MVec::<N2>::with_capacity(npot),
            MVec::<N3>::with_capacity(npot),
        );
        for t in t {
            f.0.push(<M as MIntConvert<u32>>::into(t.inner()).into());
            f.1.push(<M as MIntConvert<u32>>::into(t.inner()).into());
            f.2.push(<M as MIntConvert<u32>>::into(t.inner()).into());
        }
        f.0.resize_with(npot, Zero::zero);
        f.1.resize_with(npot, Zero::zero);
        f.2.resize_with(npot, Zero::zero);
        ntt(&mut f.0);
        ntt(&mut f.1);
        ntt(&mut f.2);
        f
    }
    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        let t1 = MInt::<N2>::new(N1::get_mod()).inv();
        let m1 = MInt::<M>::from(N1::get_mod());
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * MInt::<M>::from(N2::get_mod());
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .map(|((c1, c2), c3)| {
                let d1 = c1.inner();
                let d2 = ((c2 - MInt::<N2>::from(d1)) * t1).inner();
                let x = MInt::<N3>::new(d1) + MInt::<N3>::new(d2) * m1_3;
                let d3 = ((c3 - x) * t2).inner();
                MInt::<M>::from(d1) + MInt::<M>::from(d2) * m1 + MInt::<M>::from(d3) * m2
            })
            .collect()
    }

crates/competitive/src/math/factorial.rs (line 24)

    pub fn new(max_n: usize) -> Self {
        let mut fact = vec![MInt::one(); max_n + 1];
        let mut inv_fact = vec![MInt::one(); max_n + 1];
        for i in 2..=max_n {
            fact[i] = fact[i - 1] * MInt::from(i);
        }
        inv_fact[max_n] = fact[max_n].inv();
        for i in (3..=max_n).rev() {
            inv_fact[i - 1] = inv_fact[i] * MInt::from(i);
        }
        Self { fact, inv_fact }
    }
    #[inline]
    pub fn combination(&self, n: usize, r: usize) -> MInt<M> {
        debug_assert!(n < self.fact.len());
        if r <= n {
            self.fact[n] * self.inv_fact[r] * self.inv_fact[n - r]
        } else {
            MInt::zero()
        }
    }
    #[inline]
    pub fn permutation(&self, n: usize, r: usize) -> MInt<M> {
        debug_assert!(n < self.fact.len());
        if r <= n {
            self.fact[n] * self.inv_fact[n - r]
        } else {
            MInt::zero()
        }
    }
    #[inline]
    pub fn homogeneous_product(&self, n: usize, r: usize) -> MInt<M> {
        debug_assert!(n + r < self.fact.len() + 1);
        if n == 0 && r == 0 {
            MInt::one()
        } else {
            self.combination(n + r - 1, r)
        }
    }
    #[inline]
    pub fn inv(&self, n: usize) -> MInt<M> {
        debug_assert!(n < self.fact.len());
        debug_assert!(n > 0);
        self.inv_fact[n] * self.fact[n - 1]
    }
}

#[codesnip::entry("SmallModMemorizedFactorial", include("MIntBase", "prime_factors"))]
#[derive(Clone, Debug)]
pub struct SmallModMemorizedFactorial<M>
where
    M: MIntConvert<usize>,
{
    p: u32,
    c: u32,
    fact: Vec<MInt<M>>,
    inv_fact: Vec<MInt<M>>,
    pow: Vec<MInt<M>>,
}
#[codesnip::entry("SmallModMemorizedFactorial")]
impl<M> Default for SmallModMemorizedFactorial<M>
where
    M: MIntConvert<usize>,
{
    fn default() -> Self {
        let m = M::mod_into();
        let pf = prime_factors(m as _);
        assert!(pf.len() <= 1);
        let p = pf[0].0 as u32;
        let c = pf[0].1;
        let mut fact = vec![MInt::one(); m];
        let mut inv_fact = vec![MInt::one(); m];
        let mut pow = vec![MInt::one(); c as usize];
        for i in 2..m {
            fact[i] = fact[i - 1]
                * if i as u32 % p != 0 {
                    MInt::from(i)
                } else {
                    MInt::one()
                };
        }
        inv_fact[m - 1] = fact[m - 1].inv();
        for i in (3..m).rev() {
            inv_fact[i - 1] = inv_fact[i]
                * if i as u32 % p != 0 {
                    MInt::from(i)
                } else {
                    MInt::one()
                };
        }
        for i in 1..c as usize {
            pow[i] = pow[i - 1] * MInt::from(p as usize);
        }
        Self {
            p,
            c,
            fact,
            inv_fact,
            pow,
        }
    }

crates/library_checker/src/math/sum_of_totient_function.rs (line 19)

pub fn sum_of_totient_function(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n: u64);
    let mut s = 1;
    let mut pp = 0;
    let mut pc = 0;
    let inv2 = M::new(2).inv();
    let qa = QuotientArray::from_fn(n, |i| [M::from(i), M::from(i) * M::from(i + 1) * inv2])
        .map(|[x, y]| [x - M::one(), y - M::one()])
        .lucy_dp::<ArrayOperation<AdditiveOperation<_>, 2>>(|[x, y], p| [x, y * M::from(p)])
        .map(|[x, y]| y - x)
        .min_25_sieve::<AddMulOperation<_>>(|p, c| {
            if pp != p || pc > c {
                pp = p;
                pc = 1;
                s = p - 1;
            }
            while pc < c {
                pc += 1;
                s *= p;
            }
            M::from(s)
        });
    writeln!(writer, "{}", qa[n]).ok();
}

crates/competitive/src/math/lagrange_interpolation.rs (line 78)

pub fn lagrange_interpolation_polynomial<M>(x: &[MInt<M>], y: &[MInt<M>]) -> Vec<MInt<M>>
where
    M: MIntBase,
{
    let n = x.len() - 1;
    let mut dp = vec![MInt::zero(); n + 2];
    let mut ndp = vec![MInt::zero(); n + 2];
    dp[0] = -x[0];
    dp[1] = MInt::one();
    for x in x.iter().skip(1) {
        for j in 0..=n + 1 {
            ndp[j] = -dp[j] * x + if j >= 1 { dp[j - 1] } else { MInt::zero() };
        }
        std::mem::swap(&mut dp, &mut ndp);
    }
    let mut res = vec![MInt::zero(); n + 1];
    for i in 0..=n {
        let t = y[i]
            / (0..=n)
                .map(|j| if i != j { x[i] - x[j] } else { MInt::one() })
                .product::<MInt<M>>();
        if t.is_zero() {
            continue;
        } else if x[i].is_zero() {
            for j in 0..=n {
                res[j] += dp[j + 1] * t;
            }
        } else {
            let xinv = x[i].inv();
            let mut pre = MInt::zero();
            for j in 0..=n {
                let d = -(dp[j] - pre) * xinv;
                res[j] += d * t;
                pre = d;
            }
        }
    }
    res
}

pub fn inner(self) -> M::Inner

Examples found in repository

crates/competitive/src/num/mint/mint_base.rs (line 107)

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        Debug::fmt(&self.inner(), f)
    }
}
impl<M> Default for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn default() -> Self {
        <Self as Zero>::zero()
    }
}
impl<M> PartialEq for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        PartialEq::eq(&self.x, &other.x)
    }
}
impl<M> Eq for MInt<M> where M: MIntBase {}
impl<M> Hash for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&self.x, state)
    }
}
macro_rules! impl_mint_from {
    ($($t:ty),*) => {
        $(impl<M> From<$t> for MInt<M>
        where
            M: MIntConvert<$t>,
        {
            #[inline]
            fn from(x: $t) -> Self {
                Self::new_unchecked(<M as MIntConvert<$t>>::from(x))
            }
        }
        impl<M> From<MInt<M>> for $t
        where
            M: MIntConvert<$t>,
        {
            #[inline]
            fn from(x: MInt<M>) -> $t {
                <M as MIntConvert<$t>>::into(x.x)
            }
        })*
    };
}
impl_mint_from!(
    u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize
);
impl<M> Zero for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn zero() -> Self {
        Self::new_unchecked(M::mod_zero())
    }
}
impl<M> One for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn one() -> Self {
        Self::new_unchecked(M::mod_one())
    }
}

impl<M> Add for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn add(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_add(self.x, rhs.x))
    }
}
impl<M> Sub for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn sub(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_sub(self.x, rhs.x))
    }
}
impl<M> Mul for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn mul(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_mul(self.x, rhs.x))
    }
}
impl<M> Div for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn div(self, rhs: Self) -> Self::Output {
        Self::new_unchecked(M::mod_div(self.x, rhs.x))
    }
}
impl<M> Neg for MInt<M>
where
    M: MIntBase,
{
    type Output = Self;
    #[inline]
    fn neg(self) -> Self::Output {
        Self::new_unchecked(M::mod_neg(self.x))
    }
}
impl<M> Sum for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(<Self as Zero>::zero(), Add::add)
    }
}
impl<M> Product for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(<Self as One>::one(), Mul::mul)
    }
}
impl<'a, M: 'a> Sum<&'a MInt<M>> for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
        iter.fold(<Self as Zero>::zero(), Add::add)
    }
}
impl<'a, M: 'a> Product<&'a MInt<M>> for MInt<M>
where
    M: MIntBase,
{
    #[inline]
    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
        iter.fold(<Self as One>::one(), Mul::mul)
    }
}
impl<M> Display for MInt<M>
where
    M: MIntBase,
    M::Inner: Display,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
        write!(f, "{}", self.inner())
    }

crates/competitive/src/math/number_theoretic_transform.rs (line 355)

    fn transform(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(2).next_power_of_two();
        let mut f = (
            MVec::<N1>::with_capacity(npot),
            MVec::<N2>::with_capacity(npot),
            MVec::<N3>::with_capacity(npot),
        );
        for t in t {
            f.0.push(<M as MIntConvert<u32>>::into(t.inner()).into());
            f.1.push(<M as MIntConvert<u32>>::into(t.inner()).into());
            f.2.push(<M as MIntConvert<u32>>::into(t.inner()).into());
        }
        f.0.resize_with(npot, Zero::zero);
        f.1.resize_with(npot, Zero::zero);
        f.2.resize_with(npot, Zero::zero);
        ntt(&mut f.0);
        ntt(&mut f.1);
        ntt(&mut f.2);
        f
    }
    fn inverse_transform(f: Self::F, len: usize) -> Self::T {
        let t1 = MInt::<N2>::new(N1::get_mod()).inv();
        let m1 = MInt::<M>::from(N1::get_mod());
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * MInt::<M>::from(N2::get_mod());
        Convolve::<N1>::inverse_transform(f.0, len)
            .into_iter()
            .zip(Convolve::<N2>::inverse_transform(f.1, len))
            .zip(Convolve::<N3>::inverse_transform(f.2, len))
            .map(|((c1, c2), c3)| {
                let d1 = c1.inner();
                let d2 = ((c2 - MInt::<N2>::from(d1)) * t1).inner();
                let x = MInt::<N3>::new(d1) + MInt::<N3>::new(d2) * m1_3;
                let d3 = ((c3 - x) * t2).inner();
                MInt::<M>::from(d1) + MInt::<M>::from(d2) * m1 + MInt::<M>::from(d3) * m2
            })
            .collect()
    }

impl MInt<DynModuloU32>

pub fn set_mod(m: u32)

Examples found in repository

crates/library_checker/src/math/sqrt_mod.rs (line 11)

pub fn sqrt_mod(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, q, yp: [(u32, u32)]);
    for (y, p) in yp.take(q) {
        DynMIntU32::set_mod(p);
        if let Some(x) = DynMIntU32::from(y).sqrt() {
            writeln!(writer, "{}", x).ok();
        } else {
            writeln!(writer, "-1").ok();
        }
    }
}

impl MInt<DynModuloU64>

pub fn set_mod(m: u64)

Trait Implementations

impl<M> Add<&MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Add>::Output

The resulting type after applying the + operator.

fn add(self, other: &MInt<M>) -> <MInt<M> as Add<MInt<M>>>::Output

Performs the + operation.

impl<M> Add<&MInt<M>> for MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Add>::Output

The resulting type after applying the + operator.

fn add(self, other: &MInt<M>) -> <MInt<M> as Add<MInt<M>>>::Output

Performs the + operation.

impl<M> Add<MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Add>::Output

The resulting type after applying the + operator.

fn add(self, other: MInt<M>) -> <MInt<M> as Add<MInt<M>>>::Output

Performs the + operation.

impl<M> Add for MInt<M>

where M: MIntBase,

type Output = MInt<M>

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self::Output

Performs the + operation.

impl<M> AddAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

fn add_assign(&mut self, other: &MInt<M>)

Performs the += operation.

impl<M> AddAssign for MInt<M>

where M: MIntBase,

fn add_assign(&mut self, rhs: MInt<M>)

Performs the += operation.

impl<M> Clone for MInt<M>

where M: MIntBase,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<M> Debug for MInt<M>

where M: MIntBase,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<M> Default for MInt<M>

where M: MIntBase,

fn default() -> Self

Returns the “default value” for a type.

impl<M> Display for MInt<M>

where M: MIntBase, M::Inner: Display,

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl<M> Div<&MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Div>::Output

The resulting type after applying the / operator.

fn div(self, other: &MInt<M>) -> <MInt<M> as Div<MInt<M>>>::Output

Performs the / operation.

impl<M> Div<&MInt<M>> for MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Div>::Output

The resulting type after applying the / operator.

fn div(self, other: &MInt<M>) -> <MInt<M> as Div<MInt<M>>>::Output

Performs the / operation.

impl<M> Div<MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Div>::Output

The resulting type after applying the / operator.

fn div(self, other: MInt<M>) -> <MInt<M> as Div<MInt<M>>>::Output

Performs the / operation.

impl<M> Div for MInt<M>

where M: MIntBase,

type Output = MInt<M>

The resulting type after applying the / operator.

fn div(self, rhs: Self) -> Self::Output

Performs the / operation.

impl<M> DivAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

fn div_assign(&mut self, other: &MInt<M>)

Performs the /= operation.

impl<M> DivAssign for MInt<M>

where M: MIntBase,

fn div_assign(&mut self, rhs: MInt<M>)

Performs the /= operation.

impl<M> FormalPowerSeriesCoefficientSqrt for MInt<M>

where M: MIntConvert<u32> + MIntConvert<usize>,

fn sqrt_coefficient(&self) -> Option<Self>

impl<M> From<MInt<M>> for i128

where M: MIntConvert<i128>,

fn from(x: MInt<M>) -> i128

Converts to this type from the input type.

impl<M> From<MInt<M>> for i16

where M: MIntConvert<i16>,

fn from(x: MInt<M>) -> i16

Converts to this type from the input type.

impl<M> From<MInt<M>> for i32

where M: MIntConvert<i32>,

fn from(x: MInt<M>) -> i32

Converts to this type from the input type.

impl<M> From<MInt<M>> for i64

where M: MIntConvert<i64>,

fn from(x: MInt<M>) -> i64

Converts to this type from the input type.

impl<M> From<MInt<M>> for i8

where M: MIntConvert<i8>,

fn from(x: MInt<M>) -> i8

Converts to this type from the input type.

impl<M> From<MInt<M>> for isize

where M: MIntConvert<isize>,

fn from(x: MInt<M>) -> isize

Converts to this type from the input type.

impl<M> From<MInt<M>> for u128

where M: MIntConvert<u128>,

fn from(x: MInt<M>) -> u128

Converts to this type from the input type.

impl<M> From<MInt<M>> for u16

where M: MIntConvert<u16>,

fn from(x: MInt<M>) -> u16

Converts to this type from the input type.

impl<M> From<MInt<M>> for u32

where M: MIntConvert<u32>,

fn from(x: MInt<M>) -> u32

Converts to this type from the input type.

impl<M> From<MInt<M>> for u64

where M: MIntConvert<u64>,

fn from(x: MInt<M>) -> u64

Converts to this type from the input type.

impl<M> From<MInt<M>> for u8

where M: MIntConvert<u8>,

fn from(x: MInt<M>) -> u8

Converts to this type from the input type.

impl<M> From<MInt<M>> for usize

where M: MIntConvert<usize>,

fn from(x: MInt<M>) -> usize

Converts to this type from the input type.

impl<M> From<i128> for MInt<M>

where M: MIntConvert<i128>,

fn from(x: i128) -> Self

Converts to this type from the input type.

impl<M> From<i16> for MInt<M>

where M: MIntConvert<i16>,

fn from(x: i16) -> Self

Converts to this type from the input type.

impl<M> From<i32> for MInt<M>

where M: MIntConvert<i32>,

fn from(x: i32) -> Self

Converts to this type from the input type.

impl<M> From<i64> for MInt<M>

where M: MIntConvert<i64>,

fn from(x: i64) -> Self

Converts to this type from the input type.

impl<M> From<i8> for MInt<M>

where M: MIntConvert<i8>,

fn from(x: i8) -> Self

Converts to this type from the input type.

impl<M> From<isize> for MInt<M>

where M: MIntConvert<isize>,

fn from(x: isize) -> Self

Converts to this type from the input type.

impl<M> From<u128> for MInt<M>

where M: MIntConvert<u128>,

fn from(x: u128) -> Self

Converts to this type from the input type.

impl<M> From<u16> for MInt<M>

where M: MIntConvert<u16>,

fn from(x: u16) -> Self

Converts to this type from the input type.

impl<M> From<u32> for MInt<M>

where M: MIntConvert<u32>,

fn from(x: u32) -> Self

Converts to this type from the input type.

impl<M> From<u64> for MInt<M>

where M: MIntConvert<u64>,

fn from(x: u64) -> Self

Converts to this type from the input type.

impl<M> From<u8> for MInt<M>

where M: MIntConvert<u8>,

fn from(x: u8) -> Self

Converts to this type from the input type.

impl<M> From<usize> for MInt<M>

where M: MIntConvert<usize>,

fn from(x: usize) -> Self

Converts to this type from the input type.

impl<M> FromStr for MInt<M>

where M: MIntConvert, M::Inner: FromStr,

type Err = <<M as MIntBase>::Inner as FromStr>::Err

The associated error which can be returned from parsing.

fn from_str(s: &str) -> Result<Self, Self::Err>

Parses a string s to return a value of this type.

impl<M> Hash for MInt<M>

where M: MIntBase,

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<M> IterScan for MInt<M>

where M: MIntConvert, M::Inner: FromStr,

type Output = MInt<M>

fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output>

impl<M> Mul<&MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Mul>::Output

The resulting type after applying the * operator.

fn mul(self, other: &MInt<M>) -> <MInt<M> as Mul<MInt<M>>>::Output

Performs the * operation.

impl<M> Mul<&MInt<M>> for MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Mul>::Output

The resulting type after applying the * operator.

fn mul(self, other: &MInt<M>) -> <MInt<M> as Mul<MInt<M>>>::Output

Performs the * operation.

impl<M> Mul<MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Mul>::Output

The resulting type after applying the * operator.

fn mul(self, other: MInt<M>) -> <MInt<M> as Mul<MInt<M>>>::Output

Performs the * operation.

impl<M> Mul for MInt<M>

where M: MIntBase,

type Output = MInt<M>

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation.

impl<M> MulAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

fn mul_assign(&mut self, other: &MInt<M>)

Performs the *= operation.

impl<M> MulAssign for MInt<M>

where M: MIntBase,

fn mul_assign(&mut self, rhs: MInt<M>)

Performs the *= operation.

impl<M> Neg for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Neg>::Output

The resulting type after applying the - operator.

fn neg(self) -> <MInt<M> as Neg>::Output

Performs the unary - operation.

impl<M> Neg for MInt<M>

where M: MIntBase,

type Output = MInt<M>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<M> One for MInt<M>

where M: MIntBase,

fn one() -> Self

fn is_one(&self) -> bool

where Self: PartialEq,

fn set_one(&mut self)

impl<M> PartialEq for MInt<M>

where M: MIntBase,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, M> Product<&'a MInt<M>> for MInt<M>

where M: MIntBase + 'a,

fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by multiplying the items.

impl<M> Product for MInt<M>

where M: MIntBase,

fn product<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by multiplying the items.

impl<M> Sub<&MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Sub>::Output

The resulting type after applying the - operator.

fn sub(self, other: &MInt<M>) -> <MInt<M> as Sub<MInt<M>>>::Output

Performs the - operation.

impl<M> Sub<&MInt<M>> for MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Sub>::Output

The resulting type after applying the - operator.

fn sub(self, other: &MInt<M>) -> <MInt<M> as Sub<MInt<M>>>::Output

Performs the - operation.

impl<M> Sub<MInt<M>> for &MInt<M>

where M: MIntBase,

type Output = <MInt<M> as Sub>::Output

The resulting type after applying the - operator.

fn sub(self, other: MInt<M>) -> <MInt<M> as Sub<MInt<M>>>::Output

Performs the - operation.

impl<M> Sub for MInt<M>

where M: MIntBase,

type Output = MInt<M>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation.

impl<M> SubAssign<&MInt<M>> for MInt<M>

where M: MIntBase,

fn sub_assign(&mut self, other: &MInt<M>)

Performs the -= operation.

impl<M> SubAssign for MInt<M>

where M: MIntBase,

fn sub_assign(&mut self, rhs: MInt<M>)

Performs the -= operation.

impl<'a, M> Sum<&'a MInt<M>> for MInt<M>

where M: MIntBase + 'a,

fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by “summing up” the items.

impl<M> Sum for MInt<M>

where M: MIntBase,

fn sum<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by “summing up” the items.

impl<M> Zero for MInt<M>

where M: MIntBase,

fn zero() -> Self

fn is_zero(&self) -> bool

where Self: PartialEq,

fn set_zero(&mut self)

impl<M> Copy for MInt<M>

where M: MIntBase,

impl<M> Eq for MInt<M>

where M: MIntBase,

impl<M> FormalPowerSeriesCoefficient for MInt<M>

where M: MIntConvert<usize>,