test/phi_table.test.cpp

• View this file on GitHub
• Last update: 2025-06-06 22:43:22+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2286

Depends on

• Euler's Phi-function(table) (C++/math/phitable.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2286"
#include <iostream>
#include "C++/math/phitable.hpp"
constexpr int n = 1e6;
int main() {
    const auto phi = man::phi_table(n).get();
    std::vector<int64_t> ret(n + 1);
    ret[1] = 2;
    for(int i = 2; i <= n; ++i) {
        ret[i] = ret[i - 1] + phi[i];
    }
    int t;
    std::cin >> t;
    while(t--) {
        int i;
        std::cin >> i;
        std::cout << ret[i] << '\n';
    }
}

#line 1 "test/phi_table.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2286"
#include <iostream>
#line 2 "C++/math/phitable.hpp"

#include <vector>
#include <numeric>
#include <ranges>
namespace man {
struct phi_table {
private:
    int n;
	std::vector<int> euler;
public:
	phi_table(const int n_): n(n_), euler(n_ + 1) {
		std::iota(euler.begin(), euler.end(), 0);
		for(const auto i: std::views::iota(2, n + 1)) {
			if(euler[i] == i) {
				for(int j = i; j <= n; j += i) {
					euler[j] = euler[j] / i * (i - 1);
				}
			}
		}
	}
	inline std::vector<int> get() const noexcept { return euler; }
};
}

/**
 * @brief Euler's Phi-function(table)
 */
#line 4 "test/phi_table.test.cpp"
constexpr int n = 1e6;
int main() {
    const auto phi = man::phi_table(n).get();
    std::vector<int64_t> ret(n + 1);
    ret[1] = 2;
    for(int i = 2; i <= n; ++i) {
        ret[i] = ret[i - 1] + phi[i];
    }
    int t;
    std::cin >> t;
    while(t--) {
        int i;
        std::cin >> i;
        std::cout << ret[i] << '\n';
    }
}

Back to top page