Fast Division
(Math/fastdiv.hpp)

• View this file on GitHub
• Last update: 2023-01-17 01:58:11+09:00
• Include: #include "Math/fastdiv.hpp"

Required by

• Multivarate Convolution Cyclic (Convolution/multivariatecyclic.hpp)
• Binomial Coefficient for query (Math/binomquery.hpp)
• Dynamic Modint (Math/dynamic.hpp)
• Primitive Function (Math/primitive.hpp)
• Stirling Number for query (Math/stirlingquery.hpp)

Verified with

• Verify/LC_binomial_coefficient.test.cpp
• Verify/LC_discrete_logarithm_mod.test.cpp
• Verify/LC_multivariate_convolution_cyclic.test.cpp
• Verify/LC_stirling_number_of_the_first_kind_small_p_large_n.test.cpp
• Verify/LC_stirling_number_of_the_second_kind_small_p_large_n.test.cpp

Code

#pragma once

struct FastDiv{
    using u64=uint64_t;
    using u128=__uint128_t;
    constexpr FastDiv():m(),s(),x(){}
    constexpr FastDiv(int _m)
        :m(_m),s(__lg(m-1)),x(((u128(1)<<(s+64))+m-1)/m){}
    constexpr int get(){return m;}
    constexpr friend u64 operator/(u64 n,const FastDiv& d){
        return (u128(n)*d.x>>d.s)>>64;
    }
    constexpr friend int operator%(u64 n,const FastDiv& d){
        return n-n/d*d.m;
    }
    constexpr pair<u64,int> divmod(u64 n)const{
        u64 q=n/(*this);
        return {q,n-q*m};
    }
    int m,s; u64 x;
};

/**
 * @brief Fast Division
*/

#line 2 "Math/fastdiv.hpp"

struct FastDiv{
    using u64=uint64_t;
    using u128=__uint128_t;
    constexpr FastDiv():m(),s(),x(){}
    constexpr FastDiv(int _m)
        :m(_m),s(__lg(m-1)),x(((u128(1)<<(s+64))+m-1)/m){}
    constexpr int get(){return m;}
    constexpr friend u64 operator/(u64 n,const FastDiv& d){
        return (u128(n)*d.x>>d.s)>>64;
    }
    constexpr friend int operator%(u64 n,const FastDiv& d){
        return n-n/d*d.m;
    }
    constexpr pair<u64,int> divmod(u64 n)const{
        u64 q=n/(*this);
        return {q,n-q*m};
    }
    int m,s; u64 x;
};

/**
 * @brief Fast Division
*/

Back to top page