numtheory/lcm_convolution.cpp

View this file on GitHub
Last update: 2026-01-29 23:44:49+08:00

Verified with

test/lcm_convolution.test.cpp

Code

//#include "numtheory/linear_sieve.cpp"
//#include "numtheory/zeta_mobius_on_divisibility_lattice.cpp"

template<class T, int32_t C>
vector<T> lcm_convolution(linear_sieve<C> &ls, vector<T> a, vector<T> b) {
  assert(ssize(a) == ssize(b));
  a = zeta_transform_on_divisor(ls, a);
  b = zeta_transform_on_divisor(ls, b);
  for(int i = 0; i < ssize(a); i++)
    a[i] *= b[i];
  return mobius_transform_on_divisor(ls, a);
}

#line 1 "numtheory/lcm_convolution.cpp"
//#include "numtheory/linear_sieve.cpp"
//#include "numtheory/zeta_mobius_on_divisibility_lattice.cpp"

template<class T, int32_t C>
vector<T> lcm_convolution(linear_sieve<C> &ls, vector<T> a, vector<T> b) {
  assert(ssize(a) == ssize(b));
  a = zeta_transform_on_divisor(ls, a);
  b = zeta_transform_on_divisor(ls, b);
  for(int i = 0; i < ssize(a); i++)
    a[i] *= b[i];
  return mobius_transform_on_divisor(ls, a);
}