Module nekolib::math

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。

ButterflyCache
CompactSieve
篩。
ConstDiv
定数除算。
ConstDiv2
定数除算。
DynamicModInt
FracApproxIter
HarmonicFloorSum
$\sum_{i=1}^n \lfloor m/i\rfloor$ および $\sum_{i=1}^n (m\bmod i)$ .
Interpolation
Lagrange 補間。
LinearSieve
線形篩。
Mod998244353
Mod1000000007
ModFactorialBinom
法 $p$ での二項係数。
Polynomial
多項式。
SegmentedFactorSieve
SieveN2Plus1
$n^2+1$ 型素数の篩。
SieveN2PlusNPlus1
$n^2+n+1$ 型素数の篩。
SlopeFunction
区分線形凸関数。
StaticModInt
TwoSat
2-SAT。