結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー りすりす/TwoSquirrels
提出日時 2023-08-15 03:29:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 884 ms / 9,973 ms
コード長 6,333 bytes
コンパイル時間 11,681 ms
コンパイル使用メモリ 497,368 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-23 06:43:28
合計ジャッジ時間 14,812 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

// SPDX-License-Identifier: MIT
// (c) 2023 TwoSquirrels
// my AtCoder environment: https://github.com/TwoSquirrels/atcoder-env

#ifndef INCLUDED_MAIN
#  define INCLUDED_MAIN
#  include __FILE__

inline void cp_main() {
  int n=scan;
  for(int i=0;i<n;i++){
    i64 a_i=scan;
    cout<<a_i<<" "<<is_prime(a_i)<<"\n";
  }
}

#else // INCLUDED_MAIN

// enable debug mode when compiled with -DDEBUG
#ifdef DEBUG
#  define IS_DEBUG (1)
#else
// QCFium method
#  pragma GCC target("avx2")
#  pragma GCC optimize("O3")
#  pragma GCC optimize("unroll-loops")
#  pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#  define IS_DEBUG (0)
#endif

/// includes

// standard libraries
#if __has_include(<bits/stdc++.h>)
#  include <bits/stdc++.h>
#else
// C++17 (clang)
#  include <cassert>
#  include <cfenv>
#  include <cfloat>
#  include <ciso646>
#  include <clocale>
#  include <csetjmp>
#  include <csignal>
#  include <cstdbool>
#  include <cinttypes>
#  include <charconv>
#  include <typeindex>
#  include <any>
#  include <scoped_allocator>
#  include <forward_list>
#  include <list>
#  include <map>
#  include <set>
#  include <valarray>
#  include <variant>
#  include <unordered_map>
#  include <unordered_set>
#  include <queue>
#  include <condition_variable>
#  include <shared_mutex>
#  include <codecvt>
#  include <future>
#  include <regex>
#  include <iostream>
#  include <random>
#  include <ctgmath>
#  include <fstream>
#endif

// boost libraries
#if __has_include(<boost/multiprecision/cpp_int.hpp>)
#  define INCLUDED_BOOST_CPP_INT
#  include <boost/multiprecision/cpp_int.hpp>
#endif
#if __has_include(<boost/math/special_functions/prime.hpp>)
#  define INCLUDED_BOOST_PRIME
#  include <boost/math/special_functions/prime.hpp>
#endif
#if __has_include(<boost/multiprecision/miller_rabin.hpp>)
#  define INCLUDED_BOOST_MILLER_RABIN
#  include <boost/multiprecision/miller_rabin.hpp>
#endif

// atcoder libraries
#if __has_include(<atcoder/all>)
#  define INCLUDED_ACL
#  include <atcoder/all>
#endif

/// sfinae

#if __cplusplus >= 202002L
template <typename T>
concept IsInputable = requires (T a) {
  std::cin >> a;
};
template <typename T>
concept IsPair = requires (T a) {
  a.first;
  a.second;
};
template <typename T>
concept IsEachable = requires (T a) {
  std::begin(a);
  std::end(a);
};
#endif // C++20

/// utils

template <typename T>
constexpr int sin90(T theta90) {
  if (theta90 % 2 == 0) return 0;
  return theta90 % 4 < 2 ? 1 : -1;
}
template <typename T>
constexpr int cos90(T theta90) {
  return sin90(theta90 + 1);
}
template <typename T>
constexpr int sin45(T theta45) {
  if (theta45 % 4 == 0) return 0;
  return theta45 % 8 < 4 ? 1 : -1;
}
template <typename T>
constexpr int cos45(T theta45) {
  return sin90(theta45 + 2);
}

template <typename T, typename U>
inline bool chmin(T &&a, const U b) {
  const bool compare = a > b;
  if (compare) a = b;
  return compare;
}
template <typename T, typename U>
inline bool chmax(T &&a, const U b) {
  const bool compare = a < b;
  if (compare) a = b;
  return compare;
}

