src/math/euler_phi_table.hpp

• View this file on GitHub
• Last update: 2022-12-30 14:22:43+09:00
• Include: #include "src/math/euler_phi_table.hpp"

Verified with

• test/aoj/2286.test.cpp

Code

#pragma once

#include <bits/stdc++.h>
using namespace std;

template <typename T = int> vector<T> euler_phi_table(T n) {
  vector<T> res(n + 1);
  for (T i = 0; i <= n; ++i) {
    res[i] = i;
  }
  for (T i = 2; i <= n; ++i) {
    if (res[i] == i) {
      for (T j = i; j <= n; j += i) {
        res[j] -= res[j] / i;
      }
    }
  }
  return res;
}

#line 2 "src/math/euler_phi_table.hpp"

#include <bits/stdc++.h>
using namespace std;

template <typename T = int> vector<T> euler_phi_table(T n) {
  vector<T> res(n + 1);
  for (T i = 0; i <= n; ++i) {
    res[i] = i;
  }
  for (T i = 2; i <= n; ++i) {
    if (res[i] == i) {
      for (T j = i; j <= n; j += i) {
        res[j] -= res[j] / i;
      }
    }
  }
  return res;
}

Back to top page