math/multiplicative_function/famous_function_table.hpp

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

Depends on

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

Required by

• math/multiplicative_function/counting_square_free.hpp

Verified with

• verify/unit_test/famous_function_table.test.cpp
• verify/unit_test/multiplicative_function_table.test.cpp

Code

#ifndef KK2_MATH_MULTIPLICATIVE_FUNCTION_FAMOUS_FUNCTION_TABLE_HPP
#define KK2_MATH_MULTIPLICATIVE_FUNCTION_FAMOUS_FUNCTION_TABLE_HPP 1

#include <algorithm>
#include <cassert>
#include <vector>

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

namespace kk2 {

struct FamousFunctionTable {
  private:
    static inline std::vector<int> _v_lpf{0, 0}, _mobius{0, 1}, _sigma0{0, 1}, _euler_phi{0, 1};
    static inline std::vector<long long> _sigma1{0, 1};

  public:
    FamousFunctionTable() = delete;

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

        LPFTable::set_upper(m);

        _v_lpf.resize(m + 1, 0);
        _mobius.resize(m + 1, 1);
        _sigma0.resize(m + 1, 1);
        _sigma1.resize(m + 1, 1);
        _euler_phi.resize(m + 1, 1);

        for (int n = start; n <= m; ++n) {
            int p = LPFTable::lpf(n);
            if (p == n) {
                _v_lpf[n] = 1;
                _mobius[n] = -1;
                _sigma0[n] = 2;
                _sigma1[n] = p + 1;
                _euler_phi[n] = 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;
                if (q == 1) {
                    _mobius[n] = 0;
                    _sigma0[n] = _v_lpf[n] + 1;
                    _sigma1[n] = _sigma1[n / p] + p_pw;
                    _euler_phi[n] = p_pw - p_pw / p;
                } else {
                    _mobius[n] = _mobius[q] * _mobius[p_pw];
                    _sigma0[n] = _sigma0[q] * _sigma0[p_pw];
                    _sigma1[n] = _sigma1[q] * _sigma1[p_pw];
                    _euler_phi[n] = _euler_phi[q] * _euler_phi[p_pw];
                }
            }
        }
    }

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

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

    static long long sigma1(int n) {
        assert(n > 0);
        if ((int)_sigma1.size() <= n) set_upper(n);
        return _sigma1[n];
    }

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

} // namespace kk2

#endif // KK2_MATH_MULTIPLICATIVE_FUNCTION_FAMOUS_FUNCTION_TABLE_HPP

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



#include <algorithm>
#include <cassert>
#include <vector>

#line 1 "math/lpf_table.hpp"



#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 10 "math/multiplicative_function/famous_function_table.hpp"

namespace kk2 {

struct FamousFunctionTable {
  private:
    static inline std::vector<int> _v_lpf{0, 0}, _mobius{0, 1}, _sigma0{0, 1}, _euler_phi{0, 1};
    static inline std::vector<long long> _sigma1{0, 1};

  public:
    FamousFunctionTable() = delete;

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

        LPFTable::set_upper(m);

        _v_lpf.resize(m + 1, 0);
        _mobius.resize(m + 1, 1);
        _sigma0.resize(m + 1, 1);
        _sigma1.resize(m + 1, 1);
        _euler_phi.resize(m + 1, 1);

        for (int n = start; n <= m; ++n) {
            int p = LPFTable::lpf(n);
            if (p == n) {
                _v_lpf[n] = 1;
                _mobius[n] = -1;
                _sigma0[n] = 2;
                _sigma1[n] = p + 1;
                _euler_phi[n] = 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;
                if (q == 1) {
                    _mobius[n] = 0;
                    _sigma0[n] = _v_lpf[n] + 1;
                    _sigma1[n] = _sigma1[n / p] + p_pw;
                    _euler_phi[n] = p_pw - p_pw / p;
                } else {
                    _mobius[n] = _mobius[q] * _mobius[p_pw];
                    _sigma0[n] = _sigma0[q] * _sigma0[p_pw];
                    _sigma1[n] = _sigma1[q] * _sigma1[p_pw];
                    _euler_phi[n] = _euler_phi[q] * _euler_phi[p_pw];
                }
            }
        }
    }

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

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

    static long long sigma1(int n) {
        assert(n > 0);
        if ((int)_sigma1.size() <= n) set_upper(n);
        return _sigma1[n];
    }

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

} // namespace kk2

Back to top page