number-theory/totient-function.hpp

View this file on GitHub
Last update: 2026-06-28 15:22:40+09:00
Include: #include "number-theory/totient-function.hpp"

Depends on

LPF Table (math/lpf-table.hpp)

Code

#pragma once

#include "math/lpf-table.hpp"

namespace TotientFunction {
vector<int> table(int n) {
  vector<int> tot(n + 1, 1);
  tot[0] = 0;
  auto lpf = LPFTable(n);
  for (int x = 2; x <= n; x++) {
    int p = lpf[x];
    if (x / p % p == 0)
      tot[x] = tot[x / p] * p;
    else
      tot[x] = tot[x / p] * (p - 1);
  }
  return tot;
}
};  // namespace TotientFunction

#line 2 "number-theory/totient-function.hpp"

#line 2 "math/lpf-table.hpp"

vector<int> LPFTable(int n) {
  vector<int> lpf(n + 1, 0);
  iota(lpf.begin(), lpf.end(), 0);
  for (int p = 2; p * p <= n; p += (p & 1) + 1) {
    if (lpf[p] != p) continue;
    for (int i = p * p; i <= n; i += p)
      if (lpf[i] == i) lpf[i] = p;
  }
  return lpf;
}
/**
 * @brief LPF Table
 */
#line 4 "number-theory/totient-function.hpp"

namespace TotientFunction {
vector<int> table(int n) {
  vector<int> tot(n + 1, 1);
  tot[0] = 0;
  auto lpf = LPFTable(n);
  for (int x = 2; x <= n; x++) {
    int p = lpf[x];
    if (x / p % p == 0)
      tot[x] = tot[x / p] * p;
    else
      tot[x] = tot[x / p] * (p - 1);
  }
  return tot;
}
};  // namespace TotientFunction