結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | aajisaka |
提出日時 | 2020-04-29 18:27:00 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,075 bytes |
コンパイル時間 | 2,332 ms |
コンパイル使用メモリ | 212,288 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-29 13:55:33 |
合計ジャッジ時間 | 3,047 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 21 ms
5,376 KB |
testcase_05 | AC | 21 ms
5,376 KB |
testcase_06 | AC | 12 ms
5,376 KB |
testcase_07 | AC | 12 ms
5,376 KB |
testcase_08 | AC | 11 ms
5,376 KB |
testcase_09 | AC | 33 ms
5,376 KB |
ソースコード
/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author aajisaka */ #include<bits/stdc++.h> using namespace std; void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif #define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr) #define rep(i,n) for(int i=0; i<(int)(n); i++) #define all(v) v.begin(), v.end() template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } using ll = long long; using ull = unsigned long long; using P = pair<ll, ll>; constexpr long double PI = 3.14159265358979323846264338327950288L; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); constexpr ll mod17 = 1e9+7; constexpr ll mod19 = 1e9+9; constexpr ll mod9 = 998244353; ll mod = mod17; // Mod int libraries template<typename T> T mod_pow(T a, ll x) { T res = 1; while(x > 0) { if (x & 1) res *= a; a *= a; x >>= 1; } return res; } // Mint32 unordered_map<ll, ll> minvmap; ll minv(ll a, ll m) { auto k = a; auto p = minvmap[a]; if (p != 0) return p; ll b = m, u = 1, v = 0; while (b) { ll t = a/b; swap(a -= t*b, b); swap(u -= t*v, v); } p = (u%m+m)%m; minvmap[k] = p; return p; } struct mint { ll x; mint():x(0){} mint(ll x):x((x%mod+mod)%mod){} mint& fix() { x = (x%mod+mod)%mod; return *this;} mint operator-() const { return mint(0) - *this;} mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;} mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;} mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;} mint& operator/=(const mint& a){ (x*=minv(a.x, mod))%=mod; return *this; } mint operator+(const mint& a)const{ return mint(*this) += a;} mint operator-(const mint& a)const{ return mint(*this) -= a;} mint operator*(const mint& a)const{ return mint(*this) *= a;} mint operator/(const mint& a)const{ return mint(*this) /= a;} bool operator<(const mint& a)const{ return x < a.x;} bool operator==(const mint& a)const{ return x == a.x;} }; // Mint64 struct mint64 { ull x; static ull mod, inv, r2; mint64(): x(0){} mint64(ull x): x(init(x)) {} static ull init(ull x) { return reduce(__uint128_t(x)*r2);} static void set_mod(ull m) { mod = inv = m; for(int i=0; i<5; i++) inv *= 2 - inv*m; r2 = -__uint128_t(m)%m; } static ull reduce(__uint128_t x) { ull y = ull(x >> 64) - ull((__uint128_t(ull(x)*inv)*mod)>>64); return ll(y) < 0 ? y+mod : y; } mint64& operator+=(mint64& a) { x+=a.x-mod; if(ll(x)<0) x+=mod; return *this; } mint64 operator+(mint64& a) const{ return mint64(*this)+=a; } mint64& operator*=(mint64& a) { x=reduce(__uint128_t(x)*a.x); return *this; } mint64 operator*(mint64& a) const { return mint64(*this)*=a; } }; ull mint64::mod, mint64::inv, mint64::r2; struct Miller { const vector<ull> v = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; bool suspect(ull a, ull s, ull d, ull n) { if (mint64::mod != n) mint64::set_mod(n); mint64 one = 1, minusone = n-1, ma = a; auto x = mod_pow(ma, d); if (x.x == one.x) return true; for(int r = 0; r < s; r++) { if (x.x == minusone.x) return true; x = x * x; } return false; } // check if n is prime bool check(ull n) { if (n < 2 || (n > 2 && n % 2 == 0)) return false; ull d = n - 1; ull s = 0; while (!(d & 1)) { d >>= 1; s++; } for (auto a: v) { if (a >= n) break; if (!suspect(a, s, d, n)) return false; } return true; } }; class combination { // factorial public: std::vector<mint> fact; public: std::vector<mint> inv; combination(int n) { fact.resize(n + 1); inv.resize(n + 1); fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = fact[i - 1] * i; } inv[n] = mint(1) / fact[n]; for (int i = n - 1; i >= 0; i--) { inv[i] = inv[i + 1] * (i + 1); } } // nCr public: mint get(int n, int r) { if (n < r || n < 0 || r < 0) return 0; return fact[n]*inv[r]*inv[n-r]; } // nPr public: mint p(int n, int r) { if (n < r || n < 0) return 0; return fact[n]*inv[n-r]; } }; class TestMillerRabin { public: void solve(istream& cin, ostream& cout) { SPEED; int n; cin >> n; Miller miller; while(n--) { ll p; cin >> p; cout << p << ' '; cout << (miller.check(p) ? 1 : 0) << '\n'; } } }; signed main() { TestMillerRabin solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }