数学/オイラーの $\varphi$ 関数/オイラーの $\varphi$ 関数
(test/math/euler_phi.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D

Depends on

• オイラーの $\varphi$ 関数 (Euler's totient function) (include/emthrm/math/euler_phi.hpp)

Code

/*
 * @title 数学/オイラーの $\varphi$ 関数/オイラーの $\varphi$ 関数
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D
 */

#include <iostream>

#include "emthrm/math/euler_phi.hpp"

int main() {
  int n;
  std::cin >> n;
  std::cout << emthrm::euler_phi(n) << '\n';
  return 0;
}

#line 1 "test/math/euler_phi.test.cpp"
/*
 * @title 数学/オイラーの $\varphi$ 関数/オイラーの $\varphi$ 関数
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D
 */

#include <iostream>

#line 1 "include/emthrm/math/euler_phi.hpp"



#include <cassert>

namespace emthrm {

long long euler_phi(long long n) {
  assert(n >= 1);
  long long res = n;
  for (long long i = 2; i * i <= n; ++i) {
    if (n % i == 0) [[unlikely]] {
      res -= res / i;
      while (n % i == 0) n /= i;
    }
  }
  return n > 1 ? res - res / n : res;
}

}  // namespace emthrm


#line 10 "test/math/euler_phi.test.cpp"

int main() {
  int n;
  std::cin >> n;
  std::cout << emthrm::euler_phi(n) << '\n';
  return 0;
}

Back to top page