Skip to content

divisor_summatory.hpp

SECTIONMath INCLUDEnoya/divisor_summatory.hpp

用整除分块计算 1 到 \(n\) 的约数个数总和，即求和 \(\sum_i\tau(i)\)，无需逐个分解整数。

\[ \displaystyle S(n)=\sum_{i=1}^n \tau(i) \]

Complexity: Time: O(sqrt(n)). Space: O(1) for summatory functions; O(sqrt(n)) for quotient enumeration.

AC 记录：enumerate_quotients。

跳到代码 · GitHub ↗

Implementation

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(sqrt(n)).
/// Space: O(1) for summatory functions; O(sqrt(n)) for quotient enumeration.

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <vector>

namespace noya {

/// @brief Return sum_{i=1}^n tau(i) in O(sqrt(n)) quotient blocks.
inline unsigned __int128 summatory_divisor_count(std::uint64_t n) {
  unsigned __int128 res = 0;
  for (std::uint64_t l = 1, r; l <= n; l = r + 1) {
    std::uint64_t quo = n / l;
    r = n / quo;
    res += static_cast<unsigned __int128>(r - l + 1) * quo;
  }
  return res;
}

/// @brief Return sum_{i=1}^n sigma(i) in O(sqrt(n)); n must be at most 1e18 so
/// the exact result fits unsigned 128-bit arithmetic.
inline unsigned __int128 summatory_divisor_sum(std::uint64_t n) {
  assert(n <= 1000000000000000000ULL);
  unsigned __int128 res = 0;
  for (std::uint64_t l = 1, r; l <= n; l = r + 1) {
    std::uint64_t quo = n / l;
    r = n / quo;
    unsigned __int128 cnt = r - l + 1;
    unsigned __int128 ndp = static_cast<unsigned __int128>(l) + r;
    unsigned __int128 is = (cnt % 2 == 0) ? cnt / 2 * ndp : cnt * (ndp / 2);
    res += is * quo;
  }
  return res;
}

/// @brief Return all distinct positive values floor(n / x) in increasing
/// order. Returns an empty vector when n is zero.
inline std::vector<std::uint64_t> distinct_quotients(std::uint64_t n) {
  std::vector<std::uint64_t> res;
  for (std::uint64_t l = 1, r; l <= n; l = r + 1) {
    std::uint64_t quo = n / l;
    res.push_back(quo);
    r = n / quo;
  }
  std::reverse(res.begin(), res.end());
  return res;
}

} // namespace noya

#ifndef NOYA_DIVISOR_SUMMATORY_HPP
#define NOYA_DIVISOR_SUMMATORY_HPP 1

/// @complexity Time: O(sqrt(n)).
/// Space: O(1) for summatory functions; O(sqrt(n)) for quotient enumeration.

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <vector>

namespace noya {

/// @brief Return sum_{i=1}^n tau(i) in O(sqrt(n)) quotient blocks.
inline unsigned __int128 summatory_divisor_count(std::uint64_t n) {
  unsigned __int128 res = 0;
  for (std::uint64_t l = 1, r; l <= n; l = r + 1) {
    std::uint64_t quo = n / l;
    r = n / quo;
    res += static_cast<unsigned __int128>(r - l + 1) * quo;
  }
  return res;
}

/// @brief Return sum_{i=1}^n sigma(i) in O(sqrt(n)); n must be at most 1e18 so
/// the exact result fits unsigned 128-bit arithmetic.
inline unsigned __int128 summatory_divisor_sum(std::uint64_t n) {
  assert(n <= 1000000000000000000ULL);
  unsigned __int128 res = 0;
  for (std::uint64_t l = 1, r; l <= n; l = r + 1) {
    std::uint64_t quo = n / l;
    r = n / quo;
    unsigned __int128 cnt = r - l + 1;
    unsigned __int128 ndp = static_cast<unsigned __int128>(l) + r;
    unsigned __int128 is = (cnt % 2 == 0) ? cnt / 2 * ndp : cnt * (ndp / 2);
    res += is * quo;
  }
  return res;
}

/// @brief Return all distinct positive values floor(n / x) in increasing
/// order. Returns an empty vector when n is zero.
inline std::vector<std::uint64_t> distinct_quotients(std::uint64_t n) {
  std::vector<std::uint64_t> res;
  for (std::uint64_t l = 1, r; l <= n; l = r + 1) {
    std::uint64_t quo = n / l;
    res.push_back(quo);
    r = n / quo;
  }
  std::reverse(res.begin(), res.end());
  return res;
}

} // namespace noya

#endif // NOYA_DIVISOR_SUMMATORY_HPP

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <vector>

/// @complexity Time: O(sqrt(n)).
/// Space: O(1) for summatory functions; O(sqrt(n)) for quotient enumeration.

namespace noya {

/// @brief Return sum_{i=1}^n tau(i) in O(sqrt(n)) quotient blocks.
inline unsigned __int128 summatory_divisor_count(std::uint64_t n) {
  unsigned __int128 res = 0;
  for (std::uint64_t l = 1, r; l <= n; l = r + 1) {
    std::uint64_t quo = n / l;
    r = n / quo;
    res += static_cast<unsigned __int128>(r - l + 1) * quo;
  }
  return res;
}

/// @brief Return sum_{i=1}^n sigma(i) in O(sqrt(n)); n must be at most 1e18 so
/// the exact result fits unsigned 128-bit arithmetic.
inline unsigned __int128 summatory_divisor_sum(std::uint64_t n) {
  assert(n <= 1000000000000000000ULL);
  unsigned __int128 res = 0;
  for (std::uint64_t l = 1, r; l <= n; l = r + 1) {
    std::uint64_t quo = n / l;
    r = n / quo;
    unsigned __int128 cnt = r - l + 1;
    unsigned __int128 ndp = static_cast<unsigned __int128>(l) + r;
    unsigned __int128 is = (cnt % 2 == 0) ? cnt / 2 * ndp : cnt * (ndp / 2);
    res += is * quo;
  }
  return res;
}

/// @brief Return all distinct positive values floor(n / x) in increasing
/// order. Returns an empty vector when n is zero.
inline std::vector<std::uint64_t> distinct_quotients(std::uint64_t n) {
  std::vector<std::uint64_t> res;
  for (std::uint64_t l = 1, r; l <= n; l = r + 1) {
    std::uint64_t quo = n / l;
    res.push_back(quo);
    r = n / quo;
  }
  std::reverse(res.begin(), res.end());
  return res;
}

} // namespace noya