結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | taotao54321 |
提出日時 | 2019-03-28 00:49:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 235 ms / 9,973 ms |
コード長 | 15,856 bytes |
コンパイル時間 | 2,091 ms |
コンパイル使用メモリ | 203,728 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 23:12:47 |
合計ジャッジ時間 | 3,424 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 133 ms
5,248 KB |
testcase_05 | AC | 130 ms
5,248 KB |
testcase_06 | AC | 52 ms
5,248 KB |
testcase_07 | AC | 50 ms
5,248 KB |
testcase_08 | AC | 54 ms
5,248 KB |
testcase_09 | AC | 235 ms
5,248 KB |
ソースコード
/** * */ // header {{{ #include <bits/stdc++.h> using namespace std; using i8 = int8_t; using u8 = uint8_t; using i16 = int16_t; using u16 = uint16_t; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #ifdef __SIZEOF_INT128__ using i128 = __int128; using u128 = unsigned __int128; #endif using f32 = float; using f64 = double; using f80 = __float80; using f128 = __float128; // }}} template<typename T> constexpr T PROCON_INF(); template<> constexpr i64 PROCON_INF<i64>() { return 1'010'000'000'000'000'000LL; } template<> constexpr f64 PROCON_INF<f64>() { return 1e100; } constexpr i64 INF = PROCON_INF<i64>(); constexpr f64 FINF = PROCON_INF<f64>(); constexpr i64 MOD = 1'000'000'007LL; constexpr f64 EPS = 1e-12; constexpr f64 PI = 3.14159265358979323846; // util {{{ #define FOR(i, start, end) for(i64 i = (start), i##_end=(end); i < i##_end; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c)) #define SLICE(f,c,l,r,...) (([&](decltype((c)) cccc, decltype((l)) llll, decltype((r)) rrrr) {\ auto iiii = llll <= rrrr ? std::begin(cccc)+llll : std::end(cccc);\ auto jjjj = llll <= rrrr ? std::begin(cccc)+rrrr : std::end(cccc);\ return (f)(iiii, jjjj, ## __VA_ARGS__);\ })(c,l,r)) #define GENERIC(f) ([](auto&&... args) -> decltype(auto) { return (f)(std::forward<decltype(args)>(args)...); }) template<typename F> class FixPoint { public: explicit constexpr FixPoint(F&& f) : f_(forward<F>(f)) {} template<typename... Args> constexpr decltype(auto) operator()(Args&&... args) const { return f_(*this, forward<Args>(args)...); } private: const F f_; }; template<typename F> decltype(auto) FIX(F&& f) { return FixPoint<F>(forward<F>(f)); } template<typename C> i64 SIZE(const C& c) { return static_cast<i64>(c.size()); } template<typename T, size_t N> i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); } bool is_odd (i64 x) { return x % 2 != 0; } bool is_even(i64 x) { return x % 2 == 0; } template<typename T> i64 cmp(T x, T y) { return (y<x) - (x<y); } template<typename T> i64 sgn(T x) { return cmp(x, T(0)); } i64 ipow(i64 x, i64 e) { assert(e >= 0); i64 res = 1; REP(_, e) { res *= x; } return res; } // Haskell の divMod と同じ pair<i64,i64> divmod(i64 a, i64 b) { i64 q = a / b; i64 r = a % b; if((b>0 && r<0) || (b<0 && r>0)) { --q; r += b; } return {q,r}; } i64 div_ceil(i64 a, i64 b) { i64 q = a / b; i64 r = a % b; if((b>0 && r>0) || (b<0 && r<0)) ++q; return q; } i64 div_floor(i64 a, i64 b) { return divmod(a,b).first; } i64 modulo(i64 a, i64 b) { return divmod(a,b).second; } bool feq(f64 x, f64 y, f64 eps=EPS) { return fabs(x-y) < eps; } template<typename T, typename U> bool chmax(T& xmax, const U& x) { if(xmax < x) { xmax = x; return true; } return false; } template<typename T, typename U> bool chmin(T& xmin, const U& x) { if(x < xmin) { xmin = x; return true; } return false; } template<typename ForwardIt, typename T, typename Comp=less<>> ForwardIt bsearch_find(ForwardIt first, ForwardIt last, const T& x, Comp comp={}) { auto it = lower_bound(first, last, x, comp); if(it == last || comp(x,*it)) return last; return it; } // x 未満の最後の要素 template<typename BidiIt, typename T, typename Comp=less<>> BidiIt bsearch_lt(BidiIt first, BidiIt last, const T& x, Comp comp={}) { auto it = lower_bound(first, last, x, comp); if(it == first) return last; return prev(it); } // x 以下の最後の要素 template<typename BidiIt, typename T, typename Comp=less<>> BidiIt bsearch_le(BidiIt first, BidiIt last, const T& x, Comp comp={}) { auto it = upper_bound(first, last, x, comp); if(it == first) return last; return prev(it); } // x より大きい最初の要素 template<typename BidiIt, typename T, typename Comp=less<>> BidiIt bsearch_gt(BidiIt first, BidiIt last, const T& x, Comp comp={}) { return upper_bound(first, last, x, comp); } // x 以上の最初の要素 template<typename BidiIt, typename T, typename Comp=less<>> BidiIt bsearch_ge(BidiIt first, BidiIt last, const T& x, Comp comp={}) { return lower_bound(first, last, x, comp); } template<typename InputIt> auto SUM(InputIt first, InputIt last) { using T = typename iterator_traits<InputIt>::value_type; return accumulate(first, last, T()); } template<typename ForwardIt, typename UnaryOperation> ForwardIt transform_self(ForwardIt first, ForwardIt last, UnaryOperation op) { return transform(first, last, first, op); } template<typename C> void UNIQ(C& c) { c.erase(ALL(unique,c), end(c)); } template<typename T, typename F> enable_if_t<rank<T>::value==0> ARRAY_FOREACH(T& e, F f) { f(e); } template<typename Array, typename F> enable_if_t<rank<Array>::value!=0> ARRAY_FOREACH(Array& ary, F f) { for(auto& e : ary) ARRAY_FOREACH(e, f); } template<typename Array, typename U> enable_if_t<rank<Array>::value!=0> ARRAY_FILL(Array& ary, const U& v) { ARRAY_FOREACH(ary, [&v](auto& e) { e = v; }); } template<typename BinaryFunc, typename UnaryFunc> auto ON(BinaryFunc bf, UnaryFunc uf) { return [bf,uf](const auto& x, const auto& y) { return bf(uf(x), uf(y)); }; } template<typename F> auto LT_ON(F f) { return ON(less<>(), f); } template<typename F> auto GT_ON(F f) { return ON(greater<>(), f); } struct IDENTITY { template<typename T> constexpr T&& operator()(T&& x) const noexcept { return forward<T>(x); } }; char digit_chr(i64 n) { return static_cast<char>('0' + n); } i64 digit_ord(char c) { return c - '0'; } char lower_chr(i64 n) { return static_cast<char>('a' + n); } i64 lower_ord(char c) { return c - 'a'; } char upper_chr(i64 n) { return static_cast<char>('A' + n); } i64 upper_ord(char c) { return c - 'A'; } // 出力は operator<< を直接使わず、このテンプレート経由で行う // 提出用出力とデバッグ用出力を分けるため template<typename T> struct Formatter { static ostream& write_str(ostream& out, const T& x) { return out << x; } static ostream& write_repr(ostream& out, const T& x) { return out << x; } }; template<typename T> ostream& WRITE_STR(ostream& out, const T& x) { return Formatter<T>::write_str(out, x); } template<typename T> ostream& WRITE_REPR(ostream& out, const T& x) { return Formatter<T>::write_repr(out, x); } template<typename InputIt> ostream& WRITE_JOIN_STR(ostream& out, InputIt first, InputIt last, const string& sep) { while(first != last) { WRITE_STR(out, *first++); if(first != last) out << sep; } return out; } template<typename InputIt> ostream& WRITE_JOIN_REPR(ostream& out, InputIt first, InputIt last, const string& sep) { while(first != last) { WRITE_REPR(out, *first++); if(first != last) out << sep; } return out; } template<typename InputIt> ostream& WRITE_RANGE_STR(ostream& out, InputIt first, InputIt last) { return WRITE_JOIN_STR(out, first, last, " "); } template<typename InputIt> ostream& WRITE_RANGE_REPR(ostream& out, InputIt first, InputIt last) { out << "["; WRITE_JOIN_REPR(out, first, last, ", "); out << "]"; return out; } template<typename T> void FROM_STR(const string& s, T& x) { istringstream in(s); in >> x; } template<typename T> string TO_STR(const T& x) { ostringstream out; WRITE_STR(out, x); return out.str(); } template<typename T> string TO_REPR(const T& x) { ostringstream out; WRITE_REPR(out, x); return out.str(); } template<typename InputIt> string RANGE_TO_STR(InputIt first, InputIt last) { ostringstream out; WRITE_RANGE_STR(out, first, last); return out.str(); } template<typename InputIt> string RANGE_TO_REPR(InputIt first, InputIt last) { ostringstream out; WRITE_RANGE_REPR(out, first, last); return out.str(); } template<typename InputIt> string JOIN(InputIt first, InputIt last, const string& sep) { ostringstream out; WRITE_JOIN_STR(out, first, last, sep); return out.str(); } template<> struct Formatter<i64> { static ostream& write_str(ostream& out, i64 x) { return out << x; } static ostream& write_repr(ostream& out, i64 x) { if(x == INF) return out << "INF"; if(x == -INF) return out << "-INF"; return out << x; } }; template<> struct Formatter<f64> { static ostream& write_str(ostream& out, f64 x) { return out << x; } static ostream& write_repr(ostream& out, f64 x) { #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wfloat-equal" if(x == FINF) return out << "FINF"; if(x == -FINF) return out << "-FINF"; #pragma GCC diagnostic pop return out << x; } }; template<typename T> struct Formatter<vector<T>> { static ostream& write_str(ostream& out, const vector<T>& v) { return WRITE_RANGE_STR(out, begin(v), end(v)); } static ostream& write_repr(ostream& out, const vector<T>& v) { out << "vector"; return WRITE_RANGE_REPR(out, begin(v), end(v)); } }; template<typename T1, typename T2> struct Formatter<pair<T1,T2>> { static ostream& write_str(ostream& out, const pair<T1,T2>& p) { WRITE_STR(out, p.first); out << ' '; WRITE_STR(out, p.second); return out; } static ostream& write_repr(ostream& out, const pair<T1,T2>& p) { out << "("; WRITE_REPR(out, p.first); out << ","; WRITE_REPR(out, p.second); out << ")"; return out; } }; template<typename... TS> struct Formatter<tuple<TS...>> { template<size_t I=0, enable_if_t<I == sizeof...(TS), nullptr_t> = nullptr> static ostream& write_str_impl(ostream& out, const tuple<TS...>&) { return out; } template<size_t I=0, enable_if_t<I < sizeof...(TS), nullptr_t> = nullptr> static ostream& write_str_impl(ostream& out, const tuple<TS...>& t) { if(I != 0) out << ' '; WRITE_STR(out, get<I>(t)); return write_str_impl<I+1>(out, t); } template<size_t I=0, enable_if_t<I == sizeof...(TS), nullptr_t> = nullptr> static ostream& write_repr_impl(ostream& out, const tuple<TS...>&) { if(sizeof...(TS) == 0) out << "("; return out << ")"; } template<size_t I=0, enable_if_t<I < sizeof...(TS), nullptr_t> = nullptr> static ostream& write_repr_impl(ostream& out, const tuple<TS...>& t) { if(I == 0) out << "("; else out << ","; WRITE_REPR(out, get<I>(t)); return write_repr_impl<I+1>(out, t); } static ostream& write_str(ostream& out, const tuple<TS...>& t) { return write_str_impl(out, t); } static ostream& write_repr(ostream& out, const tuple<TS...>& t) { return write_repr_impl(out, t); } }; template<typename T> void RD(T& x) { cin >> x; #ifdef PROCON_LOCAL assert(cin); #endif } template<typename T> void RD(vector<T>& v, i64 n) { v.reserve(n); REP(_, n) { T e; RD(e); v.emplace_back(e); } } void PRINT() {} template<typename T, typename... TS> void PRINT(const T& x, const TS& ...args) { WRITE_STR(cout, x); if(sizeof...(args)) { cout << ' '; PRINT(args...); } } template<typename... TS> void PRINTLN(const TS& ...args) { PRINT(args...); cout << '\n'; } [[noreturn]] void EXIT() { #ifdef PROCON_LOCAL cerr.flush(); #endif cout.flush(); _Exit(0); } template<typename T> void DBG_IMPL(i64 line, const char* expr, const T& value) { #ifdef PROCON_LOCAL cerr << "[L " << line << "]: "; cerr << expr << " = "; WRITE_REPR(cerr, value); cerr << "\n"; #endif } template<typename T, size_t N> void DBG_ARRAY_IMPL(i64 line, const char* expr, const T (&ary)[N]) { #ifdef PROCON_LOCAL cerr << "[L " << line << "]: "; cerr << expr << " = "; WRITE_RANGE_REPR(cerr, begin(ary), end(ary)); cerr << "\n"; #endif } template<typename InputIt> void DBG_RANGE_IMPL(i64 line, const char* expr1, const char* expr2, InputIt first, InputIt last) { #ifdef PROCON_LOCAL cerr << "[L " << line << "]: "; cerr << expr1 << "," << expr2 << " = "; WRITE_RANGE_REPR(cerr, first, last); cerr << "\n"; #endif } #define DBG(expr) DBG_IMPL(__LINE__, #expr, (expr)) #define DBG_ARRAY(expr) DBG_ARRAY_IMPL(__LINE__, #expr, (expr)) #define DBG_RANGE(first,last) DBG_RANGE_IMPL(__LINE__, #first, #last, (first), (last)) #define PAIR make_pair #define TUPLE make_tuple // }}} // init {{{ struct ProconInit { static constexpr int IOS_PREC = 15; static constexpr bool AUTOFLUSH = false; ProconInit() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(IOS_PREC); #ifdef PROCON_LOCAL cerr << fixed << setprecision(IOS_PREC); #endif if(AUTOFLUSH) cout << unitbuf; } } PROCON_INIT; // }}} //-------------------------------------------------------------------- // Miller-Rabin 法 // // 参考: http://miller-rabin.appspot.com/ bool is_prime_u32(u32 n) { static constexpr u32 AS[] { 2, 7, 61, }; static const auto mulmod32 = [](u32 a, u32 b, u32 m) -> u32 { u64 res = a; res *= b; res %= m; return static_cast<u32>(res); }; static const auto powmod32 = [](u32 a, u32 b, u32 m) -> u32 { u32 res = 1; while(b > 0) { if(b & 1) res = mulmod32(res, a, m); a = mulmod32(a, a, m); b >>= 1; } return res; }; if(n <= 1) return false; if(n == 2) return true; if(n % 2 == 0) return false; u32 d = n-1; u32 s = __builtin_ctz(d); d >>= s; for(u32 a : AS) { if(a >= n) a %= n; if(a == 0) continue; u32 x = powmod32(a, d, n); if(x == 1 || x == n-1) continue; u32 r; for(r = 1; r < s; ++r) { x = mulmod32(x, x, n); if(x == 1) return false; if(x == n-1) break; } if(r == s) return false; } return true; } bool is_prime_u64(u64 n) { static constexpr u64 AS[] { 2, 325, 9375, 28178, 450775, 9780504, 1795265022, }; static const auto mulmod64 = [](u64 a, u64 b, u64 m) -> u64 { u128 res = a; res *= b; res %= m; return static_cast<u64>(res); }; static const auto powmod64 = [](u64 a, u64 b, u64 m) -> u64 { u64 res = 1; while(b > 0) { if(b & 1) res = mulmod64(res, a, m); a = mulmod64(a, a, m); b >>= 1; } return res; }; if(n <= numeric_limits<u32>::max()) return is_prime_u32(static_cast<u32>(n)); if(n % 2 == 0) return false; u64 d = n-1; u64 s = __builtin_ctzll(d); d >>= s; for(u64 a : AS) { if(a >= n) a %= n; if(a == 0) continue; u64 x = powmod64(a, d, n); if(x == 1 || x == n-1) continue; u64 r; for(r = 1; r < s; ++r) { x = mulmod64(x, x, n); if(x == 1) return false; if(x == n-1) break; } if(r == s) return false; } return true; } void solve() { i64 N; RD(N); REP(_, N) { u64 X; RD(X); bool ans = is_prime_u64(X); PRINTLN(X, ans); } } signed main() { solve(); EXIT(); }