結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー bayashi-cl
提出日時 2022-04-23 18:08:15
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 14,939 bytes
コンパイル時間 3,650 ms
コンパイル使用メモリ 152,220 KB
最終ジャッジ日時 2025-01-28 21:13:57
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 3 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#define PROBLEM "https://yukicoder.me/problems/no/3030"
/**
* @file core.hpp
* @author bayashi_cl
* @brief core/all
*
* C++ library for competitive programming by bayashi_cl
* Repository: https://github.com/bayashi-cl/byslib
* Document : https://bayashi-cl.github.io/byslib/
*/
#ifndef LOCAL
#define NDEBUG
#endif
/**
* @file stdlib.hpp
* @brief STL Template
*/
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <vector>
namespace bys {
using std::array, std::vector, std::string, std::set, std::map, std::pair;
using std::cin, std::cout, std::endl;
using std::min, std::max, std::sort, std::reverse, std::abs, std::pow;
// alias
using ll = long long int;
using ld = long double;
using Pa = pair<int, int>;
using Pall = pair<ll, ll>;
using ibool = std::int8_t;
template <class T>
using uset = std::unordered_set<T>;
template <class S, class T>
using umap = std::unordered_map<S, T>;
} // namespace bys
/**
* @file const.hpp
* @brief Const
*/
namespace bys {
constexpr int MOD = 998244353;
constexpr int MOD7 = 1000000007;
constexpr int INF = std::numeric_limits<int>::max() / 2;
constexpr ll LINF = std::numeric_limits<ll>::max() / 2;
} // namespace bys
/**
* @file types.hpp
* @brief Types
*
* type_traits
*/
namespace bys {
template <class, class = void>
struct has_lshift_to_ostream : std::false_type {};
template <class T>
struct has_lshift_to_ostream<T, std::void_t<decltype(std::declval<std::ostream&>() << std::declval<T&>())>> : std::true_type {};
template <class, class = void>
struct has_rshift_from_istream : std::false_type {};
template <class T>
struct has_rshift_from_istream<T, std::void_t<decltype(std::declval<std::istream&>() >> std::declval<T&>())>> : std::true_type {};
template <class T, class = void>
struct has_tuple_interface : std::false_type {};
template <class T>
struct has_tuple_interface<T, std::void_t<decltype(std::tuple_size<T>())>> : std::true_type {};
template <class, class = void>
struct has_iterator : std::false_type {};
template <class T>
struct has_iterator<T, std::void_t<typename T::iterator>> : std::true_type {};
struct Int1 {};
} // namespace bys
/**
* @file printer.hpp
* @brief Output
*/
namespace bys {
class Printer {
std::ostream& os;
std::string _sep = " ", _end = "\n";
template <std::size_t I, class T>
inline void print_tuple_element(T&& elem) {
if constexpr (I != 0) cat(_sep);
cat(std::forward<T>(elem));
}
template <class Tp, std::size_t... I>
inline void print_tuple(Tp&& tp, std::index_sequence<I...>) {
(print_tuple_element<I>(std::forward<decltype(std::get<I>(tp))>(std::get<I>(tp))), ...);
}
public:
Printer(std::ostream& os_) : os(os_) {}
~Printer() { os << std::flush; }
template <class T>
void cat(T&& v) {
if constexpr (has_lshift_to_ostream<std::decay_t<T>>::value) {
os << v;
} else if constexpr (has_iterator<std::decay_t<T>>::value) {
string sep2;
if constexpr (has_iterator<std::decay_t<typename std::decay_t<T>::value_type>>::value) {
sep2 = _end;
} else {
sep2 = _sep;
}
for (auto &&itr = std::begin(v), end = std::end(v); itr != end; ++itr) {
cat(*itr);
if (std::next(itr) != end) cat(sep2);
}
} else if constexpr (has_tuple_interface<std::decay_t<T>>::value) {
print_tuple(std::forward<T>(v), std::make_index_sequence<std::tuple_size_v<std::decay_t<T>>>());
} else {
static_assert([] { return false; }(), "type error");
}
}
void print() { cat(_end); }
template <class T>
void print(T&& top) {
cat(std::forward<T>(top));
cat(_end);
}
template <class T, class... Ts>
void print(T&& top, Ts&&... args) {
cat(std::forward<T>(top));
cat(_sep);
print(std::forward<Ts>(args)...);
}
//! @brief
template <class... Ts>
void operator()(Ts&&... args) {
print(std::forward<Ts>(args)...);
}
void flush() { os << std::flush; }
//! @brief flush
template <class... Ts>
void send(Ts&&... args) {
print(std::forward<Ts>(args)...);
flush();
}
//! @brief
Printer set(string sep_ = " ", string end_ = "\n") {
_sep = sep_;
_end = end_;
return *this;
}
void lf() { cat(_end); }
};
} // namespace bys
/**
* @file scanner.hpp
* @brief Input
*/
namespace bys {
class Scanner {
std::istream& is;
template <class Tp, std::size_t... I>
inline decltype(auto) read_tuple(std::index_sequence<I...>) {
return Tp{read<typename std::tuple_element_t<I, Tp>>()...};
}
public:
Scanner(std::istream& is_) : is(is_){};
template <class... Ts>
void scan(Ts&... args) {
(is >> ... >> args);
}
/**
* @brief 2
*
*
*/
template <class T, class... Us>
decltype(auto) read() {
if constexpr (sizeof...(Us) == 0) {
if constexpr (has_rshift_from_istream<T>::value) {
T res;
is >> res;
return res;
} else if constexpr (has_tuple_interface<T>::value) {
auto res = read_tuple<T>(std::make_index_sequence<std::tuple_size_v<T>>());
return res;
} else if constexpr (std::is_same_v<T, Int1>) {
int res;
is >> res;
--res;
return res;
} else if constexpr (has_iterator<T>::value) {
//! TODO: split
static_assert([] { return false; }(), "NotImplementedError");
} else {
static_assert([] { return false; }(), "TypeError");
}
} else {
return std::tuple{read<T>(), read<Us>()...};
}
}
/**
* @brief TN
*
*
*/
template <class T, std::size_t N, typename R = std::conditional_t<std::is_same_v<T, Int1>, int, T>>
std::array<R, N> read() {
std::array<R, N> res;
for (auto&& e : res) e = read<T>();
return res;
}
//! @brief nvector
template <class T, typename R = std::conditional_t<std::is_same_v<T, Int1>, int, T>>
vector<R> readvec(int n) {
vector<R> res(n);
for (auto&& e : res) e = read<T>();
return res;
}
//! @brief n*m2vector
template <class T, typename R = std::conditional_t<std::is_same_v<T, Int1>, int, T>>
vector<vector<R>> readvec(int n, int m) {
vector<vector<R>> res(n);
for (auto&& e : res) e = readvec<T>(m);
return res;
}
/**
* @brief 1
* @param f
* @param sep
*/
template <class Lambda = std::function<int(std::string)>,
typename T = std::invoke_result_t<std::decay_t<Lambda>, std::string>>
std::vector<T> readln(
Lambda f = [](string x) { return std::stoi(x); }, char sep = ' ') {
std::ws(is);
std::string elem;
std::getline(is, elem);
std::stringstream ss{elem};
std::vector<T> res;
while (std::getline(ss, elem, sep)) res.emplace_back(f(elem));
return res;
}
/**
* @brief 1
* @param skip_ws
*/
std::string getline(bool skip_ws = true) {
if (skip_ws) std::ws(is);
std::string res;
std::getline(is, res);
return res;
}
};
} // namespace bys
/**
* @file io.hpp
* @brief I/O
*/
namespace bys {
__attribute__((constructor)) void setup_io() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(11);
std::cerr << std::fixed << std::setprecision(11);
std::cerr << std::boolalpha;
}
Printer print(std::cout), debug(std::cerr);
Scanner scanner(std::cin);
} // namespace bys
/**
* @file macro.hpp
* @brief Macro
*/
// clang-format off
#ifdef LOCAL
//! @brief
#define DEBUG(...) { std::cerr << "[debug] line" << std::setw(4) << __LINE__ << ": "; debug(__VA_ARGS__); }
#else
#define DEBUG(...)
#endif
//! @brief printreturn
#define EXIT(...) { print(__VA_ARGS__); return; }
#define CONCAT_IMPL(a, b) a##b
#define CONCAT(a, b) CONCAT_IMPL(a, b)
//! @brief [[maybe_unused]]
#define UV [[maybe_unused]] auto CONCAT(unused_val_, __LINE__)
#define RE std::runtime_error("line: " + std::to_string(__LINE__) + ", func: " + __func__)
// clang-format on
/**
* @file solver.hpp
* @brief Solver
*/
namespace bys {
struct Solver {
int IT = 1;
Solver() {}
void solve();
//! @brief
void solve(int rep) {
for (; IT <= rep; ++IT) solve();
}
};
} // namespace bys
// -------------------------------------
/**
* @file bit.hpp
* @brief Bit
* @note c++20<bit>
*/
namespace bys {
/**
* @brief bit
*
* bit_width(x) - 1 < log2(x) <= bit_width(x)
*/
template <class T>
constexpr int bit_width(T x) {
int bits = 0;
x = (x < 0) ? (-x) : x;
for (; x != 0; bits++) x >>= 1;
return bits;
}
//! @brief 2
template <class T>
constexpr T bit_floor(T x) {
assert(x >= 0);
return x == 0 ? 0 : T(1) << (bit_width(x) - 1);
}
//! @brief 2
template <class T>
constexpr T bit_ceil(T x) {
assert(x >= 0);
return x == 0 ? 1 : T(1) << bit_width(x - 1);
}
//! @brief 2
template <class T>
std::string bin(T n) {
assert(n > 0);
if (n == 0) return "0";
std::string res;
while (n > 0) {
res.push_back(n & 1 ? '1' : '0');
n >>= 1;
}
std::reverse(res.begin(), res.end());
return res;
}
//! @brief d bit
template <class T>
constexpr bool pop(T s, int d) {
return s & (T(1) << d);
}
} // namespace bys
/**
* @file numeric.hpp
* @brief Numeric
*
*
*/
namespace bys {
//! @brief
constexpr ll int_pow(int a, int b) {
ll res = 1;
for (int i = 0; i < b; ++i) res *= a;
return res;
}
/**
* @brief
*
* O(log q)
*/
template <class T>
constexpr T mod_pow(T p, T q, T mod) {
T res = 1 % mod;
p %= mod;
for (; q; q >>= 1) {
if (q & 1) res = res * p % mod;
p = p * p % mod;
}
return res;
}
//! @brief ceil(x / y)
template <class T>
constexpr T ceildiv(T x, T y) {
if ((x < T(0)) ^ (y < T(0))) {
return x / y;
} else {
return (x + y + (x < T(0) ? 1 : -1)) / y;
}
}
//! @brief floor(x / y)
template <class T>
constexpr T floordiv(T x, T y) {
if ((x < T(0)) ^ (y < T(0))) {
return (x - y + (x < T(0) ? 1 : -1)) / y;
} else {
return x / y;
}
}
/**
* @brief Python::divmod
*
* See: https://docs.python.org/ja/3/library/functions.html#divmod
*/
template <class T>
constexpr std::pair<T, T> divmod(T x, T y) {
auto q = floordiv(x, y);
return {q, x - q * y};
}
/**
* @brief Python::%
*
* See: https://docs.python.org/ja/3/reference/expressions.html#index-68
*/
template <class T, class S>
constexpr T floormod(T x, S mod) {
x %= mod;
if (x < 0) x += mod;
return x;
}
constexpr ll isqrt_aux(ll c, ll n) {
if (c == 0) return 1;
ll k = (c - 1) / 2;
ll a = isqrt_aux(c / 2, n >> (2 * k + 2));
return (a << k) + (n >> (k + 2)) / a;
}
/**
* @brief Python::math.isqrt
*
* floor(sqrt(n))
* See: https://docs.python.org/ja/3/library/math.html#math.isqrt
*/
template <class T>
constexpr T isqrt(T n) {
assert(n >= 0);
if (n == T(0)) return T(0);
ll a = isqrt_aux((bit_width(n) - 1) / 2, n);
return n < a * a ? a - 1 : a;
}
/**
* @brief Nim::math::almostEqual
*
* See: https://nim-lang.org/docs/math.html#almostEqual,T,T,Natural
*/
template <class T, typename std::enable_if_t<std::is_floating_point_v<T>, std::nullptr_t> = nullptr>
constexpr bool isclose(T x, T y, T coef = 4.0) {
if (x == y) return true;
auto diff = std::abs(x - y);
return diff <= std::numeric_limits<T>::epsilon() * std::abs(x + y) * coef || diff < std::numeric_limits<T>::min();
}
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = floormod(a, b);
if (a == 0) return {b, 0};
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u;
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
} // namespace bys
/**
* @file prime.hpp
* @brief Prime
*/
namespace bys {
/**
* @brief
*
*
* O(√n)
*/
template <typename T>
vector<T> prime_factorize(T n) {
vector<T> res;
while (n % 2 == 0) {
res.push_back(2);
n /= 2;
}
T f = 3;
while (f * f <= n) {
if (n % f == 0) {
res.push_back(f);
n /= f;
} else {
f += 2;
}
}
if (n != 1) res.push_back(n);
return res;
}
/**
* @brief Miller-Rabin
*
* 2^64
* See: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
* See: https://miller-rabin.appspot.com
*/
constexpr bool is_prime(long long n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d >>= 1;
constexpr std::array<ll, 7> prime = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
for (long long p : prime) {
long long t = d;
long long y = mod_pow(p, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
} // namespace bys
namespace bys {
void Solver::solve() {
auto x = scanner.read<int>();
print(x, is_prime(x) ? 1 : 0);
}
} // namespace bys
int main() {
bys::Solver solver;
solver.solve(bys::scanner.read<int>());
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0