約数包除・GCD畳み込み

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

ソースコード

nachia/array/divisor-convolution.hpp

主な機能

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

• ゼータ変換 / メビウス変換
• GCD 畳み込み / LCM 畳み込み

関数

DivisorZeta, DivisorReversedZeta

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

• $n = $ a.size() ${}-1$
• $1 \leq n \leq 10^8$
• Elem は可換群： Elem どうしで演算 += ができる
• $O(n \log \log n)$ 時間

ゼータ変換。

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

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

• DivisorZeta の場合 ： $s$ の正の約数 $t$ について $a[t]$ の総和
• DivisorReversedZeta の場合 ： $s$ の正の倍数 $t$ について $a[t]$ の総和

DivisorMobius, DivisorReversedMobius

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

• $n = $ a.size() ${}-1$
• $1 \leq n \leq 10^8$
• Elem は可換群： Elem どうしで演算 -= ができる
• $O(n \log \log n)$ 時間

メビウス変換。

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

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

GcdConvolution

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

• a.size() $=$ b.size()
• $n = $ a.size() ${}-1$
• $1 \leq n \leq 10^8$
• Elem は可換環： Elem どうしで演算 += , -= , *= ができる
• $O(n \log \log n)$ 時間

$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.size() $=$ b.size()
• $n := $ a.size() ${}-1$
• $1 \leq n \leq 10^8$
• Elem は可換環： Elem どうしで演算 += , -= , *= ができる
• $O(n \log \log n)$ 時間

$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);

• $n := $ a.size() ${}-1$
• $1 \leq n \leq 10^8$
• Elem は可換環： Elem どうしで演算 += , -= , *= ができる
• $O(n \log \log n)$ 時間

$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