Struct MInt 

#[repr(transparent)]
pub struct MInt<M>
where
    M: MIntBase,
{
    x: M::Inner,
    _marker: PhantomData<fn() -> M>,
}

Fields

x: M::Inner

_marker: PhantomData<fn() -> M>

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 84)

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

crates/library_checker/src/number_theory/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/number_theory/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 427)

    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()
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }
    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        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 mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

impl<N1, N2, N3> ConvolveSteps for Convolve<(u64, (N1, N2, N3))>
where
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    type T = Vec<u64>;
    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(1).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(t.into());
            f.1.push(t.into());
            f.2.push(t.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 = N1::get_mod() as u64;
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * N2::get_mod() as u64;
        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();
                d1 as u64 + d2 as u64 * m1 + d3 as u64 * m2
            })
            .collect()
    }

    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }

    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        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 mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

pub trait NttReuse: ConvolveSteps {
    const MULTIPLE: bool = true;

    /// F(a) → F(a + [0] * a.len())
    fn ntt_doubling(f: Self::F) -> Self::F;

    /// F(a(x)), F(b(x)) → even(F(a(x) * b(-x)))
    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;

    /// F(a(x)), F(b(x)) → odd(F(a(x) * b(-x)))
    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;
}

thread_local!(
    static BIT_REVERSE: UnsafeCell<Vec<Vec<usize>>> = const { UnsafeCell::new(vec![]) };
);

impl<M> NttReuse for Convolve<M>
where
    M: Montgomery32NttModulus,
{
    const MULTIPLE: bool = false;

    fn ntt_doubling(mut f: Self::F) -> Self::F {
        let n = f.len();
        let k = n.trailing_zeros() as usize;
        let mut a = Self::inverse_transform(f.clone(), n);
        let mut rot = MInt::<M>::one();
        let zeta = MInt::<M>::new_unchecked(M::INFO.root[k + 1]);
        for a in a.iter_mut() {
            *a *= rot;
            rot *= zeta;
        }
        f.extend(Self::transform(a, n));
        f
    }

    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        assert_eq!(f.len(), g.len());
        assert!(f.len().is_power_of_two());
        assert!(f.len() >= 2);
        let inv2 = MInt::<M>::from(2).inv();
        let n = f.len() / 2;
        (0..n)
            .map(|i| (f[i << 1] * g[i << 1 | 1] + f[i << 1 | 1] * g[i << 1]) * inv2)
            .collect()
    }

    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        assert_eq!(f.len(), g.len());
        assert!(f.len().is_power_of_two());
        assert!(f.len() >= 2);
        let mut inv2 = MInt::<M>::from(2).inv();
        let n = f.len() / 2;
        let k = f.len().trailing_zeros() as usize;
        let mut h = vec![MInt::<M>::zero(); n];
        let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
        BIT_REVERSE.with(|br| {
            let br = unsafe { &mut *br.get() };
            if br.len() < k {
                br.resize_with(k, Default::default);
            }
            let k = k - 1;
            if br[k].is_empty() {
                let mut v = vec![0; 1 << k];
                for i in 0..1 << k {
                    v[i] = (v[i >> 1] >> 1) | ((i & 1) << (k.saturating_sub(1)));
                }
                br[k] = v;
            }
            for &i in &br[k] {
                h[i] = (f[i << 1] * g[i << 1 | 1] - f[i << 1 | 1] * g[i << 1]) * inv2;
                inv2 *= w;
            }
        });
        h
    }
}

