Multiple/Divisor Zeta/Möbius Transform
(math/number-theory/MultipleDivisorZetaMobiusTransform.hpp)

• View this file on GitHub
• Last update: 2026-04-18 20:38:59+09:00
• Include: #include "math/number-theory/MultipleDivisorZetaMobiusTransform.hpp"

概要

todo

計算量

todo

Required by

• GCD Convolution (math/number-theory/GCDConvolution.hpp)
• LCM Convolution (math/number-theory/LCMConvolution.hpp)

Verified with

• verify/LibraryChecker/math/number-theory/GCDConvolution.test.cpp
• verify/LibraryChecker/math/number-theory/LCMConvolution.test.cpp

Code

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

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

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

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

#line 1 "math/number-theory/MultipleDivisorZetaMobiusTransform.hpp"
template <class T>
vector<T> divisor_zeta(vector<T> a) {
  int n = int(a.size()) - 1;
  vector<bool> prime(n + 1, true);
  for (int p = 2; p <= n; p++) {
    if (prime[p]) {
      for (long long k = 1; k * p <= n; k++) {
        prime[k * p] = false;
        a[k * p] += a[k];
      }
    }
  }
  return a;
}

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

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

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

Back to top page