library

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

View the Project on GitHub kk2a/library

:warning: math/multiplicative_function/counting_square_free.hpp

Depends on

Code

#ifndef KK2_MATH_MULTIPLICATIVE_FUNCTION_COUNTING_SQUARE_FREE_HPP
#define KK2_MATH_MULTIPLICATIVE_FUNCTION_COUNTING_SQUARE_FREE_HPP 1

#include <cmath>

#include "../enumerate_quotients.hpp"
#include "famous_function_table.hpp"

namespace kk2 {

long long counting_square_free(long long n) {
    long long I = std::pow(n, 0.2);
    long long D = kk2::sqrt_floor(n / I);
}

} // namespace kk2


#endif // KK2_MATH_MULTIPLICATIVE_FUNCTION_COUNTING_SQUARE_FREE_HPP
#line 1 "math/multiplicative_function/counting_square_free.hpp"



#include <cmath>

#line 1 "math/enumerate_quotients.hpp"



#include <numeric>
#include <vector>

#line 1 "math/sqrt_floor.hpp"



#line 5 "math/sqrt_floor.hpp"

#line 1 "math/frac_floor.hpp"



#include <cassert>

namespace kk2 {

// floor(x) = ceil(x) - 1 (for all x not in Z) ...(1)
// floor(x) = -ceil(-x)   (for all x)          ...(2)

// return floor(a / b)
template <typename T, typename U> constexpr T fracfloor(T a, U b) {
    assert(b != 0);
    if (a % b == 0) return a / b;
    if (a >= 0) return a / b;

    // floor(x) = -ceil(-x)      by (2)
    //          = -floor(-x) - 1 by (1)
    return -((-a) / b) - 1;
}

// return ceil(a / b)
template <typename T, typename U> constexpr T fracceil(T a, U b) {
    assert(b != 0);
    if (a % b == 0) return a / b;
    if (a >= 0) return a / b + 1;

    // ceil(x) = -floor(-x)      by (2)
    return -((-a) / b);
}

} // namespace kk2


#line 7 "math/sqrt_floor.hpp"

namespace kk2 {

template <typename T> T sqrt_floor(T n) {
    assert(n >= 0);
    if (n == T(0)) return 0;
    T x = std::sqrt(n);
    if (x == T(0)) ++x;
    while (x > kk2::fracfloor(n, x)) --x;
    while (x + 1 <= kk2::fracfloor(n, x + 1)) ++x;
    return x;
}

template <typename T> T sqrt_ceil(T n) {
    assert(n >= 0);
    if (n <= T(1)) return n;
    T x = std::sqrt(n);
    if (x == T(0)) ++x;
    while (x < kk2::fracceil(n, x)) ++x;
    while (x - 1 >= kk2::fracceil(n, x - 1)) --x;
    return x;
}

} // namespace kk2


#line 8 "math/enumerate_quotients.hpp"

namespace kk2 {

template <class T> struct EnumerateQuotients {
    T n;
    int sqrt_n;
    std::vector<T> res;

    EnumerateQuotients(T n) : n(n), sqrt_n(sqrt_floor(n)) {
        res.resize(sqrt_n + n / (sqrt_n + 1));
        std::iota(res.begin(), res.begin() + sqrt_n, 1);
        for (T i = n / (sqrt_n + 1), j = sqrt_n; i; --i, ++j) res[j] = n / i;
    }

    const std::vector<T> &get() const { return res; }

    int size() const { return res.size(); }

    const T &operator[](int i) const { return res[i]; }

    int idx(T x) const {
        if (x <= sqrt_n) return x - 1;
        return size() - n / x;
    }
};

} // namespace kk2


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



#include <algorithm>
#line 7 "math/multiplicative_function/famous_function_table.hpp"

#line 1 "math/lpf_table.hpp"



#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


#line 8 "math/multiplicative_function/counting_square_free.hpp"

namespace kk2 {

long long counting_square_free(long long n) {
    long long I = std::pow(n, 0.2);
    long long D = kk2::sqrt_floor(n / I);
}

} // namespace kk2
Back to top page