View on GitHub

cp-library

約数包除・GCD畳み込み

C++ 用ライブラリ一覧に戻る

ソースコード

nachia/array/divisor-convolution.hpp

主な機能

約数・倍数の関係に基づく計算。

関数

DivisorZeta, DivisorReversedZeta

template<class Elem>
void DivisorZeta(std::vector<Elem>& a);
template<class Elem>
void DivisorReversedZeta(std::vector<Elem>& a);

ゼータ変換。

$a[0]$ の値は無視される。

$1 \leq s$ について、 $a[s]$ の値を次の値で上書きする。

DivisorMobius, DivisorReversedMobius

template<class Elem>
void DivisorMobius(std::vector<Elem>& a);
template<class Elem>
void DivisorReversedMobius(std::vector<Elem>& a);

メビウス変換。

$a[0]$ の値は無視される。

それぞれ DivisorZeta , DivisorReversedZeta の逆の変形。

GcdConvolution

template<class Elem>
std::vector<Elem> GcdConvolution(std::vector<Elem> a, std::vector<Elem> b);

$a[0]$ の値は無視される。

次で表される数列 $\lbrace c[1] , c[2] , \ldots , c[n] \rbrace$ を返す。 $c[0]$ は定義しない。

\[c[k] = \sum _ {k=\gcd(i,j) , 1 \leq i \leq n , 1 \leq j \leq n} a[i] b[j] \hspace{10px} (1 \leq k \leq n)\]

LcmConvolution

template<class Elem>
std::vector<Elem> LcmConvolution(std::vector<Elem> a, std::vector<Elem> b);

$a[0]$ の値は無視される。

次で表される数列 $\lbrace c[1] , c[2] , \ldots , c[n] \rbrace$ を返す。 $c[0]$ は定義しない。

\[c[k] = \sum _ {k=\operatorname{lcm}(i,j) , 1 \leq i \leq n , 1 \leq j \leq n} a[i] b[j] \hspace{10px} (1 \leq k \leq n)\]

SumForCoprimeIndex

template<class Elem>
void SumForCoprimeIndex(std::vector<Elem>& f);

$f[0]$ は無視される。

$k=1,2,\ldots ,n$ について $g[k]=\sum_{1\leq i\leq n,\text{gcd}(k,i)=1}f[i]$ を計算する。 $f[k]$ に $g[k]$ を代入して返る。


TOP PAGE