src/math/euler_phi.hpp

View this file on GitHub
Last update: 2022-12-30 13:58:42+09:00
Include: #include "src/math/euler_phi.hpp"

Depends on

src/math/prime_factor.hpp

Verified with

test/aoj/ntl_1_d.test.cpp

Code

#pragma once

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

#include "./prime_factor.hpp"

template <typename T = long long> T euler_phi(T n) {
  T res = n;
  for (auto &p : prime_factor(n)) {
    res -= res / p.first;
  }
  return res;
}

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

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

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

#line 4 "src/math/prime_factor.hpp"
using namespace std;

template <typename T = long long> map<T, T> prime_factor(T n) {
  map<T, T> res;
  for (T i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      ++res[i];
      n /= i;
    }
  }
  if (n != 1) {
    res[n] = 1;
  }
  return res;
}
#line 7 "src/math/euler_phi.hpp"

template <typename T = long long> T euler_phi(T n) {
  T res = n;
  for (auto &p : prime_factor(n)) {
    res -= res / p.first;
  }
  return res;
}