diff options
| -rw-r--r-- | content/latexHeaders/math.sty | 1 | ||||
| -rw-r--r-- | content/other/bitOps.cpp | 7 | ||||
| -rw-r--r-- | content/other/josephus2.cpp | 9 | ||||
| -rw-r--r-- | content/other/other.tex | 34 | ||||
| -rw-r--r-- | content/other/pbs.cpp | 3 | ||||
| -rw-r--r-- | content/other/recover.cpp | 12 | ||||
| -rw-r--r-- | content/other/stuff.cpp | 6 | ||||
| -rw-r--r-- | tcr.pdf | bin | 691029 -> 691903 bytes | |||
| -rw-r--r-- | test/other/recover.cpp | 34 |
9 files changed, 72 insertions, 34 deletions
diff --git a/content/latexHeaders/math.sty b/content/latexHeaders/math.sty index c34cc99..d758f71 100644 --- a/content/latexHeaders/math.sty +++ b/content/latexHeaders/math.sty @@ -6,6 +6,7 @@ \usepackage{mathtools} \usepackage{amssymb} \usepackage{ntheorem} +\usepackage{nicefrac} %\usepackage{pxfonts} \usepackage[scaled=0.945,largesc,looser]{newpxtext}%better than pxfonts... diff --git a/content/other/bitOps.cpp b/content/other/bitOps.cpp index 8079305..6230c86 100644 --- a/content/other/bitOps.cpp +++ b/content/other/bitOps.cpp @@ -3,13 +3,6 @@ for (int subset = bitmask; subset > 0; subset = (subset - 1) & bitmask) -// Zählt Anzahl der gesetzten Bits. -int numberOfSetBits(int i) { - i = i - ((i >> 1) & 0x5555'5555); - i = (i & 0x3333'3333) + ((i >> 2) & 0x3333'3333); - return (((i + (i >> 4)) & 0x0F0F'0F0F) * 0x0101'0101) >> 24; -} - // Nächste Permutation in Bitmaske // (z.B. 00111 => 01011 => 01101 => ...) ll nextPerm(ll v) { diff --git a/content/other/josephus2.cpp b/content/other/josephus2.cpp index 5086e13..33544ea 100644 --- a/content/other/josephus2.cpp +++ b/content/other/josephus2.cpp @@ -1,8 +1,5 @@ int rotateLeft(int n) { // Der letzte Überlebende, 1-basiert. - for (int i = 31; i >= 0; i--) { - if (n & (1 << i)) { - n &= ~(1 << i); - break; - }} - n <<= 1; n++; return n; + int bits = __lg(n); + n ^= 1 << bits; + return 2 * n + 1; } diff --git a/content/other/other.tex b/content/other/other.tex index b47893f..e8d8041 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -13,6 +13,19 @@ \sourcecode{other/timed.cpp}
\end{algorithm}
+\begin{algorithm}{Overflow-sichere arithmetische Operationen}
+ Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
+ \begin{expandtable}
+ \begin{tabularx}{\linewidth}{|lR|}
+ \hline
+ Addition & \code{__builtin_saddll_overflow(a, b, &c)} \\
+ Subtraktion & \code{__builtin_ssubll_overflow(a, b, &c)} \\
+ Multiplikation & \code{__builtin_smulll_overflow(a, b, &c)} \\
+ \hline
+ \end{tabularx}
+ \end{expandtable}
+\end{algorithm}
+
\begin{algorithm}{Bit Operations}
\begin{expandtable}
\begin{tabularx}{\linewidth}{|Ll|}
@@ -31,19 +44,6 @@ \sourcecode{other/bitOps.cpp}
\end{algorithm}
-\begin{algorithm}{Overflow-sichere arithmetische Operationen}
- Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
- \begin{expandtable}
- \begin{tabularx}{\linewidth}{|lR|}
- \hline
- Addition & \code{__builtin_saddll_overflow(a, b, &c)} \\
- Subtraktion & \code{__builtin_ssubll_overflow(a, b, &c)} \\
- Multiplikation & \code{__builtin_smulll_overflow(a, b, &c)} \\
- \hline
- \end{tabularx}
- \end{expandtable}
-\end{algorithm}
-
\begin{algorithm}{Pragmas}
\sourcecode{other/pragmas.cpp}
\end{algorithm}
@@ -95,6 +95,14 @@ \textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}
\end{algorithm}
+\vfill\null\columnbreak
+
+\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{other/recover.cpp}
+
+
\begin{algorithm}[optional]{Zeileneingabe}
\sourcecode{other/split.cpp}
\end{algorithm}
diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index 7cb60e5..5508d6c 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -10,9 +10,8 @@ while (true) { // reset simulation for (int step = 0; auto [mid, i] : focus) { - while (step <= mid) { + for (; step <= mid; step++) { // simulation step - step++; } if (/* requirement already fulfilled */) high[i] = mid; else low[i] = mid + 1; 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]}; +} diff --git a/content/other/stuff.cpp b/content/other/stuff.cpp index 41543ad..e4e37e2 100644 --- a/content/other/stuff.cpp +++ b/content/other/stuff.cpp @@ -1,13 +1,7 @@ -// Alles-Header. -#include <bits/stdc++.h> - // Setzt deutsche Tastaturlayout / toggle mit alt + space setxkbmap de setxkbmap de,us -option grp:alt_space_toggle -// Schnelle Ein-/Ausgabe mit cin/cout. -cin.tie(nullptr)->ios::sync_with_stdio(false); - // Set mit eigener Sortierfunktion. set<point2, decltype(comp)> set1(comp); diff --git a/test/other/recover.cpp b/test/other/recover.cpp new file mode 100644 index 0000000..fa491e8 --- /dev/null +++ b/test/other/recover.cpp @@ -0,0 +1,34 @@ +#include "../util.h" +#include <other/recover.cpp> +#include <math/shortModInv.cpp> + +void stress_test() { + ll queries = 0; + timer t; + for (int i = 0; i < 1000; i++) { + ll p = Random::prime<ll>(10000); + for (ll j = 0; 2*j*j < p; j++) { + for (ll b = 1; 2*b*b < p; b++) { + if (gcd(j, b) != 1) continue; + for (ll a : {-j, j}) { + ll c = a * multInv(b, p); + + t.start(); + auto [x, y] = recover(c, p); + t.stop(); + + if (a != x || b != y) cerr << "got: " << x << "/" << y << ", expected: " << a << "/" << b << FAIL; + queries++; + } + } + } + + } + cerr << "tested random queries: " << queries << endl; + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms" << endl; +} + +int main() { + stress_test(); +} |