Nyaan's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: 乗法的関数の列挙
(multiplicative-function/enumerate-multiplicative-function.hpp)

Depends on

Required by

Verified with

Code

#pragma once

#include <vector>
using namespace std;

#include "../prime/prime-enumerate.hpp"

// f(n, p, c) : n = pow(p, c), f is multiplicative function

template <typename T, T (*f)(int, int, int)>
struct enumerate_multiplicative_function {
  enumerate_multiplicative_function(int _n)
      : ps(prime_enumerate(_n)), a(_n + 1, T()), n(_n), p(ps.size()) {}

  vector<T> run() {
    a[1] = 1;
    dfs(-1, 1, 1);
    return a;
  }

 private:
  vector<int> ps;
  vector<T> a;
  int n, p;
  void dfs(int i, long long x, T y) {
    a[x] = y;
    if (y == T()) return;
    for (int j = i + 1; j < p; j++) {
      long long nx = x * ps[j];
      long long dx = ps[j];
      if (nx > n) break;
      for (int c = 1; nx <= n; nx *= ps[j], dx *= ps[j], ++c) {
        dfs(j, nx, y * f(dx, ps[j], c));
      }
    }
  }
};

template <typename T, T (*f)(int, int, int)>
using enamurate_multiplicative_function =
    enumerate_multiplicative_function<T, f>;

/**
 * @brief 乗法的関数の列挙
 */
#line 2 "multiplicative-function/enumerate-multiplicative-function.hpp"

#include <vector>
using namespace std;

#line 2 "prime/prime-enumerate.hpp"

#include <cmath>
#line 5 "prime/prime-enumerate.hpp"
using namespace std;

// Prime Sieve {2, 3, 5, 7, 11, 13, 17, ...}
vector<int> prime_enumerate(int N) {
  vector<bool> sieve(N / 3 + 1, 1);
  for (int p = 5, d = 4, i = 1, sqn = sqrt(N); p <= sqn; p += d = 6 - d, i++) {
    if (!sieve[i]) continue;
    for (int q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p,
             qe = sieve.size();
         q < qe; q += r = s - r)
      sieve[q] = 0;
  }
  vector<int> ret{2, 3};
  for (int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++)
    if (sieve[i]) ret.push_back(p);
  while (!ret.empty() && ret.back() > N) ret.pop_back();
  return ret;
}
#line 7 "multiplicative-function/enumerate-multiplicative-function.hpp"

// f(n, p, c) : n = pow(p, c), f is multiplicative function

template <typename T, T (*f)(int, int, int)>
struct enumerate_multiplicative_function {
  enumerate_multiplicative_function(int _n)
      : ps(prime_enumerate(_n)), a(_n + 1, T()), n(_n), p(ps.size()) {}

  vector<T> run() {
    a[1] = 1;
    dfs(-1, 1, 1);
    return a;
  }

 private:
  vector<int> ps;
  vector<T> a;
  int n, p;
  void dfs(int i, long long x, T y) {
    a[x] = y;
    if (y == T()) return;
    for (int j = i + 1; j < p; j++) {
      long long nx = x * ps[j];
      long long dx = ps[j];
      if (nx > n) break;
      for (int c = 1; nx <= n; nx *= ps[j], dx *= ps[j], ++c) {
        dfs(j, nx, y * f(dx, ps[j], c));
      }
    }
  }
};

template <typename T, T (*f)(int, int, int)>
using enamurate_multiplicative_function =
    enumerate_multiplicative_function<T, f>;

/**
 * @brief 乗法的関数の列挙
 */
Back to top page