Tifa's CP Library

:heavy_check_mark: src/nt/mod/montgomery/lib.hpp

Depends on

Required by

Verified with

Code

#pragma once

#include "../../../util/alias/num/lib.hpp"

namespace tifa_libs {

template <u32 MOD>
struct montgomery {
  static CEXP u32 MOD2 = MOD << 1, R2 = -(u64)(MOD) % MOD, R = [] {
    u32 iv = MOD * (2 - MOD * MOD);
    iv *= 2 - MOD * iv, iv *= 2 - MOD * iv;
    return iv * (MOD * iv - 2);
  }();
  static_assert(MOD & 1);
  static_assert(-R * MOD == 1);
  static_assert((MOD >> 30) == 0);
  static_assert(MOD != 1);
  static CEXP u32 reduce(u64 x) NE { return u32((x + u64((u32)x * R) * MOD) >> 32); }
  static CEXP u32 norm(u32 x) NE { return x - (MOD & -((MOD - 1 - x) >> 31)); }
};
template <>  // dynamic
struct montgomery<0> {
  u32 R, R2, MOD, MOD_ODD, OFFSET, MASK;
  CEXP montgomery() NE = default;
  CEXPE montgomery(u32 m) NE { reset(m); }
  CEXP void reset(u32 m) NE {
    for (assert(!(m == 1 || m >> 31)), MOD = MOD_ODD = m, OFFSET = 0; (MOD_ODD & 1) == 0; ++OFFSET, MOD_ODD /= 2);
    MASK = (1_u32 << OFFSET) - 1_u32;
    u32 iv = MOD_ODD * (2 - MOD_ODD * MOD_ODD);
    iv *= 2 - MOD_ODD * iv, iv *= 2 - MOD_ODD * iv, R = iv * (MOD_ODD * iv - 2), R2 = u32(-u64(MOD_ODD) % MOD_ODD);
  }
  ND CEXP u32 norm(i32 x) CNE { return u32(x + (-(x < 0) & (i32)MOD)); }
  ND CEXP u32 reduce(u64 x) CNE {
    cu32 t = u32((x + u64((u32)x * R) * MOD_ODD) >> 32);
    return t - (MOD_ODD & -((MOD_ODD - 1 - t) >> 31));
  }
  ND CEXP u32 tsf(u32 x) CNE { retif_((!OFFSET) [[likely]], reduce(u64(x) * R2), reduce(u64(x % MOD_ODD) * R2) << OFFSET | (x & MASK)); }
};

}  // namespace tifa_libs

#line 2 "src/nt/mod/montgomery/lib.hpp"

#line 2 "src/util/alias/num/lib.hpp"

#line 2 "src/util/util/lib.hpp"
// https://github.com/Tiphereth-A/CP-lib
#include <bits/extc++.h>
// clang-format off
namespace tifa_libs {

#define CEXP constexpr
#define CEXPE constexpr explicit
#define CR const&
#define CP const*
#define PC *const
#define CPC const*const
#define TPN typename
#define NE noexcept
#define CNE const noexcept
#define ND [[nodiscard]]
#define cT_(...) std::conditional_t<sizeof(__VA_ARGS__) <= sizeof(size_t) * 2, __VA_ARGS__, __VA_ARGS__ CR>
// NOLINTNEXTLINE(misc-const-correctness)
#define flt_(T, i, l, r, ...) for (T i = (l), i##e = (r)__VA_OPT__(, ) __VA_ARGS__; i < i##e; ++i)
#define retif_(cond, if_true, ...) if cond return if_true __VA_OPT__(; else return __VA_ARGS__)
#ifdef ONLINE_JUDGE
#undef assert
#define assert(x) 42
#endif

using namespace std::ranges;
using namespace std::literals;

template <class T>
CEXP T abs(T x) NE { retif_((x < 0), -x, x); }

}  // namespace tifa_libs
// clang-format on
#line 4 "src/util/alias/num/lib.hpp"
// clang-format off
namespace tifa_libs {

#define mk0_(w, t) using w = t; using c##w = const t
#define mk_(w, t) mk0_(w, t); CEXP w operator""_##w(unsigned long long x) NE { return (w)x; }
mk_(i8, int8_t) mk_(u8, uint8_t) mk_(i16, int16_t) mk_(u16, uint16_t) mk_(i32, int32_t) mk_(u32, uint32_t) mk_(i64, int64_t) mk_(u64, uint64_t) mk_(isz, ssize_t) mk_(usz, size_t) mk_(chr, char) mk_(schr, signed char) mk_(uchr, unsigned char) mk_(sint, signed) mk_(uint, unsigned);
mk0_(i128, __int128_t); mk0_(u128, __uint128_t); mk0_(f32, float); mk0_(f64, double); mk0_(f128, long double);
#undef mk0_
#undef mk_

}  // namespace tifa_libs
// clang-format on
#line 4 "src/nt/mod/montgomery/lib.hpp"

namespace tifa_libs {

template <u32 MOD>
struct montgomery {
  static CEXP u32 MOD2 = MOD << 1, R2 = -(u64)(MOD) % MOD, R = [] {
    u32 iv = MOD * (2 - MOD * MOD);
    iv *= 2 - MOD * iv, iv *= 2 - MOD * iv;
    return iv * (MOD * iv - 2);
  }();
  static_assert(MOD & 1);
  static_assert(-R * MOD == 1);
  static_assert((MOD >> 30) == 0);
  static_assert(MOD != 1);
  static CEXP u32 reduce(u64 x) NE { return u32((x + u64((u32)x * R) * MOD) >> 32); }
  static CEXP u32 norm(u32 x) NE { return x - (MOD & -((MOD - 1 - x) >> 31)); }
};
template <>  // dynamic
struct montgomery<0> {
  u32 R, R2, MOD, MOD_ODD, OFFSET, MASK;
  CEXP montgomery() NE = default;
  CEXPE montgomery(u32 m) NE { reset(m); }
  CEXP void reset(u32 m) NE {
    for (assert(!(m == 1 || m >> 31)), MOD = MOD_ODD = m, OFFSET = 0; (MOD_ODD & 1) == 0; ++OFFSET, MOD_ODD /= 2);
    MASK = (1_u32 << OFFSET) - 1_u32;
    u32 iv = MOD_ODD * (2 - MOD_ODD * MOD_ODD);
    iv *= 2 - MOD_ODD * iv, iv *= 2 - MOD_ODD * iv, R = iv * (MOD_ODD * iv - 2), R2 = u32(-u64(MOD_ODD) % MOD_ODD);
  }
  ND CEXP u32 norm(i32 x) CNE { return u32(x + (-(x < 0) & (i32)MOD)); }
  ND CEXP u32 reduce(u64 x) CNE {
    cu32 t = u32((x + u64((u32)x * R) * MOD_ODD) >> 32);
    return t - (MOD_ODD & -((MOD_ODD - 1 - t) >> 31));
  }
  ND CEXP u32 tsf(u32 x) CNE { retif_((!OFFSET) [[likely]], reduce(u64(x) * R2), reduce(u64(x % MOD_ODD) * R2) << OFFSET | (x & MASK)); }
};

}  // namespace tifa_libs
Back to top page
This site is open source. Improve this page.