Trait ModIntBase

pub trait ModIntBase:
    Default
    + FromStr
    + From<i8>
    + From<i16>
    + From<i32>
    + From<i64>
    + From<i128>
    + From<isize>
    + From<u8>
    + From<u16>
    + From<u32>
    + From<u64>
    + From<u128>
    + From<usize>
    + Copy
    + Eq
    + Hash
    + Display
    + Debug
    + Neg<Output = Self>
    + Add<Output = Self>
    + Sub<Output = Self>
    + Mul<Output = Self>
    + Div<Output = Self>
    + AddAssign
    + SubAssign
    + MulAssign
    + DivAssign {
    // Required methods
    fn modulus() -> u32;
    fn raw(val: u32) -> Self;
    fn val(self) -> u32;
    fn inv(self) -> Self;

    // Provided methods
    fn new<T: RemEuclidU32>(val: T) -> Self { ... }
    fn pow(self, n: u64) -> Self { ... }
}

A trait for StaticModInt and DynamicModInt.

Corresponds to atcoder::internal::modint_base in the original ACL.

Required Methods

fn modulus() -> u32

Returns the modulus.

Corresponds to atcoder::static_modint::mod and atcoder::dynamic_modint::mod in the original ACL.

Example

use ac_library::modint::ModIntBase;

fn f<Z: ModIntBase>() {
    let _: u32 = Z::modulus();
}

fn raw(val: u32) -> Self

Constructs a Self from a val < Self::modulus() without checking it.

Corresponds to atcoder::static_modint::raw and atcoder::dynamic_modint::raw in the original ACL.

Constraints

• val is less than Self::modulus()

Note that all operations assume that inner values are smaller than the modulus. If val is greater than or equal to Self::modulus(), the behaviors are not defined.

use ac_library::ModInt1000000007 as Mint;

let x = Mint::raw(1_000_000_007);
let y = x + x;
assert_eq!(0, y.val());

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `0`,
 right: `1000000007`', src/modint.rs:8:1
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Example

use ac_library::modint::ModIntBase;

fn f<Z: ModIntBase>() -> Z {
    debug_assert!(Z::modulus() >= 100);

    let mut acc = Z::new(0);
    for i in 0..100 {
        if i % 3 == 0 {
            // I know `i` is smaller than the modulus!
            acc += Z::raw(i);
        }
    }
    acc
}

fn val(self) -> u32

Retruns the representative.

Corresponds to atcoder::static_modint::val and atcoder::dynamic_modint::val in the original ACL.

Example

use ac_library::modint::ModIntBase;

fn f<Z: ModIntBase>(x: Z) {
    let _: u32 = x.val();
}

fn inv(self) -> Self

Retruns the multiplicative inverse of self.

Corresponds to atcoder::static_modint::inv and atcoder::dynamic_modint::inv in the original ACL.

Panics

Panics if the multiplicative inverse does not exist.

Example

use ac_library::modint::ModIntBase;

fn f<Z: ModIntBase>(x: Z) {
    let _: Z = x.inv();
}

Provided Methods

fn new<T: RemEuclidU32>(val: T) -> Self

Creates a new Self.

Takes any primitive integer.

Example

use ac_library::modint::ModIntBase;

fn f<Z: ModIntBase>() {
    let _ = Z::new(1u32);
    let _ = Z::new(1usize);
    let _ = Z::new(-1i64);
}

fn pow(self, n: u64) -> Self

Returns self to the power of n.

Corresponds to atcoder::static_modint::pow and atcoder::dynamic_modint::pow in the original ACL.

Example

use ac_library::modint::ModIntBase;

fn f<Z: ModIntBase>() {
    let _: Z = Z::new(2).pow(3);
}

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<I: Id> ModIntBase for DynamicModInt<I>

These methods are implemented for the struct. You don’t need to use ModIntBase to call methods of DynamicModInt.

impl<M: Modulus> ModIntBase for StaticModInt<M>

These methods are implemented for the struct. You don’t need to use ModIntBase to call methods of StaticModInt.