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

提出ソース
結果

問題	No.3030 ミラー・ラビン素数判定法のテスト
ユーザー	w2w2
提出日時	2021-12-11 03:26:33
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	43 ms / 9,973 ms
コード長	21,325 bytes
コンパイル時間	6,589 ms
コンパイル使用メモリ	304,568 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-04-28 09:49:09
合計ジャッジ時間	6,235 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	26 ms 6,940 KB
testcase_05	AC	25 ms 6,944 KB
testcase_06	AC	15 ms 6,940 KB
testcase_07	AC	14 ms 6,944 KB
testcase_08	AC	15 ms 6,944 KB
testcase_09	AC	43 ms 6,940 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#define MOD_TYPE 998244353
// #define MOD_TYPE 1000000007
// #define EXPAND
// #define MOD_EXPAND
#pragma region Macros
#pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using namespace std::literals;
#if __has_include(<atcoder/all>) || defined(EXPAND)
#include <atcoder/convolution>
#include <atcoder/fenwicktree>
#include <atcoder/lazysegtree>
#include <atcoder/math>
#include <atcoder/maxflow>
#include <atcoder/mincostflow>
#include <atcoder/modint>
#include <atcoder/scc>
#include <atcoder/segtree>
#include <atcoder/string>
#include <atcoder/twosat>
using namespace atcoder;
#endif
using ll= long long;
using ld= long double;
using ull= unsigned long long;
using i128= __int128;
using u128= unsigned __int128;
using pll= std::pair<ll, ll>;
template<class T> using vec= std::vector<T>;
template<
    class T, class Container= vec<T>,
    class Compare= std::less<typename Container::value_type>>
