src/math/ds/mint/be61n1/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../_base/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | class mint_2e61n1_tag : public mint_impl_::mint_tag_base { | ||
| 8 | static CEXP u64 MOD = (1ull << 61) - 1, _30 = (1 << 30) - 1, _31 = (1u << 31) - 1; | ||
| 9 | |||
| 10 | public: | ||
| 11 | static CEXP bool FIXED_MOD = true; | ||
| 12 | |||
| 13 | protected: | ||
| 14 | using raw_t = u64; | ||
| 15 | raw_t v_{}; | ||
| 16 | 34293 | CEXP mint_2e61n1_tag() NE = default; | |
| 17 | 264674851 | CEXP mint_2e61n1_tag(int_c auto v) NE : v_{mod(v)} {} | |
| 18 | |||
| 19 | public: | ||
| 20 | // clang-format off | ||
| 21 | template <uint_c T> | ||
| 22 |
4/4✓ Branch 0 taken 1032912769 times.
✓ Branch 1 taken 416974182 times.
✓ Branch 2 taken 6022 times.
✓ Branch 3 taken 416968160 times.
|
1714552858 | static CEXP raw_t mod(T x) NE { if(x < MOD)return (raw_t)x; if((x = T(((raw_t)x & MOD) + ((raw_t)x >> 61))) >= MOD)return x - MOD; return (raw_t)x; } |
| 23 | template <sint_c T> | ||
| 24 |
1/2✓ Branch 0 taken 69489437 times.
✗ Branch 1 not taken.
|
69489437 | static CEXP raw_t mod(T x) NE { retif_((x >= 0), mod(to_uint_t<T>(x)), MOD - mod(to_uint_t<T>(-x))); } |
| 25 | // clang-format on | ||
| 26 | 8944 | static CEXP raw_t mod() NE { return MOD; } | |
| 27 | 7930819357 | ND CEXP raw_t val() CNE { return v_; } | |
| 28 | 1999578052 | CEXP raw_t& data() NE { return v_; } | |
| 29 | |||
| 30 | protected: | ||
| 31 | template <class mint> | ||
| 32 | CEXP auto neg() CNE { return mint(MOD - val()); } | ||
| 33 | 169618226 | CEXP void add(mint_2e61n1_tag CR r) NE { data() = mod(val() + r.val()); } | |
| 34 |
2/2✓ Branch 2 taken 302255743 times.
✓ Branch 3 taken 549700045 times.
|
851955788 | CEXP void sub(mint_2e61n1_tag CR r) NE { val() < r.val() ? data() = mod(val() + MOD - r.val()) : data() -= r.val(); } |
| 35 | 978004038 | CEXP void mul(mint_2e61n1_tag CR r) NE { | |
| 36 | 978004038 | const raw_t au = val() >> 31, ad = val() & _31, bu = r.val() >> 31, bd = r.val() & _31, _ = ad * bu + au * bd; | |
| 37 | 978004038 | data() = mod(((au * bu) << 1) + ad * bd + ((_ & _30) << 31) + (_ >> 30)); | |
| 38 | 978004038 | } | |
| 39 | }; | ||
| 40 | using mint_2e61n1 = mint_impl_::mint<mint_2e61n1_tag>; | ||
| 41 | |||
| 42 | } // namespace tifa_libs | ||
| 43 |