diff options
| author | Paul Jungeblut <paul.jungeblut@gmail.com> | 2017-10-22 19:48:13 +0200 |
|---|---|---|
| committer | Paul Jungeblut <paul.jungeblut@gmail.com> | 2017-10-22 19:48:13 +0200 |
| commit | 4b48621b48d3248b5e2718a10e35e7276c504a72 (patch) | |
| tree | dc9eef769da1bf82e2d48341bf34fe7d99f35475 /math/mobius.cpp | |
| parent | 299a3b281bff9c8e01734768aa2bd90f0b9a7610 (diff) | |
Adding code for Möbius Inversion.
Diffstat (limited to 'math/mobius.cpp')
| -rw-r--r-- | math/mobius.cpp | 4 |
1 files changed, 4 insertions, 0 deletions
diff --git a/math/mobius.cpp b/math/mobius.cpp new file mode 100644 index 0000000..7830eb1 --- /dev/null +++ b/math/mobius.cpp @@ -0,0 +1,4 @@ +// 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]; |