long long int powi(int base, int exponent = 2) {
  long long int ans = 1;
  for (int i = exponent; i != 0; i += (i >= 0 ? -1 : 1)) {
    if (i >= 0) ans *= base;
    else ans /= base;
    if (ans == 0) break;
  }
  return ans;
}

template <typename T>
bool is_prime(T n) {
  if (n <= 1) return false;
  if (n == 2 || n == 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  // miller rabin
#ifdef INCLUDED_ACL
  if (n <= 1LL << 32 && n <= std::numeric_limits<int>::max()) {
    return atcoder::internal::is_prime_constexpr(n);
  }
#endif // INCLUDED_ACL
#ifdef INCLUDED_BOOST_MILLER_RABIN
  return boost::multiprecision::miller_rabin_test(n, 25);
#endif // INCLUDED_BOOST_MILLER_RABIN
  // binary search
#ifdef INCLUDED_BOOST_PRIME
  if (n <= boost::math::prime(boost::math::max_prime)) {
    // TODO: binary search
  }
#endif // INCLUDED_BOOST_PRIME
  // trial
  T tried = 3;
#ifdef INCLUDED_BOOST_PRIME
  const int primes_size = boost::math::max_prime + 1;
#else // INCLUDED_BOOST_PRIME
  const std::array primes = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
  };
  const int primes_size = primes.size();
#endif // INCLUDED_BOOST_PRIM
  for (int i = 2; i < primes_size; i++) {
#ifdef INCLUDED_BOOST_PRIME
    const auto prime_i = boost::math::prime(i);
#else // INCLUDED_BOOST_PRIME
    const auto prime_i = primes[i];
#endif // INCLUDED_BOOST_PRIM
    if (prime_i > n / prime_i) return true;
    if (n % prime_i == 0) {
      return false;
    }
    tried = prime_i;
  }
  const T n_sqrt = std::sqrt(n);
  for (T i = (tried + 5) / 6 * 6; i <= n_sqrt; i += 6) {
    if (n % (i - 1) == 0 || n % (i + 1) == 0) {
      return false;
    }
  }
  return true;
}

// input
template <typename T>
inline auto input(T &&target) -> T {
#if __cplusplus >= 202002L
  if constexpr (IsInputable<T>) {
    std::cin >> target;
  } else if constexpr (IsEachable<T>) {
    for (auto &&target_i : target) input(target_i);
  } else if constexpr (IsPair<T>) {
    input(target.first);
    input(target.second);
  } else {
    // skip
  }
#else // C++20
  std::cin >> target;
#endif // C++20
  return target;
}
// input and initialize
struct Scanner {
  template <typename T>
  inline operator T() const {
    T target;
    return input(target);
  }
} scan;

// TODO: output

// TODO: dump for debug

/// main

#if !defined(__INCLUDE_LEVEL__) || __INCLUDE_LEVEL__ <= 1

inline void cp_main();

int main() {
  using namespace std;
  using namespace std::chrono;
#  ifdef DEBUG
  cerr << "[INFO] running in debug mode!" << endl;
  const auto start = system_clock::now();
  try {
#  endif // DEBUG
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(8);
    // run!!!
    cp_main();
#  ifdef DEBUG
    cout << endl;
  } catch (exception e) {
    cout << endl;
    cerr << "[ERROR] " << e.what() << endl;
  }
  const auto end = system_clock::now();
  const auto time_ms = duration_cast<milliseconds>(end - start).count();
  cerr << "[INFO] finished in " << time_ms << " ms!" << endl;
#  endif // DEBUG
  return 0;
}

#endif // __INCLUDE_LEVEL__

/// aliases

using namespace std;

#ifdef INCLUDED_ACL
using namespace atcoder;
#endif // INCLUDED_ACL

using i64 = long long int;

#endif // INCLUDED_MAIN
0