Struct contest_algorithms::math::num::Field

pub struct Field {
    pub val: i64,
}

Represents an element of the finite (Galois) field of prime order, given by MOD. Until Rust gets const generics, MOD must be hardcoded, but any prime in [1, 2^31.5] will work. If MOD is not prime, ring operations are still valid but recip() and division are not. Note that the latter operations are also the slowest, so precompute any inverses that you intend to use frequently.

Fields

val: i64

Implementations

impl Field

pub const MOD: i64

pub fn pow(self, exp: u64) -> Self

Computes self^exp in O(log(exp)) time

pub fn vec_of_recips(n: i64) -> Vec<Self>

Computes inverses of 1 to n in O(n) time

pub fn recip(self) -> Self

Computes self^-1 in O(log(Self::MOD)) time

Trait Implementations

impl Add<Field> for Field

type Output = Self

The resulting type after applying the + operator.

fn add(self, other: Self) -> Self

Performs the + operation.

impl Clone for Field

fn clone(&self) -> Field

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Copy for Field

impl Debug for Field

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

Formats the value using the given formatter.

impl Div<Field> for Field

type Output = Self

The resulting type after applying the / operator.

fn div(self, other: Self) -> Self

Performs the / operation.

impl Eq for Field

impl From<i64> for Field

fn from(val: i64) -> Self

Performs the conversion.

impl Hash for Field

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, 

Feeds a slice of this type into the given [Hasher].

impl Mul<Field> for Field

type Output = Self

The resulting type after applying the * operator.

fn mul(self, other: Self) -> Self

Performs the * operation.

impl Neg for Field

type Output = Self

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl PartialEq<Field> for Field

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

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=.

impl StructuralEq for Field

impl StructuralPartialEq for Field

impl Sub<Field> for Field

type Output = Self

The resulting type after applying the - operator.

fn sub(self, other: Self) -> Self

Performs the - operation.