diff options
| -rw-r--r-- | math/extendedEuclid.cpp | 9 | ||||
| -rw-r--r-- | math/multInv.cpp | 7 | ||||
| -rw-r--r-- | math/shortModInv.cpp | 6 |
3 files changed, 10 insertions, 12 deletions
diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp index d016a63..ecf4a16 100644 --- a/math/extendedEuclid.cpp +++ b/math/extendedEuclid.cpp @@ -1,7 +1,6 @@ // a*x + b*y = ggt(a, b) -ll extendedEuclid(ll a, ll b, ll& x, ll& y) { - if (a == 0) {x = 0; y = 1; return b;} - ll x1, y1, d = extendedEuclid(b % a, a, x1, y1); - x = y1 - (b / a) * x1; y = x1; - return d; +array<ll, 3> extendedEuclid(ll a, ll b) { + if (a == 0) return {b, 0, 1}; + auto [d, x, y] = extendedEuclid(b % a, a); + return {d, y - (b / a) * x, x}; } diff --git a/math/multInv.cpp b/math/multInv.cpp index 87603f3..647dc2d 100644 --- a/math/multInv.cpp +++ b/math/multInv.cpp @@ -1,5 +1,4 @@ -ll multInv(ll n, ll p) { - ll x, y; - extendedEuclid(n, p, x, y); // Implementierung von oben. - return ((x % p) + p) % p; +ll multInv(ll x, ll m) { + auto [d, a, b] = extendedEuclid(x, m); // Implementierung von oben. + return ((a % m) + m) % m; } diff --git a/math/shortModInv.cpp b/math/shortModInv.cpp index 747eb7a..244bacf 100644 --- a/math/shortModInv.cpp +++ b/math/shortModInv.cpp @@ -1,3 +1,3 @@ -ll inv(ll a, ll b){ // a^{-1} mod b - return 1 < a ? b - inv(b % a, a) * b / a : 1; -}
\ No newline at end of file +ll multInv(ll x, ll m) { // x^{-1} mod m + return 1 < x ? m - inv(m % x, x) * m / x : 1; +} |