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

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

概要

todo

計算量

todo

Depends on

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

Verified with

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

Code

#include "MultipleDivisorZetaMobiusTransform.hpp"

template <class T>
vector<T> gcd_convolution(vector<T> a, vector<T> b) {
  vector<T> za = multiple_zeta(a);
  vector<T> zb = multiple_zeta(b);
  vector<T> d(a.size());
  for (int i = 0; i < a.size(); i++) d[i] = za[i] * zb[i];
  return multiple_mobius(d);
}

#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;
}
#line 2 "math/number-theory/GCDConvolution.hpp"

template <class T>
vector<T> gcd_convolution(vector<T> a, vector<T> b) {
  vector<T> za = multiple_zeta(a);
  vector<T> zb = multiple_zeta(b);
  vector<T> d(a.size());
  for (int i = 0; i < a.size(); i++) d[i] = za[i] * zb[i];
  return multiple_mobius(d);
}

Back to top page