From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- math/mobius.cpp | 25 +++++++++++++++++++++---- 1 file changed, 21 insertions(+), 4 deletions(-) (limited to 'math/mobius.cpp') diff --git a/math/mobius.cpp b/math/mobius.cpp index 7830eb1..3fb4d9e 100644 --- a/math/mobius.cpp +++ b/math/mobius.cpp @@ -1,4 +1,21 @@ -// Laufzeit: O(N*log(log(N))) -int mu[N+1]; mu[1] = 1; -for (int i = 1; i <= N; i++) { - for (int j = 2 * i; j <= N; j += i) mu[j] -= mu[i]; +ll mu(ll n) { // Laufzeit: O(sqrt(n)); + ll res = 1; + for (ll i = 2; i * i <= n; i++) { + if (n % i == 0) { // Optimierung: Nur Primzahlen + if (n % (i * i) == 0) return 0; + res *= -1; + n /= i; + }} + return n > 1 ? -res : res; +} + +// berechnet Möbiusfunktion. Laufzeit: O(N*log(log(N))) +vector mu(n + 1, 1); +for (ll i = 2; i <= n; i++) { + if (mu[i] == 1) { + for (ll j = i; j <= n; j += i) mu[j] *= -2; + for (ll j = i*i; j <= n; j += i*i) mu[j] = 0; + } + // log2(abs(mu[i])) = number of primes + mu[i] = (mu[i] > 0) - (mu[i] < 0); +} -- cgit v1.2.3