pub trait FastMath: Sized + Copy {
// Required methods
fn fast_pow(self, exponent: Self) -> Self;
fn mod_pow(self, exponent: Self, modulus: Self) -> Self;
fn mod_inv(self, modulus: Self) -> Self;
fn gcd(self, rhs: Self) -> Self;
fn lcm(self, rhs: Self) -> Self;
}Expand description
高速累乗、剰余逆元、最大公約数、最小公倍数を追加する拡張トレイトです。
i32、i64、isize、u32、u64、usize に実装されています。演算結果の
オーバーフローは検査しないため、各型に収まる入力を使ってください。
§Examples
use atcoder::math::fast_math::FastMath;
assert_eq!(3_u64.fast_pow(4), 81);
assert_eq!(2_u64.mod_pow(10, 1_000), 24);
assert_eq!(12_u64.gcd(18), 6);Required Methods§
Sourcefn fast_pow(self, exponent: Self) -> Self
fn fast_pow(self, exponent: Self) -> Self
self の exponent 乗を返します。
exponent が正の場合の計算量は O(log exponent) です。指数が 0 以下なら
1 を返します（符号付き型の負指数も 1 になります）。積のオーバーフローは検査しません。
Sourcefn mod_pow(self, exponent: Self, modulus: Self) -> Self
fn mod_pow(self, exponent: Self, modulus: Self) -> Self
二分累乗法で self.pow(exponent) mod modulus を計算します。
非負の exponent と正の modulus を指定してください。計算量は O(log exponent)、
modulus == 0 の場合は panic します。剰余前の積は通常の整数乗算なので、型の範囲を
超えるとオーバーフローします。符号付き型では負数の剰余は非負に正規化されません。
Sourcefn mod_inv(self, modulus: Self) -> Self
fn mod_inv(self, modulus: Self) -> Self
modulus における乗法逆元を返します。
modulus >= 2 が素数で、self がその法で 0 でない場合に限り、
フェルマーの小定理に基づく逆元を返します。計算量は O(log modulus) です。
この条件を満たさない入力の結果は逆元として保証されません。
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".