数学/オイラーの $\varphi$ 関数/オイラーの $\varphi$ 関数の数表2
(test/math/euler_phi_init2.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)
• オイラーの $\varphi$ 関数 (Euler's totient function) の数表2 (include/emthrm/math/euler_phi_init2.hpp)
• prime sieve (include/emthrm/math/prime_sieve.hpp)

Code

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

#include <iostream>
#include <vector>

#include "emthrm/math/euler_phi.hpp"
#include "emthrm/math/euler_phi_init2.hpp"

int main() {
  constexpr int L = 999000000, H = 1000000000;
  const std::vector<long long> ans = emthrm::euler_phi_init2(L, H + 1);
  int n;
  std::cin >> n;
  std::cout << (n >= L ? ans[n - L] : emthrm::euler_phi(n)) << '\n';
  return 0;
}

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

#include <iostream>
#include <vector>

#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 1 "include/emthrm/math/euler_phi_init2.hpp"



#include <numeric>
#line 6 "include/emthrm/math/euler_phi_init2.hpp"

#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


#line 12 "test/math/euler_phi_init2.test.cpp"

int main() {
  constexpr int L = 999000000, H = 1000000000;
  const std::vector<long long> ans = emthrm::euler_phi_init2(L, H + 1);
  int n;
  std::cin >> n;
  std::cout << (n >= L ? ans[n - L] : emthrm::euler_phi(n)) << '\n';
  return 0;
}

Back to top page