From cca8e7138626b822729aaa749ee62b07f3217004 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 18 Jun 2024 23:15:33 +0200 Subject: fix rho --- math/rho.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'math') diff --git a/math/rho.cpp b/math/rho.cpp index 635c630..7885196 100644 --- a/math/rho.cpp +++ b/math/rho.cpp @@ -1,8 +1,8 @@ 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; - auto f = [n](lll x){return (x * x) % n + 1;}; + ll x = 0, y = 0, prd = 2, i = n/2 + 7; + auto f = [&](lll x){return (x * x + i) % n;}; for (ll t = 30, i = n/2 + 7; 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; -- cgit v1.2.3 From 500ac1e618410ac453fa4fe83e2348cad8c2418f Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 22 Jun 2024 21:12:39 +0200 Subject: fix --- math/binomial0.cpp | 2 +- math/math.tex | 1 + math/tables/composite.tex | 42 +++++++++++++++++++++--------------------- tcr.pdf | Bin 665092 -> 664604 bytes 4 files changed, 23 insertions(+), 22 deletions(-) (limited to 'math') diff --git a/math/binomial0.cpp b/math/binomial0.cpp index d9af917..896a0f1 100644 --- a/math/binomial0.cpp +++ b/math/binomial0.cpp @@ -10,5 +10,5 @@ void precalc() { ll calc_binom(ll n, ll k) { if (n < 0 || n < k || k < 0) return 0; - return (fac[n] * fac[n-k] % mod) * fac[k] % mod; + return (inv[n] * inv[n-k] % mod) * fac[k] % mod; } diff --git a/math/math.tex b/math/math.tex index 8a30b86..f9a5ea5 100644 --- a/math/math.tex +++ b/math/math.tex @@ -409,6 +409,7 @@ so gilt %\begin{algorithm}{Binomialkoeffizienten} \paragraph{Binomialkoeffizienten} Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge. + \begin{methods} \method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}} \method{calc\_binom}{berechnet Binomialkoeffizient}{1} diff --git a/math/tables/composite.tex b/math/tables/composite.tex index b4c8294..1d06a62 100644 --- a/math/tables/composite.tex +++ b/math/tables/composite.tex @@ -1,26 +1,26 @@ -\begin{tabularx}{\linewidth}{|r|r|r|CICICICICICICICICICICIC|} +\begin{tabularx}{\linewidth}{|r||r|r||r|r|r||C|} \hline - \multicolumn{15}{|c|}{Highly Composite Numbers} \\ + \multicolumn{7}{|c|}{Important Numbers} \\ \hline - $10^x$ & Zahl & Teiler & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 \\ + $10^x$ & Highly Composite & \# Divs & $<$ Prime & $>$ Prime & \# Primes & \\ \hline - 1 & 6 & 4 & 1 & 1 & & & & & & & & & & \\ - 2 & 60 & 12 & 2 & 1 & 1 & & & & & & & & & \\ - 3 & 840 & 32 & 3 & 1 & 1 & 1 & & & & & & & &\\ - 4 & 7560 & 64 & 3 & 3 & 1 & 1 & & & & & & & & \\ - 5 & 83160 & 128 & 3 & 3 & 1 & 1 & 1 & & & & & & & \\ - 6 & 720720 & 240 & 4 & 2 & 1 & 1 & 1 & 1 & & & & & & \\ - 7 & 8648640 & 448 & 6 & 3 & 1 & 1 & 1 & 1 & & & & & & \\ - 8 & 73513440 & 768 & 5 & 3 & 1 & 1 & 1 & 1 & 1 & & & & & \\ - 9 & 735134400 & 1344 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & & & & & \\ - 10 & 6983776800 & 2304 & 5 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & & & & \\ - 11 & 97772875200 & 4032 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & & & & \\ - 12 & 963761198400 & 6720 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & & \\ - 13 & 9316358251200 & 10752 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & & \\ - 14 & 97821761637600 & 17280 & 5 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & \\ - 15 & 866421317361600 & 26880 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ - 16 & 8086598962041600 & 41472 & 8 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ - 17 & 74801040398884800 & 64512 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ - 18 & 897612484786617600 & 103680 & 8 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ + 1 & 6 & 4 & $-3$ & $+1$ & 4 & \\ + 2 & 60 & 12 & $-3$ & $+1$ & 25 & \\ + 3 & 840 & 32 & $-3$ & $+9$ & 168 & \\ + 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & \\ + 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & \\ + 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & \\ + 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & \\ + 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & \\ + 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & \\ + 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & \\ + 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & \\ + 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & \\ + 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & \\ + 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & \\ + 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & \\ + 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & \\ + 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & \\ + 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & \\ \hline \end{tabularx} diff --git a/tcr.pdf b/tcr.pdf index c22d0d5..63ebc4a 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3