dujiao_sieve.hpp¶
计算大 \(n\) 的 Möbius 或欧拉函数前缀和；用整除分块与记忆化避免筛到 \(n\)。
\[
\displaystyle M(x)=\sum_{i=1}^x \mu(i),\quad \Phi(x)=\sum_{i=1}^x \varphi(i)
\]
Complexity: Time: O(L) preprocessing; quotient-block memoized queries use the standard O(n^(2/3)) regime. Space: O(L + sqrt(n)) cached states.
AC 记录：sum_of_totient_function。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(L) preprocessing; quotient-block memoized queries use the standard O(n^(2/3)) regime.
/// Space: O(L + sqrt(n)) cached states.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <unordered_map>
#include <vector>
namespace noya {
/// @brief Summatory Mobius and Euler-phi functions with a linear-sieve prefix
/// and quotient-block memoization for large arguments.
struct dujiao_sieve {
std::vector<int> ps;
std::vector<int> mnp;
std::vector<std::int64_t> smu;
std::vector<__int128> sph;
std::unordered_map<std::uint64_t, std::int64_t> cmu;
std::unordered_map<std::uint64_t, __int128> cph;
explicit dujiao_sieve(int lim) { prepare(lim); }
/// @brief Rebuild the direct prefix tables through limit.
void prepare(int lim) {
assert(lim >= 0);
ps.clear();
mnp.assign(lim + 1, 0);
std::vector<std::int64_t> mu(lim + 1);
std::vector<std::uint64_t> phi(lim + 1);
if (lim >= 1) {
mu[1] = 1;
phi[1] = 1;
}
for (int val = 2; val <= lim; val++) {
if (mnp[val] == 0) {
mnp[val] = val;
ps.push_back(val);
mu[val] = -1;
phi[val] = val - 1;
}
for (int p : ps) {
if (p > mnp[val] || std::uint64_t(val) * p > std::uint64_t(lim)) {
break;
}
int prd = val * p;
mnp[prd] = p;
if (val % p == 0) {
mu[prd] = 0;
phi[prd] = phi[val] * p;
} else {
mu[prd] = -mu[val];
phi[prd] = phi[val] * (p - 1);
}
}
}
smu.assign(lim + 1, 0);
sph.assign(lim + 1, 0);
for (int val = 1; val <= lim; val++) {
smu[val] = smu[val - 1] + mu[val];
sph[val] = sph[val - 1] + phi[val];
}
cmu.clear();
cph.clear();
}
/// @brief Return sum_{i=1}^n mu(i).
std::int64_t summatory_mobius(std::uint64_t n) {
if (n < smu.size()) {
return smu[n];
}
if (auto it = cmu.find(n); it != cmu.end()) {
return it->second;
}
std::int64_t res = 1;
for (std::uint64_t l = 2, r; l <= n; l = r + 1) {
std::uint64_t quo = n / l;
r = n / quo;
res -= std::int64_t(r - l + 1) * summatory_mobius(quo);
}
return cmu.emplace(n, res).first->second;
}
/// @brief Return sum_{i=1}^n phi(i) as a signed 128-bit integer.
__int128 summatory_phi(std::uint64_t n) {
if (n < sph.size()) {
return sph[n];
}
if (auto it = cph.find(n); it != cph.end()) {
return it->second;
}
__int128 res = __int128(n) * (n + 1) / 2;
for (std::uint64_t l = 2, r; l <= n; l = r + 1) {
std::uint64_t quo = n / l;
r = n / quo;
res -= __int128(r - l + 1) * summatory_phi(quo);
}
return cph.emplace(n, res).first->second;
}
};
} // namespace noya
#ifndef NOYA_DUJIAO_SIEVE_HPP
#define NOYA_DUJIAO_SIEVE_HPP 1
/// @complexity Time: O(L) preprocessing; quotient-block memoized queries use the standard O(n^(2/3)) regime.
/// Space: O(L + sqrt(n)) cached states.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <unordered_map>
#include <vector>
namespace noya {
/// @brief Summatory Mobius and Euler-phi functions with a linear-sieve prefix
/// and quotient-block memoization for large arguments.
struct dujiao_sieve {
std::vector<int> ps;
std::vector<int> mnp;
std::vector<std::int64_t> smu;
std::vector<__int128> sph;
std::unordered_map<std::uint64_t, std::int64_t> cmu;
std::unordered_map<std::uint64_t, __int128> cph;
explicit dujiao_sieve(int lim) { prepare(lim); }
/// @brief Rebuild the direct prefix tables through limit.
void prepare(int lim) {
assert(lim >= 0);
ps.clear();
mnp.assign(lim + 1, 0);
std::vector<std::int64_t> mu(lim + 1);
std::vector<std::uint64_t> phi(lim + 1);
if (lim >= 1) {
mu[1] = 1;
phi[1] = 1;
}
for (int val = 2; val <= lim; val++) {
if (mnp[val] == 0) {
mnp[val] = val;
ps.push_back(val);
mu[val] = -1;
phi[val] = val - 1;
}
for (int p : ps) {
if (p > mnp[val] || std::uint64_t(val) * p > std::uint64_t(lim)) {
break;
}
int prd = val * p;
mnp[prd] = p;
if (val % p == 0) {
mu[prd] = 0;
phi[prd] = phi[val] * p;
} else {
mu[prd] = -mu[val];
phi[prd] = phi[val] * (p - 1);
}
}
}
smu.assign(lim + 1, 0);
sph.assign(lim + 1, 0);
for (int val = 1; val <= lim; val++) {
smu[val] = smu[val - 1] + mu[val];
sph[val] = sph[val - 1] + phi[val];
}
cmu.clear();
cph.clear();
}
/// @brief Return sum_{i=1}^n mu(i).
std::int64_t summatory_mobius(std::uint64_t n) {
if (n < smu.size()) {
return smu[n];
}
if (auto it = cmu.find(n); it != cmu.end()) {
return it->second;
}
std::int64_t res = 1;
for (std::uint64_t l = 2, r; l <= n; l = r + 1) {
std::uint64_t quo = n / l;
r = n / quo;
res -= std::int64_t(r - l + 1) * summatory_mobius(quo);
}
return cmu.emplace(n, res).first->second;
}
/// @brief Return sum_{i=1}^n phi(i) as a signed 128-bit integer.
__int128 summatory_phi(std::uint64_t n) {
if (n < sph.size()) {
return sph[n];
}
if (auto it = cph.find(n); it != cph.end()) {
return it->second;
}
__int128 res = __int128(n) * (n + 1) / 2;
for (std::uint64_t l = 2, r; l <= n; l = r + 1) {
std::uint64_t quo = n / l;
r = n / quo;
res -= __int128(r - l + 1) * summatory_phi(quo);
}
return cph.emplace(n, res).first->second;
}
};
} // namespace noya
#endif // NOYA_DUJIAO_SIEVE_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <unordered_map>
#include <vector>
/// @complexity Time: O(L) preprocessing; quotient-block memoized queries use the standard O(n^(2/3)) regime.
/// Space: O(L + sqrt(n)) cached states.
namespace noya {
/// @brief Summatory Mobius and Euler-phi functions with a linear-sieve prefix
/// and quotient-block memoization for large arguments.
struct dujiao_sieve {
std::vector<int> ps;
std::vector<int> mnp;
std::vector<std::int64_t> smu;
std::vector<__int128> sph;
std::unordered_map<std::uint64_t, std::int64_t> cmu;
std::unordered_map<std::uint64_t, __int128> cph;
explicit dujiao_sieve(int lim) { prepare(lim); }
/// @brief Rebuild the direct prefix tables through limit.
void prepare(int lim) {
assert(lim >= 0);
ps.clear();
mnp.assign(lim + 1, 0);
std::vector<std::int64_t> mu(lim + 1);
std::vector<std::uint64_t> phi(lim + 1);
if (lim >= 1) {
mu[1] = 1;
phi[1] = 1;
}
for (int val = 2; val <= lim; val++) {
if (mnp[val] == 0) {
mnp[val] = val;
ps.push_back(val);
mu[val] = -1;
phi[val] = val - 1;
}
for (int p : ps) {
if (p > mnp[val] || std::uint64_t(val) * p > std::uint64_t(lim)) {
break;
}
int prd = val * p;
mnp[prd] = p;
if (val % p == 0) {
mu[prd] = 0;
phi[prd] = phi[val] * p;
} else {
mu[prd] = -mu[val];
phi[prd] = phi[val] * (p - 1);
}
}
}
smu.assign(lim + 1, 0);
sph.assign(lim + 1, 0);
for (int val = 1; val <= lim; val++) {
smu[val] = smu[val - 1] + mu[val];
sph[val] = sph[val - 1] + phi[val];
}
cmu.clear();
cph.clear();
}
/// @brief Return sum_{i=1}^n mu(i).
std::int64_t summatory_mobius(std::uint64_t n) {
if (n < smu.size()) {
return smu[n];
}
if (auto it = cmu.find(n); it != cmu.end()) {
return it->second;
}
std::int64_t res = 1;
for (std::uint64_t l = 2, r; l <= n; l = r + 1) {
std::uint64_t quo = n / l;
r = n / quo;
res -= std::int64_t(r - l + 1) * summatory_mobius(quo);
}
return cmu.emplace(n, res).first->second;
}
/// @brief Return sum_{i=1}^n phi(i) as a signed 128-bit integer.
__int128 summatory_phi(std::uint64_t n) {
if (n < sph.size()) {
return sph[n];
}
if (auto it = cph.find(n); it != cph.end()) {
return it->second;
}
__int128 res = __int128(n) * (n + 1) / 2;
for (std::uint64_t l = 2, r; l <= n; l = r + 1) {
std::uint64_t quo = n / l;
r = n / quo;
res -= __int128(r - l + 1) * summatory_phi(quo);
}
return cph.emplace(n, res).first->second;
}
};
} // namespace noya