This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub noshi91/Library
#include "other/ceildiv.cpp" #include "other/int_alias.cpp" #include <vector> template <class G> void divisor_mobius_transform(std::vector<typename G::value_type> &a) { const usize n = a.size(); std::vector<bool> sieve(n, true); for (usize p = 2; p < n; p += 1) { if (!sieve[p]) continue; for (usize k = ceildiv(n, p); k != 1;) { k -= 1; sieve[k * p] = false; a[k * p] = G::operation(G::inverse(a[k]), a[k * p]); } } } /** * @brief Divisor Möbius Transform */
#line 1 "other/ceildiv.cpp" template <class T> constexpr T ceildiv(const T &n, const T &d) { return n / d + (n % d != 0 ? 1 : 0); } #line 2 "other/int_alias.cpp" #include <cstddef> #include <cstdint> using i32 = std::int32_t; using i64 = std::int64_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using isize = std::ptrdiff_t; using usize = std::size_t; #line 3 "algorithm/divisor_mobius_transform.cpp" #include <vector> template <class G> void divisor_mobius_transform(std::vector<typename G::value_type> &a) { const usize n = a.size(); std::vector<bool> sieve(n, true); for (usize p = 2; p < n; p += 1) { if (!sieve[p]) continue; for (usize k = ceildiv(n, p); k != 1;) { k -= 1; sieve[k * p] = false; a[k * p] = G::operation(G::inverse(a[k]), a[k * p]); } } } /** * @brief Divisor Möbius Transform */