math/Moebius.cpp

• View this file on GitHub
• Last update: 2021-03-21 09:59:09+09:00

Depends on

• math/PrimeFactor.cpp

Code

#pragma once
#include "./PrimeFactor.cpp"
#include <map>

template <class T> std::map<T, int> Moebius(T n) {
	std::map<T, int> result;
	auto primes = PrimeFactor(n);
	int m = primes.size();
	for (int bit = 0; bit < (1 << m); ++bit) {
		int mul = 1, d = 1;
		for (int i = 0; i < m; ++i) {
			if (bit & (1 << i)) {
				mul *= -1;
				d *= primes[i].first;
			}
		}
		result[d] = mul;
	}
	return result;
}

#line 2 "math/PrimeFactor.cpp"
#include <map>
#include <vector>
#include <utility>
#include <cassert>

template <class T> std::vector<std::pair<T, int>> PrimeFactor(T n) {
	assert(1 <= n);
	if (n == 1) {
		return {};
	}
	std::vector<std::pair<T, int>> result;
	for (T i = 2; i * i <= n; ++i) {
		if (n % i == 0) {
			result.emplace_back(i, 0);
			while (n % i == 0) {
				result.back().second++;
				n /= i;
			}
		}
	}
	if (n != 1) {
		result.emplace_back(n, 1);
	}
	return result;
}
template <class T> std::map<T, int> PrimeFactor_map(T n) {
	assert(1 <= n);
	if (n == 1) {
		return {};
	}
	std::map<T, int> result;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			result[i]++;
			n /= i;
		}
	}
	if (n != 1) {
		result[n] = 1;
	}
	return result;
}
template <class T> std::vector<T> PrimeFactor_vector(T n) {
	assert(1 <= n);
	if (n == 1) {
		return {};
	}
	std::vector<T> result;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			result.push_back(i);
			n /= i;
		}
	}
	if (n != 1) {
		result.push_back(n);
	}
	return result;
}
#line 4 "math/Moebius.cpp"

template <class T> std::map<T, int> Moebius(T n) {
	std::map<T, int> result;
	auto primes = PrimeFactor(n);
	int m = primes.size();
	for (int bit = 0; bit < (1 << m); ++bit) {
		int mul = 1, d = 1;
		for (int i = 0; i < m; ++i) {
			if (bit & (1 << i)) {
				mul *= -1;
				d *= primes[i].first;
			}
		}
		result[d] = mul;
	}
	return result;
}

Back to top page