updated tcr

1 files changed, 21 insertions, 4 deletions

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<int> 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);
+}