using prique= std::priority_queue<T, Container, Compare>;
using vi= vec<int>;
using vl= vec<ll>;
using vd= vec<ld>;
using vs= vec<std::string>;
using vi128= vec<i128>;
using vpll= vec<pll>;
using vvi= vec<vi>;
using vvl= vec<vl>;
using vvd= vec<vd>;
using vvs= vec<vs>;
using vvi128= vec<vi128>;
using vvpll= vec<vpll>;
#if __has_include(<atcoder/modint>) || defined(MOD_EXPAND)
#if MOD_TYPE == 1000000007
using mint= atcoder::modint1000000007;
#elif MOD_TYPE == 998244353
using mint= atcoder::modint998244353;
#endif
using vm= vec<mint>;
using vvm= vec<vm>;
#endif
#if MOD_TYPE == 1000000007
constexpr ll mod= 1000000007ll;
#elif MOD_TYPE == 998244353
constexpr ll mod= 998244353ll;
#endif
#define ALL(x) (x).begin(), (x).end()
#define OVERLOAD3(_1, _2, _3, name, ...) name
#define REPBASE(i, a, b) for(ll i= (a), i##_b= (b); i < i##_b; i++)
#define RREPBASE(i, a, b) for(ll i= (a), i##_b= (b); i >= i##_b; i--)
#define LOOP(n) REPBASE(i##__COUNTER__##_##__LINE__, 0, n)
#define REPB(i, n) REPBASE(i, 0, n)
#define REPS(i, n) REPBASE(i, 1, n + 1)
#define RREP(i, n) RREPBASE(i, n - 1, 0)
#define RREPS(i, n) RREPBASE(i, n, 1)
#define REP(...) OVERLOAD3(__VA_ARGS__, REPBASE, REPB, LOOP)(__VA_ARGS__)
#define EACH1(x, c) for(auto &&x: c)
#define EACH2(x, y, c) for(auto &&[x, y]: c)
#define EACH(...) OVERLOAD3(__VA_ARGS__, EACH2, EACH1)(__VA_ARGS__)
#define PERM(p)        \
    std::sort(ALL(p)); \
    for(bool(p##c)= true; (p##c); (p##c)= std::next_permutation(ALL(p)))
#define eb emplace_back
#define fi first
#define se second
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
template<class T> struct is_pair : std::false_type {};
template<class T1, class T2> struct is_pair<std::pair<T1, T2>> : std::true_type {};
template<class T> inline constexpr bool is_pair_v= is_pair<T>::value;
template<class T> struct is_tuple : std::false_type {};
template<class... Ts> struct is_tuple<std::tuple<Ts...>> : std::true_type {};
template<class T> inline constexpr bool is_tuple_v= is_tuple<T>::value;
template<class, class= void> inline constexpr bool has_iterator= false;
template<class T>
inline constexpr bool has_iterator<T, std::void_t<typename T::iterator>> = true;
template<class, class= void> inline constexpr bool has_value_type= false;
template<class T>
inline constexpr bool has_value_type<T, std::void_t<typename T::value_type>> = true;
#if __has_include(<atcoder/modint>) || defined(MOD_EXPAND)
template<class T>
inline constexpr bool is_modint_v= atcoder::internal::is_modint<T>::value;
#endif
template<class T> constexpr ll sz(const T &x) {
    return std::size(x);
}
constexpr ll topbit(const ll &t) {
    return (t == 0 ? -1 : 63 - __builtin_clzll(t));
}
constexpr ll bit(const ll &n) noexcept {
    return (1ll << n);
}
template<class T, class U> constexpr T ceil(const T &a, const U &b) {
    assert(b != 0);
    if((a < 0) == (b < 0)) {
        return (a + b - (b > 0) + (b < 0)) / b;
    } else {
        return a / b;
    }
}
template<class T, class U> constexpr T floor(const T &a, const U &b) {
    assert(b != 0);
    if((a < 0) == (b < 0)) {
        return a / b;
    } else {
        return (a - b + (b > 0) - (b < 0)) / b;
    }
}
std::string YES(const bool &n) noexcept {
    return (n ? "YES"s : "NO"s);
}
std::string Yes(const bool &n) noexcept {
    return (n ? "Yes"s : "No"s);
}
std::string yes(const bool &n) noexcept {
    return (n ? "yes"s : "no"s);
}
template<class T> constexpr void uniq(T &v) {
    v.erase(std::unique(v.begin(), v.end()), v.end());
}
template<class T, class U> constexpr ll lb(const T &v, const U &x) {
    return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x));
}
template<class T, class U, class Compare>
constexpr ll lb(const T &v, const U &x, Compare comp) {
    return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x, comp));
}
template<class T, class U> constexpr ll ub(const T &v, const U &x) {
    return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x));
}
template<class T, class U, class Compare>
constexpr ll ub(const T &v, const U &x, Compare comp) {
    return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x, comp));
}
template<class T, class U, class V> constexpr ll er(const T &v, const U &x, const V &y) {
    return std::distance(
        std::lower_bound(v.begin(), v.end(), x), std::upper_bound(v.begin(), v.end(), y));
}
template<class T, class U, class V, class Compare>
constexpr ll er(const T &v, const U &x, const V &y, Compare comp) {
    return std::distance(
        std::lower_bound(v.begin(), v.end(), x, comp),
        std::upper_bound(v.begin(), v.end(), y, comp));
}
template<class T, class U> constexpr bool chmax(T &a, const U &b) noexcept {
    if(a < b) {
        a= b;
        return true;
    }
    return false;
}
template<class T, class U, class Compare>
constexpr bool chmax(T &a, const U &b, Compare comp) noexcept {
    if(comp(a, b)) {
        a= b;
        return true;
    }
    return false;
}
template<class T, class U> constexpr bool chmin(T &a, const U &b) noexcept {
    if(b < a) {
        a= b;
        return true;
    }
    return false;
}
template<class T, class U, class Compare>
constexpr bool chmin(T &a, const U &b, Compare comp) noexcept {
    if(comp(b, a)) {
        a= b;
        return true;
    }
    return false;
}
template<class Container> typename Container::value_type sum(Container &c) {
    return std::accumulate(c.begin(), c.end(), typename Container::value_type());
}
constexpr std::array<pll, 4> dx4{{{1ll, 0ll}, {0ll, 1ll}, {-1ll, 0ll}, {0ll, -1ll}}};
constexpr std::array<pll, 8> dx8{
    {{1ll, 0ll},
     {1ll, 1ll},
     {0ll, 1ll},
     {-1ll, 1ll},
     {-1ll, 0ll},
     {-1ll, -1ll},
     {0ll, -1ll},
     {1ll, -1ll}}};
