summaryrefslogtreecommitdiff
path: root/content/math
diff options
context:
space:
mode:
Diffstat (limited to 'content/math')
-rw-r--r--content/math/bigint.cpp4
-rw-r--r--content/math/binomial1.cpp2
-rw-r--r--content/math/divisors.cpp2
-rw-r--r--content/math/gcd-lcm.cpp4
-rw-r--r--content/math/linearSieve.cpp12
-rw-r--r--content/math/math.tex4
-rw-r--r--content/math/piLegendre.cpp46
-rw-r--r--content/math/polynomial.cpp6
-rw-r--r--content/math/primeSieve.cpp2
-rw-r--r--content/math/recover.cpp2
-rw-r--r--content/math/rho.cpp4
-rw-r--r--content/math/simpson.cpp2
-rw-r--r--content/math/sqrtModCipolla.cpp2
-rw-r--r--content/math/tables/prime-composite.tex10
14 files changed, 51 insertions, 51 deletions
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<ll> 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<vector<ll>> memo(cache * cache, vector<ll>(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<vector<ll>> memo(cache * cache, vector<ll>(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<ll> _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<ll, 2> recover(ll c, ll m) {
array<ll, 2> 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<ll, int>& 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}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 16:25:32 +0000