impl<M, N1, N2, N3> NttReuse for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    fn ntt_doubling(f: Self::F) -> Self::F {
        (
            Convolve::<N1>::ntt_doubling(f.0),
            Convolve::<N2>::ntt_doubling(f.1),
            Convolve::<N3>::ntt_doubling(f.2),
        )
    }

    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        fn even_mul_normal_neg_corrected<M>(f: &[MInt<M>], g: &[MInt<M>], m: u32) -> Vec<MInt<M>>
        where
            M: Montgomery32NttModulus,
        {
            let n = f.len();
            assert_eq!(f.len(), g.len());
            assert!(f.len().is_power_of_two());
            assert!(f.len() >= 2);
            let inv2 = MInt::<M>::from(2).inv();
            let u = MInt::<M>::new(m) * MInt::<M>::from(n as u32);
            let n = f.len() / 2;
            (0..n)
                .map(|i| {
                    (f[i << 1]
                        * if i == 0 {
                            g[i << 1 | 1] + u
                        } else {
                            g[i << 1 | 1]
                        }
                        + f[i << 1 | 1] * g[i << 1])
                        * inv2
                })
                .collect()
        }

        let m = M::mod_into();
        (
            even_mul_normal_neg_corrected(&f.0, &g.0, m),
            even_mul_normal_neg_corrected(&f.1, &g.1, m),
            even_mul_normal_neg_corrected(&f.2, &g.2, m),
        )
    }

    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        fn odd_mul_normal_neg_corrected<M>(f: &[MInt<M>], g: &[MInt<M>], m: u32) -> Vec<MInt<M>>
        where
            M: Montgomery32NttModulus,
        {
            assert_eq!(f.len(), g.len());
            assert!(f.len().is_power_of_two());
            assert!(f.len() >= 2);
            let mut inv2 = MInt::<M>::from(2).inv();
            let u = MInt::<M>::new(m) * MInt::<M>::from(f.len() as u32);
            let n = f.len() / 2;
            let k = f.len().trailing_zeros() as usize;
            let mut h = vec![MInt::<M>::zero(); n];
            let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
            BIT_REVERSE.with(|br| {
                let br = unsafe { &mut *br.get() };
                if br.len() < k {
                    br.resize_with(k, Default::default);
                }
                let k = k - 1;
                if br[k].is_empty() {
                    let mut v = vec![0; 1 << k];
                    for i in 0..1 << k {
                        v[i] = (v[i >> 1] >> 1) | ((i & 1) << (k.saturating_sub(1)));
                    }
                    br[k] = v;
                }
                for &i in &br[k] {
                    h[i] = (f[i << 1]
                        * if i == 0 {
                            g[i << 1 | 1] + u
                        } else {
                            g[i << 1 | 1]
                        }
                        - f[i << 1 | 1] * g[i << 1])
                        * inv2;
                    inv2 *= w;
                }
            });
            h
        }

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))
    }
}
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<Inner: Display>,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
        write!(f, "{}", self.inner())
    }
}
impl<M> FromStr for MInt<M>
where
    M: MIntConvert + MIntBase<Inner: FromStr>,
{
    type Err = <M::Inner as FromStr>::Err;
    #[inline]
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        s.parse::<M::Inner>().map(Self::new)
    }
}
impl<M> IterScan for MInt<M>
where
    M: MIntConvert + MIntBase<Inner: FromStr>,
{
    type Output = Self;
    #[inline]
    fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
        iter.next()?.parse::<MInt<M>>().ok()
    }
}
impl<M> SerdeByteStr for MInt<M>
where
    M: MIntBase<Inner: SerdeByteStr>,
{
    fn serialize(&self, buf: &mut Vec<u8>) {
        self.inner().serialize(buf)
    }

    fn deserialize<I>(iter: &mut I) -> Self
    where
        I: Iterator<Item = u8>,
    {
        Self::new_unchecked(M::Inner::deserialize(iter))
    }

crates/competitive/src/num/mint/mod.rs (line 34)

        fn rand(&self, rng: &mut Xorshift) -> MInt<M> {
            MInt::<M>::new_unchecked(rng.random(..M::get_mod()))
        }

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

    fn ntt_doubling(mut f: Self::F) -> Self::F {
        let n = f.len();
        let k = n.trailing_zeros() as usize;
        let mut a = Self::inverse_transform(f.clone(), n);
        let mut rot = MInt::<M>::one();
        let zeta = MInt::<M>::new_unchecked(M::INFO.root[k + 1]);
        for a in a.iter_mut() {
            *a *= rot;
            rot *= zeta;
        }
        f.extend(Self::transform(a, n));
        f
    }

    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        assert_eq!(f.len(), g.len());
        assert!(f.len().is_power_of_two());
        assert!(f.len() >= 2);
        let inv2 = MInt::<M>::from(2).inv();
        let n = f.len() / 2;
        (0..n)
            .map(|i| (f[i << 1] * g[i << 1 | 1] + f[i << 1 | 1] * g[i << 1]) * inv2)
            .collect()
    }

    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        assert_eq!(f.len(), g.len());
        assert!(f.len().is_power_of_two());
        assert!(f.len() >= 2);
        let mut inv2 = MInt::<M>::from(2).inv();
        let n = f.len() / 2;
        let k = f.len().trailing_zeros() as usize;
        let mut h = vec![MInt::<M>::zero(); n];
        let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
        BIT_REVERSE.with(|br| {
            let br = unsafe { &mut *br.get() };
            if br.len() < k {
                br.resize_with(k, Default::default);
            }
            let k = k - 1;
            if br[k].is_empty() {
                let mut v = vec![0; 1 << k];
                for i in 0..1 << k {
                    v[i] = (v[i >> 1] >> 1) | ((i & 1) << (k.saturating_sub(1)));
                }
                br[k] = v;
            }
            for &i in &br[k] {
                h[i] = (f[i << 1] * g[i << 1 | 1] - f[i << 1 | 1] * g[i << 1]) * inv2;
                inv2 *= w;
            }
        });
        h
    }
}

