diff options
| -rw-r--r-- | math/legendre.cpp | 17 | ||||
| -rw-r--r-- | math/math.tex | 1 | ||||
| -rw-r--r-- | math/phi.cpp | 11 | ||||
| -rw-r--r-- | math/primeSieve.cpp | 2 | ||||
| -rw-r--r-- | math/primes.cpp | 4 | ||||
| -rw-r--r-- | tcr.pdf | bin | 289450 -> 290527 bytes |
6 files changed, 28 insertions, 7 deletions
diff --git a/math/legendre.cpp b/math/legendre.cpp new file mode 100644 index 0000000..adfd3c6 --- /dev/null +++ b/math/legendre.cpp @@ -0,0 +1,17 @@ +int legendre(ll a, ll p) { + a %= p; + if (a == 0) return 0; + if (a == 1 || p == 2) return 1; + if (a == 2) return (((p * p - 1) / 8) & 1) ? -1 : 1; + if (isPrime(a)) { + return legendre(p, a) * ((((p - 1) * (a - 1) / 4) & 1) ? -1 : 1); + } else { + map<ll, int> facts; + factor(a, facts); + int res = 1; + for (auto f : facts) + if (f.second & 1) + res *= legendre(f.first, p); + return res; + } +} diff --git a/math/math.tex b/math/math.tex index 074daae..c3cf473 100644 --- a/math/math.tex +++ b/math/math.tex @@ -148,6 +148,7 @@ Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: \legendre{p}{q} \cdot \legendre{q}{p} &= (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} \end{align*} +\lstinputlisting{math/legendre.cpp} \subsection{Kombinatorik} diff --git a/math/phi.cpp b/math/phi.cpp index c8f8900..492a9d2 100644 --- a/math/phi.cpp +++ b/math/phi.cpp @@ -1,8 +1,11 @@ -ll phi(ll n) { +ll phi(ll n) { // Laufzeit: O(sqrt(n)) + // Optimierung: Falls n prim, n - 1 zurückgeben (Miller-Rabin/Sieb). ll result = n; - for(int i = 2; i * i <= n; ++i) if(n % i == 0) { - while(n % i == 0)n /= i; - result -= result / i; + for(int i = 2; i * i <= n; ++i) { + if(n % i == 0) { // Optimierung: Nur über Primzahlen iterieren. + while(n % i == 0)n /= i; + result -= result / i; + } } if(n > 1) result -= result / n; return result; diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 656a597..7e8b288 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -2,7 +2,7 @@ #define N 100000000 // Bis 10^8 in unter 64MB Speicher. bitset<N / 2> isNotPrime; -inline bool check(int x) { // Diese Methode zum Lookup verwenden. +inline bool isPrime(int x) { // Diese Methode zum Lookup verwenden. if (x < 2) return false; else if (x == 2) return true; else if (!(x & 1)) return false; diff --git a/math/primes.cpp b/math/primes.cpp index 0065939..1694f6a 100644 --- a/math/primes.cpp +++ b/math/primes.cpp @@ -22,7 +22,7 @@ ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim. x = (multMod(x, x, n) + c) % n; y = (multMod(y, y, n) + c) % n; y = (multMod(y, y, n) + c) % n; - d = __gcd(abs(x - y), n); + d = gcd(abs(x - y), n); // Implementierung von oben. } return d == n ? rho(n) : d; } @@ -34,6 +34,6 @@ void factor(ll n, map<ll, int> &facts) { return; } ll f = rho(n); - factor(n/f, facts); + factor(n / f, facts); factor(f, facts); } Binary files differ |