test/EnumerateEuler.test.cpp

• View this file on GitHub
• Last update: 2021-03-21 09:59:09+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/RUPC/2286?year=2011

Depends on

• math/Euler.cpp
• math/PrimeFactor.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/RUPC/2286?year=2011"
#include "./../math/Euler.cpp"
#include <iostream>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	const int MAX_A = 1000000;
	vector<int> euler = EnumerateEuler(MAX_A);
	vector<long long> ans(MAX_A + 1, 1);
	for (int i = 1; i <= MAX_A; ++i) {
		ans[i] = ans[i - 1] + euler[i];
	}

	int q;
	cin >> q;
	while (q--) {
		int x;
		cin >> x;
		cout << ans[x] << '\n';
	}
}

#line 1 "test/EnumerateEuler.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/RUPC/2286?year=2011"
#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;
}
#line 3 "test/EnumerateEuler.test.cpp"
#include <iostream>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	const int MAX_A = 1000000;
	vector<int> euler = EnumerateEuler(MAX_A);
	vector<long long> ans(MAX_A + 1, 1);
	for (int i = 1; i <= MAX_A; ++i) {
		ans[i] = ans[i - 1] + euler[i];
	}

	int q;
	cin >> q;
	while (q--) {
		int x;
		cin >> x;
		cout << ans[x] << '\n';
	}
}

Back to top page