From 3c174f527d8b16e84b3aaaf7b448469bb9682566 Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Sun, 17 Nov 2024 16:32:46 +0100
Subject: allow multInv(x, m) with x >= m

---
 content/math/shortModInv.cpp | 2 +-
 test/math/shortModInv.cpp    | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/content/math/shortModInv.cpp b/content/math/shortModInv.cpp
index cf91ca0..7d3002c 100644
--- a/content/math/shortModInv.cpp
+++ b/content/math/shortModInv.cpp
@@ -1,3 +1,3 @@
 ll multInv(ll x, ll m) { // x^{-1} mod m
-	return 1 < x ? m - multInv(m % x, x) * m / x : 1;
+	return 1 < (x %= m) ? m - multInv(m, x) * m / x : 1;
 }
diff --git a/test/math/shortModInv.cpp b/test/math/shortModInv.cpp
index 26960bf..565989c 100644
--- a/test/math/shortModInv.cpp
+++ b/test/math/shortModInv.cpp
@@ -7,7 +7,7 @@ void stress_test() {
 		ll n = Random::integer<ll>(2, 1'000'000'000);
 		ll x = 0;
 		do {
-			x = Random::integer<ll>(0, n);
+			x = Random::integer<ll>(0, 1'000'000'000);
 		} while (gcd(x, n) != 1);
 		ll y = multInv(x, n);
 		ll got = (x*y) % n;
-- 
cgit v1.2.3