ZetaMobiusDivMul 名前空間

倍数・約数ゼータ・メビウス変換 [詳解]

関数
void	Init (int n=1e6)
template<typename Monoid>
vector< typename Monoid::Type >	MultipleZeta (vector< typename Monoid::Type > v)
	倍数高速ゼータ変換
template<typename Monoid>
vector< typename Monoid::Type >	DvisorZeta (vector< typename Monoid::Type > v)
	約数高速ゼータ変換
template<typename Abel>
vector< typename Abel::Type >	MultipleMobius (vector< typename Abel::Type > v)
	倍数高速メビウス変換
template<typename Abel>
vector< typename Abel::Type >	DivisorMobius (vector< typename Abel::Type > v)
	約数高速メビウス変換

変数
vector< int >	primes

詳解

倍数・約数ゼータ・メビウス変換

関数詳解

Init()

void ZetaMobiusDivMul::Init

(

int

n = 1e6

)

zeta_mobius_div_mul.hpp の 7 行目に定義があります。

MultipleZeta()

template<typename Monoid>

vector< typename Monoid::Type > ZetaMobiusDivMul::MultipleZeta

(

vector< typename Monoid::Type >

v

)

倍数高速ゼータ変換

v'[k] = Σ_{k|d} v[d] なる v' を返す

覚え書き

O(N log(log(N)))

zeta_mobius_div_mul.hpp の 13 行目に定義があります。

参照先 Init().

DvisorZeta()

template<typename Monoid>

vector< typename Monoid::Type > ZetaMobiusDivMul::DvisorZeta

(

vector< typename Monoid::Type >

v

)

約数高速ゼータ変換

v'[k] = Σ_{d|k} v[d] なる v' を返す

覚え書き

O(N log(log(N)))

zeta_mobius_div_mul.hpp の 24 行目に定義があります。

参照先 Init().

MultipleMobius()

template<typename Abel>

vector< typename Abel::Type > ZetaMobiusDivMul::MultipleMobius

(

vector< typename Abel::Type >

v

)

倍数高速メビウス変換

v'[k] = Σ_{k|d} μ(d) v[d] なる v' を返す

覚え書き

逆変換が必要なので、v は可換群の元である必要がある

O(N log(log(N)))

zeta_mobius_div_mul.hpp の 36 行目に定義があります。

参照先 Init().

DivisorMobius()

template<typename Abel>

vector< typename Abel::Type > ZetaMobiusDivMul::DivisorMobius

(

vector< typename Abel::Type >

v

)

約数高速メビウス変換

v'[k] = Σ_{d|k} μ(d) v[k/d] なる v' を返す

覚え書き

逆変換が必要なので、v は可換群の元である必要がある

O(N log(log(N)))

zeta_mobius_div_mul.hpp の 48 行目に定義があります。

参照先 Init().

変数詳解

primes

vector<int> ZetaMobiusDivMul::primes

zeta_mobius_div_mul.hpp の 6 行目に定義があります。