numtheory/dirichlet_convolution.cpp

• View this file on GitHub
• Last update: 2025-12-12 18:41:06+08:00

Code

template<class T>
vector<T> dirichlet_convolution(vector<T> a, vector<T> b) {
  assert(size(a) == size(b));
  vector<T> c(size(a));
  for(int i = 1; i < ssize(a); i++)
    for(int j = 1; i * j < ssize(a); j++)
      c[i * j] += a[i] * b[j];
  return c;
}

#line 1 "numtheory/dirichlet_convolution.cpp"
template<class T>
vector<T> dirichlet_convolution(vector<T> a, vector<T> b) {
  assert(size(a) == size(b));
  vector<T> c(size(a));
  for(int i = 1; i < ssize(a); i++)
    for(int j = 1; i * j < ssize(a); j++)
      c[i * j] += a[i] * b[j];
  return c;
}

Back to top page