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

提出ソース
結果

問題	No.3030 ミラー・ラビン素数判定法のテスト
ユーザー	w2w2
提出日時	2021-12-10 02:48:47
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	224 ms / 9,973 ms
コード長	19,909 bytes
コンパイル時間	5,777 ms
コンパイル使用メモリ	299,344 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-04-28 09:48:14
合計ジャッジ時間	6,924 ms
ジャッジサーバーID （参考情報）	judge4 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	122 ms 5,376 KB
testcase_05	AC	120 ms 5,376 KB
testcase_06	AC	51 ms 5,376 KB
testcase_07	AC	50 ms 5,376 KB
testcase_08	AC	47 ms 5,376 KB
testcase_09	AC	224 ms 5,376 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 pll= std::pair<long long, long long>;
template<class T> using vec= std::vector<T>;
template<
    class T, class Container= std::vector<T>,
    class Compare= std::less<typename Container::value_type>>
using prique= std::priority_queue<T, Container, Compare>;
using vi= std::vector<int>;
using vl= std::vector<long long>;
using vd= std::vector<long double>;
using vs= std::vector<std::string>;
using vi128= std::vector<__int128>;
using vpll= std::vector<std::pair<long long, long long>>;
using vvi= std::vector<std::vector<int>>;
using vvl= std::vector<std::vector<long long>>;
using vvd= std::vector<std::vector<long double>>;
using vvs= std::vector<std::vector<std::string>>;
using vvi128= std::vector<std::vector<__int128>>;
using vvpll= std::vector<std::vector<std::pair<long long, long long>>>;
#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= std::vector<mint>;
using vvm= std::vector<std::vector<mint>>;
#endif
#if MOD_TYPE == 1000000007
constexpr long long mod= 1000000007ll;
#elif MOD_TYPE == 998244353
constexpr long long mod= 998244353ll;
#endif
#define ALL(x) (x).begin(), (x).end()
#define OVERLOAD3(_1, _2, _3, name, ...) name
#define REPBASE(i, a, b) for(long long i= (a), i##_b= (b); i < i##_b; i++)
#define RREPBASE(i, a, b) for(long long 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 long long sz(const T &x) {
    return std::size(x);
}
constexpr long long topbit(const long long &t) {
    return (t == 0 ? -1 : 63 - __builtin_clzll(t));
}
constexpr long long bit(const long long &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;
    }
}
template<class T> constexpr std::string YES(const T &n) noexcept {
    return (n ? "YES"s : "NO"s);
}
template<class T> constexpr std::string Yes(const T &n) noexcept {
    return (n ? "Yes"s : "No"s);
}
template<class T> constexpr std::string yes(const T &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 long long 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 long long 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 long long 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 long long 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 long long 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 long long 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<std::pair<long long, long long>, 4> dx4{
    {{1ll, 0ll}, {0ll, 1ll}, {-1ll, 0ll}, {0ll, -1ll}}};
constexpr std::array<std::pair<long long, long long>, 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 __int128 parse(std::string s) {
    std::reverse(s.begin(), s.end());
    __int128 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(__int128 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(unsigned __int128 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(...)            \
    long long __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, ...)             \
    std::vector<__VA_ARGS__> name(size); \
    input(name)
#define VV(name, h, w, ...)                             \
    std::vector name((h), std::vector<__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<__int128, T> ||
                         std::is_same_v<unsigned __int128, 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(long double &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 long long &a) {
        std::printf("%lld", a);
    }
    static inline void print_impl(const __int128 &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 unsigned long long &a) {
        std::printf("%llu", a);
    }
    static inline void print_impl(const unsigned __int128 &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 long double &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

/* modpow */
/* O(logN) */
/* define 0^0 as 1 */
/* constraint : 0 <= a */
/*              0 <= b */
/*              0 <= m */
constexpr unsigned long long modpow(unsigned long long a, unsigned long long b,
                                    unsigned long long m= mod) {
    unsigned long long 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<unsigned long long>(
                     static_cast<unsigned __int128>(a) * a % m),
                 b>>= 1) {
            if(b & 1ull)
                res= static_cast<unsigned long long>(
                    static_cast<unsigned __int128>(res) * a % m);
        }
        return res % m;
    }
}


/* Miller-Rabin primality test */
/* requirement : modpow */
/* O(logN) */
/* constraint : 0 <= n */
constexpr bool miller_rabin(const unsigned long long &n) {
    if(n <= 1ull) return false;
    if(n <= (1ull << 31)) {
        if(n == 2ull || n == 7ull || n == 61ull) return true;
        if(~n & 1ull) return false;
        std::array<unsigned long long, 3> bases{2ull, 7ull, 61ull};
        unsigned int d= n ^ 1u;
        d>>= __builtin_ctz(d);
        for(unsigned long long a : bases) {
            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 {
        constexpr std::array<unsigned long long, 7> bases{
            2ull,      325ull,     9375ull,      28178ull,
            450775ull, 9780504ull, 1795265022ull};
        if(~n & 1) return false;
        unsigned long long d= n ^ 1ull;
        d>>= __builtin_ctzll(d);
        for(unsigned long long a : bases) {
            unsigned long long t= d;
            a= modpow(a, d, n);
            if(a == 1ull) continue;
            while(t != (n ^ 1ull) && a != 1ull && a != (n ^ 1ull)) {
                a= static_cast<unsigned long long>(
                    static_cast<unsigned __int128>(a) * a % n);
                t<<= 1;
            }
            if(a != (n ^ 1ull)) 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

結果

テストケース

ソースコード
