C++ Library for Competitive Programming
#include "emthrm/math/euler_phi_init2.hpp"
$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$) の数表 |
名前 | 戻り値 |
---|---|
std::vector<long long> euler_phi_init2(const long long low, const long long high); |
$\varphi(i)$ ($\mathrm{low} \leq i < \mathrm{high}$) の数表 |
数表2
#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