約数・倍数変換
(number-theory/divisor-multiple-transform.hpp)

• View this file on GitHub
• Last update: 2025-10-10 17:35:46+09:00
• Include: #include "number-theory/divisor-multiple-transform.hpp"

約数・倍数変換

長さ $\red{N+1}$ の vector $(a_0,a_1,\dots,a_N)$ を受け取る．

(約数/倍数)(ゼータ/メビウス)変換では次を満たす vector $(b_0,b_1,\dots,b_N)$ を返す．

• $b_0=0$．
• ゼータ変換：$b_i\ (1\leq i\leq N)$ は $i$ の(約数/倍数)である $j$ についての $a_j$ の総和．
• メビウス変換：ゼータ変換の逆変換．

いずれも時間計算量は $O(N\log\log N)$．

GCD/LCM 畳み込み

代表的な使用例．

• gcd 畳み込み：数列 $a,b$ から $c_k=\sum_{\gcd(i,j)=k}a_ib_j$ を満たす数列 $c$ を得る．
• lcm 畳み込み：数列 $a,b$ から $c_k=\sum_{\operatorname{lcm}(i,j)=k}a_ib_j$ を満たす数列 $c$ を得る．

ゼータ変換し，各点積をとってメビウス変換すればよい．

Required by

• gcd 畳み込み (convolution/gcd.hpp)
• lcm 畳み込み (convolution/lcm.hpp)

Verified with

• verify/convolution/LC_gcd_convolution.test.cpp
• verify/convolution/LC_lcm_convolution.test.cpp

Code

#pragma once

template <class T>
void DivisorZetaTransform(vector<T>& a) {
  if (a.empty()) return;
  int n = a.size();
  vector<bool> sieve(n, true);
  for (int p = 2; p < n; p++) {
    if (sieve[p]) {
      for (int k = 1; k * p < n; k++) {
        sieve[k * p] = false;
        a[k * p] += a[k];
      }
    }
  }
}

template <class T>
void DivisorMobiusTransform(vector<T>& a) {
  if (a.empty()) return;
  int n = a.size();
  vector<bool> sieve(n, true);
  for (int p = 2; p < n; p++) {
    if (sieve[p]) {
      for (int k = (n - 1) / p; k > 0; k--) {
        sieve[k * p] = false;
        a[k * p] -= a[k];
      }
    }
  }
}

template <class T>
void MultipleZetaTransform(vector<T>& a) {
  if (a.empty()) return;
  int n = a.size();
  vector<bool> sieve(n, true);
  for (int p = 2; p < n; p++) {
    if (sieve[p]) {
      for (int k = (n - 1) / p; k > 0; k--) {
        sieve[k * p] = false;
        a[k] += a[k * p];
      }
    }
  }
}

template <class T>
void MultipleMobiusTransform(vector<T>& a) {
  if (a.empty()) return;
  int n = a.size();
  vector<bool> sieve(n, true);
  for (int p = 2; p < n; p++) {
    if (sieve[p]) {
      for (int k = 1; k * p < n; k++) {
        sieve[k * p] = false;
        a[k] -= a[k * p];
      }
    }
  }
}

/**
 * @brief 約数・倍数変換
 * @docs docs/number-theory/divisor-multiple-transform.md
 */

#line 2 "number-theory/divisor-multiple-transform.hpp"

template <class T>
void DivisorZetaTransform(vector<T>& a) {
  if (a.empty()) return;
  int n = a.size();
  vector<bool> sieve(n, true);
  for (int p = 2; p < n; p++) {
    if (sieve[p]) {
      for (int k = 1; k * p < n; k++) {
        sieve[k * p] = false;
        a[k * p] += a[k];
      }
    }
  }
}

template <class T>
void DivisorMobiusTransform(vector<T>& a) {
  if (a.empty()) return;
  int n = a.size();
  vector<bool> sieve(n, true);
  for (int p = 2; p < n; p++) {
    if (sieve[p]) {
      for (int k = (n - 1) / p; k > 0; k--) {
        sieve[k * p] = false;
        a[k * p] -= a[k];
      }
    }
  }
}

template <class T>
void MultipleZetaTransform(vector<T>& a) {
  if (a.empty()) return;
  int n = a.size();
  vector<bool> sieve(n, true);
  for (int p = 2; p < n; p++) {
    if (sieve[p]) {
      for (int k = (n - 1) / p; k > 0; k--) {
        sieve[k * p] = false;
        a[k] += a[k * p];
      }
    }
  }
}

template <class T>
void MultipleMobiusTransform(vector<T>& a) {
  if (a.empty()) return;
  int n = a.size();
  vector<bool> sieve(n, true);
  for (int p = 2; p < n; p++) {
    if (sieve[p]) {
      for (int k = 1; k * p < n; k++) {
        sieve[k * p] = false;
        a[k] -= a[k * p];
      }
    }
  }
}

/**
 * @brief 約数・倍数変換
 * @docs docs/number-theory/divisor-multiple-transform.md
 */

Back to top page