From ac2d9ad3f2c88bc12420fc439e8d0b4775a11169 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Fri, 30 Aug 2024 15:04:20 +0200
Subject: various small improvements

---
 content/other/recover.cpp | 12 ++++++++++++
 1 file changed, 12 insertions(+)
 create mode 100644 content/other/recover.cpp

(limited to 'content/other/recover.cpp')

diff --git a/content/other/recover.cpp b/content/other/recover.cpp
new file mode 100644
index 0000000..0d3c3ea
--- /dev/null
+++ b/content/other/recover.cpp
@@ -0,0 +1,12 @@
+ll sq(ll x) {return x*x;}
+
+pair<ll, ll> recover(ll c, ll m) {
+	array<ll, 3> u = {1, 0, m}, v = {0, 1, c};
+	while (m <= 2 * sq(v[2])) {
+		ll q = u[2] / v[2];
+		for (int i : {0, 1, 2}) u[i] -= q * v[i];
+		swap(u, v);
+	}
+	if (v[1] < 0 || 2 * sq(v[1]) >= m) return {-1, -1};
+	return {v[2], v[1]};
+}
-- 
cgit v1.2.3