various small improvements

1 files changed, 12 insertions, 0 deletions

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]};
+}