test/aoj/2286.test.cpp

View this file on GitHub
Last update: 2023-07-30 00:54:52+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/2286

Depends on

Code

// 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_();
}