src/nt/gl/inv_gcd/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../math/safe_mod/lib.hpp" | ||
| 4 | #include "../../../util/alias/others/lib.hpp" | ||
| 5 | #include "../exgcd/lib.hpp" | ||
| 6 | |||
| 7 | namespace tifa_libs { | ||
| 8 | |||
| 9 | template <uint_c T> | ||
| 10 | 2576006513 | CEXP ptt<T> inv_gcd(T n, T mod) NE { | |
| 11 | using U = to_sint_t<T>; | ||
| 12 | 2576006513 | auto [g, x] = exgcd<U, true>(U(n % mod), (U)mod); | |
| 13 | 2576006513 | return {g, safe_mod(x, mod)}; | |
| 14 | } | ||
| 15 | |||
| 16 | } // namespace tifa_libs | ||
| 17 |