impl<M, N1, N2, N3> NttReuse for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    fn ntt_doubling(f: Self::F) -> Self::F {
        (
            Convolve::<N1>::ntt_doubling(f.0),
            Convolve::<N2>::ntt_doubling(f.1),
            Convolve::<N3>::ntt_doubling(f.2),
        )
    }

    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        fn even_mul_normal_neg_corrected<M>(f: &[MInt<M>], g: &[MInt<M>], m: u32) -> Vec<MInt<M>>
        where
            M: Montgomery32NttModulus,
        {
            let n = f.len();
            assert_eq!(f.len(), g.len());
            assert!(f.len().is_power_of_two());
            assert!(f.len() >= 2);
            let inv2 = MInt::<M>::from(2).inv();
            let u = MInt::<M>::new(m) * MInt::<M>::from(n as u32);
            let n = f.len() / 2;
            (0..n)
                .map(|i| {
                    (f[i << 1]
                        * if i == 0 {
                            g[i << 1 | 1] + u
                        } else {
                            g[i << 1 | 1]
                        }
                        + f[i << 1 | 1] * g[i << 1])
                        * inv2
                })
                .collect()
        }

        let m = M::mod_into();
        (
            even_mul_normal_neg_corrected(&f.0, &g.0, m),
            even_mul_normal_neg_corrected(&f.1, &g.1, m),
            even_mul_normal_neg_corrected(&f.2, &g.2, m),
        )
    }

    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        fn odd_mul_normal_neg_corrected<M>(f: &[MInt<M>], g: &[MInt<M>], m: u32) -> Vec<MInt<M>>
        where
            M: Montgomery32NttModulus,
        {
            assert_eq!(f.len(), g.len());
            assert!(f.len().is_power_of_two());
            assert!(f.len() >= 2);
            let mut inv2 = MInt::<M>::from(2).inv();
            let u = MInt::<M>::new(m) * MInt::<M>::from(f.len() as u32);
            let n = f.len() / 2;
            let k = f.len().trailing_zeros() as usize;
            let mut h = vec![MInt::<M>::zero(); n];
            let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
            BIT_REVERSE.with(|br| {
                let br = unsafe { &mut *br.get() };
                if br.len() < k {
                    br.resize_with(k, Default::default);
                }
                let k = k - 1;
                if br[k].is_empty() {
                    let mut v = vec![0; 1 << k];
                    for i in 0..1 << k {
                        v[i] = (v[i >> 1] >> 1) | ((i & 1) << (k.saturating_sub(1)));
                    }
                    br[k] = v;
                }
                for &i in &br[k] {
                    h[i] = (f[i << 1]
                        * if i == 0 {
                            g[i << 1 | 1] + u
                        } else {
                            g[i << 1 | 1]
                        }
                        - f[i << 1 | 1] * g[i << 1])
                        * inv2;
                    inv2 *= w;
                }
            });
            h
        }

pub fn get_mod() -> M::Inner

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

