From 0fb5b77d3faf56b8c1d83516256f359086f3addd Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Fri, 21 Nov 2014 16:02:51 +0100 Subject: Primzahlsieb Signed-off-by: kittobi1992 --- math/primeSieve.cpp | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) create mode 100644 math/primeSieve.cpp (limited to 'math') diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp new file mode 100644 index 0000000..9981981 --- /dev/null +++ b/math/primeSieve.cpp @@ -0,0 +1,24 @@ +#include +#include + +vector primeSieve(int n) { + vector primes; + vector isPrime(n,true); + for(int i = 2; i < n; i+=2) { + if(i*i <= n) { + if(isPrime[i]) { + primes.push_back(i); + for(int j = 1; i*j < n; j++) { + isPrime[i*j] = false; + } + } + } + else { + if(isPrime[i]) + primes.push_back(i); + } + if(i == 2) + i--; + } + return primes; +} \ No newline at end of file -- cgit v1.2.3 From f0ca9a96291d0cc2d1af337ca4d6838339f94539 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Fri, 21 Nov 2014 16:07:24 +0100 Subject: Update primeSieve.cpp --- math/primeSieve.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'math') diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 9981981..c17b626 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -8,7 +8,7 @@ vector primeSieve(int n) { if(i*i <= n) { if(isPrime[i]) { primes.push_back(i); - for(int j = 1; i*j < n; j++) { + for(int j = 2; i*j < n; j++) { isPrime[i*j] = false; } } @@ -21,4 +21,4 @@ vector primeSieve(int n) { i--; } return primes; -} \ No newline at end of file +} -- cgit v1.2.3 From fa83b8c841073b462840260b54593767e597f543 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Fri, 21 Nov 2014 19:33:12 +0100 Subject: Update primeSieve.cpp fastest prime sieve --- math/primeSieve.cpp | 22 ++++++++++------------ 1 file changed, 10 insertions(+), 12 deletions(-) (limited to 'math') diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index c17b626..82a4cfd 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -1,22 +1,20 @@ #include #include -vector primeSieve(int n) { +using namespace std; + +typedef unsigned long long ll; + +vector primeSieve(ll n) { vector primes; vector isPrime(n,true); - for(int i = 2; i < n; i+=2) { - if(i*i <= n) { - if(isPrime[i]) { - primes.push_back(i); - for(int j = 2; i*j < n; j++) { - isPrime[i*j] = false; - } + for(ll i = 2; i < n; i+=2) { + if(isPrime[i]) { + primes.push_back(i); + if(i*i <= n) { + for(ll j = i; i*j < n; j+=2) isPrime[i*j] = false; } } - else { - if(isPrime[i]) - primes.push_back(i); - } if(i == 2) i--; } -- cgit v1.2.3 From 79901fdf49fd97df29cefa56b26afd9d2e109b81 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 11:16:18 +0100 Subject: Update primeSieve.cpp Final update! --- math/primeSieve.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'math') diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 82a4cfd..4c82bbe 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -7,7 +7,7 @@ typedef unsigned long long ll; vector primeSieve(ll n) { vector primes; - vector isPrime(n,true); + vector isPrime(n,true); for(ll i = 2; i < n; i+=2) { if(isPrime[i]) { primes.push_back(i); -- cgit v1.2.3 From ca740ed7caeca4deb09a2fc7912f599555442e15 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 11:46:50 +0100 Subject: bisschen LGS --- math/lgsFp.cpp | 27 +++++++++++++++++++++++++++ math/math.tex | 7 +++++++ math/modExp.cpp | 7 +++++++ math/multInv.cpp | 5 +++++ 4 files changed, 46 insertions(+) create mode 100644 math/lgsFp.cpp create mode 100644 math/modExp.cpp create mode 100644 math/multInv.cpp (limited to 'math') diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp new file mode 100644 index 0000000..e42e4ab --- /dev/null +++ b/math/lgsFp.cpp @@ -0,0 +1,27 @@ +void normalLine(ll n, ll line, ll p) { //normalisiert Zeile line + ll factor = multInv(mat[line][line], p); //Implementierung von oben + for (ll i = 0; i <= n; i++) { + mat[line][i] *= factor; + mat[line][i] %= p; + } +} + +void takeAll(ll n, ll line, ll p) { //zieht Vielfaches von line von allen anderen Zeilen ab + for (ll i = 0; i < n; i++) { + if (i == line) continue; + ll diff = mat[i][line]; //abziehen + for (ll j = 0; j <= n; j++) { + mat[i][j] -= (diff * mat[line][j]) % p; + while (mat[i][j] < 0) { + mat[i][j] += p; + } + } + } +} + +void gauss(ll n, ll p) { //n x n+1-Matrix, Koerper F_p + for (ll line = 0; line < n; line++) { + normalLine(n, line, p); + takeAll(n, line, p); + } +} \ No newline at end of file diff --git a/math/math.tex b/math/math.tex index f82ab65..db42b74 100644 --- a/math/math.tex +++ b/math/math.tex @@ -15,6 +15,13 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \end{itemize} \item[Falls $d \neq 1$:] es existiert kein $x^{-1}$ \end{description} +\lstinputlisting{math/multInv.cpp} + +\subsubsection{Mod-Exponent über $\mathbb{F}_p$} +\lstinputlisting{math/modExp.cpp} + +\subsection{LGS über $\mathbb{F}_p$} +\lstinputlisting{math/lgsFp.cpp} \subsection{Binomialkoeffizienten} \lstinputlisting{math/binomial.cpp} \ No newline at end of file diff --git a/math/modExp.cpp b/math/modExp.cpp new file mode 100644 index 0000000..f738268 --- /dev/null +++ b/math/modExp.cpp @@ -0,0 +1,7 @@ +ll modPow(ll b, ll e, ll p) { + if (e == 0) return 1; + if (e == 1) return b; + ll half = modPow(b, e / 2, p), res = (half * half) % p; + if (e & 1) res *= b; res %= p; + return res; +} \ No newline at end of file diff --git a/math/multInv.cpp b/math/multInv.cpp new file mode 100644 index 0000000..f9db815 --- /dev/null +++ b/math/multInv.cpp @@ -0,0 +1,5 @@ +ll multInv(ll n, ll p) { //berechnet das multiplikative Inverse von n in F_p + extendedEuclid(n, p); //implementierung von oben + x += ((x / p) + 1) * p; + return x % p; +} \ No newline at end of file -- cgit v1.2.3 From 0c7cf202fabe4cd1845963ae24955f7636ca5c7b Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 12:14:18 +0100 Subject: Create factor.cpp Factorize a number n --- math/factor.cpp | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) create mode 100644 math/factor.cpp (limited to 'math') diff --git a/math/factor.cpp b/math/factor.cpp new file mode 100644 index 0000000..43aeae3 --- /dev/null +++ b/math/factor.cpp @@ -0,0 +1,45 @@ +#include +#include + +using namespace std; + +typedef unsigned long long ll; + +const ll PRIME_SIZE = 10000000; +vector primes; + +//Call before calculating anything +void primeSieve() { + vector isPrime(PRIME_SIZE,true); + for(ll i = 2; i < PRIME_SIZE; i+=2) { + if(isPrime[i]) { + primes.push_back(i); + if(i*i <= PRIME_SIZE) { + for(ll j = i; i*j < PRIME_SIZE; j+=2) isPrime[i*j] = false; + } + } + if(i == 2) + i--; + } +} + +//Factorize the number n +vector factorize(ll n) { + vector factor; + ll num = n; + int pos = 0; + while(num != 1) { + if(num % primes[pos] == 0) { + num /= primes[pos]; + factor.push_back(primes[pos]); + } + else + pos++; + if(primes[pos]*primes[pos] > n) + break; + } + if(num != 1) + factor.push_back(num); + return factor; + +} -- cgit v1.2.3 From 44921d90e48ff259926d9173eaf4dd975e001424 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 12:18:05 +0100 Subject: Update math.tex update math.tex --- math/math.tex | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) (limited to 'math') diff --git a/math/math.tex b/math/math.tex index db42b74..71e5648 100644 --- a/math/math.tex +++ b/math/math.tex @@ -17,6 +17,13 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \end{description} \lstinputlisting{math/multInv.cpp} + +\subsubsection{Primzahlsieb von Eratosthenes} +\lstinputlisting{math/primeSieve.cpp} + +\subsubsection{Faktorisierung} +\lstinputlisting{math/factor.cpp} + \subsubsection{Mod-Exponent über $\mathbb{F}_p$} \lstinputlisting{math/modExp.cpp} @@ -24,4 +31,4 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \lstinputlisting{math/lgsFp.cpp} \subsection{Binomialkoeffizienten} -\lstinputlisting{math/binomial.cpp} \ No newline at end of file +\lstinputlisting{math/binomial.cpp} -- cgit v1.2.3 From 9fe234e7181b1cad9652655e674e7f9f821814b7 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 12:50:19 +0100 Subject: Artikulationpunkte --- graph/articulationPoints.cpp | 47 +++++++++++++++++++++++++++++++++++++++++++ graph/graph.tex | 3 +++ math/math.tex | 7 +++---- tcr.pdf | Bin 291824 -> 297317 bytes 4 files changed, 53 insertions(+), 4 deletions(-) create mode 100644 graph/articulationPoints.cpp (limited to 'math') diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp new file mode 100644 index 0000000..b99a286 --- /dev/null +++ b/graph/articulationPoints.cpp @@ -0,0 +1,47 @@ +vector< vector > adjlist; +vector low; +vector d; +vector isArtPoint; +vector< vector > bridges; //nur fuer Bruecken +int counter = 0; + +void visit(int v, int parent) { + d[v] = low[v] = ++counter; + int numVisits = 0, maxlow = 0; + + for (vector::iterator vit = adjlist[v].begin(); vit != adjlist[v].end(); vit++) { + if (d[*vit] == 0) { + numVisits++; + visit(*vit, v); + if (low[*vit] > maxlow) { + maxlow = low[*vit]; + } + + if (low[*vit] > d[v]) { //nur fuer Bruecken + bridges[v].push_back(*vit); bridges[*vit].push_back(v); + } + + low[v] = min(low[v], low[*vit]); + } else { + if (d[*vit] < low[v]) { + low[v] = d[*vit]; + } + } + } + + if (parent == -1) { + if (numVisits > 1) isArtPoint[v] = true; + } else { + if (maxlow >= d[v]) isArtPoint[v] = true; + } +} + +void findArticulationPoints() { + low.clear(); low.resize(adjlist.size()); + d.clear(); d.assign(adjlist.size(), 0); + isArtPoint.clear(); isArtPoint.assign(adjlist.size(), false); + bridges.clear(); isBridge.resize(adjlist.size()); //nur fuer Bruecken + for (int v = 0; v < (int)adjlist.size(); v++) { + if (d[v] == 0) visit(v, -1); + } +} \ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 2bf395c..5fc725e 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -13,5 +13,8 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} +\subsection{Artikulationspunkte und Brücken} +\lstinputlisting{graph/articulationPoints.cpp} + \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file diff --git a/math/math.tex b/math/math.tex index 71e5648..973103a 100644 --- a/math/math.tex +++ b/math/math.tex @@ -17,10 +17,6 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \end{description} \lstinputlisting{math/multInv.cpp} - -\subsubsection{Primzahlsieb von Eratosthenes} -\lstinputlisting{math/primeSieve.cpp} - \subsubsection{Faktorisierung} \lstinputlisting{math/factor.cpp} @@ -32,3 +28,6 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \subsection{Binomialkoeffizienten} \lstinputlisting{math/binomial.cpp} + +\subsection{Primzahlsieb von Eratosthenes} +\lstinputlisting{math/primeSieve.cpp} diff --git a/tcr.pdf b/tcr.pdf index 8a59d24..c4e7d62 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3