Multiple/Divisor Fast Zeta/Möbius Transform
(convolution/divisor_zeta_moebius_transform.hpp)

• View this file on GitHub
• Last update: 2024-01-07 22:37:45+09:00
• Include: #include "convolution/divisor_zeta_moebius_transform.hpp"

Description

約数に関する zeta 変換は，写像 $f$ が与えられたとき，以下を満たす写像 $g$ を得る変換である．Möbius 変換は，zeta 変換の逆変換である (つまり，写像 $g$ が与えられたとき，以下を満たす写像 $f$ を得る変換である)．

\[g(n) = \sum_{m | n} f(m)\]

倍数に関する変換も同様である．

約数に関する FZT/FMT を用いると，LCM convolution が高速に計算できる．

\[c_k = \sum_{\mathrm{lcm}(i,j)=k} a_i b_j\]

倍数に関する FZT/FMT を用いると，GCD convolution が高速に計算できる．

\[c_k = \sum_{\gcd(i,j)=k} a_i b_j\]

Operations

• void divisor_fzt(vector<T> a)
• void multiple_fzt(vector<T> a)
  • 数列 $a$ を約数/倍数に関して高速 zeta 変換する
  • 時間計算量: $O(n\log\log n)$
• void divisor_fmt(vector<T> a)
• void multiple_fzt(vector<T> a)
  • 数列 $a$ を約数に関して高速 Möbius 変換する
  • 時間計算量: $O(n\log\log n)$

Note

畳み込み	変換	逆変換
$\max$	zeta 変換 (累積和，下位)	Möbius 変換 (累積和，下位)
$\min$	zeta 変換 (累積和，上位)	Möbius 変換 (累積和，上位)
$\gcd$	zeta 変換 (倍数)	Möbius 変換 (倍数)
$\mathrm{lcm}$	zeta 変換 (約数)	Möbius 変換 (約数)
$\mathrm{bitwise\ and}$	zeta 変換 (bit，上位)	Möbius 変換 (bit，上位)
$\mathrm{bitwise\ or}$	zeta 変換 (bit，下位)	Möbius 変換 (bit，下位)
$\mathrm{bitwise\ xor}$	Walsh-Hadamard 変換	逆 Walsh-Hadamard 変換
$+$	Fourier 変換，数論変換	逆 Fourier 変換，逆数論変換

Reference

• ゼータ変換・メビウス変換を理解する - Qiita
  • これを読むと，zeta/Möbius 変換が絡む一連の畳み込み操作に関して完全に理解した気持ちになれる．
• 高速ゼータ変換の約数版 O(N log(log(N))) - noshi91のメモ
  • 約数に関する FZT/FMT を高速に計算する方法が書かれている (通常は $O(n\log n)$)．

Required by

• GCD/LCM Convolution (convolution/gcd_lcm_convolution.hpp)

Verified with

• test/yosupo/gcd_convolution.test.cpp
• test/yosupo/lcm_convolution.test.cpp

Code

#pragma once
#include <vector>

template <typename T>
void divisor_fzt(std::vector<T>& a) {
    const int n = a.size();
    std::vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (!sieve[p]) continue;
        for (int k = 1; k * p < n; ++k) {
            sieve[k * p] = false;
            a[k * p] += a[k];
        }
    }
}

template <typename T>
void divisor_fmt(std::vector<T>& a) {
    const int n = a.size();
    std::vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (!sieve[p]) continue;
        for (int k = (n - 1) / p; k > 0; --k) {
            sieve[k * p] = false;
            a[k * p] -= a[k];
        }
    }
}

template <typename T>
void multiple_fzt(std::vector<T>& a) {
    const int n = a.size();
    std::vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (!sieve[p]) continue;
        for (int k = (n - 1) / p; k > 0; --k) {
            sieve[k * p] = false;
            a[k] += a[k * p];
        }
    }
}

template <typename T>
void multiple_fmt(std::vector<T>& a) {
    const int n = a.size();
    std::vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (!sieve[p]) continue;
        for (int k = 1; k * p < n; ++k) {
            sieve[k * p] = false;
            a[k] -= a[k * p];
        }
    }
}

#line 2 "convolution/divisor_zeta_moebius_transform.hpp"
#include <vector>

template <typename T>
void divisor_fzt(std::vector<T>& a) {
    const int n = a.size();
    std::vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (!sieve[p]) continue;
        for (int k = 1; k * p < n; ++k) {
            sieve[k * p] = false;
            a[k * p] += a[k];
        }
    }
}

template <typename T>
void divisor_fmt(std::vector<T>& a) {
    const int n = a.size();
    std::vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (!sieve[p]) continue;
        for (int k = (n - 1) / p; k > 0; --k) {
            sieve[k * p] = false;
            a[k * p] -= a[k];
        }
    }
}

template <typename T>
void multiple_fzt(std::vector<T>& a) {
    const int n = a.size();
    std::vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (!sieve[p]) continue;
        for (int k = (n - 1) / p; k > 0; --k) {
            sieve[k * p] = false;
            a[k] += a[k * p];
        }
    }
}

template <typename T>
void multiple_fmt(std::vector<T>& a) {
    const int n = a.size();
    std::vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (!sieve[p]) continue;
        for (int k = 1; k * p < n; ++k) {
            sieve[k * p] = false;
            a[k] -= a[k * p];
        }
    }
}

Back to top page