Examples found in repository

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

    fn pow(self, exp: usize) -> Self {
        Self::pow(self, exp)
    }

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

    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 341)

    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
        intt(&mut f);
        f.truncate(len);
        let inv = MInt::from(len.max(1).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).max(Self::length(&b)) <= 100 {
            return convolve_karatsuba(&a, &b);
        }
        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(1).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(1).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()
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }
    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        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 mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

impl<N1, N2, N3> ConvolveSteps for Convolve<(u64, (N1, N2, N3))>
where
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    type T = Vec<u64>;
    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(1).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(t.into());
            f.1.push(t.into());
            f.2.push(t.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 = N1::get_mod() as u64;
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * N2::get_mod() as u64;
        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();
                d1 as u64 + d2 as u64 * m1 + d3 as u64 * m2
            })
            .collect()
    }

    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }

    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        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 mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

pub trait NttReuse: ConvolveSteps {
    const MULTIPLE: bool = true;

    /// F(a) → F(a + [0] * a.len())
    fn ntt_doubling(f: Self::F) -> Self::F;

    /// F(a(x)), F(b(x)) → even(F(a(x) * b(-x)))
    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;

    /// F(a(x)), F(b(x)) → odd(F(a(x) * b(-x)))
    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F;
}

thread_local!(
    static BIT_REVERSE: UnsafeCell<Vec<Vec<usize>>> = const { UnsafeCell::new(vec![]) };
);

impl<M> NttReuse for Convolve<M>
where
    M: Montgomery32NttModulus,
{
    const MULTIPLE: bool = false;

    fn ntt_doubling(mut f: Self::F) -> Self::F {
        let n = f.len();
        let k = n.trailing_zeros() as usize;
        let mut a = Self::inverse_transform(f.clone(), n);
        let mut rot = MInt::<M>::one();
        let zeta = MInt::<M>::new_unchecked(M::INFO.root[k + 1]);
        for a in a.iter_mut() {
            *a *= rot;
            rot *= zeta;
        }
        f.extend(Self::transform(a, n));
        f
    }

    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        assert_eq!(f.len(), g.len());
        assert!(f.len().is_power_of_two());
        assert!(f.len() >= 2);
        let inv2 = MInt::<M>::from(2).inv();
        let n = f.len() / 2;
        (0..n)
            .map(|i| (f[i << 1] * g[i << 1 | 1] + f[i << 1 | 1] * g[i << 1]) * inv2)
            .collect()
    }

    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        assert_eq!(f.len(), g.len());
        assert!(f.len().is_power_of_two());
        assert!(f.len() >= 2);
        let mut inv2 = MInt::<M>::from(2).inv();
        let n = f.len() / 2;
        let k = f.len().trailing_zeros() as usize;
        let mut h = vec![MInt::<M>::zero(); n];
        let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
        BIT_REVERSE.with(|br| {
            let br = unsafe { &mut *br.get() };
            if br.len() < k {
                br.resize_with(k, Default::default);
            }
            let k = k - 1;
            if br[k].is_empty() {
                let mut v = vec![0; 1 << k];
                for i in 0..1 << k {
                    v[i] = (v[i >> 1] >> 1) | ((i & 1) << (k.saturating_sub(1)));
                }
                br[k] = v;
            }
            for &i in &br[k] {
                h[i] = (f[i << 1] * g[i << 1 | 1] - f[i << 1 | 1] * g[i << 1]) * inv2;
                inv2 *= w;
            }
        });
        h
    }
}