template<class F> struct rec {
    F f;
    rec(F &&f_) : f(std::forward<F>(f_)) {}
    template<class... Args> decltype(auto) operator()(Args &&...args) const {
        return f(*this, std::forward<Args>(args)...);
    }
};
template<class T, class U>
constexpr std::pair<T, U> operator+(std::pair<T, U> p, const std::pair<T, U> &q) {
    p+= q;
    return p;
}
template<class T, class U>
constexpr std::pair<T, U> &operator+=(std::pair<T, U> &p, const std::pair<T, U> &q) {
    p.first+= q.first;
    p.second+= q.second;
    return p;
}
template<class T, class U>
constexpr std::pair<T, U> operator-(std::pair<T, U> p, const std::pair<T, U> &q) {
    p-= q;
    return p;
}
template<class T, class U>
constexpr std::pair<T, U> &operator-=(std::pair<T, U> &p, const std::pair<T, U> &q) {
    p.first-= q.first;
    p.second-= q.second;
    return p;
}
template<class T, class U> constexpr std::pair<T, U> operator+(const std::pair<T, U> &p) {
    return p;
}
template<class T, class U> constexpr std::pair<T, U> operator-(const std::pair<T, U> &p) {
    return {-p.first, -p.second};
}
inline i128 parse(std::string s) {
    std::reverse(s.begin(), s.end());
    i128 ret= 0;
    bool minus= false;
    if(s.back() == '-') {
        minus= true;
        s.pop_back();
    }
    while(!s.empty()) {
        if('0' <= s.back() && s.back() <= '9') {
            ret= ret * 10 + s.back() - '0';
            s.pop_back();
        } else {
            break;
        }
    }
    std::reverse(s.begin(), s.end());
    if(minus) ret*= -1;
    return ret;
}
inline std::string to_string(i128 val) {
    std::string ret= ""s;
    bool minus= false;
    if(val < 0) {
        minus= true;
        val*= -1;
    }
    do {
        char digit= '0' + static_cast<char>(val % 10);
        ret+= digit;
        val/= 10;
    } while(val != 0);
    if(minus) ret+= "-"s;
    std::reverse(ret.begin(), ret.end());
    return ret;
}
inline std::string to_string(u128 val) {
    std::string ret= ""s;
    do {
        char digit= '0' + static_cast<char>(val % 10);
        ret+= digit;
        val/= 10;
    } while(val != 0);
    std::reverse(ret.begin(), ret.end());
    return ret;
}
#define CHR(...)      \
    char __VA_ARGS__; \
    input(__VA_ARGS__)
