kpr/math/Montgomery.hpp

• View this file on GitHub
• Last update: 2023-05-30 09:27:18+09:00
• Include: #include "kpr/math/Montgomery.hpp"

Depends on

• kpr/meta/setting.hpp

Required by

• kpr/all.hpp
• kpr/all/all.hpp
• kpr/math/DynamicModInt.hpp
• kpr/math/factorize.hpp
• kpr/math/is_prime.hpp
• kpr/math/math.hpp
• kpr/template/alias.hpp
• kpr/template/template.hpp

Verified with

• verify/yosupo/factorize.test.cpp

Code

#pragma once
#include <cstdint>
#include <limits>
#include <type_traits>
#include "../meta/setting.hpp"

namespace kpr {
    template<class T>
    struct Montgomery {
        static_assert(is_unsigned_integer_v<T>, "The given type must be an unsigned integer type");

        using value_type = T;

        T mod;

    private:
        using larger_type = next_integer_t<T>;

        T r, n2;

    public:
        constexpr void set_mod(T mod) noexcept {
            this->mod = mod;
            n2 = -static_cast<larger_type>(mod) % mod;
            T t = 0;
            r = 0;
            for (int i = 0; i < std::numeric_limits<T>::digits; ++i) {
                if (!(t & 1)) {
                    t += mod;
                    r += static_cast<T>(1) << static_cast<T>(i);
                }
                t >>= 1;
            }
        }

        constexpr KYOPRO_BASE_INT get_mod() const noexcept {
            return mod;
        }

        Montgomery() noexcept = default;
        Montgomery(T mod) noexcept {
            set_mod(mod);
        }

        constexpr T transform(T x) const noexcept {
            return reduce(static_cast<larger_type>(x) * n2);
        }

        constexpr T inv_transform(T x) const noexcept {
            T y = reduce(x);
            return y >= mod ? y - mod : y;
        }

        constexpr T reduce(larger_type x) const noexcept {
            return (x + static_cast<larger_type>(static_cast<T>(x) * r) * mod) >> std::numeric_limits<T>::digits;
        }
    };
} // namespace kpr

#line 2 "kpr/math/Montgomery.hpp"
#include <cstdint>
#include <limits>
#include <type_traits>
#line 3 "kpr/meta/setting.hpp"

#ifndef KYOPRO_BASE_INT
// 基本符号付き整数型

#define KYOPRO_BASE_INT std::int64_t
#endif

#ifndef KYOPRO_BASE_UINT
// 基本符号なし整数型

#define KYOPRO_BASE_UINT std::uint64_t
#endif

#ifndef KYOPRO_BASE_FLOAT
// 基本浮動小数点数型

#define KYOPRO_BASE_FLOAT double
#endif

#ifndef KYOPRO_LL
// ll

#define KYOPRO_LL long long
#endif

#ifndef KYOPRO_LF
// lf

#define KYOPRO_LF double
#endif

#ifndef KYOPRO_MINT
// mint

#define KYOPRO_MINT kpr::ModInt<mod>
#endif

#ifndef KYOPRO_DEFAULT_MOD
// 問題で設定されたmod

#define KYOPRO_DEFAULT_MOD (static_cast<KYOPRO_BASE_UINT>(998244353))
#endif

#ifndef KYOPRO_DECIMAL_PRECISION
// 小数精度(桁)

#define KYOPRO_DECIMAL_PRECISION (static_cast<KYOPRO_BASE_UINT>(12))
#endif

#ifndef KYOPRO_INF_DIV
// 無限大を表す整数が最大値の何分の一かを表す

#define KYOPRO_INF_DIV (static_cast<KYOPRO_BASE_UINT>(3))
#endif

#ifndef KYOPRO_BUFFER_SIZE
// デフォルトのバッファサイズ

#define KYOPRO_BUFFER_SIZE (static_cast<KYOPRO_BASE_UINT>(2048))
#endif

#ifndef KYOPRO_BINOM_MOD_MAX
// デフォルトのBinomModの計算上限

#define KYOPRO_BINOM_MOD_MAX (static_cast<KYOPRO_BASE_UINT>(1000000))
#endif
#line 6 "kpr/math/Montgomery.hpp"

namespace kpr {
    template<class T>
    struct Montgomery {
        static_assert(is_unsigned_integer_v<T>, "The given type must be an unsigned integer type");

        using value_type = T;

        T mod;

    private:
        using larger_type = next_integer_t<T>;

        T r, n2;

    public:
        constexpr void set_mod(T mod) noexcept {
            this->mod = mod;
            n2 = -static_cast<larger_type>(mod) % mod;
            T t = 0;
            r = 0;
            for (int i = 0; i < std::numeric_limits<T>::digits; ++i) {
                if (!(t & 1)) {
                    t += mod;
                    r += static_cast<T>(1) << static_cast<T>(i);
                }
                t >>= 1;
            }
        }

        constexpr KYOPRO_BASE_INT get_mod() const noexcept {
            return mod;
        }

        Montgomery() noexcept = default;
        Montgomery(T mod) noexcept {
            set_mod(mod);
        }

        constexpr T transform(T x) const noexcept {
            return reduce(static_cast<larger_type>(x) * n2);
        }

        constexpr T inv_transform(T x) const noexcept {
            T y = reduce(x);
            return y >= mod ? y - mod : y;
        }

        constexpr T reduce(larger_type x) const noexcept {
            return (x + static_cast<larger_type>(static_cast<T>(x) * r) * mod) >> std::numeric_limits<T>::digits;
        }
    };
} // namespace kpr

Back to top page