Skip to content

divisor_table.hpp

SECTIONMath INCLUDEnoya/divisor_table.hpp

线性预处理上界内每个整数的约数个数 τ 和约数和 σ，供大量逐点查询使用。

\[ \displaystyle (\tau(n),\sigma(n)) \]

Complexity: Time: O(n) build and O(1) table lookup. Space: O(n).

跳到代码 · GitHub ↗

Implementation

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

/// @complexity Time: O(n) build and O(1) table lookup.
/// Space: O(n).

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

namespace noya {

/// @brief Linear-sieve table of divisor count tau(n) and divisor sum sigma(n)
/// for every integer through a limit.
struct divisor_table {
  std::vector<int> ps;
  std::vector<int> mnp;
  std::vector<int> exp;
  std::vector<std::uint64_t> pp;
  std::vector<std::uint64_t> tau;
  std::vector<std::uint64_t> sig;

  divisor_table() = default;
  explicit divisor_table(int lim) { build(lim); }

  void build(int lim) {
    assert(lim >= 0);
    ps.clear();
    mnp.assign(lim + 1, 0);
    exp.assign(lim + 1, 0);
    pp.assign(lim + 1, 1);
    tau.assign(lim + 1, 0);
    sig.assign(lim + 1, 0);
    if (lim >= 1) {
      tau[1] = sig[1] = 1;
    }
    for (int val = 2; val <= lim; val++) {
      if (mnp[val] == 0) {
        mnp[val] = val;
        exp[val] = 1;
        pp[val] = val;
        tau[val] = 2;
        sig[val] = val + 1;
        ps.push_back(val);
      }
      for (int p : ps) {
        if (val > lim / p) {
          break;
        }
        int prd = val * p;
        mnp[prd] = p;
        if (val % p == 0) {
          exp[prd] = exp[val] + 1;
          pp[prd] = pp[val] * p;
          int res = int(val / pp[val]);
          tau[prd] = tau[res] * std::uint64_t(exp[prd] + 1);
          sig[prd] = sig[res] * ((pp[prd] * p - 1) / (p - 1));
          break;
        }
        exp[prd] = 1;
        pp[prd] = p;
        tau[prd] = tau[val] * 2;
        sig[prd] = sig[val] * (p + 1);
      }
    }
  }
};

} // namespace noya

#ifndef NOYA_DIVISOR_TABLE_HPP
#define NOYA_DIVISOR_TABLE_HPP 1

/// @complexity Time: O(n) build and O(1) table lookup.
/// Space: O(n).

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

namespace noya {

/// @brief Linear-sieve table of divisor count tau(n) and divisor sum sigma(n)
/// for every integer through a limit.
struct divisor_table {
  std::vector<int> ps;
  std::vector<int> mnp;
  std::vector<int> exp;
  std::vector<std::uint64_t> pp;
  std::vector<std::uint64_t> tau;
  std::vector<std::uint64_t> sig;

  divisor_table() = default;
  explicit divisor_table(int lim) { build(lim); }

  void build(int lim) {
    assert(lim >= 0);
    ps.clear();
    mnp.assign(lim + 1, 0);
    exp.assign(lim + 1, 0);
    pp.assign(lim + 1, 1);
    tau.assign(lim + 1, 0);
    sig.assign(lim + 1, 0);
    if (lim >= 1) {
      tau[1] = sig[1] = 1;
    }
    for (int val = 2; val <= lim; val++) {
      if (mnp[val] == 0) {
        mnp[val] = val;
        exp[val] = 1;
        pp[val] = val;
        tau[val] = 2;
        sig[val] = val + 1;
        ps.push_back(val);
      }
      for (int p : ps) {
        if (val > lim / p) {
          break;
        }
        int prd = val * p;
        mnp[prd] = p;
        if (val % p == 0) {
          exp[prd] = exp[val] + 1;
          pp[prd] = pp[val] * p;
          int res = int(val / pp[val]);
          tau[prd] = tau[res] * std::uint64_t(exp[prd] + 1);
          sig[prd] = sig[res] * ((pp[prd] * p - 1) / (p - 1));
          break;
        }
        exp[prd] = 1;
        pp[prd] = p;
        tau[prd] = tau[val] * 2;
        sig[prd] = sig[val] * (p + 1);
      }
    }
  }
};

} // namespace noya

#endif // NOYA_DIVISOR_TABLE_HPP

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

/// @complexity Time: O(n) build and O(1) table lookup.
/// Space: O(n).

namespace noya {

/// @brief Linear-sieve table of divisor count tau(n) and divisor sum sigma(n)
/// for every integer through a limit.
struct divisor_table {
  std::vector<int> ps;
  std::vector<int> mnp;
  std::vector<int> exp;
  std::vector<std::uint64_t> pp;
  std::vector<std::uint64_t> tau;
  std::vector<std::uint64_t> sig;

  divisor_table() = default;
  explicit divisor_table(int lim) { build(lim); }

  void build(int lim) {
    assert(lim >= 0);
    ps.clear();
    mnp.assign(lim + 1, 0);
    exp.assign(lim + 1, 0);
    pp.assign(lim + 1, 1);
    tau.assign(lim + 1, 0);
    sig.assign(lim + 1, 0);
    if (lim >= 1) {
      tau[1] = sig[1] = 1;
    }
    for (int val = 2; val <= lim; val++) {
      if (mnp[val] == 0) {
        mnp[val] = val;
        exp[val] = 1;
        pp[val] = val;
        tau[val] = 2;
        sig[val] = val + 1;
        ps.push_back(val);
      }
      for (int p : ps) {
        if (val > lim / p) {
          break;
        }
        int prd = val * p;
        mnp[prd] = p;
        if (val % p == 0) {
          exp[prd] = exp[val] + 1;
          pp[prd] = pp[val] * p;
          int res = int(val / pp[val]);
          tau[prd] = tau[res] * std::uint64_t(exp[prd] + 1);
          sig[prd] = sig[res] * ((pp[prd] * p - 1) / (p - 1));
          break;
        }
        exp[prd] = 1;
        pp[prd] = p;
        tau[prd] = tau[val] * 2;
        sig[prd] = sig[val] * (p + 1);
      }
    }
  }
};

} // namespace noya