src/nt/crt/mod/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 | |||
| 8 | template <uint_c T = u64> | ||
| 9 | 25 | CEXP auto crt_mod(vec<T> CR r, vec<T> m, cu64 mod) NE { | |
| 10 | static_assert(sizeof(T) >= 8); | ||
| 11 | using S = to_sint_t<T>; | ||
| 12 | 25 | std::optional<ptt<T>> ret; | |
| 13 | 25 | cu32 l = (u32)m.size(); | |
| 14 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 25 times.
|
25 | assert(r.size() == l); |
| 15 | 25 | m.push_back(mod); | |
| 16 | 50 | vec<T> p(l + 1, 1), x(l + 1); | |
| 17 |
2/2✓ Branch 0 taken 16890 times.
✓ Branch 1 taken 22 times.
|
16912 | flt_ (u32, i, 0, l) { |
| 18 | 16890 | T b = r[i], n = m[i]; | |
| 19 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 16890 times.
|
16890 | assert(n > 0); |
| 20 | 16890 | auto [g, ip] = inv_gcd(p[i], n); | |
| 21 | 16890 | S q = S(b - x[i]) / (S)g; | |
| 22 |
2/2✓ Branch 1 taken 3 times.
✓ Branch 2 taken 16887 times.
|
16890 | if (S(b - x[i]) % (S)g) return ret; |
| 23 | 16887 | n /= g; | |
| 24 | 16887 | T t = (T)safe_mod(q % (S)n * (S)ip, n); | |
| 25 |
2/2✓ Branch 5 taken 8394186 times.
✓ Branch 6 taken 16887 times.
|
8411073 | flt_ (u32, j, i + 1, l + 1) (x[j] += t * p[j]) %= m[j], (p[j] *= n) %= m[j]; |
| 26 | } | ||
| 27 | 22 | ret.emplace(x.back(), p.back()); | |
| 28 | 22 | return ret; | |
| 29 | 25 | } | |
| 30 | |||
| 31 | } // namespace tifa_libs | ||
| 32 |