math/multiplicative_function/famous_function.hpp

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

Depends on

• math/pow.hpp

Verified with

• verify/unit_test/multiplicative_function_table.test.cpp

Code

#ifndef KK2_MATH_MULTIPLICATIVE_FUNCTION_FAMOUS_FUNCTION_HPP
#define KK2_MATH_MULTIPLICATIVE_FUNCTION_FAMOUS_FUNCTION_HPP 1

#include "../pow.hpp"

namespace kk2 {

namespace mf {

long long mobius(long long, long long e) { return e == 1 ? -1 : 0; }

long long sigma0(long long, long long e) { return e + 1; }

long long sigma1(long long p, long long e) {
    long long p_e = pow<long long>(p, e);
    return p_e + (p_e - 1) / (p - 1);
}

long long euler_phi(long long p, long long e) {
    long long p_e = pow<long long>(p, e);
    return p_e - p_e / p;
}

} // namespace mf

} // namespace kk2

#endif // KK2_MATH_MULTIPLICATIVE_FUNCTION_FAMOUS_FUNCTION_HPP

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



#line 1 "math/pow.hpp"



#include <cassert>

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 5 "math/multiplicative_function/famous_function.hpp"

namespace kk2 {

namespace mf {

long long mobius(long long, long long e) { return e == 1 ? -1 : 0; }

long long sigma0(long long, long long e) { return e + 1; }

long long sigma1(long long p, long long e) {
    long long p_e = pow<long long>(p, e);
    return p_e + (p_e - 1) / (p - 1);
}

long long euler_phi(long long p, long long e) {
    long long p_e = pow<long long>(p, e);
    return p_e - p_e / p;
}

} // namespace mf

} // namespace kk2

Back to top page