#623644 (C++17) No.3030 ミラー・ラビン素数判定法のテスト

• 問題: No.3030 ミラー・ラビン素数判定法のテスト
• ユーザー: anqooqie
• 提出日時: 2021-02-28 18:43:50
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 241 ms / 9,973 ms
• コード長: 6,454 bytes
• コンパイル時間: 2,435 ms
• コンパイル使用メモリ: 202,772 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-16 23:36:46
• 合計ジャッジ時間: 3,580 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	137 ms; 5,248 KB
testcase_05	AC	132 ms; 5,248 KB
testcase_06	AC	56 ms; 5,248 KB
testcase_07	AC	55 ms; 5,248 KB
testcase_08	AC	53 ms; 5,248 KB
testcase_09	AC	241 ms; 5,248 KB

ソースコード

#line 1 "/home/anqooqie/.proconlib/tools/util.hpp"



#ifdef LOCAL
  #ifndef _GLIBCXX_DEBUG
    #define _GLIBCXX_DEBUG
  #endif
#else
  #ifndef NDEBUG
    #define NDEBUG
  #endif
#endif

#include <bits/stdc++.h>

using i64 = ::std::int_fast64_t;
using u64 = ::std::uint_fast64_t;
using i32 = ::std::int_fast32_t;
using u32 = ::std::uint_fast32_t;

#define ALL(x) ::std::begin((x)), ::std::end((x))

namespace tools {
  namespace detail {
    namespace util {
      template <typename T>
      class is_range {
      private:
        template <typename U>
        static auto check(U x) -> decltype(::std::begin(x), ::std::end(x), ::std::true_type{});
        static ::std::false_type check(...);

      public:
        static const bool value = decltype(check(::std::declval<T>()))::value;
      };

      template <typename T>
      class has_val {
      private:
        template <typename U>
        static auto check(U x) -> decltype(x.val(), ::std::true_type{});
        static ::std::false_type check(...);

      public:
        static const bool value = decltype(check(::std::declval<T>()))::value;
      };

      template <typename T>
      ::std::istream& read(::std::istream& is, T& container) {
        for (auto& v : container) {
          is >> v;
        }
        return is;
      }

      template <typename T>
      ::std::ostream& debug_print(::std::ostream& os, const T& container) {
        ::std::string delimiter = "";
        os << '[';
        for (const auto& v : container) {
          os << delimiter << v;
          delimiter = ", ";
        }
        os << ']';
        return os;
      }
    }
  }

  template <class T, class Allocator, typename Head>
  void resize(::std::vector<T, Allocator>& vector, const Head& head) {
    vector.resize(head);
  }
  template <class T, class Allocator, typename Head, typename... Tail>
  void resize(::std::vector<T, Allocator>& vector, const Head& head, const Tail&... tail) {
    vector.resize(head);
    for (auto& child : vector) {
      ::tools::resize(child, tail...);
    }
  }

  template <class T, class Allocator, typename V>
  auto fill(::std::vector<T, Allocator>& vector, const V& value) -> ::std::enable_if_t<!::tools::detail::util::is_range<T>::value, void> {
    ::std::fill(::std::begin(vector), ::std::end(vector), value);
  }
  template <class T, class Allocator, typename V>
  auto fill(::std::vector<T, Allocator>& vector, const V& value) -> ::std::enable_if_t<::tools::detail::util::is_range<T>::value, void> {
    for (auto& child : vector) {
      ::tools::fill(child, value);
    }
  }
}

