Möbius function
(Mylib/Number/mobius_function.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

• Codeforces Round #548 (Div. 2) D. Steps to One

References

• https://en.wikipedia.org/wiki/M%C3%B6bius_function

Code

#pragma once
#include <vector>

namespace haar_lib {
  template <typename Checker>
  std::vector<int> mobius_function(int n, Checker is_prime) {
    std::vector<int> ret(n + 1), ps;

    ret[1] = 1;

    for (int i = 2; i <= n; ++i) {
      if (is_prime(i)) {
        ps.push_back(i);
        ret[i] = -1;
      }
      for (auto &j : ps) {
        if (i * j > n) break;
        if (i % j == 0)
          ret[i * j] = 0;
        else
          ret[i * j] = ret[i] * ret[j];
      }
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/mobius_function.cpp"
#include <vector>

namespace haar_lib {
  template <typename Checker>
  std::vector<int> mobius_function(int n, Checker is_prime) {
    std::vector<int> ret(n + 1), ps;

    ret[1] = 1;

    for (int i = 2; i <= n; ++i) {
      if (is_prime(i)) {
        ps.push_back(i);
        ret[i] = -1;
      }
      for (auto &j : ps) {
        if (i * j > n) break;
        if (i % j == 0)
          ret[i * j] = 0;
        else
          ret[i * j] = ret[i] * ret[j];
      }
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page