Euler's totient function (Table)
(Mylib/Number/Totient/totient_table.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• totient_table(n)
  • i in [0, n]について$\varphi(i)$を求める。
  • $\varphi(nm) = \varphi(n) * \varphi(m)$ if nとmが互いに素

Requirements

Notes

Problems

• Manthan, Codefest 19 G. Polygons

References

Required by

• Sum of totient function (Mylib/Number/Totient/totient_sum.cpp)

Verified with

• test/yosupo-judge/sum_of_totient_function/main.test.cpp

Code

#pragma once
#include <numeric>
#include <vector>

namespace haar_lib {
  std::vector<int> totient_table(int n) {
    std::vector<int> ret(n + 1);
    std::iota(ret.begin(), ret.end(), 0);

    for (int i = 2; i <= n; ++i) {
      if (ret[i] == i) {
        for (int j = i; j <= n; j += i) {
          ret[j] = ret[j] / i * (i - 1);
        }
      }
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/Totient/totient_table.cpp"
#include <numeric>
#include <vector>

namespace haar_lib {
  std::vector<int> totient_table(int n) {
    std::vector<int> ret(n + 1);
    std::iota(ret.begin(), ret.end(), 0);

    for (int i = 2; i <= n; ++i) {
      if (ret[i] == i) {
        for (int j = i; j <= n; j += i) {
          ret[j] = ret[j] / i * (i - 1);
        }
      }
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page