test/phi_table.test.cpp

View this file on GitHub
Last update: 2024-03-03 06:51: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 = 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>
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(int i = 2; i <= n; ++i) {
			if(euler[i] == i) {
				for(int j = i; j <= n; j += i) {
					euler[j] = euler[j] / i * (i - 1);
				}
			}
		}
	}
	std::vector<int> get() const { return euler; }
};

/**
 * @brief Euler's Phi-function(table)
 */
#line 4 "test/phi_table.test.cpp"
constexpr int n = 1e6;
int main() {
    const auto phi = 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';
    }
}