impl<M, N1, N2, N3> NttReuse for Convolve<(M, (N1, N2, N3))>
where
    M: MIntConvert + MIntConvert<u32>,
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    fn ntt_doubling(f: Self::F) -> Self::F {
        (
            Convolve::<N1>::ntt_doubling(f.0),
            Convolve::<N2>::ntt_doubling(f.1),
            Convolve::<N3>::ntt_doubling(f.2),
        )
    }

    fn even_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        fn even_mul_normal_neg_corrected<M>(f: &[MInt<M>], g: &[MInt<M>], m: u32) -> Vec<MInt<M>>
        where
            M: Montgomery32NttModulus,
        {
            let n = f.len();
            assert_eq!(f.len(), g.len());
            assert!(f.len().is_power_of_two());
            assert!(f.len() >= 2);
            let inv2 = MInt::<M>::from(2).inv();
            let u = MInt::<M>::new(m) * MInt::<M>::from(n as u32);
            let n = f.len() / 2;
            (0..n)
                .map(|i| {
                    (f[i << 1]
                        * if i == 0 {
                            g[i << 1 | 1] + u
                        } else {
                            g[i << 1 | 1]
                        }
                        + f[i << 1 | 1] * g[i << 1])
                        * inv2
                })
                .collect()
        }

        let m = M::mod_into();
        (
            even_mul_normal_neg_corrected(&f.0, &g.0, m),
            even_mul_normal_neg_corrected(&f.1, &g.1, m),
            even_mul_normal_neg_corrected(&f.2, &g.2, m),
        )
    }

    fn odd_mul_normal_neg(f: &Self::F, g: &Self::F) -> Self::F {
        fn odd_mul_normal_neg_corrected<M>(f: &[MInt<M>], g: &[MInt<M>], m: u32) -> Vec<MInt<M>>
        where
            M: Montgomery32NttModulus,
        {
            assert_eq!(f.len(), g.len());
            assert!(f.len().is_power_of_two());
            assert!(f.len() >= 2);
            let mut inv2 = MInt::<M>::from(2).inv();
            let u = MInt::<M>::new(m) * MInt::<M>::from(f.len() as u32);
            let n = f.len() / 2;
            let k = f.len().trailing_zeros() as usize;
            let mut h = vec![MInt::<M>::zero(); n];
            let w = MInt::<M>::new_unchecked(M::INFO.inv_root[k]);
            BIT_REVERSE.with(|br| {
                let br = unsafe { &mut *br.get() };
                if br.len() < k {
                    br.resize_with(k, Default::default);
                }
                let k = k - 1;
                if br[k].is_empty() {
                    let mut v = vec![0; 1 << k];
                    for i in 0..1 << k {
                        v[i] = (v[i >> 1] >> 1) | ((i & 1) << (k.saturating_sub(1)));
                    }
                    br[k] = v;
                }
                for &i in &br[k] {
                    h[i] = (f[i << 1]
                        * if i == 0 {
                            g[i << 1 | 1] + u
                        } else {
                            g[i << 1 | 1]
                        }
                        - f[i << 1 | 1] * g[i << 1])
                        * inv2;
                    inv2 *= w;
                }
            });
            h
        }

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

    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 }
    }

crates/competitive/src/math/black_box_matrix.rs (line 290)

    fn black_box_linear_equation(&self, mut b: Vec<MInt<M>>) -> Option<Vec<MInt<M>>>
    where
        M: MIntConvert<u64>,
    {
        assert_eq!(self.shape().0, self.shape().1);
        assert_eq!(self.shape().1, b.len());
        let n = self.shape().0;
        let p = self.minimal_polynomial();
        if p.is_empty() || p[0].is_zero() {
            return None;
        }
        let p0_inv = p[0].inv();
        let mut x = vec![MInt::zero(); n];
        for p in p.into_iter().skip(1) {
            let p = -p * p0_inv;
            for i in 0..n {
                x[i] += p * b[i];
            }
            b = self.apply(&b);
        }
        Some(x)
    }

crates/library_checker/src/number_theory/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
}

