Euler's Phi(オイラーのφ関数) (math/number-theory/euler-phi.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "math/number-theory/euler-phi.hpp"

概要

正の整数 $n$ が与えられたとき, $1$ から $n$ までの自然数のうち $n$ と互いに素なものの個数 $\phi(n)$ を求める.

以下の式で効率的に求めることができる.

$\phi(n)=n\displaystyle\prod_{i=1}^k(1-\dfrac{1}{p_i})$ (ただし $p_i$ は $n$ の素因数)

• euler_phi(n): $\phi(n)$ を返す.

計算量

• $O(\sqrt N)$

Required by

• Mod Tetration(テトレーション) (math/combinatorics/mod-tetration.hpp)

Verified with

• test/verify/aoj-ntl-1-d.test.cpp
• test/verify/yosupo-tetration-mod.test.cpp

Code

/**
 * @brief Euler's Phi(オイラーのφ関数)
 *
 */
template <typename T>
T euler_phi(T n) {
  T ret = n;
  for (T i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      ret -= ret / i;
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) ret -= ret / n;
  return ret;
}

#line 1 "math/number-theory/euler-phi.hpp"
/**
 * @brief Euler's Phi(オイラーのφ関数)
 *
 */
template <typename T>
T euler_phi(T n) {
  T ret = n;
  for (T i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      ret -= ret / i;
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) ret -= ret / n;
  return ret;
}

Back to top page