divisor_summatory.hpp

SECTIONMath INCLUDEnoya/math/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

ReferenceSourceExpanded

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

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

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

namespace noya {

/// @brief Return sum_{i=1}^n tau(i) by splitting at floor(sqrt(n)).
inline unsigned __int128 summatory_divisor_count(std::uint64_t n) {
  unsigned __int128 res = 0;
  std::uint64_t r = 0;
  for (std::uint64_t i = 1; i <= n / i; i++) {
    res += n / i;
    r = i;
  }
  // Count both halves of a*b <= n, subtracting their shared r-by-r square.
  return 2 * res - static_cast<unsigned __int128>(r) * r;
}

/// @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);
  using u128 = unsigned __int128;
  unsigned __int128 res = 0;
  std::uint64_t r = 0;
  for (std::uint64_t i = 1; i <= n / i; i++) {
    std::uint64_t q = n / i;
    res += u128(i) * q + u128(q) * (q + 1) / 2;
    r = i;
  }
  // The shared square contributes r * (1 + ... + r).
  return res - u128(r) * r * (r + 1) / 2;
}

/// @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;
  std::uint64_t r = 0;
  for (std::uint64_t i = 1; i <= n / i; i++) {
    res.push_back(i);
    r = i;
  }
  for (std::uint64_t i = n / (r + 1); i > 0; i--)
    res.push_back(n / i);
  return res;
}

} // namespace noya

 // NOYA_DIVISOR_SUMMATORY_HPP

#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 <cassert>
#include <cstdint>
#include <vector>

namespace noya {

/// @brief Return sum_{i=1}^n tau(i) by splitting at floor(sqrt(n)).
inline unsigned __int128 summatory_divisor_count(std::uint64_t n) {
  unsigned __int128 res = 0;
  std::uint64_t r = 0;
  for (std::uint64_t i = 1; i <= n / i; i++) {
    res += n / i;
    r = i;
  }
  // Count both halves of a*b <= n, subtracting their shared r-by-r square.
  return 2 * res - static_cast<unsigned __int128>(r) * r;
}

/// @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);
  using u128 = unsigned __int128;
  unsigned __int128 res = 0;
  std::uint64_t r = 0;
  for (std::uint64_t i = 1; i <= n / i; i++) {
    std::uint64_t q = n / i;
    res += u128(i) * q + u128(q) * (q + 1) / 2;
    r = i;
  }
  // The shared square contributes r * (1 + ... + r).
  return res - u128(r) * r * (r + 1) / 2;
}

/// @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;
  std::uint64_t r = 0;
  for (std::uint64_t i = 1; i <= n / i; i++) {
    res.push_back(i);
    r = i;
  }
  for (std::uint64_t i = n / (r + 1); i > 0; i--)
    res.push_back(n / i);
  return res;
}

} // namespace noya

#endif // NOYA_DIVISOR_SUMMATORY_HPP

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

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

namespace noya {

/// @brief Return sum_{i=1}^n tau(i) by splitting at floor(sqrt(n)).
inline unsigned __int128 summatory_divisor_count(std::uint64_t n) {
  unsigned __int128 res = 0;
  std::uint64_t r = 0;
  for (std::uint64_t i = 1; i <= n / i; i++) {
    res += n / i;
    r = i;
  }
  // Count both halves of a*b <= n, subtracting their shared r-by-r square.
  return 2 * res - static_cast<unsigned __int128>(r) * r;
}

/// @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);
  using u128 = unsigned __int128;
  unsigned __int128 res = 0;
  std::uint64_t r = 0;
  for (std::uint64_t i = 1; i <= n / i; i++) {
    std::uint64_t q = n / i;
    res += u128(i) * q + u128(q) * (q + 1) / 2;
    r = i;
  }
  // The shared square contributes r * (1 + ... + r).
  return res - u128(r) * r * (r + 1) / 2;
}

/// @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;
  std::uint64_t r = 0;
  for (std::uint64_t i = 1; i <= n / i; i++) {
    res.push_back(i);
    r = i;
  }
  for (std::uint64_t i = n / (r + 1); i > 0; i--)
    res.push_back(n / i);
  return res;
}

} // namespace noya

 // NOYA_DIVISOR_SUMMATORY_HPP