math/multiplicative_function/arbitrary_table.hpp

• View this file on GitHub
• Last update: 2025-04-05 12:46:42+09:00
• Include: #include "math/multiplicative_function/arbitrary_table.hpp"

Depends on

• math/lpf_table.hpp
• math/pow.hpp

Verified with

• verify/unit_test/multiplicative_function_table.test.cpp

Code

#ifndef KK2_MATH_MULTIPLICATIVE_FUNCTION_ARBITRARY_TABLE_HPP
#define KK2_MATH_MULTIPLICATIVE_FUNCTION_ARBITRARY_TABLE_HPP 1

#include <cassert>
#include <vector>

#include "../lpf_table.hpp"
#include "../pow.hpp"

namespace kk2 {

template <class T, T (*f)(long long, long long)> struct MultiplicativeFunctionTable {
  private:
    static inline std::vector<int> _v_lpf{0, 0};
    static inline std::vector<T> _table{0, 1};

  public:
    MultiplicativeFunctionTable() = delete;

    static void set_upper(int m) {
        if ((int)_table.size() > m) return;
        int start = _table.size();

        LPFTable::set_upper(m);

        _v_lpf.resize(m + 1, 0);
        _table.resize(m + 1);

        for (int n = start; n <= m; ++n) {
            int p = LPFTable::lpf(n);
            if (p == n) {
                _v_lpf[n] = 1;
                _table[n] = f(p, 1);
            } else {
                if (n / p % p == 0) _v_lpf[n] = _v_lpf[n / p] + 1;
                else _v_lpf[n] = 1;

                int p_pw = pow<int>(p, _v_lpf[n]);
                int q = n / p_pw;
                T p_pw_val = f(p, _v_lpf[n]);
                if (q == 1) {
                    _table[n] = p_pw_val;
                } else {
                    _table[n] = _table[q] * p_pw_val;
                }
            }
        }
    }

    static T val(int n) {
        assert(n > 0);
        if ((int)_table.size() <= n) set_upper(n);
        return _table[n];
    }
};

} // namespace kk2

#endif // KK2_MATH_MULTIPLICATIVE_FUNCTION_ARBITRARY_TABLE_HPP

#line 1 "math/multiplicative_function/arbitrary_table.hpp"



#include <cassert>
#include <vector>

#line 1 "math/lpf_table.hpp"



#include <algorithm>
#line 6 "math/lpf_table.hpp"
#include <numeric>
#line 8 "math/lpf_table.hpp"

namespace kk2 {

struct LPFTable {
  private:
    static inline std::vector<int> _primes{2}, _lpf{};

  public:
    LPFTable() = delete;

    static void set_upper(int m, int reserve_size = 26355867) {
        if ((int)_lpf.size() == 0) _primes.reserve(reserve_size);
        if ((int)_lpf.size() > m) return;
        m = std::max<int>(2 * _lpf.size(), m);
        _lpf.resize(m + 1);
        iota(_lpf.begin(), _lpf.end(), 0);
        for (int i = 2; i <= m; i++) {
            if (_lpf[i] == i and _primes.back() < i) _primes.emplace_back(i);
            for (const long long p : _primes) {
                if (p * i > m) break;
                if (_lpf[i] < p) break;
                _lpf[p * i] = p;
            }
        }
    }

    static const std::vector<int> &primes() { return _primes; }

    template <typename It> struct PrimeIt {
        It bg, ed;

        PrimeIt(It bg_, It ed_) : bg(bg_), ed(ed_) {}

        It begin() const { return bg; }

        It end() const { return ed; }

        int size() const { return ed - bg; }

        int operator[](int i) const { return bg[i]; }

        std::vector<int> to_vec() const { return std::vector<int>(bg, ed); }
    };

    static auto primes(int n) {
        if (n >= (int)_lpf.size()) set_upper(n);
        return PrimeIt(_primes.begin(), std::upper_bound(_primes.begin(), _primes.end(), n));
    }

    static int lpf(int n) {
        assert(n > 1);
        if (n >= (int)_lpf.size()) set_upper(n);
        return _lpf[n];
    }

    static bool isprime(int n) {
        assert(n > 0);
        if (n >= (int)_lpf.size()) set_upper(n);
        return n != 1 and _lpf[n] == n;
    }
};

} // namespace kk2



#line 1 "math/pow.hpp"



#line 5 "math/pow.hpp"

namespace kk2 {

template <class S, class T, class U> constexpr S pow(T x, U n) {
    assert(n >= 0);
    S r = 1, y = x;
    while (n) {
        if (n & 1) r *= y;
        if (n >>= 1) y *= y;
    }
    return r;
}

} // namespace kk2


#line 9 "math/multiplicative_function/arbitrary_table.hpp"

namespace kk2 {

template <class T, T (*f)(long long, long long)> struct MultiplicativeFunctionTable {
  private:
    static inline std::vector<int> _v_lpf{0, 0};
    static inline std::vector<T> _table{0, 1};

  public:
    MultiplicativeFunctionTable() = delete;

    static void set_upper(int m) {
        if ((int)_table.size() > m) return;
        int start = _table.size();

        LPFTable::set_upper(m);

        _v_lpf.resize(m + 1, 0);
        _table.resize(m + 1);

        for (int n = start; n <= m; ++n) {
            int p = LPFTable::lpf(n);
            if (p == n) {
                _v_lpf[n] = 1;
                _table[n] = f(p, 1);
            } else {
                if (n / p % p == 0) _v_lpf[n] = _v_lpf[n / p] + 1;
                else _v_lpf[n] = 1;

                int p_pw = pow<int>(p, _v_lpf[n]);
                int q = n / p_pw;
                T p_pw_val = f(p, _v_lpf[n]);
                if (q == 1) {
                    _table[n] = p_pw_val;
                } else {
                    _table[n] = _table[q] * p_pw_val;
                }
            }
        }
    }

    static T val(int n) {
        assert(n > 0);
        if ((int)_table.size() <= n) set_upper(n);
        return _table[n];
    }
};

} // namespace kk2

Back to top page