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 --- 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 +++---- 14 files changed, 51 insertions(+), 51 deletions(-) (limited to 'content/math') 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} -- cgit v1.2.3