結果
| 問題 |
No.8030 ミラー・ラビン素数判定法のテスト
|
| ユーザー |
 w2w2
|
| 提出日時 | 2021-12-11 03:02:14 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 47 ms / 9,973 ms |
| コード長 | 21,211 bytes |
| コンパイル時間 | 20,846 ms |
| コンパイル使用メモリ | 355,156 KB |
| 最終ジャッジ日時 | 2025-01-26 07:40:37 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
ソースコード
#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= u128(1) << 64;
while(rep > 1) {
if(~mul & 1) {
mul+= m;
result|= b;
}
mul>>= 1;
rep>>= 1;
b<<= 1;
}
return {m, result, -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;
}
ull val() const {
ull ret= (u128(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= (u128(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 << 31)) {
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 & 1) 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(1, pre)) continue;
while(t != (n ^ 1ull) && b != Montgomery64(1, pre) &&
b != Montgomery64(n ^ 1, pre)) {
b*= b;
t<<= 1;
}
if(b != Montgomery64(n ^ 1, 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));
}
}