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

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/math/euler_phi_init2.hpp"

オイラーの $\varphi$ 関数 (Euler’s totient function)

$n \in \mathbb{N}^+$ に対して

\[\varphi(n) \mathrel{:=} \# \lbrace k \in \lbrace 1, 2, \ldots, n \rbrace \mid k \perp n \rbrace\]

と定義される $\varphi(n)$ である。素因数分解 $n = \prod_{i = 1}^k p_i^{e_i}$ に対して

\[\varphi(n) = n \prod_{i = 1}^k \left(1 - \frac{1}{p_i}\right)\]

が成り立つ。

オイラーの定理

$n \perp a$ を満たす $n, a \in \mathbb{N}^+$ に対して $a^{\varphi(n)} \equiv 1 \pmod{n}$ が成り立つ。

時間計算量

	時間計算量
	$O(\sqrt{N})$
数表	$O(N\log{\log{N}})$
数表2	$O\left(\sqrt{H}\log{\log{H}} + \frac{(H - L)\sqrt{H}}{\log{H}}\right)$ ?

仕様

名前	戻り値
long long euler_phi(long long n);	$\varphi(n)$

数表

名前	戻り値
std::vector<int> euler_phi_init(const int n);	$\varphi(i)$ ($1 \leq i \leq n$) の数表

数表2

名前	戻り値
std::vector<long long> euler_phi_init2(const long long low, const long long high);	$\varphi(i)$ ($\mathrm{low} \leq i < \mathrm{high}$) の数表

参考文献

• Leonhard Euler: Theoremata arithmetica nova methodo demonstrata, Novi Commentarii academiae scientiarum Petropolitanae, Vol. 8, pp. 74–104 (1763).
• https://ei1333.github.io/algorithm/euler-phi.html

数表2

• https://github.com/spaghetti-source/algorithm/blob/87f5b3e4a3c10d8b85048f4fc4e4842ad11e9670/number_theory/euler_phi.cc

TODO

• $\sum_{i = 1}^n \varphi(i)$ を $O(N^{\frac{2}{3}})$ で求める。
  • https://yukicoder.me/wiki/sum_totient
  • https://min-25.hatenablog.com/entry/2018/11/11/172216
  • https://judge.yosupo.jp/problem/sum_of_totient_function

Submissons

• https://onlinejudge.u-aizu.ac.jp/solutions/problem/NTL_1_D/review/4088206/emthrm/C++14
• 数表
• 数表2

Depends on

• prime sieve (include/emthrm/math/prime_sieve.hpp)

Verified with

• 数学/オイラーの $\varphi$ 関数/オイラーの $\varphi$ 関数の数表2 (test/math/euler_phi_init2.test.cpp)

Code

#ifndef EMTHRM_MATH_EULER_PHI_INIT2_HPP_
#define EMTHRM_MATH_EULER_PHI_INIT2_HPP_

#include <numeric>
#include <vector>

#include "emthrm/math/prime_sieve.hpp"

namespace emthrm {

std::vector<long long> euler_phi_init2(const long long low,
                                       const long long high) {
  std::vector<long long> phi(high - low), rem(high - low);
  std::iota(phi.begin(), phi.end(), low);
  std::iota(rem.begin(), rem.end(), low);
  long long root = 1;
  while ((root + 1) * (root + 1) < high) ++root;
  for (const int p : prime_sieve<true>(root)) {
    for (long long i = (low + p - 1) / p * p; i < high; i += p) {
      phi[i - low] -= phi[i - low] / p;
      while (rem[i - low] % p == 0) rem[i - low] /= p;
    }
  }
  for (int i = 0; i < high - low; ++i) {
    if (rem[i] > 1) phi[i] -= phi[i] / rem[i];
  }
  return phi;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_EULER_PHI_INIT2_HPP_

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



#include <numeric>
#include <vector>

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



#line 6 "include/emthrm/math/prime_sieve.hpp"

namespace emthrm {

template <bool GETS_ONLY_PRIME>
std::vector<int> prime_sieve(const int n) {
  std::vector<int> smallest_prime_factor(n + 1), prime;
  std::iota(smallest_prime_factor.begin(), smallest_prime_factor.end(), 0);
  for (int i = 2; i <= n; ++i) {
    if (smallest_prime_factor[i] == i) [[unlikely]] prime.emplace_back(i);
    for (const int p : prime) {
      if (i * p > n || p > smallest_prime_factor[i]) break;
      smallest_prime_factor[i * p] = p;
    }
  }
  return GETS_ONLY_PRIME ? prime : smallest_prime_factor;
}

}  // namespace emthrm


#line 8 "include/emthrm/math/euler_phi_init2.hpp"

namespace emthrm {

std::vector<long long> euler_phi_init2(const long long low,
                                       const long long high) {
  std::vector<long long> phi(high - low), rem(high - low);
  std::iota(phi.begin(), phi.end(), low);
  std::iota(rem.begin(), rem.end(), low);
  long long root = 1;
  while ((root + 1) * (root + 1) < high) ++root;
  for (const int p : prime_sieve<true>(root)) {
    for (long long i = (low + p - 1) / p * p; i < high; i += p) {
      phi[i - low] -= phi[i - low] / p;
      while (rem[i - low] % p == 0) rem[i - low] /= p;
    }
  }
  for (int i = 0; i < high - low; ++i) {
    if (rem[i] > 1) phi[i] -= phi[i] / rem[i];
  }
  return phi;
}

}  // namespace emthrm

Back to top page