From e55df069a8f83b2c0c2b56c035f49e89516cdaaa Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Sat, 16 Nov 2024 17:48:10 +0100 Subject: minor fixes, let code breathe where possible --- TestMakefile | 61 ---------------------------- content/datastructures/dynamicConvexHull.cpp | 8 ++-- content/datastructures/lichao.cpp | 14 +++---- content/datastructures/persistentArray.cpp | 48 +++++++++++----------- content/geometry/delaunay.cpp | 11 ++--- content/geometry/formulas.cpp | 13 +++--- content/geometry/formulas3d.cpp | 16 ++++---- content/geometry/geometry.tex | 1 + content/geometry/hpi.cpp | 4 +- content/geometry/linesAndSegments.cpp | 2 +- content/geometry/polygon.cpp | 4 +- content/geometry/sortAround.cpp | 22 +++++----- content/geometry/triangle.cpp | 4 +- content/graph/2sat.cpp | 16 ++++---- content/graph/LCA_sparse.cpp | 2 +- content/graph/bitonicTSP.cpp | 2 +- content/graph/cycleCounting.cpp | 2 +- content/graph/hopcroftKarp.cpp | 4 +- content/graph/stoerWagner.cpp | 8 ++-- content/graph/virtualTree.cpp | 4 +- content/math/bigint.cpp | 4 +- content/math/binomial1.cpp | 2 +- content/math/divisors.cpp | 2 +- content/math/gcd-lcm.cpp | 4 +- content/math/linearSieve.cpp | 12 +++--- content/math/math.tex | 4 +- content/math/piLegendre.cpp | 46 ++++++++++----------- content/math/polynomial.cpp | 6 +-- content/math/primeSieve.cpp | 2 +- content/math/recover.cpp | 2 +- content/math/rho.cpp | 4 +- content/math/simpson.cpp | 2 +- content/math/sqrtModCipolla.cpp | 2 +- content/math/tables/prime-composite.tex | 10 ++--- content/other/fastIO.cpp | 2 +- content/other/other.tex | 4 +- content/other/timed.cpp | 2 +- content/string/ahoCorasick.cpp | 2 +- content/string/rollingHash.cpp | 2 +- content/string/rollingHashCf.cpp | 2 +- content/string/suffixArray.cpp | 7 ++-- content/string/suffixAutomaton.cpp | 2 +- content/string/trie.cpp | 2 +- 43 files changed, 156 insertions(+), 217 deletions(-) delete mode 100644 TestMakefile diff --git a/TestMakefile b/TestMakefile deleted file mode 100644 index 58d2678..0000000 --- a/TestMakefile +++ /dev/null @@ -1,61 +0,0 @@ -with-defines-subsets = $(if $2,$(call with-defines-subsets,$1,$(call dropfirst,$2)) $(call with-defines-subsets,$1.$(firstword $2),$(call dropfirst,$2)),$1) -dropfirst = $(wordlist 2,$(words $1),$1) - -source = $(dir $*)$(firstword $(subst ., ,$(notdir $*))) -flags = $(call dropfirst,$(subst ., -D,$(notdir $*))) $(CPPFLAGS) -predep = $(patsubst $(source)=%,%,$(filter $(source)=%,$(PREDEPS))) - -TESTS := \ - $(call with-defines-subsets,datastructures/test/segmentTree,SEGTREE_MUL SEGTREE_INIT_DEFAULT SEGTREE_RANGE_UPDATE) \ - $(call with-defines-subsets,datastructures/test/segmentTree.SEGTREE_FIRST_NEG,SEGTREE_INIT_DEFAULT) \ - $(call with-defines-subsets,datastructures/test/lazyPropagation,SEGTREE_FIRST_NEG SEGTREE_INIT_DEFAULT) \ - $(call with-defines-subsets,datastructures/test/lazyPropagation.SEGTREE_MAX,SEGTREE_INIT_DEFAULT) \ - datastructures/test/waveletTree \ - datastructures/test/fenwickTree \ - datastructures/test/fenwickTree2 \ - datastructures/test/treap2 \ - datastructures/test/sparseTable \ - datastructures/test/sparseTableDisjoint \ - datastructures/test/monotonicConvexHull \ - datastructures/test/persistent \ - graph/test/binary_lifting \ - graph/test/LCA_sparse \ - math/test/binomial0 - -# Dependencies which must be present before generating the .d file. -PREDEPS := \ - datastructures/test/segmentTree=datastructures/test/segmentTree.tmp.cpp \ - datastructures/test/lazyPropagation=datastructures/test/lazyPropagation.tmp.cpp - -CPPFLAGS := -include test.h -std=gnu++20 -Wall -Wextra \ - -Werror -fsanitize=address,undefined -fno-sanitize-recover -g - -test: $(TESTS:=.ok) - -cleantest: - rm -f $(TESTS:=.test) $(TESTS:=.ok) $(TESTS:=.d) \ - datastructures/test/segmentTree.tmp.cpp - -%.ok: %.test - timeout -v 2 ./$< - @touch $@ - -.SECONDEXPANSION: -%.test: $$(source).cpp - g++ $(flags) -o $@ $< - -%.d: $$(source).cpp $$(predep) - g++ -MM -MT '$*.test $*.d' -MF '$@' $(flags) $< - -datastructures/test/segmentTree.tmp.cpp: datastructures/segmentTree.cpp \ - datastructures/test/segmentTree.awk - awk -f datastructures/test/segmentTree.awk $< > $@ -datastructures/test/lazyPropagation.tmp.cpp: \ - datastructures/lazyPropagation.cpp datastructures/test/lazyPropagation.awk - awk -f datastructures/test/lazyPropagation.awk $< > $@ - -.PHONY: test cleantest -.SECONDARY: $(TESTS:=.test) - -include $(TESTS:=.d) - diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index 7148e31..36ef6f5 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -1,15 +1,15 @@ struct Line { mutable ll m, c, p; - bool operator<(const Line& o) const {return m < o.m;} - bool operator<(ll x) const {return p < x;} + bool operator<(const Line& o) const { return m < o.m; } + bool operator<(ll x) const { return p < x; } }; struct HullDynamic : multiset> { // max über Geraden // (for doubles, use INF = 1/.0, div(a,c) = a/c) - ll div(ll a, ll c) {return a / c - ((a ^ c) < 0 && a % c);} + ll div(ll a, ll c) { return a / c - ((a ^ c) < 0 && a % c); } bool isect(iterator x, iterator y) { - if (y == end()) {x->p = INF; return false;} + if (y == end()) { x->p = INF; return false; } if (x->m == y->m) x->p = x->c > y->c ? INF : -INF; else x->p = div(y->c - x->c, x->m - y->m); return x->p >= y->p; diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp index 1318ca7..c20c61d 100644 --- a/content/datastructures/lichao.cpp +++ b/content/datastructures/lichao.cpp @@ -1,9 +1,9 @@ vector xs; // IMPORTANT: Initialize before constructing! -int findX(int i) {return lower_bound(all(xs), i) - begin(xs);} +int findX(int i) { return lower_bound(all(xs), i) - begin(xs); } -struct Fun { // Default: Linear function. Change as needed. +struct Fun { // Default: Linear function. Change as needed. ll m, c; - ll operator()(int x) {return m*xs[x] + c;} + ll operator()(int x) { return m*xs[x] + c; } }; // Default: Computes min. Change lines with comment for max. @@ -12,17 +12,17 @@ struct Lichao { int n, cap; vector seg; Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {} - + void _insert(Fun f, int l, int r, int i) { while (i < 2 * cap) { int m = (l+r)/2; - if (m >= n) {r = m; i = 2*i; continue;} + if (m >= n) { r = m; i = 2*i; continue; } Fun &g = seg[i]; if (f(m) < g(m)) swap(f, g); // > if (f(l) < g(l)) r = m, i = 2*i; // > else l = m, i = 2*i+1; }} - void insert(Fun f) {_insert(f, 0, cap, 1);} + void insert(Fun f) { _insert(f, 0, cap, 1); } void _segmentInsert(Fun f, int l, int r, int a, int b, int i) { if (l <= a && b <= r) _insert(f, a, b, i); @@ -42,5 +42,5 @@ struct Lichao { } return ans; } - ll query(ll x) {return _query(findX(x));} + ll query(ll x) { return _query(findX(x)); } }; diff --git a/content/datastructures/persistentArray.cpp b/content/datastructures/persistentArray.cpp index 8326700..903bd0e 100644 --- a/content/datastructures/persistentArray.cpp +++ b/content/datastructures/persistentArray.cpp @@ -1,24 +1,24 @@ -template -struct persistentArray { - int time; - vector> data; - vector> mods; - - persistentArray(int n, T value = {}) - : time(0), data(n, {time, value}) {} - - T get(int p, int t) {return data[p].get(t);} - - int set(int p, T value) { - mods.push_back({p, data[p].set(value)}); - return mods.back().second; - } - - void reset(int t) { - while (!mods.empty() && mods.back().second > t) { - data[mods.back().first].data.pop_back(); - mods.pop_back(); - } - time = t; - } -}; +template +struct persistentArray { + int time; + vector> data; + vector> mods; + + persistentArray(int n, T value = {}) + : time(0), data(n, {time, value}) {} + + T get(int p, int t) { return data[p].get(t); } + + int set(int p, T value) { + mods.push_back({p, data[p].set(value)}); + return mods.back().second; + } + + void reset(int t) { + while (!mods.empty() && mods.back().second > t) { + data[mods.back().first].data.pop_back(); + mods.pop_back(); + } + time = t; + } +}; diff --git a/content/geometry/delaunay.cpp b/content/geometry/delaunay.cpp index c813892..5672b57 100644 --- a/content/geometry/delaunay.cpp +++ b/content/geometry/delaunay.cpp @@ -3,7 +3,8 @@ using pt = complex; constexpr pt INF_PT = pt(2e18, 2e18); -bool circ(pt p, pt a, pt b, pt c) {// p in circle(A,B,C), ABC must be ccw +// p in circle(A,B,C), ABC must be ccw +bool circ(pt p, pt a, pt b, pt c) { return imag((c-b)*conj(p-c)*(a-p)*conj(b-a)) < 0; } @@ -12,10 +13,10 @@ struct QuadEdge { QuadEdge* onext = nullptr; pt orig = INF_PT; bool used = false; - QuadEdge* rev() const {return rot->rot;} - QuadEdge* lnext() const {return rot->rev()->onext->rot;} - QuadEdge* oprev() const {return rot->onext->rot;} - pt dest() const {return rev()->orig;} + QuadEdge* rev() const { return rot->rot; } + QuadEdge* lnext() const { return rot->rev()->onext->rot; } + QuadEdge* oprev() const { return rot->onext->rot; } + pt dest() const { return rev()->orig; } }; deque edgeData; diff --git a/content/geometry/formulas.cpp b/content/geometry/formulas.cpp index 5d4e10d..b339451 100644 --- a/content/geometry/formulas.cpp +++ b/content/geometry/formulas.cpp @@ -6,20 +6,17 @@ constexpr double PIU = acos(-1.0l); // PIL < PI < PIU constexpr double PIL = PIU-2e-19l; // Winkel zwischen Punkt und x-Achse in [-PI, PI]. -double angle(pt a) {return arg(a);} +double angle(pt a) { return arg(a); } // rotiert Punkt im Uhrzeigersinn um den Ursprung. -pt rotate(pt a, double theta) {return a * polar(1.0, theta);} +pt rotate(pt a, double theta) { return a * polar(1.0, theta); } // Skalarprodukt. -auto dot(pt a, pt b) {return real(conj(a) * b);} - -// abs()^2.(pre c++20) -auto norm(pt a) {return dot(a, a);} +auto dot(pt a, pt b) { return real(conj(a) * b); } // Kreuzprodukt, 0, falls kollinear. -auto cross(pt a, pt b) {return imag(conj(a) * b);} -auto cross(pt p, pt a, pt b) {return cross(a - p, b - p);} +auto cross(pt a, pt b) { return imag(conj(a) * b); } +auto cross(pt p, pt a, pt b) { return cross(a - p, b - p); } // 1 => c links von a->b // 0 => a, b und c kolliniear diff --git a/content/geometry/formulas3d.cpp b/content/geometry/formulas3d.cpp index 63de2ce..66a4644 100644 --- a/content/geometry/formulas3d.cpp +++ b/content/geometry/formulas3d.cpp @@ -2,20 +2,20 @@ auto operator|(pt3 a, pt3 b) { return a.x * b.x + a.y*b.y + a.z*b.z; } -auto dot(pt3 a, pt3 b) {return a|b;} +auto dot(pt3 a, pt3 b) { return a|b; } // Kreuzprodukt -pt3 operator*(pt3 a, pt3 b) {return {a.y*b.z - a.z*b.y, - a.z*b.x - a.x*b.z, - a.x*b.y - a.y*b.x};} -pt3 cross(pt3 a, pt3 b) {return a*b;} +pt3 operator*(pt3 a, pt3 b) { return {a.y*b.z - a.z*b.y, + a.z*b.x - a.x*b.z, + a.x*b.y - a.y*b.x}; } +pt3 cross(pt3 a, pt3 b) { return a*b; } // Länge von a -double abs(pt3 a) {return sqrt(dot(a, a));} -double abs(pt3 a, pt3 b) {return abs(b - a);} +double abs(pt3 a) { return sqrt(dot(a, a)); } +double abs(pt3 a, pt3 b) { return abs(b - a); } // Mixedprodukt -auto mixed(pt3 a, pt3 b, pt3 c) {return a*b|c;}; +auto mixed(pt3 a, pt3 b, pt3 c) { return a*b|c; } // orientierung von p zu der Ebene durch a, b, c // -1 => gegen den Uhrzeigersinn, diff --git a/content/geometry/geometry.tex b/content/geometry/geometry.tex index 019a264..976fb4d 100644 --- a/content/geometry/geometry.tex +++ b/content/geometry/geometry.tex @@ -29,6 +29,7 @@ \subsection{Formeln~~--~\texttt{std::complex}} \sourcecode{geometry/formulas.cpp} +\columnbreak \sourcecode{geometry/linesAndSegments.cpp} \sourcecode{geometry/sortAround.cpp} \input{geometry/triangle} diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp index 02c71e3..ec27254 100644 --- a/content/geometry/hpi.cpp +++ b/content/geometry/hpi.cpp @@ -1,6 +1,6 @@ constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP -bool left(pt p) {return real(p) < 0 || +bool left(pt p) {return real(p) < 0 || (real(p) == 0 && imag(p) < 0);} struct hp { pt from, to; @@ -11,7 +11,7 @@ struct hp { bool dummy() const {return from == to;} pt dir() const {return dummy() ? to : to - from;} bool operator<(const hp& o) const { - if (left(dir()) != left(o.dir())) + if (left(dir()) != left(o.dir())) return left(dir()) > left(o.dir()); return cross(dir(), o.dir()) > 0; } diff --git a/content/geometry/linesAndSegments.cpp b/content/geometry/linesAndSegments.cpp index ddab554..db34179 100644 --- a/content/geometry/linesAndSegments.cpp +++ b/content/geometry/linesAndSegments.cpp @@ -66,7 +66,7 @@ vector segmentIntersection2(pt a, pt b, pt c, pt d) { double x = cross(b - a, d - c); double y = cross(c - a, d - c); double z = cross(b - a, a - c); - if (x < 0) {x = -x; y = -y; z = -z;} + if (x < 0) { x = -x; y = -y; z = -z; } if (y < -EPS || y-x > EPS || z < -EPS || z-x > EPS) return {}; if (x > EPS) return {a + y/x*(b - a)}; vector result; diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp index 064d81f..b9ecebb 100644 --- a/content/geometry/polygon.cpp +++ b/content/geometry/polygon.cpp @@ -91,8 +91,8 @@ double dist(const vector& ps, vector qs) { return intersect ? 0 : res; } -bool left(pt of, pt p) {return cross(p, of) < 0 || - (cross(p, of) == 0 && dot(p, of) > 0);} +bool left(pt of, pt p) { return cross(p, of) < 0 || + (cross(p, of) == 0 && dot(p, of) > 0); } // convex hulls without duplicates, hull[0] == hull.back() and // hull[0] must be a convex point (with angle < pi) diff --git a/content/geometry/sortAround.cpp b/content/geometry/sortAround.cpp index 98d17a8..9b09808 100644 --- a/content/geometry/sortAround.cpp +++ b/content/geometry/sortAround.cpp @@ -1,11 +1,11 @@ -bool left(pt p) {return real(p) < 0 || - (real(p) == 0 && imag(p) < 0);} - -// counter clockwise, starting with "11:59" -void sortAround(pt p, vector& ps) { - sort(all(ps), [&](const pt& a, const pt& b){ - if (left(a - p) != left(b - p)) - return left(a - p) > left(b - p); - return cross(p, a, b) > 0; - }); -} +bool left(pt p) { return real(p) < 0 || + (real(p) == 0 && imag(p) < 0); } + +// counter clockwise, starting with "11:59" +void sortAround(pt p, vector& ps) { + sort(all(ps), [&](const pt& a, const pt& b){ + if (left(a - p) != left(b - p)) + return left(a - p) > left(b - p); + return cross(p, a, b) > 0; + }); +} diff --git a/content/geometry/triangle.cpp b/content/geometry/triangle.cpp index 534bb10..eab17f4 100644 --- a/content/geometry/triangle.cpp +++ b/content/geometry/triangle.cpp @@ -1,5 +1,5 @@ // Mittelpunkt des Dreiecks abc. -pt centroid(pt a, pt b, pt c) {return (a + b + c) / 3.0;} +pt centroid(pt a, pt b, pt c) { return (a + b + c) / 3.0; } // Flächeninhalt eines Dreicks bei bekannten Eckpunkten. double area(pt a, pt b, pt c) { @@ -30,7 +30,7 @@ pt circumCenter(pt a, pt b, pt c) { // -1 => p außerhalb Kreis durch a,b,c // 0 => p auf Kreis durch a,b,c // 1 => p im Kreis durch a,b,c -int insideOutCenter(pt a, pt b, pt c, pt p) {// braucht lll +int insideOutCenter(pt a, pt b, pt c, pt p) { // braucht lll return ccw(a,b,c) * sgn(imag((c-b)*conj(p-c)*(a-p)*conj(b-a))); } diff --git a/content/graph/2sat.cpp b/content/graph/2sat.cpp index 75e54e6..2b49fc6 100644 --- a/content/graph/2sat.cpp +++ b/content/graph/2sat.cpp @@ -4,19 +4,19 @@ struct sat2 { sat2(int vars) : n(vars*2), adj(n) {} - static int var(int i) {return i << 1;} // use this! + static int var(int i) { return i << 1; } // use this! void addImpl(int a, int b) { adj[a].push_back(b); adj[1^b].push_back(1^a); } - void addEquiv(int a, int b) {addImpl(a, b); addImpl(b, a);} - void addOr(int a, int b) {addImpl(1^a, b);} - void addXor(int a, int b) {addOr(a, b); addOr(1^a, 1^b);} - void addTrue(int a) {addImpl(1^a, a);} - void addFalse(int a) {addTrue(1^a);} - void addAnd(int a, int b) {addTrue(a); addTrue(b);} - void addNand(int a, int b) {addOr(1^a, 1^b);} + void addEquiv(int a, int b) { addImpl(a, b); addImpl(b, a); } + void addOr(int a, int b) { addImpl(1^a, b);} + void addXor(int a, int b) { addOr(a, b); addOr(1^a, 1^b); } + void addTrue(int a) { addImpl(1^a, a);} + void addFalse(int a) { addTrue(1^a);} + void addAnd(int a, int b) { addTrue(a); addTrue(b); } + void addNand(int a, int b) { addOr(1^a, 1^b); } bool solve() { scc(); //scc code von oben diff --git a/content/graph/LCA_sparse.cpp b/content/graph/LCA_sparse.cpp index 3e87cde..e391948 100644 --- a/content/graph/LCA_sparse.cpp +++ b/content/graph/LCA_sparse.cpp @@ -28,5 +28,5 @@ struct LCA { return visited[st.queryIdempotent(first[u], first[v] + 1)]; } - ll getDepth(int v) {return depth[first[v]];} + ll getDepth(int v) { return depth[first[v]]; } }; diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp index eee5082..a6f4c6e 100644 --- a/content/graph/bitonicTSP.cpp +++ b/content/graph/bitonicTSP.cpp @@ -13,7 +13,7 @@ auto bitonicTSP() { dp[i] = opt; pre[i] = j; }}} - // return dp.back(); // Länger der Tour + // return dp.back(); // Länge der Tour int j, n = sz(dist) - 1; vector ut, lt = {n, n - 1}; diff --git a/content/graph/cycleCounting.cpp b/content/graph/cycleCounting.cpp index 6a299ee..471d399 100644 --- a/content/graph/cycleCounting.cpp +++ b/content/graph/cycleCounting.cpp @@ -36,7 +36,7 @@ struct cycles { cur[id].flip(); }}} - bool isCycle(cycle cur) {//cycle must be constrcuted from base + bool isCycle(cycle cur) { // cycle must be constrcuted from base if (cur.none()) return false; init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ for (int i = 0; i < sz(edges); i++) { diff --git a/content/graph/hopcroftKarp.cpp b/content/graph/hopcroftKarp.cpp index c1f5d1c..7c0fec5 100644 --- a/content/graph/hopcroftKarp.cpp +++ b/content/graph/hopcroftKarp.cpp @@ -5,14 +5,14 @@ vector pairs, dist, ptr; bool bfs(int l) { queue q; for(int v = 0; v < l; v++) { - if (pairs[v] < 0) {dist[v] = 0; q.push(v);} + if (pairs[v] < 0) { dist[v] = 0; q.push(v); } else dist[v] = -1; } bool exist = false; while(!q.empty()) { int v = q.front(); q.pop(); for (int u : adj[v]) { - if (pairs[u] < 0) {exist = true; continue;} + if (pairs[u] < 0) { exist = true; continue; } if (dist[pairs[u]] < 0) { dist[pairs[u]] = dist[v] + 1; q.push(pairs[u]); diff --git a/content/graph/stoerWagner.cpp b/content/graph/stoerWagner.cpp index 97e667a..0a6f653 100644 --- a/content/graph/stoerWagner.cpp +++ b/content/graph/stoerWagner.cpp @@ -31,21 +31,21 @@ ll stoer_wagner() { while (!pq.empty()) { int c = pq.top().second; pq.pop(); - if (con[c] < 0) continue; //already seen + if (con[c] < 0) continue; // already seen con[c] = -1; for (auto e : tmp[c]) { - if (con[e.to] >= 0) {//add edge to cut + if (con[e.to] >= 0) { // add edge to cut con[e.to] += e.cap; pq.push({con[e.to], e.to}); cur += e.cap; - } else if (e.to != c) {//remove edge from cut + } else if (e.to != c) { // remove edge from cut cur -= e.cap; }} state.push_back({cur, c}); } int t = state.back().second; state.pop_back(); - if (state.empty()) return 0; //graph is not connected?! + if (state.empty()) return 0; // graph is not connected?! merge(state.back().second, t); res = min(res, state.back().first); } diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp index 6233b27..153ed0b 100644 --- a/content/graph/virtualTree.cpp +++ b/content/graph/virtualTree.cpp @@ -2,11 +2,11 @@ vector in, out; void virtualTree(vector ind) { // indices of used nodes - sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); + sort(all(ind), [&](int x, int y) { return in[x] < in[y]; }); for (int i = 1, n = sz(ind); i < n; i++) { ind.push_back(lca(ind[i - 1], ind[i])); } - sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); + sort(all(ind), [&](int x, int y) { return in[x] < in[y]; }); ind.erase(unique(all(ind)), ind.end()); int n = sz(ind); diff --git a/content/math/bigint.cpp b/content/math/bigint.cpp index 1b3b953..4dad2be 100644 --- a/content/math/bigint.cpp +++ b/content/math/bigint.cpp @@ -7,9 +7,9 @@ struct bigint { bigint() : sign(1) {} - bigint(ll v) {*this = v;} + bigint(ll v) { *this = v; } - bigint(const string &s) {read(s);} + bigint(const string &s) { read(s); } void operator=(ll v) { sign = 1; diff --git a/content/math/binomial1.cpp b/content/math/binomial1.cpp index dab20b3..d0fce18 100644 --- a/content/math/binomial1.cpp +++ b/content/math/binomial1.cpp @@ -1,7 +1,7 @@ ll calc_binom(ll n, ll k) { if (k > n) return 0; ll r = 1; - for (ll d = 1; d <= k; d++) {// Reihenfolge => Teilbarkeit + for (ll d = 1; d <= k; d++) { // Reihenfolge => Teilbarkeit r *= n--, r /= d; } return r; diff --git a/content/math/divisors.cpp b/content/math/divisors.cpp index 5afd4fb..2a17f54 100644 --- a/content/math/divisors.cpp +++ b/content/math/divisors.cpp @@ -2,7 +2,7 @@ ll countDivisors(ll n) { ll res = 1; for (ll i = 2; i * i * i <= n; i++) { ll c = 0; - while (n % i == 0) {n /= i; c++;} + while (n % i == 0) { n /= i; c++; } res *= c + 1; } if (isPrime(n)) res *= 2; diff --git a/content/math/gcd-lcm.cpp b/content/math/gcd-lcm.cpp index a1c63c8..1ee7ef5 100644 --- a/content/math/gcd-lcm.cpp +++ b/content/math/gcd-lcm.cpp @@ -1,2 +1,2 @@ -ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);} -ll lcm(ll a, ll b) {return a * (b / gcd(a, b));} +ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } +ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); } diff --git a/content/math/linearSieve.cpp b/content/math/linearSieve.cpp index 64440dd..2ea1e94 100644 --- a/content/math/linearSieve.cpp +++ b/content/math/linearSieve.cpp @@ -3,12 +3,12 @@ ll small[N], power[N], sieved[N]; vector primes; //wird aufgerufen mit (p^k, p, k) für prime p und k > 0 -ll mu(ll pk, ll p, ll k) {return -(k == 1);} -ll phi(ll pk, ll p, ll k) {return pk - pk / p;} -ll div(ll pk, ll p, ll k) {return k+1;} -ll divSum(ll pk, ll p, ll k) {return (pk*p-1) / (p - 1);} -ll square(ll pk, ll p, ll k) {return k % 2 ? pk / p : pk;} -ll squareFree(ll pk, ll p, ll k) {return p;} +ll mu(ll pk, ll p, ll k) { return -(k == 1); } +ll phi(ll pk, ll p, ll k) { return pk - pk / p; } +ll div(ll pk, ll p, ll k) { return k+1; } +ll divSum(ll pk, ll p, ll k) { return (pk*p-1) / (p - 1); } +ll square(ll pk, ll p, ll k) { return k % 2 ? pk / p : pk; } +ll squareFree(ll pk, ll p, ll k) { return p; } void sieve() { // O(N) small[1] = power[1] = sieved[1] = 1; diff --git a/content/math/math.tex b/content/math/math.tex index 644fbc8..2f50845 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -544,8 +544,8 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text \subsection{Wichtige Zahlen} \input{math/tables/prime-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)} +\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ } +\method{recover}{findet $x$ und $y$ für $c=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} diff --git a/content/math/piLegendre.cpp b/content/math/piLegendre.cpp index 21b974b..46c8584 100644 --- a/content/math/piLegendre.cpp +++ b/content/math/piLegendre.cpp @@ -1,23 +1,23 @@ -constexpr ll cache = 500; // requires O(cache^3) -vector> memo(cache * cache, vector(cache)); - -ll pi(ll n); - -ll phi(ll n, ll k) { - if (n <= 1 || k < 0) return 0; - if (n <= primes[k]) return n - 1; - if (n < N && primes[k] * primes[k] > n) return n - pi(n) + k; - bool ok = n < cache * cache; - if (ok && memo[n][k] > 0) return memo[n][k]; - ll res = n/primes[k] - phi(n/primes[k], k - 1) + phi(n, k - 1); - if (ok) memo[n][k] = res; - return res; -} - -ll pi(ll n) { - if (n < N) { // implement this as O(1) lookup for speedup! - return distance(primes.begin(), upper_bound(all(primes), n)); - } else { - ll k = pi(sqrtl(n) + 1); - return n - phi(n, k) + k; -}} +constexpr ll cache = 500; // requires O(cache^3) +vector> memo(cache * cache, vector(cache)); + +ll pi(ll n); + +ll phi(ll n, ll k) { + if (n <= 1 || k < 0) return 0; + if (n <= primes[k]) return n - 1; + if (n < N && primes[k] * primes[k] > n) return n - pi(n) + k; + bool ok = n < cache * cache; + if (ok && memo[n][k] > 0) return memo[n][k]; + ll res = n/primes[k] - phi(n/primes[k], k - 1) + phi(n, k - 1); + if (ok) memo[n][k] = res; + return res; +} + +ll pi(ll n) { + if (n < N) { // implement this as O(1) lookup for speedup! + return distance(primes.begin(), upper_bound(all(primes), n)); + } else { + ll k = pi(sqrtl(n) + 1); + return n - phi(n, k) + k; +}} diff --git a/content/math/polynomial.cpp b/content/math/polynomial.cpp index 84f3aaa..4698a00 100644 --- a/content/math/polynomial.cpp +++ b/content/math/polynomial.cpp @@ -4,15 +4,15 @@ struct poly { poly(int deg = 0) : data(1 + deg) {} poly(initializer_list _data) : data(_data) {} - int size() const {return sz(data);} + int size() const { return sz(data); } void trim() { for (ll& x : data) x = (x % mod + mod) % mod; while (size() > 1 && data.back() == 0) data.pop_back(); } - ll& operator[](int x) {return data[x];} - const ll& operator[](int x) const {return data[x];} + ll& operator[](int x) { return data[x]; } + const ll& operator[](int x) const { return data[x]; } ll operator()(int x) const { ll res = 0; diff --git a/content/math/primeSieve.cpp b/content/math/primeSieve.cpp index 1b0f514..2b2bf26 100644 --- a/content/math/primeSieve.cpp +++ b/content/math/primeSieve.cpp @@ -8,7 +8,7 @@ bool isPrime(ll x) { } void primeSieve() { - for (ll i = 3; i < N; i += 2) {// i * i < N reicht für isPrime + for (ll i = 3; i < N; i += 2) { // i * i < N reicht für isPrime if (!isNotPrime[i / 2]) { primes.push_back(i); // optional for (ll j = i * i; j < N; j+= 2 * i) { diff --git a/content/math/recover.cpp b/content/math/recover.cpp index 1a593f0..a4c22aa 100644 --- a/content/math/recover.cpp +++ b/content/math/recover.cpp @@ -1,4 +1,4 @@ -ll sq(ll x) {return x*x;} +ll sq(ll x) { return x*x; } array recover(ll c, ll m) { array u = {m, 0}, v = {c, 1}; diff --git a/content/math/rho.cpp b/content/math/rho.cpp index ad640cd..c7f7a70 100644 --- a/content/math/rho.cpp +++ b/content/math/rho.cpp @@ -2,7 +2,7 @@ using lll = __int128; ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim. if (n % 2 == 0) return 2; ll x = 0, y = 0, prd = 2, i = n/2 + 7; - auto f = [&](lll c){return (c * c + i) % n;}; + auto f = [&](lll c) { return (c * c + i) % n; }; for (ll t = 30; t % 40 || gcd(prd, n) == 1; t++) { if (x == y) x = ++i, y = f(x); if (ll q = (lll)prd * abs(x-y) % n; q) prd = q; @@ -13,7 +13,7 @@ ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim. void factor(ll n, map& facts) { if (n == 1) return; - if (isPrime(n)) {facts[n]++; return;} + if (isPrime(n)) { facts[n]++; return; } ll f = rho(n); factor(n / f, facts); factor(f, facts); } diff --git a/content/math/simpson.cpp b/content/math/simpson.cpp index 7f237a4..da9c002 100644 --- a/content/math/simpson.cpp +++ b/content/math/simpson.cpp @@ -1,4 +1,4 @@ -//double f(double x) {return x;} +//double f(double x) { return x; } double simps(double a, double b) { return (f(a) + 4.0 * f((a + b) / 2.0) + f(b)) * (b - a) / 6.0; diff --git a/content/math/sqrtModCipolla.cpp b/content/math/sqrtModCipolla.cpp index 1fac0c5..d52d258 100644 --- a/content/math/sqrtModCipolla.cpp +++ b/content/math/sqrtModCipolla.cpp @@ -1,4 +1,4 @@ -ll sqrtMod(ll a, ll p) {// teste mit legendre ob lösung existiert +ll sqrtMod(ll a, ll p) { // teste mit Legendre ob Lösung existiert if (a < 2) return a; ll t = 0; while (legendre((t*t-4*a) % p, p) >= 0) t = rng() % p; diff --git a/content/math/tables/prime-composite.tex b/content/math/tables/prime-composite.tex index 073b4ba..b8adadf 100644 --- a/content/math/tables/prime-composite.tex +++ b/content/math/tables/prime-composite.tex @@ -1,12 +1,12 @@ \begin{expandtable} -\begin{tabularx}{\linewidth}{|r|rIr|rIr|r|r|} +\begin{tabularx}{\linewidth}{|r|rIr|rIr|r|R|} \hline \multirow{2}{*}{$10^x$} & \multirow{2}{*}{Highly Composite} & \multirow{2}{*}{\# Divs} - & \multicolumn{2}{|c|}{Prime} - & \multirow{2}{*}{\# Primes} & \multirow{2}{*}{Primorial} \\ - & & & $<$ & $>$ & & \\ + & \multicolumn{2}{c|}{Prime} + & \multirow{2}{*}{\# Primes} & \# Prime \\ + & & & $<$ & $>$ & & Factors \\ \hline 1 & 6 & 4 & $-3$ & $+1$ & 4 & 2 \\ 2 & 60 & 12 & $-3$ & $+1$ & 25 & 3 \\ @@ -25,7 +25,7 @@ 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & 13 \\ 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & 13 \\ 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & 14 \\ - 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & 16 \\ + 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & 15 \\ \hline \end{tabularx} \end{expandtable} diff --git a/content/other/fastIO.cpp b/content/other/fastIO.cpp index 9badcc7..09473f4 100644 --- a/content/other/fastIO.cpp +++ b/content/other/fastIO.cpp @@ -16,7 +16,7 @@ void printPositive(int n) { } void fastprint(int n) { - if(n == 0) {putchar('0'); return;} + if(n == 0) { putchar('0'); return; } if (n < 0) { putchar('-'); printPositive(-n); diff --git a/content/other/other.tex b/content/other/other.tex index 59b5790..426875a 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -31,7 +31,7 @@ \begin{tabularx}{\linewidth}{|Ll|} \hline Bit an Position j lesen & \code{(x \& (1 << j)) != 0} \\ - Bit an Position j setzten & \code{x |= (1 << j)} \\ + Bit an Position j setzen & \code{x |= (1 << j)} \\ Bit an Position j löschen & \code{x \&= ~(1 << j)} \\ Bit an Position j flippen & \code{x ^= (1 << j)} \\ Anzahl an führenden nullen ($x \neq 0$) & \code{__builtin_clzll(x)} \\ @@ -211,7 +211,7 @@ Berechnung: Maximales Matching in bipartitem Graphen. Dupliziere jedes $s \in S$ in $u_s$ und $v_s$. Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu. - Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden. + Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Antikette zu finden. \item \textbf{\textsc{Turan}'s-Theorem:} Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist: diff --git a/content/other/timed.cpp b/content/other/timed.cpp index b3ed4ef..a3ede29 100644 --- a/content/other/timed.cpp +++ b/content/other/timed.cpp @@ -1,3 +1,3 @@ int times = clock(); //run for 900ms -while (1000*(clock()-times)/CLOCKS_PER_SEC < 900) {...} +while (1000*(clock()-times)/CLOCKS_PER_SEC < 900) { ... } diff --git a/content/string/ahoCorasick.cpp b/content/string/ahoCorasick.cpp index 390d16d..c65e20a 100644 --- a/content/string/ahoCorasick.cpp +++ b/content/string/ahoCorasick.cpp @@ -4,7 +4,7 @@ struct AhoCorasick { int suffix = 0, ch, cnt = 0; array nxt = {}; - vert(int p, int c) : suffix(-p), ch(c) {fill(all(nxt), -1);} + vert(int p, int c): suffix(-p), ch(c) { fill(all(nxt), -1); } }; vector aho = {{0, -1}}; diff --git a/content/string/rollingHash.cpp b/content/string/rollingHash.cpp index 6e914aa..1157cb7 100644 --- a/content/string/rollingHash.cpp +++ b/content/string/rollingHash.cpp @@ -14,5 +14,5 @@ struct Hash { return (pref[r] - mul(power[r-l], pref[l]) + M) % M; } - static ll mul(__int128 a, ll b) {return a * b % M;} + static ll mul(__int128 a, ll b) { return a * b % M; } }; diff --git a/content/string/rollingHashCf.cpp b/content/string/rollingHashCf.cpp index 84b2e4e..c08a9d3 100644 --- a/content/string/rollingHashCf.cpp +++ b/content/string/rollingHashCf.cpp @@ -13,5 +13,5 @@ struct Hash { return (pref[r] - mul(power[r-l], pref[l]) + M) % M; } - static ll mul(__int128 a, ll b) {return a * b % M;} + static ll mul(__int128 a, ll b) { return a * b % M; } }; diff --git a/content/string/suffixArray.cpp b/content/string/suffixArray.cpp index 8b698d2..0e301b2 100644 --- a/content/string/suffixArray.cpp +++ b/content/string/suffixArray.cpp @@ -8,7 +8,7 @@ struct SuffixArray { P(__lg(2 * n - 1) + 1, vector(n)) { P[0].assign(all(s)); iota(all(SA), 0); - sort(all(SA), [&](int a, int b) {return s[a] < s[b];}); + sort(all(SA), [&](int a, int b) { return s[a] < s[b]; }); vector x(n); for (int k = 1, c = 1; c < n; k++, c *= 2) { iota(all(x), n - c); @@ -19,7 +19,7 @@ struct SuffixArray { partial_sum(all(cnt), begin(cnt)); for (int i : x | views::reverse) SA[--cnt[P[k-1][i]]] = i; - auto p = [&](int i) {return i < n ? P[k-1][i] : -1;}; + auto p = [&](int i) { return i < n ? P[k-1][i] : -1; }; for (int i = 1; i < n; i++) { int a = SA[i-1], b = SA[i]; P[k][b] = P[k][a] + (p(a) != p(b) || p(a+c) != p(b+c)); @@ -27,7 +27,8 @@ struct SuffixArray { for (int i = 1; i < n; i++) LCP[i] = lcp(SA[i-1], SA[i]); } - int lcp(int x, int y) {//x & y are text-indices, not SA-indices + // x & y are text-indices, not SA-indices + int lcp(int x, int y) { if (x == y) return n - x; int res = 0; for (int i = sz(P) - 1; i >= 0 && max(x, y) + res < n; i--) { diff --git a/content/string/suffixAutomaton.cpp b/content/string/suffixAutomaton.cpp index 9a68cb3..d81a05d 100644 --- a/content/string/suffixAutomaton.cpp +++ b/content/string/suffixAutomaton.cpp @@ -4,7 +4,7 @@ struct SuffixAutomaton { struct State { int len, link = -1; array nxt; // map if large Alphabet - State(int l) : len(l) {fill(all(nxt), -1);} + State(int l): len(l) { fill(all(nxt), -1); } }; vector st = {State(0)}; diff --git a/content/string/trie.cpp b/content/string/trie.cpp index 03cf947..d5e092c 100644 --- a/content/string/trie.cpp +++ b/content/string/trie.cpp @@ -3,7 +3,7 @@ constexpr int ALPHABET_SIZE = 2; struct node { int words, ends; array nxt; - node() : words(0), ends(0) {fill(all(nxt), -1);} + node(): words(0), ends(0) { fill(all(nxt), -1); } }; vector trie = {node()}; -- cgit v1.2.3