template <class T, class Allocator>
::std::istream& operator>>(::std::istream& is, ::std::vector<T, Allocator>& vector) {
  return ::tools::detail::util::read(is, vector);
}
template <class T, ::std::size_t N>
::std::istream& operator>>(::std::istream& is, ::std::array<T, N>& array) {
  return ::tools::detail::util::read(is, array);
}
template <class T, class Allocator>
::std::ostream& operator<<(::std::ostream& os, const ::std::vector<T, Allocator>& vector) {
  return ::tools::detail::util::debug_print(os, vector);
}
template <class T, ::std::size_t N>
::std::ostream& operator<<(::std::ostream& os, const ::std::array<T, N>& array) {
  return ::tools::detail::util::debug_print(os, array);
}
template <class Key, class Hash, class Pred, class Allocator>
::std::ostream& operator<<(::std::ostream& os, const ::std::unordered_set<Key, Hash, Pred, Allocator>& unordered_set) {
  return ::tools::detail::util::debug_print(os, unordered_set);
}

template <class T, class Container>
::std::ostream& operator<<(::std::ostream& os, ::std::stack<T, Container>& stack) {
  ::std::stack<T, Container> other;
  std::string delimiter = "";
  os << '[';
  while (!stack.empty()) {
    os << delimiter << stack.top();
    delimiter = ", ";
    other.push(stack.top());
    stack.pop();
  }
  os << ']';

  while (!other.empty()) {
    stack.push(other.top());
    other.pop();
  }

  return os;
}

template <class T1, class T2>
::std::ostream& operator<<(::std::ostream& os, const ::std::pair<T1, T2>& pair) {
  return os << '[' << pair.first << ", " << pair.second << ']';
}
template <int I = -1, typename... Args>
::std::ostream& operator<<(::std::ostream& os, const ::std::tuple<Args...>& tuple) {
  if constexpr (I == -1) {
    os << '[';
  } else if constexpr (I == int(sizeof...(Args))) {
    os << ']';
  } else if constexpr (I == 0) {
    os << ::std::get<I>(tuple);
  } else {
    os << ", " << ::std::get<I>(tuple);
  }

  if constexpr (I < int(sizeof...(Args))) {
    return operator<<<I + 1>(os, tuple);
  } else {
    return os;
  }
}

template <typename T>
auto operator<<(::std::ostream& os, const T& x) -> ::std::enable_if_t<::tools::detail::util::has_val<T>::value, ::std::ostream&> {
  return os << x.val();
}


#line 2 "main.cpp"

constexpr ::std::uint_fast64_t prod_mod(const ::std::uint_fast64_t x, const ::std::uint_fast64_t y, const ::std::uint_fast64_t m) {
  using u128 = unsigned __int128;
  return ::std::uint_fast64_t((u128(x) * u128(y)) % u128(m));
}

constexpr ::std::uint_fast64_t pow_mod(const ::std::uint_fast64_t x, ::std::uint_fast64_t n, const ::std::uint_fast64_t m) {
  if (m == 1) return 0;
  ::std::uint_fast64_t r = 1;
  ::std::uint_fast64_t y = x % m;
  while (n > 0) {
    if ((n & 1) > 0) {
      r = prod_mod(r, y, m);
    }
    y = prod_mod(y, y, m);
    n /= 2;
  }
  return r;
}

constexpr bool is_prime(const ::std::uint_fast64_t n) {
  constexpr ::std::array<::std::uint_fast64_t, 7> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

  if (n <= 1) return false;
  if (n == 2) return true;
  if (n % 2 == 0) return false;

  ::std::uint_fast64_t d = n - 1;
  for (; d % 2 == 0; d /= 2);

  for (const ::std::uint_fast64_t a : bases) {
    if (a % n == 0) return true;

    ::std::uint_fast64_t power = d;
    ::std::uint_fast64_t target = pow_mod(a, power, n);

    bool is_composite = true;
    if (target == 1) is_composite = false;
    for (; is_composite && power != n - 1; power *= 2, target = prod_mod(target, target, n)) {
      if (target == n - 1) is_composite = false;
    }

    if (is_composite) {
      return false;
    }
  }

  return true;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  i64 n;
  std::cin >> n;
  std::vector<i64> x(n);
  std::cin >> x;

  for (const i64& x_i : x) {
    std::cout << x_i << ' ' << (is_prime(x_i) ? 1 : 0) << '\n';
  }
  return 0;
}