src/nt/crt/basic/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../math/safe_mod/lib.hpp" | ||
| 4 | #include "../../gl/inv_gcd/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | namespace crt_impl_ { | ||
| 8 | 17000036 | CEXP auto crt2(i64 a0, u64 m0, i64 a1, u64 m1) NE { | |
| 9 | 17000036 | std::optional<pttii> ret; | |
| 10 |
2/2✓ Branch 0 taken 6600022 times.
✓ Branch 1 taken 10400014 times.
|
17000036 | if (m0 < m1) swap(a0, a1), swap(m0, m1); |
| 11 | 17000036 | auto [d, x] = inv_gcd(m0, m1); | |
| 12 | 17000036 | ci64 a1_a0 = a1 - a0, a1_a0_d = a1_a0 / (i64)d; | |
| 13 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 17000036 times.
|
17000036 | if (a1_a0 != a1_a0_d * (i64)d) return ret; |
| 14 | 17000036 | ci64 m1_d = (i64)(m1 / d); | |
| 15 | 17000036 | i64 k0 = (i64)x % m1_d * (a1_a0_d % m1_d) % m1_d; | |
| 16 |
2/2✓ Branch 0 taken 4186755 times.
✓ Branch 1 taken 12813281 times.
|
17000036 | if (k0 < 0) k0 += m1_d; |
| 17 | 17000036 | ret.emplace(a0 + k0 * (i64)m0, (i64)m0 * m1_d); | |
| 18 | 17000036 | return ret; | |
| 19 | } | ||
| 20 | } // namespace crt_impl_ | ||
| 21 | |||
| 22 | // Returns (remainder, modular) | ||
| 23 | 5400014 | CEXP auto crt(spnii a, spnuu m) NE { | |
| 24 | 5400014 | std::optional<pttuu> ret; | |
| 25 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 5400014 times.
|
5400014 | if (a.size() != m.size()) return ret; |
| 26 | 5400014 | ret.emplace(0, 1); | |
| 27 | 5400014 | cu32 n = (u32)a.size(); | |
| 28 |
2/2✓ Branch 0 taken 17000036 times.
✓ Branch 1 taken 5400014 times.
|
22400050 | flt_ (u32, i, 0, n) |
| 29 |
1/2✗ Branch 9 not taken.
✓ Branch 10 taken 17000036 times.
|
17000036 | if (ret = crt_impl_::crt2(safe_mod(a[i], m[i]), m[i], (i64)ret->first, ret->second); !ret) return ret; |
| 30 | 5400014 | return ret; | |
| 31 | } | ||
| 32 | CEXP auto crt(spnuu a, spnuu m) NE { | ||
| 33 | vecii a_(a.size()); | ||
| 34 | flt_ (u32, i, 0, (u32)a.size()) a_[i] = (i64)a[i]; | ||
| 35 | return crt(a_, m); | ||
| 36 | } | ||
| 37 | |||
| 38 | } // namespace tifa_libs | ||
| 39 |