#define STR(...)             \
    std::string __VA_ARGS__; \
    input(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    input(__VA_ARGS__)
#define LD(...)     \
    ld __VA_ARGS__; \
    input(__VA_ARGS__)
#define I128(...)     \
    i128 __VA_ARGS__; \
    input(__VA_ARGS__)
#define VEC(name, size, ...)     \
    vec<__VA_ARGS__> name(size); \
    input(name)
#define VV(name, h, w, ...)                     \
    std::vector name((h), vec<__VA_ARGS__>(w)); \
    input(name)
#ifdef _WIN32
int inline getchar_unlocked() {
    return _getchar_nolock();
}
void inline putchar_unlocked(char c) {
    _putchar_nolock(c);
}
#endif
struct in {
    in()= delete;
    static inline void input_impl(char &a) {
        do { a= static_cast<char>(getchar_unlocked()); } while(a == ' ' || a == '\n');
    }
    static inline void input_impl(std::string &a) {
        a= ""s;
        int c;
        do { c= getchar_unlocked(); } while(c == ' ' || c == '\n');
        do {
            a+= static_cast<char>(c);
            c= getchar_unlocked();
        } while(c != EOF && c != ' ' && c != '\n');
        std::ungetc(c, stdin);
    }
    template<
        class T,
        std::enable_if_t<
            std::is_integral_v<T> || std::is_same_v<i128, T> || std::is_same_v<u128, T>,
            std::nullptr_t> = nullptr>
    static inline void input_impl(T &a) {
        a= 0;
        int c;
        do { c= getchar_unlocked(); } while(c == ' ' || c == '\n');
        bool minus= 0;
        if(c == '-') {
            minus= 1;
            c= getchar_unlocked();
        }
        if(c < '0' || '9' < c) {
            std::ungetc(c, stdin);
            return;
        }
        do {
            (a*= 10)+= c - 48;
            c= getchar_unlocked();
        } while('0' <= c && c <= '9');
        std::ungetc(c, stdin);
        if(minus) a*= -1;
    }
    static inline void input_impl(float &a) {
        std::scanf("%f", &a);
    }
    static inline void input_impl(double &a) {
        std::scanf("%lf", &a);
    }
    static inline void input_impl(ld &a) {
        std::scanf("%Lf", &a);
    }
    template<class T1, class T2> static inline void input_impl(std::pair<T1, T2> &a) {
        input_impl(a.first);
        input_impl(a.second);
    }
    template<class T, std::enable_if_t<is_tuple_v<T>, std::nullptr_t> = nullptr>
    static inline void input_impl(T &a) {
        if constexpr(std::tuple_size_v<T> != 0) {
            input_impl_tuple_impl(a, std::make_index_sequence<std::tuple_size_v<T>>());
        }
    }
    template<class T, std::enable_if_t<has_iterator<T>, std::nullptr_t> = nullptr>
    static inline void input_impl(T &a) {
        for(auto &&e: a) { input_impl(e); }
    }

   private:
    template<class T, std::size_t... Seq>
    static inline void input_impl_tuple_impl(T &A, std::index_sequence<Seq...>) {
        using swallow= std::initializer_list<int>;
        swallow{(input_impl(std::get<Seq>(A)), 0)...};
    }
};
template<class... Args> inline void input(Args &...args) {
    using swallow= std::initializer_list<int>;
    swallow{(in::input_impl(args), 0)...};
}
struct out {
    out()= delete;
    template<class T> static inline void print_impl(T *const &a) {
        std::printf("%p", a);
    }
    static inline void print_impl(const char &a) {
        putchar_unlocked(a);
    }
    static inline void print_impl(const std::string &a) {
        std::fputs(a.c_str(), stdout);
    }
    template<std::size_t length> static inline void print_impl(const char (&a)[length]) {
        std::fputs(a, stdout);
    }
    static inline void print_impl(const bool &a) {
        putchar_unlocked('0' + a);
    }
    static inline void print_impl(const signed char &a) {
        std::printf("%hhd", a);
    }
    static inline void print_impl(const short &a) {
        std::printf("%hd", a);
    }
    static inline void print_impl(const int &a) {
        std::printf("%d", a);
    }
    static inline void print_impl(const long &a) {
        std::printf("%ld", a);
    }
    static inline void print_impl(const ll &a) {
        std::printf("%lld", a);
    }
    static inline void print_impl(const i128 &a) {
        std::fputs(to_string(a).c_str(), stdout);
    }
    static inline void print_impl(const unsigned char &a) {
        std::printf("%hhu", a);
    }
    static inline void print_impl(const unsigned short &a) {
        std::printf("%hu", a);
    }
    static inline void print_impl(const unsigned int &a) {
        std::printf("%u", a);
    }
    static inline void print_impl(const unsigned long &a) {
        std::printf("%lu", a);
    }
    static inline void print_impl(const ull &a) {
        std::printf("%llu", a);
    }
    static inline void print_impl(const u128 &a) {
        std::fputs(to_string(a).c_str(), stdout);
    }
    static inline void print_impl(const float &a) {
        std::printf("%.15f", a);
    }
    static inline void print_impl(const double &a) {
        std::printf("%.15lf", a);
    }
    static inline void print_impl(const ld &a) {
        std::printf("%.15Lf", a);
    }
    template<class T1, class T2>
    static inline void print_impl(const std::pair<T1, T2> &a) {
        print_impl(a.first);
        putchar_unlocked(' ');
        print_impl(a.second);
    }
#if __has_include(<atcoder/modint>) || defined(MOD_EXPAND)
    static inline void print_impl(const mint &a) {
        std::printf("%u", a.val());
    }
#endif
    template<class T, std::enable_if_t<is_tuple_v<T>, std::nullptr_t> = nullptr>
    static inline void print_impl(const T &a) {
        if constexpr(std::tuple_size_v<T> != 0) {
            print_impl_tuple_impl(
                a, std::make_index_sequence<std::tuple_size_v<T> - 1>());
        }
    }
    template<class T, std::enable_if_t<has_iterator<T>, std::nullptr_t> = nullptr>
    static inline void print_impl(const T &a) {
        if(a.begin() == a.end()) return;
        print_impl(*(a.begin()));
        if constexpr(!has_value_type<T> || !has_iterator<typename T::value_type>) {
            std::for_each(std::next(a.begin()), a.end(), [](const auto &value) {
                putchar_unlocked(' ');
                print_impl(value);
            });
        } else if constexpr(
            !has_value_type<typename T::value_type> ||
            !has_iterator<typename T::value_type::value_type>) {
            std::for_each(std::next(a.begin()), a.end(), [](const auto &value) {
                putchar_unlocked('\n');
                print_impl(value);
            });
        } else {
            std::for_each(std::next(a.begin()), a.end(), [](const auto &value) {
                putchar_unlocked('\n');
                putchar_unlocked('\n');
                print_impl(value);
            });
        }
    }

   private:
    template<class T, std::size_t... Seq>
    static inline void print_impl_tuple_impl(const T &A, std::index_sequence<Seq...>) {
        print_impl(std::get<0>(A));
        using swallow= std::initializer_list<int>;
        swallow{(putchar_unlocked(' '), print_impl(std::get<Seq + 1>(A)), 0)...};
    }
};
inline void print() {
    putchar_unlocked('\n');
}
template<class Head, class... Tail> inline void print(Head &&H, Tail &&...T) {
    out::print_impl(H);
    using swallow= std::initializer_list<int>;
    swallow{(putchar_unlocked(' '), out::print_impl(T), 0)...};
    putchar_unlocked('\n');
}
template<class... Args> inline void print_flush(Args &&...args) {
    print(std::forward<Args>(args)...);
    fflush(stdout);
}
template<class... Args> void debug([[maybe_unused]] Args... args) {
#ifdef _DEBUG
    print_flush(std::forward<Args>(args)...);
#endif
}
#pragma endregion

constexpr tuple<ull, ull, ull> precalc_montgomery64(const ull &m) {
    ull result= 0, mul= 0, b= 1;
    u128 rep= static_cast<u128>(1) << 64;
    while(rep > 1) {
        if(~mul & 1) {
            mul+= m;
            result|= b;
        }
        mul>>= 1;
        rep>>= 1;
        b<<= 1;
    }
    return {m, result, -static_cast<u128>(m) % m};
}

struct Montgomery64 {
    constexpr Montgomery64(u128 val, tuple<ull, ull, ull> precalc)
        : _mod(std::get<0>(precalc)), _neginv(std::get<1>(precalc)),
          _r2(std::get<2>(precalc)), _val(val * std::get<2>(precalc)) {
        reduce();
    }

    Montgomery64 &operator+=(const Montgomery64 &rhs) {
        _val+= rhs._val;
        if(_val >= _mod) _val-= _mod;
        return *this;
    }

    Montgomery64 &operator-=(const Montgomery64 &rhs) {
        _val+= _mod - rhs._val;
        if(_val >= _mod) _val-= _mod;
        return *this;
    }

    Montgomery64 &operator*=(const Montgomery64 &rhs) {
        _val*= rhs._val;
        reduce();
        return *this;
    }

    Montgomery64 operator+() const {
        return *this;
    }

    Montgomery64 operator-() const {
        Montgomery64 ret= *this;
        ret._val= _mod - this->_val;
        return ret;
    }

    friend Montgomery64 operator+(Montgomery64 lhs, const Montgomery64 &rhs) {
        lhs+= rhs;
        return lhs;
    }

    friend Montgomery64 operator-(Montgomery64 lhs, const Montgomery64 &rhs) {
        lhs-= rhs;
        return lhs;
    }

    friend Montgomery64 operator*(Montgomery64 lhs, const Montgomery64 &rhs) {
        lhs*= rhs;
        return lhs;
    }

    friend bool operator==(const Montgomery64 &lhs, const Montgomery64 &rhs) {
        return lhs._val == rhs._val;
    }

    friend bool operator!=(const Montgomery64 &lhs, const Montgomery64 &rhs) {
        return lhs._val != rhs._val;
    }

    Montgomery64 pow(ull n) const {
        Montgomery64 res= Montgomery64(1, {_mod, _neginv, _r2}), a= *this;
        for(; n; a*= a, n>>= 1) {
            if(n & 1ull) res*= a;
        }
        return res;
    }

    constexpr ull val() const {
        ull ret=
            (static_cast<u128>(static_cast<ull>(_val) * _neginv) * _mod + _val) >> 64;
        if(ret >= _mod) ret-= _mod;
        return ret;
    }

   private:
    ull _mod;
    ull _neginv;
    ull _r2;
    u128 _val;

    constexpr void reduce() {
        _val= (static_cast<u128>(static_cast<ull>(_val) * _neginv) * _mod + _val) >> 64;
        if(_val >= _mod) _val-= _mod;
    }
};

/* modpow */
/* O(logN) */
/* define 0^0 as 1 */
/* constraint : 0 <= a */
/*              0 <= b */
/*              0 <= m */
constexpr ull modpow(ull a, ull b, ull m= mod) {
    ull res= 1ull;
    if(m < (1ull << 32)) {
        for(a%= m; b; a= a * a % m, b>>= 1) {
            if(b & 1ull) res= res * a % m;
        }
        return res % m;
    } else {
        for(; b; a= static_cast<ull>(static_cast<u128>(a) * a % m), b>>= 1) {
            if(b & 1ull) res= static_cast<ull>(static_cast<u128>(res) * a % m);
        }
        return res % m;
    }
}

/* Miller-Rabin primality test */
/* requirement : modpow */
/* O(logN) */
/* constraint : 0 <= n */
constexpr bool miller_rabin(const ull &n) {
    if(n <= 1ull) return false;
    if(n < (1ull << 32)) {
        if(n == 2ull || n == 7ull || n == 61ull) return true;
        if(~n & 1ull) return false;
        unsigned int d= n ^ 1u;
        d>>= __builtin_ctz(d);
        for(ull a: {2ull, 7ull, 61ull}) {
            unsigned int t= d;
            a= modpow(a, d, n);
            if(a == 1ull) continue;
            while(t != (n ^ 1ull) && a != 1ull && a != (n ^ 1ull)) {
                a= a * a % n;
                t<<= 1;
            }
            if(a != (n ^ 1ull)) return false;
        }
        return true;
    } else {
        if(~n & 1ull) return false;
        ull d= n ^ 1ull;
        d>>= __builtin_ctzll(d);
        tuple<ull, ull, ull> pre= precalc_montgomery64(n);
        for(ull a:
            {2ull, 325ull, 9375ull, 28178ull, 450775ull, 9780504ull, 1795265022ull}) {
            ull t= d;
            Montgomery64 b(a, pre);
            b= b.pow(d);
            if(b == Montgomery64(1ull, pre)) continue;
            while(t != (n ^ 1ull) && b != Montgomery64(1ull, pre) &&
                  b != Montgomery64(n ^ 1ull, pre)) {
                b*= b;
                t<<= 1;
            }
            if(b != Montgomery64(n ^ 1ull, pre)) return false;
        }
        return true;
    }
}

signed main() {
    setvbuf(stdin, nullptr, _IOFBF, 1 << 17);
    setvbuf(stdout, nullptr, _IOFBF, 1 << 17);
    LL(T);
    REP(T) {
        LL(A);
        print(A, miller_rabin(A));
    }
}
yukicoder

結果

テストケース

ソースコード
