Src/Number/Mersenne61ModInt.hpp

View this file on GitHub
Last update: 2023-12-04 20:18:49+09:00
Include: #include "Src/Number/Mersenne61ModInt.hpp"
Link: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6

Depends on

標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

Verified with

Code

#pragma once

#include "../Template/TypeAlias.hpp"

namespace zawa {

// @reference: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
class Mersenne61ModInt {
public:
    using Value = u64;
private:
    static constexpr Value MOD{(1ull << 61) - 1}; // == MASK61
    static constexpr Value MASK30{(1ull << 30) - 1};
    static constexpr Value MASK31{(1ull << 31) - 1};
    Value v_{};
public:
    constexpr Mersenne61ModInt() {}

    static constexpr Value Mod() noexcept {
        return MOD;
    }
    static constexpr Value Modulo(const Value& v) noexcept {
        Value res{(v >> 61) + (v & MOD)};
        res = (res >= MOD ? res - MOD : res);
        return res;
    }
    static constexpr Value UnsafeMul(const Value& a, const Value& b) noexcept {
        Value fa{a >> 31}, fb{b >> 31};
        Value ba{a & MASK31}, bb{b & MASK31};
        Value mid{fa * bb + fb * ba};
        return Value{2}*fa*fb + (mid >> 30) + ((mid & MASK30) << 31) + ba*bb;
    }
    static constexpr Value Mul(const Value& a, const Value& b) noexcept {
        return Modulo(UnsafeMul(a, b));
    }
};

};

#line 2 "Src/Number/Mersenne61ModInt.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Number/Mersenne61ModInt.hpp"

namespace zawa {

// @reference: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
class Mersenne61ModInt {
public:
    using Value = u64;
private:
    static constexpr Value MOD{(1ull << 61) - 1}; // == MASK61
    static constexpr Value MASK30{(1ull << 30) - 1};
    static constexpr Value MASK31{(1ull << 31) - 1};
    Value v_{};
public:
    constexpr Mersenne61ModInt() {}

    static constexpr Value Mod() noexcept {
        return MOD;
    }
    static constexpr Value Modulo(const Value& v) noexcept {
        Value res{(v >> 61) + (v & MOD)};
        res = (res >= MOD ? res - MOD : res);
        return res;
    }
    static constexpr Value UnsafeMul(const Value& a, const Value& b) noexcept {
        Value fa{a >> 31}, fb{b >> 31};
        Value ba{a & MASK31}, bb{b & MASK31};
        Value mid{fa * bb + fb * ba};
        return Value{2}*fa*fb + (mid >> 30) + ((mid & MASK30) << 31) + ba*bb;
    }
    static constexpr Value Mul(const Value& a, const Value& b) noexcept {
        return Modulo(UnsafeMul(a, b));
    }
};

};