math/Euler.cpp

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

Depends on

• math/PrimeFactor.cpp

Verified with

• test/EnumerateEuler.test.cpp
• test/Euler.test.cpp

Code

#pragma once
#include "./PrimeFactor.cpp"
#include <vector>
#include <numeric>

template <class T> T Euler(T x) {
	T result = x;
	for (auto [p, e] : PrimeFactor(x)) {
		result = result / p * (p - 1);
	}
	return result;
}

std::vector<int> EnumerateEuler(int x) {
	std::vector<int> result(x + 1);
	std::iota(result.begin(), result.end(), 0);
	for (int i = 2; i <= x; ++i) {
		if (result[i] == i) {
			for (int j = i; j <= x; j += i) {
				result[j] = result[j] / i * (i - 1);
			}
		}
	}
	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/Euler.cpp"
#include <numeric>

template <class T> T Euler(T x) {
	T result = x;
	for (auto [p, e] : PrimeFactor(x)) {
		result = result / p * (p - 1);
	}
	return result;
}

std::vector<int> EnumerateEuler(int x) {
	std::vector<int> result(x + 1);
	std::iota(result.begin(), result.end(), 0);
	for (int i = 2; i <= x; ++i) {
		if (result[i] == i) {
			for (int j = i; j <= x; j += i) {
				result[j] = result[j] / i * (i - 1);
			}
		}
	}
	return result;
}

Back to top page