test/yukicoder/3030/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://yukicoder.me/problems/no/3030
• Link: View error logs on GitHub Actions

Depends on

• Input tuple (Mylib/IO/input_tuple.cpp)
• Input tuples (Mylib/IO/input_tuples.cpp)
• 128-bit int (Mylib/Misc/int128.cpp)
• Primality test (Miller-Rabin algorithm) (Mylib/Number/Prime/miller_rabin.cpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/3030"

#include <iostream>
#include "Mylib/IO/input_tuples.cpp"
#include "Mylib/Number/Prime/miller_rabin.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N;
  std::cin >> N;

  for (auto [x] : hl::input_tuples<int64_t>(N)) {
    std::cout << x << " " << hl::miller_rabin(x) << "\n";
  }

  return 0;
}

#line 1 "test/yukicoder/3030/main.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3030"

#include <iostream>
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#include <utility>
#include <vector>
#line 6 "Mylib/IO/input_tuple.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
  }

  template <typename T, typename U>
  std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
    s >> value.first >> value.second;
    return s;
  }

  template <typename... Args>
  std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
    input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
    return s;
  }
}  // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"

namespace haar_lib {
  template <typename... Args>
  class InputTuples {
    struct iter {
      using value_type = std::tuple<Args...>;
      value_type value;
      bool fetched = false;
      int N, c = 0;

      value_type operator*() {
        if (not fetched) {
          std::cin >> value;
        }
        return value;
      }

      void operator++() {
        ++c;
        fetched = false;
      }

      bool operator!=(iter &) const {
        return c < N;
      }

      iter(int N) : N(N) {}
    };

    int N;

  public:
    InputTuples(int N) : N(N) {}

    iter begin() const { return iter(N); }
    iter end() const { return iter(N); }
  };

  template <typename... Args>
  auto input_tuples(int N) {
    return InputTuples<Args...>(N);
  }
}  // namespace haar_lib
#line 2 "Mylib/Number/Prime/miller_rabin.cpp"
#include <cstdint>
#line 2 "Mylib/Misc/int128.cpp"

namespace haar_lib {
#ifdef __SIZEOF_INT128__
  using uint128_t = __uint128_t;
  using int128_t  = __int128_t;
#else
#include <boost/multiprecision/cpp_int.hpp>
  using uint128_t = boost::multiprecision::uint128_t;
  using int128_t  = boost::multiprecision::int128_t;
#endif
}  // namespace haar_lib
#line 5 "Mylib/Number/Prime/miller_rabin.cpp"

namespace haar_lib {
  namespace miller_rabin_impl {
    uint128_t power(uint128_t a, uint128_t b, uint128_t p) {
      uint128_t ret = 1;

      while (b > 0) {
        if (b & 1) ret = ret * a % p;
        a = a * a % p;
        b >>= 1;
      }

      return ret;
    }

    bool is_composite(uint64_t a, uint64_t p, int s, uint64_t d) {
      uint128_t x = power(a, d, p);

      if (x == 1) return false;

      for (int i = 0; i < s; ++i) {
        if (x == p - 1) return false;
        x = x * x % p;
      }

      return true;
    }
  }  // namespace miller_rabin_impl

  bool miller_rabin(uint64_t n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    int s      = 0;
    uint64_t d = n - 1;
    while ((d & 1) == 0) {
      s += 1;
      d >>= 1;
    }

    if (n < 4759123141) {
      for (uint64_t x : {2, 7, 61}) {
        if (x < n and miller_rabin_impl::is_composite(x, n, s, d)) return false;
      }

      return true;
    }

    for (uint64_t x : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
      if (x < n and miller_rabin_impl::is_composite(x, n, s, d)) return false;
    }

    return true;
  }
}  // namespace haar_lib
#line 6 "test/yukicoder/3030/main.test.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N;
  std::cin >> N;

  for (auto [x] : hl::input_tuples<int64_t>(N)) {
    std::cout << x << " " << hl::miller_rabin(x) << "\n";
  }

  return 0;
}

Back to top page