numtheory/phi_array.cpp

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

Code

template<class T, int32_t C>
array<T, C> phi_array(linear_sieve<C> &ls) {
  array<T, C> phi = {};
  if (C > 1) phi[1] = T(1);
  auto &mpf = ls.mpf;
  for(int i = 2; i < C; i++)
    phi[i] = phi[i / mpf[i]] * (mpf[i] == mpf[i / mpf[i]] ? mpf[i] : T(mpf[i] - 1));
  return phi;
}

#line 1 "numtheory/phi_array.cpp"
template<class T, int32_t C>
array<T, C> phi_array(linear_sieve<C> &ls) {
  array<T, C> phi = {};
  if (C > 1) phi[1] = T(1);
  auto &mpf = ls.mpf;
  for(int i = 2; i < C; i++)
    phi[i] = phi[i / mpf[i]] * (mpf[i] == mpf[i / mpf[i]] ? mpf[i] : T(mpf[i] - 1));
  return phi;
}