Expand description
数学関連のアルゴリズムたち。
基本的な数学関数。
直線の集合を管理するクラスなど、抽象化しにくいものは ds ではなくこちらに含めた。
計算機科学自体 mathematics では？とも思うが…
Modules§
- bit_
binom_ - 組合せのビット表現。
- carmichael_
lambda - Carmichael の $\lambda$ 関数。
- common_
quot - 商が共通の区間の列挙。
- compact_
sieve - 篩。
- const_
div - 定数除算。
- continued_
fraction_ - 連分数展開。
- convolution
- digit_
sum - 桁和。
- digits
- divisors
- 約数列挙。
- dlog
- 離散対数。
- equiv_
mod - Chinese remaindering
- euler_
phi - Euler の $\varphi$ 関数。
- factors
- 素因数分解。
- factors_
dup - 素因数分解。
- frac_
approx - fraction_
bisect - garner
- gcd
- 最大公約数。
- gcd_
recip - 最大公約数と逆元。
- harmonic_
floor_ sum - $\sum_{i=1}^n \lfloor m/i\rfloor$ および $\sum_{i=1}^n (m\bmod i)$.
- interpolation
- Lagrange 補間。
- is_
close_ float - lcm
- 最小公倍数。
- linear_
floor_ sum - $ \sum_{i=0}^{n-1} \left\lfloor\frac{ai+b}{m}\right\rfloor. $
- linear_
sieve - 線形篩。
- miller_
rabin - mod_
ackermann - Ackermann 関数。
- mod_
factorial_ binom - 法 $p$ での二項係数。
- mod_ord
- 位数。
- mod_pow
- 冪乗。
- mod_
recip_ table_ - 素数 $m$ を法とした逆元のテーブル。
- mod_
tetration - tetration。
- modint
- polynomial
- 多項式。
- prime_
pi_ - 素数の数え上げ。
- segmented_
factor_ sieve - sieve_
n2_ plus_ 1 - $n^2+1$ 型素数の篩。
- sieve_
n2_ plus_ n_ plus_ 1 - $n^2+n+1$ 型素数の篩。
- slope_
function - 区分線形凸関数。
- sqrt
- 平方根。
- sqrt_
fraction_ - 平方根の連分数展開。
- stern_
brocot_ - Stern–Brocot tree
- two_sat
- 2-SAT。
Structs§
- Butterfly
Cache - Compact
Sieve - 篩。
- Const
Div - 定数除算。
- Const
Div2 - 定数除算。
- Dynamic
ModInt - Frac
Approx Iter - Harmonic
Floor Sum - $\sum_{i=1}^n \lfloor m/i\rfloor$ および $\sum_{i=1}^n (m\bmod i)$.
- Interpolation
- Lagrange 補間。
- Linear
Sieve - 線形篩。
- Mod998244353
- Mod1000000007
- ModFactorial
Binom - 法 $p$ での二項係数。
- Polynomial
- 多項式。
- Segmented
Factor Sieve - Sieve
N2Plus1 - $n^2+1$ 型素数の篩。
- Sieve
N2PlusN Plus1 - $n^2+n+1$ 型素数の篩。
- Slope
Function - 区分線形凸関数。
- Static
ModInt - TwoSat
- 2-SAT。
Enums§
Traits§
- Carmichael
Lambda - Carmichael の $\lambda$ 関数。
- Common
Quot - 商が共通の区間の列挙。
- CrtMod
- CrtWrapping
- DLog
- 離散対数。
- Digit
Sum - 桁和。
- Digits
- Divisors
- 約数列挙。
- Equiv
Mod - Chinese remaindering。
- Equiv
ModIter - Chinese remaindering。
- Euler
Phi - Euler の $\varphi$ 関数。
- Factors
- 素因数分解。
- Factors
Dup - 素因数分解。
- Frac
Approx - Fraction
Bisect - Gcd
- 最大公約数。
- GcdRecip
- 最大公約数と逆元。
- IsClose
Float - Lcm
- 最小公倍数。
- Linear
Floor Sum - $ \sum_{i=0}^{n-1} \left\lfloor\frac{ai+b}{m}\right\rfloor. $
- Miller
Rabin - ModAckermann
- Ackermann 関数。
- ModInt
Base - ModOrd
- 位数。
- ModPow
- 冪乗。
- ModTetration
- tetration。
- Modulus
- NttFriendly
- Sqrt
- 平方根。
Functions§
- bit_
binom - 組合せのビット表現。
- butterfly
- butterfly_
inv - continued_
fraction - 連分数展開。
- convolve
- convolve_
u64 - convolve_
u32_ mod - convolve_
u64_ mod - convolve_
u128 - convolve_
u128_ mod - convolve_
wrapping_ u64 - convolve_
wrapping_ u128 - mod_
recip_ table_ prime - 素数 $m$ を法とした逆元のテーブル。
- prime_
pi - 素数の数え上げ。
- sqrt_
fraction - 平方根の連分数展開。
- sqrt_
fraction_ fn - 平方根の連分数展開。
- stern_
brocot - Stern–Brocot tree