This documentation is automatically generated by online-judge-tools/verification-helper
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2286
#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/math/totient-enumeration.hpp"
#include <iostream>
#include <vector>
namespace luz {
void main_() {
constexpr u32 MAX_N = 1000000;
std::vector< u64 > rs = totient_enumeration< u64 >(MAX_N);
for (usize i: rep(2, rs.size())) {
rs[i] += rs[i - 1];
}
usize t;
std::cin >> t;
for ([[maybe_unused]] usize _: rep(0, t)) {
usize n;
std::cin >> n;
std::cout << rs[n] + 1 << std::endl;
}
}
} // namespace luz
int main() {
luz::main_();
}
#line 1 "test/aoj/2286.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2286
#line 2 "src/cpp-template/header/int-alias.hpp"
#include <cstdint>
namespace luz {
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
} // namespace luz
#line 2 "src/cpp-template/header/rep.hpp"
#line 2 "src/cpp-template/header/size-alias.hpp"
#include <cstddef>
namespace luz {
using isize = std::ptrdiff_t;
using usize = std::size_t;
} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"
#include <algorithm>
namespace luz {
struct rep {
struct itr {
usize i;
constexpr itr(const usize i) noexcept: i(i) {}
void operator++() noexcept {
++i;
}
constexpr usize operator*() const noexcept {
return i;
}
constexpr bool operator!=(const itr x) const noexcept {
return i != x.i;
}
};
const itr f, l;
constexpr rep(const usize f, const usize l) noexcept
: f(std::min(f, l)),
l(l) {}
constexpr auto begin() const noexcept {
return f;
}
constexpr auto end() const noexcept {
return l;
}
};
struct rrep {
struct itr {
usize i;
constexpr itr(const usize i) noexcept: i(i) {}
void operator++() noexcept {
--i;
}
constexpr usize operator*() const noexcept {
return i;
}
constexpr bool operator!=(const itr x) const noexcept {
return i != x.i;
}
};
const itr f, l;
constexpr rrep(const usize f, const usize l) noexcept
: f(l - 1),
l(std::min(f, l) - 1) {}
constexpr auto begin() const noexcept {
return f;
}
constexpr auto end() const noexcept {
return l;
}
};
} // namespace luz
#line 2 "src/math/totient-enumeration.hpp"
#line 4 "src/math/totient-enumeration.hpp"
#include <cassert>
#include <limits>
#include <vector>
namespace luz {
template < typename T >
std::vector< T > totient_enumeration(T n) {
static_assert(std::numeric_limits< T >::is_integer,
"T must be integer");
assert(n >= 0);
n += 1;
std::vector< T > totients(n);
for (T i: rep(0, n)) {
totients[i] = i;
}
for (T i: rep(2, n)) {
if (totients[i] != i) continue;
for (T j = i; j < n; j += i) {
totients[j] = totients[j] / i * (i - 1);
}
}
return totients;
}
} // namespace luz
#line 7 "test/aoj/2286.test.cpp"
#include <iostream>
#line 10 "test/aoj/2286.test.cpp"
namespace luz {
void main_() {
constexpr u32 MAX_N = 1000000;
std::vector< u64 > rs = totient_enumeration< u64 >(MAX_N);
for (usize i: rep(2, rs.size())) {
rs[i] += rs[i - 1];
}
usize t;
std::cin >> t;
for ([[maybe_unused]] usize _: rep(0, t)) {
usize n;
std::cin >> n;
std::cout << rs[n] + 1 << std::endl;
}
}
} // namespace luz
int main() {
luz::main_();
}