math/divisor-table.hpp

• View this file on GitHub
• Last update: 2023-07-08 14:12:19+09:00
• Include: #include "math/divisor-table.hpp"

Depends on

• math/base.hpp

Code

#pragma once

#include "./base.hpp"

#include <vector>

namespace matumoto {
  struct DivisorTable {
    vector<int> smallest_ps;
    DivisorTable(int N): smallest_ps(N + 1, 1) {}

    void build() {
      int N = smallest_ps.size();
      for (long long i = 2; i <= N; i++) {
        if (smallest_ps[i] != 1)
          continue;
        smallest_ps[i] = i;
        for (long long j = i * i; j <= N; j += i) {
          if (smallest_ps[j] != 1)
            continue;
          smallest_ps[j] = i;
        }
      }
    }

    // M := count({ p = prime, p|x })
    // O(M2^M log x)
    vector<int> divisor(int x) {
      vector<int> ps;
      while (smallest_ps[x] != 1) {
        ps.push_back(smallest_ps[x]);
        x /= smallest_ps[x];
      }
      int m = ps.size();
      vector<int> ds(1 << m);
      for (int i = 0; i < (1 << m); i++) {
        int prod = 1;
        for (int j = 0; j < m; j++) {
          if (i >> j & 1)
            prod *= ps[j];
        }
        ds[i] = prod;
      }
      return ds;
    }

    bool is_prime(int k) {
      if (k <= 1)
        return false;
      return smallest_ps[k] == k;
    }

    int operator[](int i) {
      return smallest_ps[i];
    }
  };
} // namespace matumoto

#line 2 "math/divisor-table.hpp"

#line 2 "math/base.hpp"

namespace matumoto {
  using namespace std;
  using ll = long long;
} // namespace matumoto
#line 4 "math/divisor-table.hpp"

#include <vector>

namespace matumoto {
  struct DivisorTable {
    vector<int> smallest_ps;
    DivisorTable(int N): smallest_ps(N + 1, 1) {}

    void build() {
      int N = smallest_ps.size();
      for (long long i = 2; i <= N; i++) {
        if (smallest_ps[i] != 1)
          continue;
        smallest_ps[i] = i;
        for (long long j = i * i; j <= N; j += i) {
          if (smallest_ps[j] != 1)
            continue;
          smallest_ps[j] = i;
        }
      }
    }

    // M := count({ p = prime, p|x })
    // O(M2^M log x)
    vector<int> divisor(int x) {
      vector<int> ps;
      while (smallest_ps[x] != 1) {
        ps.push_back(smallest_ps[x]);
        x /= smallest_ps[x];
      }
      int m = ps.size();
      vector<int> ds(1 << m);
      for (int i = 0; i < (1 << m); i++) {
        int prod = 1;
        for (int j = 0; j < m; j++) {
          if (i >> j & 1)
            prod *= ps[j];
        }
        ds[i] = prod;
      }
      return ds;
    }

    bool is_prime(int k) {
      if (k <= 1)
        return false;
      return smallest_ps[k] == k;
    }

    int operator[](int i) {
      return smallest_ps[i];
    }
  };
} // namespace matumoto

Back to top page