crates/competitive/src/math/mint_matrix.rs (line 55)

    fn determinant_linear_non_singular(mut self, mut other: Self) -> Option<Vec<MInt<M>>>
    where
        M: MIntBase,
    {
        let n = self.data.len();
        let mut f = MInt::one();
        for d in 0..n {
            let i = other.data.iter().position(|other| !other[d].is_zero())?;
            if i != d {
                self.data.swap(i, d);
                other.data.swap(i, d);
                f = -f;
            }
            f *= other[d][d];
            let r = other[d][d].inv();
            for j in 0..n {
                self[d][j] *= r;
                other[d][j] *= r;
            }
            assert!(other[d][d].is_one());
            for i in d + 1..n {
                let a = other[i][d];
                for k in 0..n {
                    self[i][k] = self[i][k] - a * self[d][k];
                    other[i][k] = other[i][k] - a * other[d][k];
                }
            }
            for j in d + 1..n {
                let a = other[d][j];
                for k in 0..n {
                    self[k][j] = self[k][j] - a * self[k][d];
                    other[k][j] = other[k][j] - a * other[k][d];
                }
            }
        }
        for s in self.data.iter_mut() {
            for s in s.iter_mut() {
                *s = -*s;
            }
        }
        let mut p = self.characteristic_polynomial();
        for p in p.iter_mut() {
            *p *= f;
        }
        Some(p)
    }

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<Inner: Display>,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
        write!(f, "{}", self.inner())
    }
}
impl<M> FromStr for MInt<M>
where
    M: MIntConvert + MIntBase<Inner: FromStr>,
{
    type Err = <M::Inner as FromStr>::Err;
    #[inline]
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        s.parse::<M::Inner>().map(Self::new)
    }
}
impl<M> IterScan for MInt<M>
where
    M: MIntConvert + MIntBase<Inner: FromStr>,
{
    type Output = Self;
    #[inline]
    fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
        iter.next()?.parse::<MInt<M>>().ok()
    }
}
impl<M> SerdeByteStr for MInt<M>
where
    M: MIntBase<Inner: SerdeByteStr>,
{
    fn serialize(&self, buf: &mut Vec<u8>) {
        self.inner().serialize(buf)
    }

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

    fn transform(t: Self::T, len: usize) -> Self::F {
        let npot = len.max(1).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()
    }
    fn multiply(f: &mut Self::F, g: &Self::F) {
        assert_eq!(f.0.len(), g.0.len());
        assert_eq!(f.1.len(), g.1.len());
        assert_eq!(f.2.len(), g.2.len());
        for (f, g) in f.0.iter_mut().zip(g.0.iter()) {
            *f *= *g;
        }
        for (f, g) in f.1.iter_mut().zip(g.1.iter()) {
            *f *= *g;
        }
        for (f, g) in f.2.iter_mut().zip(g.2.iter()) {
            *f *= *g;
        }
    }
    fn convolve(a: Self::T, b: Self::T) -> Self::T {
        if Self::length(&a).max(Self::length(&b)) <= 300 {
            return convolve_karatsuba(&a, &b);
        }
        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 mut a = Self::transform(a, len);
        let b = Self::transform(b, len);
        Self::multiply(&mut a, &b);
        Self::inverse_transform(a, len)
    }
}

impl<N1, N2, N3> ConvolveSteps for Convolve<(u64, (N1, N2, N3))>
where
    N1: Montgomery32NttModulus,
    N2: Montgomery32NttModulus,
    N3: Montgomery32NttModulus,
{
    type T = Vec<u64>;
    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(1).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(t.into());
            f.1.push(t.into());
            f.2.push(t.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 = N1::get_mod() as u64;
        let m1_3 = MInt::<N3>::new(N1::get_mod());
        let t2 = (m1_3 * MInt::<N3>::new(N2::get_mod())).inv();
        let m2 = m1 * N2::get_mod() as u64;
        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();
                d1 as u64 + d2 as u64 * m1 + d3 as u64 * m2
            })
            .collect()
    }

impl MInt<DynModuloU32>

pub fn set_mod(m: u32)

Examples found in repository

crates/library_checker/src/number_theory/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<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> FormalPowerSeriesCoefficient for MInt<M>

where M: MIntConvert<usize>,

type Base = M

fn pow(self, exp: usize) -> Self

fn memorized_inv(mf: &MemorizedFactorial<Self::Base>, n: usize) -> Self

fn memorized_factorial(n: usize) -> MemorizedFactorial<Self::Base>

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 + MIntBase<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 + MIntBase<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> RandomSpec<MInt<M>> for RangeFull

where M: MIntBase, RangeTo<M::Inner>: RandomSpec<M::Inner>,

fn rand(&self, rng: &mut Xorshift) -> MInt<M>

Return a random value.

fn rand_iter(self, rng: &mut Xorshift) -> RandIter<'_, T, Self>

Return an iterator that generates random values.

impl<M> SerdeByteStr for MInt<M>

where M: MIntBase<Inner: SerdeByteStr>,

fn serialize(&self, buf: &mut Vec<u8>)

fn deserialize<I>(iter: &mut I) -> Self

where I: Iterator<Item = u8>,

fn serialize_bytestr(&self) -> String

fn deserialize_from_bytes(bytes: &[u8]) -> Self

where Self: Sized,

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,