Struct ModInt 

pub struct ModInt<const MOD: i64> { /* private fields */ }

コンパイル時定数 MOD を法とする剰余整数です。

構築時に値を剰余で正規化し、保持値は常に 0 <= value < MOD です。MOD は正である必要が あります。pow は非負整数の指数に使います。inv と / は MOD が素数で、対象の値が 法 MOD で 0 でない場合にのみ数学的な乗法逆元として機能します。 加算・減算・乗算・累乗の途中計算は i64 で行うため、中間値が i64 に収まる MOD を 選んでください。乗算については、少なくとも (MOD - 1) * (MOD - 1) が i64::MAX 以下に なる法であることを確認してください。

Panics

MOD <= 0 の場合は構築時に panic します。

Examples

use atcoder::math::mod_int::Mod998;

let value = Mod998::new(-1);
assert_eq!(value.value(), 998_244_352);
assert_eq!((value + Mod998::new(2)).value(), 1);

Implementations

impl<const MOD: i64> ModInt<MOD>

pub fn new(value: i64) -> Self

value を法 MOD で正規化した値を作ります。負の値も 0..MOD に収めます。 計算量は O(1) です。

Panics

MOD <= 0 の場合に panic します。

pub const fn value(self) -> i64

正規化済みの値（0..MOD）を返します。

pub const fn val(&self) -> i64

正規化済みの値（0..MOD）を参照経由で返します。

value と同じです。

pub fn inv(self) -> Self

フェルマーの小定理に基づき、self の乗法逆元候補を返します。

MOD が素数かつ self.value() != 0 の場合に、数学的な逆元になることを保証します。 素数判定やゼロの検査は行いません。MOD == 1 では指数が負になるため panic します。 それ以外の条件外の入力でも逆元としての正しさは保証しないため、呼び出し側で条件を保証してください。 計算量は O(log MOD) です。

pub fn pow(self, exponent: i64) -> Self

self の exponent 乗を法 MOD で返します。

exponent は非負である必要があります。計算量は O(log exponent) です。 乗算中間値を i64 で計算するため、想定法に対してその値が範囲内に収まることが必要です。

Panics

exponent < 0 の場合に panic します。

Trait Implementations

impl<const MOD: i64> Add for ModInt<MOD>

type Output = ModInt<MOD>

The resulting type after applying the + operator.

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

Performs the + operation.

impl<const MOD: i64> AddAssign for ModInt<MOD>

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl<const MOD: i64> Clone for ModInt<MOD>

fn clone(&self) -> ModInt<MOD>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<const MOD: i64> Copy for ModInt<MOD>

impl<const MOD: i64> Debug for ModInt<MOD>

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

Formats the value using the given formatter.

impl<const MOD: i64> Display for ModInt<MOD>

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

Formats the value using the given formatter.

impl<const MOD: i64> Div for ModInt<MOD>

type Output = ModInt<MOD>

The resulting type after applying the / operator.

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

Performs the / operation.

impl<const MOD: i64> DivAssign for ModInt<MOD>

fn div_assign(&mut self, rhs: Self)

Performs the /= operation.

impl<const MOD: i64> Eq for ModInt<MOD>

impl<const MOD: i64> Hash for ModInt<MOD>

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<const MOD: i64> Mul for ModInt<MOD>

type Output = ModInt<MOD>

The resulting type after applying the * operator.

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

Performs the * operation.

impl<const MOD: i64> MulAssign for ModInt<MOD>

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation.

impl<const MOD: i64> Ord for ModInt<MOD>

fn cmp(&self, other: &ModInt<MOD>) -> Ordering

This method returns an Ordering between self and other.

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

where Self: Sized,

Compares and returns the maximum of two values.

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

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<const MOD: i64> PartialEq for ModInt<MOD>

fn eq(&self, other: &ModInt<MOD>) -> bool

Equality operator ==.

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

Inequality operator !=.

impl<const MOD: i64> PartialOrd for ModInt<MOD>

fn partial_cmp(&self, other: &ModInt<MOD>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<const MOD: i64> StructuralPartialEq for ModInt<MOD>

impl<const MOD: i64> Sub for ModInt<MOD>

type Output = ModInt<MOD>

The resulting type after applying the - operator.

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

Performs the - operation.

impl<const MOD: i64> SubAssign for ModInt<MOD>

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation.