cpp_src/number_theory/HelperFunctions.hpp

• View this file on GitHub
• Last update: 2023-01-02 15:43:52+09:00
• Include: #include "cpp_src/number_theory/HelperFunctions.hpp"

Code

// floor(a / b)
template <class T>
T div_floor(T a, T b) {
    return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}

// ceil(a / b)
template <class T>
T div_ceil(T a, T b) {
    return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}

// x^k mod m
template <class T, class U>
T powmod(T x, U k, T m) {
    x %= m;
    T res = 1 % m;
    while (k) {
        if (k & 1) {
            res = res * x % m;
        }
        k >>= 1;
        x = x * x % m;
    }
    return res;
}

// x mod m, negative allowed
template <class T>
T mod(T x, T m) {
    T res = x % m;
    if (res < 0) res += m;
    return res;
}

constexpr ll floor_sqrt(ll n) {
    if (n == 0) return 0;
    return llround(trunc(floor(sqrt((long double)n))));
}

constexpr ll ceil_sqrt(ll n) {
    if (n == 0) return 0;
    return llround(trunc(ceil(sqrt((long double)n))));
}

// from USACO
using ull = unsigned long long;
using L = __uint128_t;

struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b;  // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
};

#line 1 "cpp_src/number_theory/HelperFunctions.hpp"
// floor(a / b)
template <class T>
T div_floor(T a, T b) {
    return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}

// ceil(a / b)
template <class T>
T div_ceil(T a, T b) {
    return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}

// x^k mod m
template <class T, class U>
T powmod(T x, U k, T m) {
    x %= m;
    T res = 1 % m;
    while (k) {
        if (k & 1) {
            res = res * x % m;
        }
        k >>= 1;
        x = x * x % m;
    }
    return res;
}

// x mod m, negative allowed
template <class T>
T mod(T x, T m) {
    T res = x % m;
    if (res < 0) res += m;
    return res;
}

constexpr ll floor_sqrt(ll n) {
    if (n == 0) return 0;
    return llround(trunc(floor(sqrt((long double)n))));
}

constexpr ll ceil_sqrt(ll n) {
    if (n == 0) return 0;
    return llround(trunc(ceil(sqrt((long double)n))));
}

// from USACO
using ull = unsigned long long;
using L = __uint128_t;

struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b;  // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
};

Back to top page