From 0257f0b3c61f203f64c3817dfe19a08f6191517c Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Wed, 11 Sep 2024 00:29:27 +0200
Subject: moved stuff

---
 content/math/linearRecurrence.cpp | 14 +++++++-------
 content/math/math.tex             |  7 ++++++-
 content/math/recover.cpp          | 13 +++++++++++++
 3 files changed, 26 insertions(+), 8 deletions(-)
 create mode 100644 content/math/recover.cpp

(limited to 'content/math')

diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp
index c15c25c..ab86f71 100644
--- a/content/math/linearRecurrence.cpp
+++ b/content/math/linearRecurrence.cpp
@@ -10,21 +10,21 @@
 // 	return c;
 // }
 
-ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k){
+ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) {
 	int n = sz(c);
-	vector<ll> q(n+1, 1);
-	for(int i = 1; i <= n; i++) q[i] = (mod-c[i-1])%mod;
+	vector<ll> q(n + 1, 1);
+	for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i])%mod;
 	vector<ll> p = mul(f, q);
 	p.resize(n);
 	p.push_back(0);
-	do{
+	do {
 		vector<ll> q2 = q;
-		for(int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
+		for (int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
 		vector<ll> x = mul(p, q2), y = mul(q, q2);
-		for(int i = 0; i <= n; i++){
+		for (int i = 0; i <= n; i++){
 			p[i] = i == n ? 0 : x[2*i + (k&1)];
 			q[i] = y[2*i];
 		}
-	}while(k /= 2);
+	} while (k /= 2);
 	return p[0];
 }
\ No newline at end of file
diff --git a/content/math/math.tex b/content/math/math.tex
index fb66110..4ac6c9e 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -544,6 +544,11 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text
 \subsection{Wichtige Zahlen}
 \input{math/tables/composite}
 
+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }
+\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}
+\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
+\sourcecode{math/recover.cpp}
+
 \optional{
 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
 \begin{methods}
@@ -552,10 +557,10 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text
 	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
 \end{methods}
 \sourcecode{math/piLehmer.cpp}
-}
 
 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
 \sourcecode{math/piLegendre.cpp}
+}
 
 \begin{algorithm}[optional]{Big Integers}
 	\sourcecode{math/bigint.cpp}
diff --git a/content/math/recover.cpp b/content/math/recover.cpp
new file mode 100644
index 0000000..1a593f0
--- /dev/null
+++ b/content/math/recover.cpp
@@ -0,0 +1,13 @@
+ll sq(ll x) {return x*x;}
+
+array<ll, 2> recover(ll c, ll m) {
+	array<ll, 2> u = {m, 0}, v = {c, 1};
+	while (m <= 2 * sq(v[0])) {
+		ll q = u[0] / v[0];
+		u[0] -= q * v[0];
+		u[1] -= q * v[1];
+		swap(u, v);
+	}
+	if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1};
+	return v;
+}
-- 
cgit v1.2.3